等概率随机数生成器

题目：假设你已经有一个随机数生成器，能够以概率p生成0，概率1-p生成1，请问如何设计算法以概率q等概率地生成0-6这七个数字中的一个？即每个数字的概率均为q,q<1/7.

我们先从简单的情况开始考虑，假设需要生成0和1，二者概率均为q。那么我们可以让已有的随机数生成器产生两个数字，那么产生的数字及概率是：

Number	Prob
00	p2p2
01	p(1−p)p(1−p)
10	p(1−p)p(1−p)
11	(1−p)2(1−p)2

注意到01和10的概率是相等的，所以可以当得到01时输出0，得到10时输出1，并令p(1-p)=q, 可以求得p的值，显然p有两个关于1/2的对称解，从直观上来理解这也是必然的，因为0和1是对称的。

这种解法可以推广到n个数的情况，生成的00…001对应0，00…010对应1，00…100对应2，……，01…000对应n-1，10…000对应n。同样令

,即可求得p的值。

 

转自https://blog.csdn/chfe007/article/details/80045166