如何用一个1-8随机数生成器制作一个1-7随机数生成器？ 第1页

其实最简单可行的方法就是重复调用rand8()，如果抽到8就重抽，直到结果小于8为止。这个方法看起来很简单，但其实是有道理的。它利用了Rejection sampling技术，这是一种常用的采样算法。

如果写成C代码的话，大概是这样：

       int rand7(){     int a;     while ( (a=rand8())==8 );     return a; }      

题注还提到了rand8()的开销比较大，那我们就来分析一下这种基于Rejection sampling方法构造的rand7()的效率。

设成功执行一次rand7()所需要的rand8()的次数为N，N是个随机变量，服从参数为7/8的几何分布，其数学期望E[N]=8/7=1.143，方差D[N]=8/49=0.163，标准差大约是0.404。

从这个结果来看，上述rand7()的平均开销和波动都不算大。执行超过五次rand8()的概率约为十万分之三，而超过十次的概率不足十亿分之一。十亿分之一什么概念？假如你有1GB的数据，你希望针对其中的每一个字节做一个和rand7有关的处理，那么你把整个数据库处理完，估计也就能碰上一次倒霉需要抽十次rand8()。而我认为这种程度的“倒霉”是完全可以接受的。

问题本身就算是答完了，再补充一些内容：

第一、关于楼主提到的“最高效率”，我想只能从信息论的角度给出一个界限。一次rand7的算法所能提供的信息量是log7，而一次rand8是log8，所以无论怎样，平均一次rand7所需要执行的rand8的次数至少为log7/log8=0.9358。我们的算法需要1.143次，效率也还可以。

理论上能接近这个界限的方法大概就是王赟 Maigo基于七、八进制小数转换的方法，但该方法需要生成无穷多位八进制小数才能保证完全准确的rand7()。实际应用中，为了提高rand7()的精度，也不得不多产生一些八进制小数。当所需的rand7()的样本较少时，效率也不一定很高。

第二、简要介绍一下Rejection sampling。

Rejection Sampling解决的是这样一类问题：我们希望对目标分布进行采样，但直接构造这样一个随机数生成器可能比较困难。我们就先构造一个简单的随机数生成器，使之能产生与近似的分布，然后再利用如下方法就可以得到的样本：

1、对采样，得到样本。
2、对0~1之间的均匀分布采样，得到样本，如果，则接受这个，否则重复1操作。（这一步其实就是以概率接受）。这里是一个常数，要求对于任意的，有，证明也不太复杂，如果记为随机事件“接纳样本”，则经过筛选的分布其实就是条件概率，简单推导一下。因此接受的样本服从分布。

把这个方法应用到rand7()问题上就得到了开始的算法。

1、调用rand8()进行采样，得到一个整数x
2、如果x等于8，则接受概率为0，扔掉这个样本，如果x等于7，则接受概率为1，保留这个样本。

第三、关于多次采样时样本间的独立性问题。这是随机数生成器的一个重要指标。基于Rejection Sampling的这个算法可以保证每次产生的随机数是独立的，因为新样本的产生完全不依赖现有的结果。有人在评论里问我，如果产生的样本等于8则取上一次输出的结果作为本次结果，可以不可以。回答是不可以，虽然这种方案可以保证每一个样本的边缘分布都是1到7的均匀分布，但是这种方法产生的随机数样本之间是有相关性的。假设本次生成的样本是1，考察下一个样本还是1的条件概率，显然执行rand8()的结果无论是1还是8，输出的结果都是1，因此条件概率等于2/8。而独立性要求这个值等于1/7。所以这种方法不能满足独立性的要求。而且这个方法还有一个问题，需要先执行一次rand7()，拿到第一个样本，才能够保证后续样本的边缘分布都是1到7的均匀分布。

第四、关于能不能保证算法在有限次内结束。这个算法在有限次内结束的概率是1，需要执行无穷多次rand7()的概率是0。但概率是0并不代表不会发生，样本空间里是有这种情况的。而能保证有限次内结束的非近似算法，我想是不存在的。假设算法在M次内结束，那么样本空间就有8的M次方个基本元素，每个基本元素的概率相同。而这个数字又不能被7整除，怕是没办法了。我想这就好比是用尺规三等分任意角，如果能无限次操作的话，也是可以做到的，因为1/3=1/4+1/16+1/64+1/256...。而对于这个问题如果采用Rejection Sampling方法，则是1/7=1/8+1/64+1/512+1/4096...这么搞出来个1/7。