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 which 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 which force a way to below 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).

Figure 2.19. A Galton board

A Galton board

A Galton board with n=4 (5 tubes).

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 which was returned by the random source. It returns the number of the tube into which the ball has fallen. 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
#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:
// 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;
}

Further information

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

Exercises

Exercise 17.

Write a program to throw two dice a million times, sum up in every throw the two numbers thrown, and count which sum was thrown how often.

Remember the result well if you are an enthusiastic Monopoly™ player. If your fellow player stands on “Free Parking”, then where should you build your hotel, on Atlantic Avenue or on Ventnor Avenue?




Imprint-Dataprotection