基于概率的随机数

Question

我在生成不遵循离散均匀分布的随机数时遇到了麻烦.

例如,假设我有5个数字(为了保持简单),生成数字k的概率为k/15.(k = 1到5)

我的想法是使用rand()生成一个随机数j,如果这个数字j是:

1 =>然后生成数字1

2或3 => num 2

4或5或6 => num 3

7或8或9或10 => num 4

11或12或13或14或15 =>数字5

现在将其缩放为生成1-10,1-100,1-1000.这是否按照我打算的方式工作？我已经构建了一个循环,每次需要生成一个数字时都会这样做,我认为它可能是低效的,因为它一直上升,直到找到在其中一个范围内生成的j数.​​..有什么可能是更好的方法去做这个？

编辑:或者可能使用正确的数字创建一个数组,然后使用rand()更好的解决方案？

Answer 1

你似乎走在正确的轨道上,但C++已经有了专门的随机数分布, std::discrete_distribution

#include <iostream>
#include <vector>
#include <map>
#include <random>

int main()
{
    std::random_device rd;
    std::mt19937 gen(rd());

    // list of probabilities    
    std::vector<double> p = {0, 1.0/15, 2.0/15, 3.0/15, 4.0/15, 5.0/15};
    // could also be min, max, and a generating function (n/15 in your case?)
    std::discrete_distribution<> d(p.begin(), p.end());

    // some statistics
    std::map<int, int> m;
    for(int n=0; n<10000; ++n) {
        ++m[d(gen)];
    }
    for(auto p : m) {
        std::cout << p.first << " generated " << p.second << " times\n";
    }
}

在线演示:http://ideone.com/jU1ll

Answer 2

考虑到总和s整数从1到n是s = n * (n + 1) / 2.解决n得到n = (± sqrt(8*s + 1) - 1) / 2.我们可以忽略负平方根,因为我们知道n是积极的.因此n = (sqrt(8*s + 1) - 1) / 2.

因此,插入s1到15之间的整数:

s  n
01 1.000000
02 1.561553
03 2.000000
04 2.372281
05 2.701562
06 3.000000
07 3.274917
08 3.531129
09 3.772002
10 4.000000
11 4.216991
12 4.424429
13 4.623475
14 4.815073
15 5.000000

如果我们取每个计算的上限n(最小整数不小于n),我们得到这个:

s  n
01 1
02 2
03 2
04 3
05 3
06 3
07 4
08 4
09 4
10 4
11 5
12 5
13 5
14 5
15 5

因此,您可以在恒定空间和恒定时间内从均匀分布到分布(没有迭代,也没有预先计算的表):

double my_distribution_from_uniform_distribution(double s) {
    return ceil((sqrt(8*s + 1) - 1) / 2);
}

NB这依赖于sqrt给出一个完美正方形的精确结果(例如,正好返回精确的正数为49).这通常是一个安全的假设,因为IEEE 754要求精确舍入平方根.

IEEE 754双精度数可以表示从1到2 ^ 53的所有整数(以及许多更大的整数,但在2 ^ 53之后不连续).所以这个函数应该适用于s从1到1的所有floor((2^53 - 1) / 8) = 1125899906842623.