利用等概率 Rand5 产生等概率 Rand3

问题本身很明确，但不知道起个什么题目好，姑且先这么说吧。

问题描述：现在有一个叫做 Rand5 的函数，可以生成等概率的 [0, 5) 范围内的随机整数，要求利用此函数写一个 Rand3 函数（除此之外，不能再使用任何能产生随机数的函数或数据源），生成等概率的 [0, 3) 范围内的随机整数。

我第一次遇到这个问题的时候，着实犯了一回傻，自以为是地证明了这个题目是无解的。其实从概率的角度来看，题目的要求就是，利用一个 1/5 的概率源，通过某种方式产生出 1/3 的概率输出。我们都知道，概率运算法则有加法和乘法，而在我的记忆中，算法是“在有限步骤内求解某一问题所使用的一组定义明确的规则”，算法的一个重要特征就是有穷性，即一个算法必须保证执行有限步之后结束。那么有限多个 1/5 通过加法和乘法是不可能的到 1/3 这个数值的，因为加法和乘法都不会给分母带来新的因子，那么分母中的 3 根本就不可能出现。

然而我忽略了这样一个式子：

基于这个想法，我们来看看这个算法是什么样子的：

1
2
3
4
5

def Rand3():
    x = -1
    while not 0 <= x < 3:
        x = Rand5()
    return x

1
2
3
4
5
6
7
8
9

int Rand3()
{
    int x;
    do
    {
        x = Rand5();
    } while (x >= 3);
    return x;
}

算法很简单，x 是我们最终要输出的数字，只要它不在 [0, 3) 范围内，就不断地调用 Rand5 来更新它。直观地看，算法输出的数字只有 0、1、2 这三个，而且对任何一个都没有偏袒，那么显然每个数字的概率都是 1/3，那让我们来严格地计算一下。

以输出 0 为例，看看概率是多少。x 的第一个有效数值是通过 Rand5 得到的。Rand5 返回 0 的概率是 1/5，如果这事儿发生了，我们就得到了 0，否则只有当 Rand5 返回 3 或 4 的时候，我们才有机会再次调用它来得到新的数据。第二次调用 Rand5 之后，又是有 1/5 的概率得到 0，2/5 的概率得到 3 或 4 导致循环继续执行下去，如此反复。因此概率的计算公式为：

喏，计算表明，Rand3 输出 0 的概率确实是 1/3，对于另外两个数字也是一样的。

那么这段代码是不是一个算法呢，它是否满足算法的有穷性呢？我不能确定，虽然它不停机的概率是 0，然而这个概率是一个极限值，唉，回去复习极限知识先。

【2013 年 11 月 7 日添加】今天想到，对于上面那个函数，需要再了解一下它消耗的时间。具体来讲，就是要知道平均每调用一次 Rand3，相当于调用了多少次 Rand5。根据算法可以知道，Rand3 函数执行一次，有 3/5 的概率是只调用一次 Rand5 就能停机；刚好调用两次 Rand5 后停机的概率是 (2/5) * (3/5)。类推下去，刚好调用 k 次 Rand5 后停机的概率应该是 (2/5) ^ (k-1) * (3/5)。根据这个概率分布，可以计算出停机前 Rand5 被调用次数的数学期望，即

可见，Rand3 函数每运行一次，平均需要调用 1.67 次 Rand5。

更一般地，当我们依据上述算法，将一种分布的随机信号转换成另外一种随机信号时，如果每消耗 m 个源信号，就有 p 的概率可以产生一个目标信号，那么平均来讲，停机前需要使用的源信号数据个数的期望为：

【2013 年 11 月 7 日添加结束】

改变一下题目，如果要求利用 Rand5 编写 Rand7 怎么办？很简单，用两个 Rand5 可以拼出 Rand25，然后就用前面的方法即可：

1
2
3
4
5

def Rand7():
    x = -1
    while not 0 <= x < 21:
        x = Rand5() * 5 + Rand5()
    return x % 7

1
2
3
4
5
6
7
8
9

int Rand7()
{
    int x;
    do
    {
        x = Rand5() * 5 + Rand5();
    } while (x >= 21);
    return x % 7;
}

【2013 年 11 月 7 日】可以直接算出，按照这种方法，平均每运行一次 Rand7，需要调用 Rand5 的次数。这里 m 等于 2，p 等于 21/25，所以最后的结果是 50/21，大约是 2.38。

Like this post? Share on: Twitter ❄ Facebook ❄ Email