随机数的扩展

问题介绍与扩展

几天前偶然在网上看到这样一道面试题：

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?

当时第一反应是无法承诺在有限步之内做到，只能逼近。今天突然想到这个问题，深入探究后发现收获不少。为了叙述方便，我们构造集合$A$，对于任何正整数n，若可以得到$(1,n)$均匀随机数生成方法，则说$n$在集合$A$中。

将面试题推广一下，就是给定一个$1\sim m$的均匀随机数生成器，是否能构造一个$1\sim n$的均匀随机数生成器？也就是说，$m\in A$是否可以推出$n\in A$？

性质与推论

关于集合$A$，很容易得到的性质有：

• 1. 由$m\in A$和$n\in A$可以推出$mn\in A$，特别的，对于素数$p$，$p\in A$推出$p^n\in A$（$n$是任一正整数）。
• 2. 由$d\mid n$和$n\in A$可以推出$d\in A$。
• 3. 由上面两条性质，对正整数$n$作素因子分解$n=\prod_i p_i^{\alpha_i}$，则$n\in A$等价于对任意$i$，$p_i\in A$。

第3条性质非常重要，它引导我们先从素数入手，即假设给定$p$和$q$为素数，且$p≠q$。直觉说来$p\in A$无法导出$q\in A$，是否可以证明呢？为此我们需要探究$p\in A$时，$A$中必须有哪些元素。一个非常直接的断言是下面的性质：

• 4. 若素数$p\in A$，则$A=\{p^n\mid n\in N\}$是符合题意的最小集合。

性质4的证明：设$q∉A$，不妨取$n$次$1\sim p$均匀随机数（因为有限步之内完成，所以可以限定一个$n$），若能得到$1\sim q$的均匀随机数，有多元函数$f$使得$f(x_1,x_2,…,x_n)$的值域为$1\sim q$之间的整数，其中$x_i$由$1\sim p$随机生成器生成，即取值范围是$1\sim p$。因为定义域实际上为$p^n$个$n$维空间的点，所以$f$是这$p^n$个点到$1\sim q$个数的单射。由于$1\sim q$个数每个数的原像无交集，概率相等（因为每个点的取值概率相等，所以概率大小取决于点的个数），所以定义域必然是$q$的倍数，这就矛盾了。

这个证明还不能说十分完善，因为$A$中还有不同于$p$的数（比如$p^2$），但是利用这个证明的思想可以得到更强的性质：

• 4(推论). 若素数$p_1,p_2,…,p_n\in A$，则$A=\{\prod_i p_i^{\alpha_i}\mid α_i\in N\}$是符合题意的最小集合。
  甚至还能推广到无穷个素数的情况：
• 4(推论2). 若素数$\{p_n\}\in A$（$p_n$两两不同），则$A=\{\prod_i q_i\mid q_i\in \{p_n\}, i\in N\}$是符合题意的最小集合。

问题解决

现在原题已经很清楚了。如果仅有$1\sim m$均匀随机数生成器，若$n$的素因子都是$m$的素因子，那么可以利用素因子分解和上面的提到的性质构造$1\sim n$的均匀随机数生成器，否则就没法构造。

问题并不是到此为止了，对于已经证明无法构造的随机数生成器，在实际情况下我们可能仍然需要考虑写一个功能接近的投入使用，因为总是有误差可以被允许的。

我们再次从素数入手（已经分析过了，解决了素数就解决了一切）把问题描述为：

给定素数$p≠q$，现在有外部函数int rand_p()，它可以等概率返回一个$1\sim p$的整数（但你无法查看函数细节），请你写一个函数int rand_q()，它可以等概率返回一个$1\sim q$的整数。

首先由费马小定理可知$p^{q-1}≡1\pmod q$，进一步得到$p^{n(q-1)}≡1\pmod q$。由于我们有$1\sim p^{n(q-1)}$的均匀随机数生成方法（为了简洁下面记$N= p^{n(q-1)}$），利用函数$y=x\%q+1$得到$1\sim q$的随机数（$x$是$1\sim N$的随机数）。除了取到1的概率为$1/q+(1-1/q)/N$外，其余值被取到的概率为$1/q-1/(qN)$，当n取得充分大的时候可以让误差充分小。这种方法就是我们平时用<stdlib.h>中的rand()函数来取整数$a\sim b$的随机数的方法。代码如下：

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

#define p (2)
#define q (5)

extern int rand_p();
/* return rand()%p+1; */

//求1~p^n随机数，要求n是正整数
int rand_p_n(int n)
{
    int sum=rand_p()-1;
    for(int i=0;i<n-1; i++)
    {
        sum*=p;
        sum+=rand_p()-1;
    }
    return sum+1;
}

int rand_q()
{
    return rand_p_n(3*(q-1))%q+1;
    //这里可以对p^(q-1)的值进行评估
    //若太小，采用p^(k(q-1))，k为大小合适的正整数
    //若太大，适当减小q-1的值也可
}

int main()
{
    int n=100000;
    srand((unsigned)time(NULL));
    int count[q]={0};
    while(n--)
        count[rand_q()-1]++;
    for(int i=0;i<q;i++)
        printf("%d ",count[i]);
}

此外我还想到另一种方法，看起来更完美一些，牺牲一点点时间可以换取完全的等概率。前面提到$N≡1\pmod q$（还是记$N=p^{n(q-1)}$），现在取$1\sim N$随机数，取到$N$时丢弃此次结果，重新选取。虽然不能预先确定几步之内可以完成选取，但是有限步之内完成的几率为1。即：

int rand_q()
{
    int k=rand_p_n(3*(q-1));
    while(k==0)
        k=rand_p_n(3*(q-1));
    return k%q+1;
    //若q太大，同样可以适当减小q-1的值
    //但p^k最好还是能与较小的数同余(mod q)
}

至此已经可以完全地回答前面的面试提问——

5和7是不相等的素数，仅依靠1~5随机数生成器无法在确定的有限步内得到1~7的随机数生成器。由于5^(7-1)=15625，且我们可以构造1~15625之间的随机数，可以用如下方法来构造1~7之间的随机数：

取1~15625的随机数x，若x为15625，重复上述步骤，否则y=x%7+1就是要求的1~7的随机数。（15625-1=2232*7）

但其实不需要构造1~15625之间的随机数，而是应该构造1~25之间的随机数更快，见下文。

复杂度补充

假设从$1\sim m$的均匀随机数生成器中取出一个数字的用时为1，相比之下一般的加减乘除和取余数运算可以忽略用时。
我们想要获得$1\sim k$的均匀随机数($k<m$)的话(取到大于k的数则重取)，期望用时为

$1+\frac{m-k}{m}+(\frac{m-k}{m})^2+\ldots\,=\frac{1}{1-(m-k)/m} = \frac{m}{k}$

通过调整可以使$k\geq [(m+1)/2]$，从而上式至多为2。

假设利用$1\sim m$的均匀随机数生成器构造$1\sim m^a$的均匀随机数生成器，则取一次随机数的用时变为$a$，假设我们想要获得$1\sim k'$的均匀随机数($k'<m^a$)，期望用时为$am^a/k'>a$。

若$a\geq 2$，则此式必然超过前式，换言之，平方扩展不如不扩展。

但不是说扩展的越少($a$越小)越好。特殊情形举例：

给定1~61的均匀随机数生成器，要构造1~1861的均匀随机数生成器。假设取1~61的随机数用时为1，则取1~61^2的随机数用时为2，在其中构造取1~1861的随机数用时约为4，但若取1~61^3的随机数用时为3，在其中构造取1~1861的随机数用时约为3。在这个例子中可以认为$a=1.5$。