logo头像
Snippet 博客主题

Problem2 随机数生成器

随机数生成器

(1)有一枚不均匀的硬币,可以概率p投出正面,1-p反面,且p不等于0.5。问如何投掷该硬币来设计一个随机数生成器,使得以等概率输出0,1?
Solution:
设:正为0为p,反为1为1-p。

Number Probability
00 pp
01 p(1-p)
10 p(1-p)
11 (1-p)(1-p)

注意到01和10 的概率是相等的,概率为 p(1-p)。那就可以将01对应输出0,10对应输出1,其余的都舍掉。这样就可以等概率P输出0,1。
(2) 推广到等概率输出n个数的情况?
Solution: 这种解法可以推广到n个数的情况,生成的00…001对应0,00…010对应1,00…100对应2,……,01…000对应n-1,10…000对应n,概率均为$p^n(1-p)$,可以等概率输出。其余的都舍掉。

(3) 等概率0 1随机数生成器为的0的期望?
Solution: 每次试验都是独立的。输出结果只有0,1 两种,所以这是伯努利试验,将伯努利试验独立重复n次,称为n重伯努利试验。
若每次试验成功的概率为p(0<p<1),则在第k次试验才首次成功的概率服从几何分布。第k次才成功的概率P(ξ=k)=(1-p)的(k-1)次方乘以p (k=1,2,…,0<p<1)。期望是1/p,方差是 (1-p)/(p的平方)。