Page 46 -

1.2 Basic sampling 33

1.2.3 Finite distributions

The sampling ofnonuniform finite distributions has an archetypal ex-
amplein the Saturday night problem.We imagine K possibleevening
activities that wedo notfeel equally enthusiastic about: study(k =1,
probability π 1 0),chores (k = 2, probability π 2 ≪ 1),cinema, book
writing, etc.The probabilities π k are all known, but wemay still have
trouble deciding what to do. This means that wehavetroubleinsam-
pling the distribution {π 1 ,... ,π K }.Two methods allow usto solvethe
Saturday night problem: a basic rejectionalgorithm, and tower sampling,
a rejection-free approach.

procedure reject-finite
π max ← max K π k
k=1
1 k ← nran(1,K)
Υ ← ran (0,π max )
if (Υ >π k ) goto 1
output k
——

Algorithm 1.13 reject-finite. Sampling a finite distribution
{π 1,...,π K } with a rejection algorithm.

π
max

write read
π this this
1
study chores jog book movie go out book
0
1 k K

Fig. 1.28 Saturday night problem solved by Alg. 1.13 (reject-finite).

In the rejectionmethod (see Alg.1.13 (reject-finite)),pebbles are
randomly throwninto abig frame containing boxes forall the activities,
whose sizes represent their probabilities. Eventually, one pebblefallsinto
one of them and makes ourchoice. Clearly, the acceptance rate ofthe
algorithm is given by the ratioofthe sum ofthe volumes ofall boxes to
the volume of the big frame and is equal to π /π max , where the mean

probability is π = π k /K.This implies that onaverage wehaveto
k
throw π max / π pebbles before wehavea hit.This number can easily
become solarge that the rejectionalgorithm is notreally an option.
Tower sampling is a vastly more elegant solutionto the Saturday night
problem.Instead ofplacing the boxes nextto each other, as in Fig.1.28,
wepilethem up (see Fig.1.29). Algorithm 1.14 (tower-sample) keeps
track ofthe numbers Π 1 = π 1 , Π 2 = π 1 + π 2 ,etc.With a singlerandom
number ran (0, Π K ),anactivity k is then chosen.There is no rejection.