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/10i.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 .. 1If 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.

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