The class `random_source`

also has a
*bit mode*. In this mode
it creates bit strings of a length defined before. This is
particularly suitable for algorithms that toss a coin in
certain positions and branch depending on the result
“head” or “tail”, respectively.

As a program example for this we simulate a *Galton board*, named
after the statistician Francis Galton (1822-1911). Figure 2.19 shows such a
board.
It consists of a triangularly layered arrangement of pins on a crooked
plane. Starting from the position over the topmost pin, one lets small
balls roll to the bottom of the board, where they are collected in a
series of tubes. The balls can branch either to the right or to the
left with probability 1/2 at every pin (that is on every layer).

This experiment serves for the experimental determination of the
*binomial
distribution*.
With n+1 tubes altogether there are always n layers above; a rolling
of a ball corresponds to n coin tosses. The most improbable outcome is
that the ball lands in the very left or the very right tube; this
corresponds to a result of n consecutive “heads” or n
consecutive “tails”. The probability for
this is 2^{-n} because only one of the
2^{n} ways altogether is the correct one (the
one in which the ball branches always to the left or always to the
right). The most probable end tube is the one in the
middle (the two tubes in the middle in case of n being odd). To
get here, the ball must branch to the left just as often as to the
right. The number of combinations for this is (n,n/2) with (n,k)
denoting the binomial
coefficient introduced in Section “Enlarging arrays dynamically”. (From n positions, in which the
ball can branch to the left, it arbitrarily chooses n/2.) It generally
holds that the ball lands in tube k with probability
(n,k)·2^{-n}. (What we do not want to prove
here.) This number is called the *Bernoulli probability*. It
denotes the probability that “head” is tossed exactly k
times in a sequence of n coin tosses.

So if we let run 2^{n} balls
altogether, the number of balls in the tubes thereafter should
correspond to approximately the binomial coefficients from
Pascal's triangle, which we also got to know in Section “Enlarging arrays dynamically”.

The following program uses a random source in the 1-bit
mode to simulate the branches or coining tosses,
respectively. With n layers and n+1 tubes it assumes 2n+1
virtual intermediate positions, which are numbered at the bottom
of Figure 2.19. The function
`let_it_roll() `

starts in the middle
intermediate position and then branches n times to the left or
to the right, depending on the bit that was returned by the
random source. It returns the number of the tube that the
ball has fallen into. The numbering of the tubes starts with 0. The
main program lets 2^{n} balls roll and
then outputs the number of balls in the individual tubes by means
of the function `print_counters()`

.

#include <LEDA/random_source.h> #include <LEDA/array.h> #include <iostream> using leda::random_source; using leda::array; using std::cout; random_source S(1); // Random source in 1-bit-mode void print_counters(array<int>&); // The following function was originally written by Chuck Berry int let_it_roll(int n) { int vpos = n; // initial virtual position int left_or_right; for(int layers = 1; layers <= n; layers++) { S >> left_or_right; if(left_or_right == 0) vpos--; else vpos++; } return (vpos / 2); } int main() { const int n = 9; // number of layers const int num_balls = (1 << n); array<int> counter(0,n); counter.init(0); for(int i = 1; i <= num_balls; i++) counter[let_it_roll(n)]++; print_counters(counter); } void print_counters(array<int>& counter) { int max = counter[0]; for(int i = 1; i <= counter.high(); i++) if(max < counter[i]) max = counter[i]; // print 50 stars for the maximum, the rest corresp. for(int j = 0; j <= counter.high(); j++) { cout << j << ": "; for(int k = 0; k <= counter[j] * 50 / max; k++) cout << "*"; cout << " (" << counter[j] << ")\n"; } }

An output of a run on the machine of the author was the following:

0: * (1) 1: *** (5) 2: ********************* (51) 3: ************************************ (87) 4: ************************************************* (120) 5: *************************************************** (123) 6: ********************************* (80) 7: *************** (35) 8: **** (9) 9: * (1)

Compare this with the 9th line of the output of the program for the computation of Pascal's triangle, which we have implemented in Section “Enlarging arrays dynamically”!

By the definition of a random source by

random_source S(p);

with only one integer `p`

as the argument this source
is put into the *p-bit mode*. It then returns an
integer number at every call of the operator
`>>`

whose last p bits are random; all the
higher-order bits are 0. p must be between 1 and 31 and is referred to
as the *precision*.

With the method

S.set_precision(p);

the precision can be modified afterwards.

Furthermore a random number
with a certain precision p can also be created directly from a random
source `S`

by the call

int random_number = S(p);

Of course, the above function
`let_it_roll()`

with its virtual intermediate
positions is unnecessarily complex. Since its task merely
consists in counting how often “head” occurs in a
result of n coin tosses, we simply do this and nothing more:

// And later optimized by The Rolling Stones int let_it_rock(int n) { int num_heads = 0; int heads_or_tails; for(int i = 1; i <= n; i++) { S >> heads_or_tails; // As heads is tails just call me... if(heads_or_tails == 1) num_heads++; } return num_heads; }

More about random sources can be found on the corresponding manual page.