如何根据概率选号？

Question

我想 select 来自 0,1,2,3...n 的随机数，但是我想通过乘以 selecting k|0<k<n 的机会降低x 从 select 到 k - 1 所以 x = (k - 1) / k。数字越大捡到的几率越小

作为答案，我想看看下一个方法的实现：

int pickANumber(n,x)

这是针对我正在开发的游戏，我认为这些问题相关但不完全相同：

How to pick an item by its probability
C Function for picking from a list where each element has a distinct probabili

Answer 1

p1 + p2 + ... + pn = 1
p1 = p2 * x
p2 = p3 * x
...
p_n-1 = pn * x

解决这个问题可以得到：

p1 + p2 + ... + pn = 1
(p2 * x) + (p3 * x) + ... + (pn * x) + pn = 1
((p3*x) * x) + ((p4*x) * x) + ... + ((p_n-1*x) * x) + pn = 1
....
pn* (x^(n-1) + x^(n-2) + ... +x^1 + x^0) = 1
pn*(1-x^n)/(1-x) = 1
pn = (1-x)/(1-x^n)

这为您提供了需要设置为 pn 的概率，您可以从中计算所有其他 p1、p2、...p_n-1

的概率

现在，您可以使用 "black box" RNG 选择具有分布的数字，就像您提到的线程中的那些。

一个简单的方法是设置一个辅助数组：

aux[i] = p1 + p2 + ... + pi

现在，抽取一个在0到aux[n]之间均匀分布的随机数，使用二分查找（aux数组已排序），得到第一个值，匹配[=18中的值=]大于你得到的随机统一数

原始答案，用于减法（在编辑问题之前）：

对于n项，您需要解方程：

p1 + p2 + ... + pn = 1
p1 = p2 + x
p2 = p3 + x
...
p_n-1 = pn + x

解决这个问题可以得到：

p1 + p2 + ... + pn = 1
(p2 + x) + (p3 + x) + ... + (pn + x) + pn = 1
((p3+x) + x) + ((p4+x) + x) + ... + ((p_n-1+x) + x) + pn = 1
....
pn* ((n-1)x + (n-2)x + ... +x + 0) = 1
pn* x = n(n-1)/2
pn = n(n-1)/(2x)

这为您提供了需要设置为 pn 的概率，您可以从中计算所有其他 p1、p2、...p_n-1

的概率

现在，您可以使用 "black box" RNG 选择具有分布的数字，就像您提到的线程中的那些。

请注意，这不能保证您会有一个解决方案，例如 0<p_i<1 对于所有 i，但您不能保证根据您的要求给出一个解决方案，这将取决于值n 和 x 适合。

Answer 2

编辑这个答案是针对OP的原始问题，不同之处在于每个概率应该比前一个概率低一个固定数量。

好吧，让我们看看约束条件是怎么说的。你想要 P(k) = P(k - 1) - x。所以我们有：

P(0)

P(1) = P(0) - x

P(2) = P(0) - 2x ...

此外，Sum_k P(k) = 1。求和，我们得到：

1 = (n + 1)P(0) -x * n / 2 (n + 1),

这为您提供了 x 和 P(0) 之间的简单约束。根据另一个来解决一个问题。

Answer 3

为此，我将使用 Boost 提供的 Mersenne Twister 算法进行均匀分布，然后使用映射函数将该随机分布的结果映射到实际数字 select。

这是一个潜在实现的简单示例，尽管我省略了二次方程的实现，因为它是众所周知的：

int f_of_xib(int x, int i, int b)
{
    return x * i * i / 2 + b * i;
}

int b_of_x(int i, int x)
{
    return (r - ( r ) / 2 );
}


int pickANumber(mt19937 gen, int n, int x)
{
    // First, determine the range r required where the probability equals i * x
    // since probability of each increasing integer is x higher of occuring.
    // Let f(i) = r and given f'(i) = x * i then r = ( x * i ^2 ) / 2 + b * i
    // where b = ( r - ( x * i ^ 2 ) / 2 ) / i . Since r = x when i = 1 from problem
    // definition, this reduces down to b = r - r / 2. therefore to find r_max simply
    // plugin x to find b, then plugin n for i, x, and b to get r_max since r_max occurs
    // when n == i.

    // Find b when 
    int b = b_of_x(x);
    int r_max = f_of_xib(x, n, b);

    boost::uniform_int<> range(0, r_max);
    boost::variate_generator<boost::mt19937&, boost::uniform_int<> > next(gen, range);

    // Now to map random number to desired number, just find the positive value for i
    // when r is the return random number which boils down to finding the non-zero root
    // when 0 = ( x * i ^ 2 ) / 2 + b * i - r
    int random_number = next();

    return quadtratic_equation_for_positive_value(1, b, r);
}



int main(int argc, char** argv)
{
    mt19937 gen;
    gen.seed(time(0));

    pickANumber(gen, 10, 1);

    system("pause");
}

如何根据概率选号？

How to pick a number based on probability?

algorithm

math

probability