Dr. Mark Humphrys

School of Computing. Dublin City University.

Home      Blog      Teaching      Research      Contact

Search:

CA216      CA249      CA318

CA400      CA651      CA668

How to make a decision probabilistically

Say we have decided that:

Event a1 will happen with probability 1/10
Event a2 will happen with probability 3/10
Event a3 will happen with probability 1/10
Event a4 will happen with probability 3/10
Event a5 will happen with probability 2/10
i.e. 1 time out of 10 we will pick a1, 3 times out of 10 we will pick a2, and so on.

When asked to make a decision, what algorithm should we use so that the above will hold?

Imagine the probabilities on a line as follows:

+----+------------+----+------------+--------+
| a1 |   a2       | a3 |   a4       |  a5    |
+----+------------+----+------------+--------+
0    0.1         0.4   ..                    1
If we pick a random number between 0 and 1, it is 3 times more likely to fall in a2's segment than in a1's.

Sometimes described as "spinning the weighted wheel" where the wheel is divided into segments whose size corresponds to the probabilities. We spin it and see in whose segment it stops.




Algorithm:


x := random number 0 to 1 exclusive

// avoid x = 0 exactly, makes for simpler logic below

sum := 0
i := 0

while sum < x		// will always enter this loop at least once
{
  i++
  sum := sum + probability of ai
}

return i


Feeds      w2mind.org

On Internet since 1987.