機率生成器-算法

1.假設我有個{0,1}生成器，生成0的機率為p,生成1的機率為q,如何通過此發生器獲得一個均為1/2的{0,1}生成器呢？

【答】思路：尋找兩個等機率事件。易知連續投擲兩次獲得01或者10的機率均為p(1-p) =Y，是以如果我們連續生成兩個數，如果獲得00或者11機率為U=p^2+(1-p)^2，則繼續再擷取兩個數，直到擷取到10或者01為止。機率為(1+U+U^2+U^3+...)*Y 求極限為Y*(1/(1-U))=0.5

是以 我們得到了想要的，我們可以認為最終得到10的為事件0，最終得到01的為事件1，這樣子就達到目的了。

2.假設我有一個随機數生成器範圍為{1,2,3,4,5} 如何獲得一個等機率的{0，1}生成器

【答】思路：同樣采取上題的思路構造兩個等機率事件：事件A: 不停生成數 直至生成的數A<3 事件B 不停生成數直至生成數A>3 同樣可以證明這個兩個事件發生機率都是0.5

3. 假設我有一個随機數生成器範圍為{1,2,3,4,5} 如何獲得一個{1-n}的等機率随機生成器

【答】思路：

（1）首先我們獲得一個{0,1}等機率生成器

（2）我們獲得一個XXX的随機二進制序清單示範圍(0,1,2,...,2^k-1)。其中2^(K-1)<=n<2^k

（3）定義n個事件 其中M事件為:如果XXX屬于{n+1,2^k-1}則再生成一個XXX的随機序列屬于{0,1,2,..,n} 其中XXX=M的機率為1/n

擴充解法：已 知一随機發生器，産生0的機率是p，産生1的機率是1-p，現在要你構造一個發生器，使得它構造0和1的機率均為1/2；構造一個發生器，使得它構造1、 2、3的機率均為1/3；...，構造一個發生器，使得它構造1、2、3、...n的機率均為1/n，要求複雜度最低。

首先是1/2的情況，我們一次性生成兩個數值，如果是00或者11丢棄，否則留下，01為1，10為0，他們的機率都是p*(1-p)是相等的，是以等機率了。 然 後是1/n的情況了，我們以5為例，此時我們取x=2，因為C(2x,x)=C(4,2)=6是比5大的最小的x，此時我們就是一次性生成4位二進制，把 1出現個數不是2的都丢棄，這時候剩下六個:0011,0101,0110,1001,1010,1100，取最小的5個，即丢棄1100，那麼我們對于 前5個分别編号1到5，這時候他們的機率都是p*p*(1-p)*(1-p)相等了。

關鍵是找那個最小的x，使得C(2x,x)>=n這樣能提升查找效率

PS：C(2x,x)的意思是生成2x位的二進制數，其中x位為1，x位為0，那麼這樣的數的機率都為p^x * (1-p)^x,在這樣的數種取最小的前n個數即可.....