問題:

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?

(給定一個隨機(jī)數(shù)生成器，這個生成器能均勻生成1到5(1,5)的隨機(jī)數(shù)，如何使用這個生成器生成均勻分布的1到7(1,7)的數(shù)?)

解法一:
拒絕采樣定理
簡單的說, 把 1-5 的隨機(jī)數(shù)發(fā)生器用兩次, 拼成一個5進(jìn)制的數(shù), 就是1-25. 將這 1-25 平均分配的25種情況映射到7種情況上, 問題就解決了. 因?yàn)?1是7的倍數(shù), 我們可以每三個映射到一個, 即1-3 映射到1, …, 19-21 映射到7. 可見, 這些情況之間的概率是一樣的. 那么, 要是拼成的數(shù)字正好是 22-25 這四個呢? 有兩種方法, 第一種是丟棄這個數(shù)字, 從頭再來, 直到拼成的數(shù)字在1-21之間. 因?yàn)檫@個是個概率算法, 不能保證每次都能落在1-21, 所以采樣的密度不高. 還有一種方法, 是說, 假如落到了 22-25, 那這次的采樣結(jié)果就用上次的. 可以證明, 這看上去兩個互相矛盾的算法, 結(jié)果都能均等的得到等概率的分布. (前者叫做 Reject Sampling, 后者叫做 Metropolis Algorithm, 都是數(shù)學(xué)物理模擬里面常用的方法)

解法二:
二進(jìn)制
1-2映射到0，3跳過，4-5映射到1
生成三位的二進(jìn)制即可