如何使用错误的生成器获取随机数

Question

问题:假设您有一个随机数生成器randn(),它返回0到n-1之间的均匀分布的随机数.给定任意数m,写一个随机数生成器,返回0到m-1之间的均匀分布的随机数.

我的答案:

-(int)randm() {
    int k=1;
    while (k*n < m) {
        ++k;
    }
    int x = 0;
    for (int i=0; i<k; ++i) {
        x += randn();
    }
    if (x < m) {
        return x;
    } else {
        return randm();
    }
}

它是否正确？

Answer 1

你很接近,但你的答案的问题是,有一种方法可以将一个数字写成另外两个数字的总和.

如果m<n,那么这是有效的,因为数字0,1,...,m-1看起来每个都具有相同的概率,并且算法几乎肯定终止.

这个答案一般不起作用,因为有多种方法可以将数字写成另外两个数字的总和.例如,只有一种方法可以获得,0但有许多方法可以获得m/2,因此概率不会相等.

示例:n = 2和m=3

0 = 0+0
1 = 1+0 or 0+1
2 = 1+1

所以你方法的概率分布是

P(0)=1/4
P(1)=1/2
P(2)=1/4

哪个不统一.

要解决此问题,您可以使用唯一分解.写入m基数n,跟踪所需的最大指数,比方说e.然后,找到它的最大倍数m小于n^e,称之为k.最后,生成e数字randn(),将它们作为n某些数字的基本扩展x,if x < k*m,return x,否则再试一次.

m < n^2那么假设那样

int randm() {

    // find largest power of n needed to write m in base n
    int e=0;
    while (m > n^e) {
        ++e;
    }

    // find largest multiple of m less than n^e
    int k=1;
    while (k*m < n^2) {
        ++k
    }
    --k; // we went one too far

    while (1) {
        // generate a random number in base n
        int x = 0;
        for (int i=0; i<e; ++i) {
            x = x*n + randn(); 
        }
        // if x isn't too large, return it x modulo m
        if (x < m*k) 
            return (x % m);
    }
}