如何获得随机数与错误的产生 [英] How to get random numbers with the wrong generator

问题描述

问题：假设有一个随机数发生器randn（），该返回0和n-1个均匀分布的随机数。给定任何数量的米，写一个随机数发生器，它返回介于0和M-1均匀分布的随机数。

Question: Suppose you have a random number generator randn() that returns a uniformly distributed random number between 0 and n-1. Given any number m, write a random number generator that returns a uniformly distributed random number between 0 and 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();
    }
}

这是正确的？

Is this correct?

推荐答案

您正在接近，但与你的答案的问题是，有写一些其他两个数字的总和不止一种方式。

You're close, but the problem with your answer is that there is more than one way to write a number as a sum of two other numbers.

如果 M＆n种，那么这个工程，因为数字 0,1，...，M-1 出现在每个等概率，算法结束几乎肯定。

If m<n, then this works because the numbers 0,1,...,m-1 appear each with equal probability, and the algorithm terminates almost surely.

这答案并不在一般的工作，因为那里是写了一些其他两个数字的总和不止一种方法。举例来说，只有一种方式来获得 0 但也有很多很多的方法来获得 M / 2 ，所以的概率会不相等。

This answer does not work in general because there is more than one way to write a number as a sum of two other numbers. For instance, there is only one way to get 0 but there are many many ways to get m/2, so the probabilities will not be equal.

示例： N = 2 和 M = 3

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

所以从你的方法的概率分布

so the probability distribution from your method is

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

这是不均匀的。

which is not uniform.

要解决这个问题，你可以使用独特的分解。写 M 在基地 N ，跟踪最大需要的指数，比如电子。然后，找到最大的多 M 比ñ^ E ，把它叫做小氏/ code>。最后，生成电子的数字与 randn（），把它们作为基 N 扩大一定数量的 X ，如果 X＆LT; K *米，返回 X ，否则重试。

To fix this, you can use unique factorization. Write m in base n, keeping track of the largest needed exponent, say e. Then, find the biggest multiple of m that is smaller than n^e, call it k. Finally, generate e numbers with randn(), take them as the base n expansion of some number x, if x < k*m, return x, otherwise try again.

假设 M＆LT; 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);
    }
}

这篇关于如何获得随机数与错误的产生的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！