mcx*_*oke 12 random algorithm numbers
如果我有一个名为rand1()的函数生成数字0(概率为30%)或1(概率为70%),如何编写生成数字0或1等概率的函数rand2()使用rand1()？
更新:
最后,我发现这是"算法入门"(第2版)(我已经购买了本书的中文版),练习5.1-3,原来的问题是:
5.1-3假设您希望以概率1/2输出0,以概率1/2输出1.你可以使用一个程序BIASED-RANDOM,它输出0或1.它以概率p和0输出1,其中0 <p <1,但你不知道p是什么.给出一个使用BIASED-RANDOM作为子程序的算法,并返回一个无偏的答案,以概率1/2返回0,以概率1/2返回1.作为p的函数,算法的预期运行时间是多少？
解决方案是:(见:http://www.cnblogs.com/meteorgan/archive/2012/05/04/2482317.html)
为了获得无偏的随机位,只给出了对BIASED-RANDOM的调用,请调用两次BIASED-RANDOM.重复执行此操作,直到两个调用返回不同的值,并且当发生这种情况时,返回两位中的第一位:
UNBIASED-RANDOM
while TRUE
do
x ? BIASED-RANDOM
y ? BIASED-RANDOM
if x != y
then return x
要看到UNBIASED-RANDOM以概率1/2返回0和1,请注意给定迭代返回0的概率是
Pr {x = 0 and y = 1} = (1 ? p)p ,
并且给定迭代返回1的概率是
Pr {x = 1 and y = 0} = p(1 ? p) .
(我们依赖于BIASED-RANDOM返回的比特是独立的.)因此,给定迭代返回0的概率等于它返回1的概率.由于UNBIASED-RANDOM没有其他方法返回值,它返回0和1各有概率1/2.
Joa*_*son 13
生成两个数字,a和b.
如果a为0且b为1(偶然性为21%),则生成0.
如果a为1且b为0(概率为21%),则生成1.
对于所有其他情况(58%的可能性),只需生成一个新的a,b然后再试一次.