### 2.5.2. The bit mode

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 2n 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 2n 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 2n balls roll and then outputs the number of balls in the individual tubes by means of the function `print_counters()`.

Filename: GaltonBoard.C
LEDA users as of version 5.0: Note that header files are now partitioned into modules (subfolders)!
```#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:

Filename:
LEDA users as of version 5.0: Note that header files are now partitioned into modules (subfolders)!
```// And later optimized by The Rolling Stones

int let_it_rock(int n) {

for(int i = 1; i <= n; i++) {