首页 文章

如何根据概率选择一个数字？

提问于
浏览 次
-1

我想从 0,1,2,3...n 中选择一个随机数，但是我想通过选择 k - 1 与 x = (k - 1) / k 相乘来选择 k|0<k<n 的机会会降低 . 数量越大，拾取的机会就越小 .

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

int pickANumber(n,x)

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

algorithm math probability

3 回答

  • 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的概率

    现在，你可以使用一个“黑匣子”RNG来选择一个带有分布的数字，就像你提到的那些线程中那样 .

    一个简单的方法是设置辅助阵列：

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

    现在，在 0 到 aux[n] 之间绘制一个均匀分布的随机数，并使用二分搜索（辅助数组排序），得到第一个值， aux 中的匹配值大于你得到的随机统一数

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

    对于 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的概率

    现在，你可以使用一个“黑匣子”RNG来选择一个带有分布的数字，就像你提到的那些线程中那样 .

    请注意，这并不能保证你会得到 0<p_i<1 所有 i 的解决方案，但你不能保证根据你的要求提供一个解决方案，并且它将取决于 n 和 x 的值 .

    回复于
  • 2

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

    好吧，让我们看看约束说的是什么 . 你想要P（k）= P（k - 1） - x . 所以我们有：

    P（0）

    P（1）= P（0） - x

    P（2）= P（0） - 2x ......

    另外，Sumk P（k）= 1.求和，我们得到：

    1 =（n 1）P（0）-x * n / 2（n 1），

    这为您提供了x和P（0）之间的简单约束 . 解决另一个问题 .

    回复于
  • 0

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

    这是一个潜在实现的快速示例，尽管我遗漏了四元方程实现，因为它是众所周知的：

    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");
}
    回复于

相关问题