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