网上找了两份CLRS的答案，一份是民间的一份是官方的，都没有这题的解答。
跟两位大牛讨论了一下，觉得应该没什么问题了，发一个。
题目：
假设有一个随机数发生器R(0,1)能均匀产生{0,1}中的一个数，即P(0)=1/2,P(1)=1/2
利用它实现一个能产生[a..b]之间的随机数发生器R(a,b)
大致思路：
首先,R(0,1)能产生两个数
考虑由它得到R(0,b-a)，能产生[0.. b-a]之间的b-a+1个数。
则a+R(0,b-a) 能产生[a..b]之间的b-a+1个数。
问题转化为怎么求R(0,b-a)，举一个例子说明。
假设要得到R(0,4)，即[0..4]之间的5个数。
考虑R(0,7)共8个数，调用lg8=3次的R(0,1)显然可以得到
{0,1}^3的3-串，相当于binary的0-7
它们是等概率分布的8个数(P(each) = 1/2*1/2*1/2 = 1/8)。
则问题又转化为如何由1/8等概率的数得到1/5等概率的数，
without loss of generality，设为前5个数。
Proposition:
运行3次R(0,1)，如果得到(101,110,111) bin=(5,6,7) dec 则再次运行3次R(0,1)，
直到得到前5个数之间的一个才返回。它们的概率是1/5.
Prove:
以运行3次R(0,1)为一个单位，假设运行了k次才得到[0..4]之中的一个，k -> infinite
即前k-1次都得到[5..7]中的一个，第k次猜得到[0..4]之中的一个（否则算法不结束）
令：
事件a="前k-1次为[5..7]，最后得到[0..4]"
事件b="前k-1次为[5..7]，最后得到一个确定的x \in [0..4]"
显然每次"抛骰子"都是独立的，易得
P(a)=(3/8)^{k-1} * 5/8
P(ab)=(3/8)^{k-1} * 1/8
则P(b|a)=P(ab)/P(a)=(1/8) / (5/8) = 1/5
即统计意义上，for i \in [0..4]，b的概率为1/5
类似地，可得算法：
function: R(a,b)
input: int a,b
let: L = floor(lg(b-a))+1, size=2^L, result=0
repeat{
result = 0;
for i in [1 .. L]
temp = temp << 1 + R(0,1);
endfor
}until (temp < b-a+1);
return temp+a;
算法的期望运行时间：
for loop的运行时间为2^L
E[n] = sum( i*P(i) ) * 2^L
其中P(i)是算法repeat loop运行i次的概率，则P(i) = (3/8)^(i-1) * (5/8)
sum里面展开后大概是个这样的东西：
1*5/8 + 2*3/8*5/8+3*(3/8)^2*5/8+....+n*(3/8)^{n-1}*5/8
另外bug大牛是这样算期望的：
E(n) = 1 + 上一步算法没结束的概率 * E(n-1)
好像也对，没有具体展开……
No comments:
Post a Comment