2
$\begingroup$

I have a list of couples "probability"+"value". What is the best algorithm for generating random values with that specified level of probability?

1st proposal:

Approximate the probability up to 10^-k. Create a set of 10^k items each of witch with the corresponding value, Eg:

x=[0.1:a, 0.2:b, 0.4:c 0.3:d]

Approximating with 10^-1 accuracy, we get a set of 1 element a + 2 elements b + 4 elements c + 3 elements d. For a total of 10^1 elements.

Create a set/array of those values

1->a
2->b
3->b
4->c
5->c
6->c
7->c
8->d
9->d
10-d

And now extract a random item (generating a random number with uniform distribution from 0 to 10k.) The correspective value associated is the random value.

  • Pro:
  • It's O(n) in pre-computation
  • Theoretically I think it scales easily
  • Cons:
  • It's very ugly and uses a lot of space, in O(N)

2nd proposal:

  • Pre-computation:

    • for each position, save the current weight + the value of all the other weight.

  • Run-time:

    • extract a random number x from 0 to 1.
    • Compare the current array[i] with x, if x > index[i], skip to the next, otherwise return the value of the current.
    • Iterate until a result.

  • Pro:

    • easy and nice
  • Cons:
    • -

3rd proposal:

Create a binary tree, where the laves contain the value, while the nodes are just "decision", and the edges are probability values. The values of the edges are created according to the sum of the probability of the exiting edges of their children.

> x=[0.1:a, 0.2:b, 0.4:c 0.3:d] 
> 
> root->(node1, 0.3),(node2, 0.7) 
> node1->(a, 0,1),(b, 0.2) 
> node2->(c,0.4),(d, 0.3)

Generate a random number from 0 to 1. Follow the tree from the root finding the closest values of leaf.

  • Pro:
    • Graphs ;)
    • Pre-computation O(n)?
    • Execution is just O(logn)
  • Cons:
    • -

I have found a really nice heuristic for creating the tree, and i think it's the best one.

Perhaps it's possible to do something using (stochastic?) matrix / graph (heap?) / finite state automata, but I'm not 100% sure.

Are there any others better algorithms? Any paper/link or documentation on software who do this works it's appreciated.

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ In line with the second proposal, keep an array of the accumulated probabilities ie [0.1, 0.2, 0.3, 0.4] -> [0.0, 0.1, 0.3, 0.6, 1.0] (note the 0 prepended at the beginning) and you can do something like a binary search in this array to find the interval in which your uniformly generated random number (between 0 and 1) falls. There's no need to sort anything beforehand, but make sure the weights are normalised to sum to one. Hope I'm being clear - don't have to time to elaborate. $\endgroup$ – Aky May 14 '14 at 15:43
  • $\begingroup$ you are damn right, it was a stupid mistake. Just removed. $\endgroup$ – asdf May 15 '14 at 10:11
  • 1
    $\begingroup$ No worries, but I hope you realise that since the accumulation array will always be sorted, that you can use a binary search instead of a linear one $\endgroup$ – Aky May 15 '14 at 10:18
  • $\begingroup$ possible duplicate of Non-uniform random distribution: How do I get a random between 100 and 180 that is on average close to 120? (like in a Gaussian distribution) $\endgroup$ – Yuval Filmus May 15 '14 at 14:44
  • $\begingroup$ Use the alias method. See this answer: cs.stackexchange.com/questions/18467/…. $\endgroup$ – Yuval Filmus May 15 '14 at 14:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.