问题:
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
生成三位的二进制即可