随机数的扩展

问题介绍与扩展

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

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?

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

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

性质与推论

关于集合AA,很容易得到的性质有:

  • 1. 由mAm\in AnAn\in A可以推出mnAmn\in A,特别的,对于素数pppAp\in A推出pnAp^n\in Ann是任一正整数)。
  • 2. 由dnd\mid nnAn\in A可以推出dAd\in A
  • 3. 由上面两条性质,对正整数nn作素因子分解n=ipiαin=\prod_i p_i^{\alpha_i},则nAn\in A等价于对任意iipiAp_i\in A

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

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

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

这个证明还不能说十分完善,因为AA中还有不同于pp的数(比如p2p^2),但是利用这个证明的思想可以得到更强的性质:

  • 4(推论). 若素数p1,p2,,pnAp_1,p_2,…,p_n\in A,则A={ipiαiαiN}A=\{\prod_i p_i^{\alpha_i}\mid α_i\in N\}是符合题意的最小集合。
    甚至还能推广到无穷个素数的情况:
  • 4(推论2). 若素数{pn}A\{p_n\}\in Apnp_n两两不同),则A={iqiqi{pn},iN}A=\{\prod_i q_i\mid q_i\in \{p_n\}, i\in N\}是符合题意的最小集合。

问题解决

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

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

我们再次从素数入手(已经分析过了,解决了素数就解决了一切)把问题描述为:

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#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]);
}

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

1
2
3
4
5
6
7
8
9
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之间的随机数更快,见下文。

复杂度补充

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

1+mkm+(mkm)2+=11(mk)/m=mk1+\frac{m-k}{m}+(\frac{m-k}{m})^2+\ldots\,=\frac{1}{1-(m-k)/m} = \frac{m}{k}

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

假设利用1m1\sim m的均匀随机数生成器构造1ma1\sim m^a的均匀随机数生成器,则取一次随机数的用时变为aa,假设我们想要获得1k1\sim k'的均匀随机数(k<mak'<m^a),期望用时为ama/k>aam^a/k'>a

a2a\geq 2,则此式必然超过前式,换言之,平方扩展不如不扩展。

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

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