利用随机数生成器生成固定概率生成器

一个有趣的题目：假设现有一随机数生成器可以产生一个一位数:0 or 1, 产生 0 的概率为 p p p, 产生1的概率为 1 − p 1-p 1−p ,试调用此随机数生成器，写出一个新随机数生成器产生概率为 1 / n 1/n 1/n的n个事件。

此题可从概率论的角度思考，每次试验(即随机数生成器产生一个数)产生事件0的概率为 p p p, 产生事件1的概率为 1 − p 1-p 1−p, 因为试验本身是相互独立的，故可以采用N重伯努利概型:
C n 0 p n + C n 1 p n − 1 p − 1 1 + C n 2 p n − 2 p − 1 2 + . . . + C n n p − 1 n C_n^0p^n+C_n^1p^{n-1}p-1^1+C_n^2p^{n-2}p-1^2 + ... + C_n^np-1^n Cn0​pn+Cn1​pn−1p−11+Cn2​pn−2p−12+...+Cnn​p−1n

可以发现 C n 1 p n − 1 p − 1 1 C_n^1p^{n-1}p-1^1 Cn1​pn−1p−11共有n个 ( p − 1 ) p n − 1 (p-1)p^{n-1} (p−1)pn−1这n个相同事件发生的概率相同，就可以取出这个事件做随机数生成器，其余事件全部丢弃。在实际程序中，就是通过循环产生n个1bit的数，将其存入一个数组中，如果该数存在多个1则丢弃，全为0丢弃，这样就可以实现了。