Dr. Mark Humphrys

School of Computing. Dublin City University.

Home      Blog      Teaching      Research      Contact

My big idea: Ancient Brain

Search:

CA114      CA170

CA668      CA669      Projects

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


ancientbrain.com      w2mind.org      humphrysfamilytree.com

On the Internet since 1987.

Wikipedia: Sometimes I link to Wikipedia. I have written something In defence of Wikipedia. It is often a useful starting point but you cannot trust it. Linking to it is like linking to a Google search. A starting point, not a destination. I automatically highlight in red all links to Wikipedia and Google search and other possibly-unreliable user-generated content.