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

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 , 如果 x < k*m , 返回 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);
    }
}