Как выбрать число, основанное на вероятности?

Question

Я хочу, чтобы выбрать случайное число от 0,1,2,3...n, однако я хочу сделать так, чтобы шанс выбора k|0<k<n будет ниже путем умножения x от выбора 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

Теперь вы можете использовать «черный ящик» RNG, который выбирает номер с дистрибутивом, как в упомянутых вами потоках.

Простой подход, чтобы сделать это, чтобы установить добавочному массив:

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

Теперь нарисуйте случайное число с равномерным распределением между 0 в aux[n], и с помощью бинарного поиска (Окс массив отсортирован), получаем первое значение, которое подходящее значение в aux больше, чем случайное равномерном числа вы получили

---

Оригинальный ответ, за вычитанием (до вопрос Editted):

Для 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, чтобы соответствовать ,

Answer 2

Редактировать Этот ответ был для исходного вопроса OPs, который отличался тем, что каждая вероятность должна была быть ниже на фиксированную сумму, чем предыдущая.

Хорошо, давайте посмотрим, что говорят ограничения. Вы хотите иметь P (k) = P (k - 1) - x. Итак, мы имеем:

P (0)

P (1) = P (0) - х

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

Кроме того, Сумма _k P (k) = 1. Суммируя, получаем:

1 = (п + 1) P (0) -х * п/2 (п + 1),

Это дает вам простой ограничение между х и P (0). Решите для одного в терминах другого.

Answer 3

Для этого я использовал бы алгоритм Mersenne Twister для равномерного распределения, который предоставляет Boost, а затем имеет функцию сопоставления для сопоставления результатов этого случайного распределения с фактическим выбором номера.

Вот краткий пример возможного осуществления, хотя я ушел из quadtratic реализации уравнения, так как хорошо известно:

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