[面试题][数学与概率]设计随机数生成器

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

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

Number	Prob
00	p2 p 2 $$p^2$$
01	p(1−p) p ( 1 − p ) $$p(1-p)$$
10	p(1−p) p ( 1 − p ) $$p(1-p)$$
11	(1−p)2 ( 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。同样令

pn−1(1−p)=q p n − 1 ( 1 − p ) = q $$p^{n-1}(1-p)=q$$ 即可求得p的值。

参考文献：https://blog.csdn/lijiecao0226/article/details/24199049