algorithm - How to pick a number based on probability?

Question

I want to select a random number from 0,1,2,3...n, however I want to make it that the chance of selecting k|0<k<n will be lower by multiplication of x from selecting k - 1 so x = (k - 1) / k. As bigger the number as smaller the chances to pick it up.

As an answer I want to see the implementation of the next method:

int pickANumber(n,x)

This is for a game that I am developing, I saw those questions as related but not exactly that same:

• 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

Solving this gives you:

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)

This gives you the probability you need to set to pn, and from it you can calculate the probabilities for all other p1,p2,...p_n-1

Now, you can use a "black box" RNG that chooses a number with a distribution, like those in the threads you mentioned.

A simple approach to do it is to set an auxillary array:

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

Now, draw a random number with uniform distribution between 0 to aux[n], and using binary search (aux array is sorted), get the first value, which matching value in aux is greater than the random uniform number you got

---

Original answer, for substraction (before question was editted):

For n items, you need to solve the equation:

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

Solving this gives you:

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)

This gives you the probability you need to set to pn, and from it you can calculate the probabilities for all other p1,p2,...p_n-1

Now, you can use a "black box" RNG that chooses a number with a distribution, like those in the threads you mentioned.

---

Be advised, this is not guaranteed you will have a solution such that 0<p_i<1 for all i, but you cannot guarantee one given from your requirements, and it is going to depend on values of n and x to fit.