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.