Page 16 -

1.1 Popular games in Monaco 3

1.1 Popular games in Monaco

The concept ofsampling (obtaining the randompositions) is truly com-
plex,and we had better get a grasp of the idea in a simplified setting be-
fore applying it in its full power and versatility to the complicated cases
of later chapters.Wemust clearly distinguish between two fundamen-
tally different sampling approaches: direct sampling and Markov-chain
sampling.

1.1.1 Direct sampling

Direct sampling is exemplified by an amusing game that we can imagine
children playing on the beaches of Monaco. In the sand, they first draw
a large circleand a square exactly containing it (see Fig.1.1). They
2
then randomly throw pebbles. Each pebblefalling inside the square
constitutes a trial, and pebbles inside the circleare also counted as
“hits”.
By keeping track ofthe numbers oftrials and hits, the children perform
a direct-sampling Monte Carlo calculation: the ratioofhits to trials
is close to the ratioofthe areas ofthe circleand the square, namely
/4.The other day, in a game of4000 trials, they threw 3156 pebbles
inside the circle (see Table 1.1). This means that they got 3156 hits,
and obtained the approximation 3.156 by just shifting the decimal
point.
Let us write upthe children’s game in a fewlines ofcomputer code
(see Alg.1.1 (direct-pi)). Asit isdifficultto agree on language and
dialect, we use the universal pseudocode throughoutthis book. Readers
can then translate the general algorithms into their favorite program-
ming language, and are strongly encouraged to do so. Suffice it to say
here that callsto the function ran (−1, 1) produce uniformly distributed
real randomnumbers between −1 and 1. Subsequent calls yield inde-
pendent numbers.

procedure direct-pi
N hits ← 0 (initialize)
for i =1,... ,N do
⎧
⎨ x ← ran (−1, 1)
y ← ran (−1, 1)
⎩ 2 2
if (x + y < 1) N hits ← N hits +1 Table 1.1 Results of five runs of
Alg. 1.1 (direct-pi)with N = 4000
output N hits
——
Algorithm 1.1 direct-pi. Using the children’s game with N pebbles Run N hits Estimate of
to compute .
1 3156 3.156
2 3150 3.150
The results ofseveral runs of Alg.1.1 (direct-pi) are shownin Ta- 3 3127 3.127
ble 1.1. During each trial, N = 4000 pebbles were thrown, butthe ran- 4 3171 3.171
5 3148 3.148
2 The Latin word for “pebble” is calculus.