Page 47 -

34 Monte Carlo methods

procedure tower-sample
Π
K
input {π 1 ,... ,π K }
Π 0 ← 0
for l =1,... ,K do Π l ← Π l−1 + π l
activity Υ ← ran (0, Π K )
K
∗ find k with Π k−1 < Υ < Π k
output k
——
go out
Algorithm 1.14 tower-sample. Tower sampling of a finite distribution
{π 1,...,π K } without rejections.
movie
Π
k
activity
k Tower sampling can be applied to discrete distributions with a total
Π
k−1 number K in the hundreds, thousands, oreven millions.It often works
jog when the naive rejectionmethod of Fig.1.28 fails because oftoo many
rejections.Tower sampling becomes impracticable only when the prob-
chores
abilities {π 1 ,...,π K } can nolonger be listed.
study In Alg.1.14 (tower-sample), wemust clarify how weactually find
Π = 0
0
the element k,i.e. how weimplement the line marked by an asterisk.
Forsmall K, wemay go through the ordered table {Π 0 ,... , Π K } one
Fig. 1.29 Saturday night problem byone, until the element k, with Π k−1 < Υ ≤ Π k ,is encountered.For
solved by tower sampling. large K, a bisectionmethodshouldbeimplemented if weare making
heavy use oftower sampling: wefirstcheck whether Υ is smaller or larger
than Π K/2 ,and then cutthe possible range of indices k in half oneach
subsequent iteration.Algorithm 1.15 (bisection-search) terminates in
about log K steps.
2

procedure bisection-search
input Υ, {Π 0, Π 1 ,... , Π K } (ordered table with Π k ≥ Π k−1 )
k min ← 0
k max ← K +1
for i =1, 2,... do
⎧
⎪ k ← (k min + k max )/2 (integer arithmetic)
⎪
⎪
⎪ if (Π k < Υ)then
⎪
⎪
⎪
⎪ k min ← k
⎪
⎪
⎨
else if (Π k−1 > Υ)then

k max ← k
⎪
⎪
⎪ else
⎪
⎪
⎪
⎪
⎪ output k
⎪
⎪
⎩
exit
——
Algorithm 1.15 bisection-search. Locating the element k with
Π k−1 < Υ < Π k in an ordered table {Π 0,.. ., Π K}.