Selecting a number from a list with a given probability

S

siddharth_jain_1

Hello

Could someone please suggest an algorithm for selecting a number from a
list of n numbers such that the i-th number is chosen with a given
initial probability p_i and the p_i's change according to a piece of
code that works after every selection.

Thanks in advance.

Siddharth Jain
 
E

el goog

It depends on how many p_i's change in each iteration.
If they all do, then there's not much more you can do
than generate a random number r between 0 and 1
and do a linear scan through the n elements until the
sum exceeds r. If n is not large, this might be the
easiest approach.

On the other hand if n is large and there are only a
small number of p_i's change per iteration, you can
achieve O(log n) per random selection and
O(log n) per p_i change. The basic idea is to
maintain the n elements in a complete binary
tree with binary heap style indices (number 1 at the
root, numbers 2 and 3 as its to children, and so on).
In node i store p_i and also store the cumulative
mass of probability in the subtree rooted at i. Now,
when p_i changes you only need to update the
O(log n) nodes on the path from the root to i. You
can also generate a random element in O(log n)
time by generating a random number between 0 and 1,
and going down one side of the tree or other based
on the cumulative probability counts.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top