問題:
Given a random number generator which can generate the number in range (1,5) uniformly. How can you use it to build a random number generator which can generate the number in range (1,7) uniformly?
(給定一個隨機數生成器，這個生成器能均勻生成1到5(1,5)的隨機數，如何使用這個生成器生成均勻分布的1到7(1,7)的數?)
解法一:
拒絕采樣定理
簡單的說, 把 1-5 的隨機數發生器用兩次, 拼成一個5進制的數, 就是1-25. 將這 1-25 平均分配的25種情況映射到7種情況上, 問題就解決了. 因為21是7的倍數, 我們可以每三個映射到一個, 即1-3 映射到1, …, 19-21 映射到7. 可見, 這些情況之間的概率是一樣的. 那么, 要是拼成的數字正好是 22-25 這四個呢? 有兩種方法, 第一種是丟棄這個數字, 從頭再來, 直到拼成的數字在1-21之間. 因為這個是個概率算法, 不能保證每次都能落在1-21, 所以采樣的密度不高. 還有一種方法, 是說, 假如落到了 22-25, 那這次的采樣結果就用上次的. 可以證明, 這看上去兩個互相矛盾的算法, 結果都能均等的得到等概率的分布. (前者叫做 Reject Sampling, 后者叫做 Metropolis Algorithm, 都是數學物理模擬里面常用的方法)
解法二:
二進制
1-2映射到0，3跳過，4-5映射到1
生成三位的二進制即可