Die Klasse random_source besitzt auch einen Bit-Modus. In diesem erzeugt sie Bitstrings einer vorher festgelegten Länge; er eignet sich insbesondere für Algorithmen, die an bestimmten Stellen eine Münze werfen und je nach dem Ergebnis „Kopf“ oder „Zahl“ verzweigen.

Als Beispielprogramm dazu simulieren wir ein Galton-Brett, benannt nach dem Statistiker Francis Galton (1822-1911). Abbildung 2.19 zeigt ein solches Brett. Es besteht aus einer dreieckig geschichteten Anordnung von Stiften auf einer schiefen Ebene. Von der Position über dem obersten Stift lässt man kleine Bälle loslaufen, die sich einen Weg nach unten bahnen, wo sie in einer Reihe von Röhren gesammelt werden. An jedem Stift (also auf jeder Schicht) können die Bälle entweder nach rechts oder links verzweigen (jeweils mit Wahrscheinlichkeit 1/2).

Abbildung 2.19. Ein Galton-Brett

Ein Galton-Brett mit n=4 (5 Röhren).

Dieses Experiment dient zur experimentellen Bestimmung der Binomialverteilung. Bei insgesamt n+1 Röhren gibt es immer n Schichten darüber; ein Lauf der Kugel entspricht n Münzwürfen. Am unwahrscheinlichsten ist es, dass die Kugel in der Röhre ganz links bzw. ganz rechts landet; das entspricht einer Folge von n Mal „Kopf“ bzw. n Mal „Zahl“ hintereinander. Die Wahrscheinlichkeit dafür ist 2^-n, denn nur einer von insgesamt 2ⁿ möglichen Wegen ist der richtige (derjenige, bei dem die Kugel immer nach links bzw. immer nach rechts verzweigt). Am wahrscheinlichsten ist die Position in der Mitte (bzw. die beiden Positionen in der Mitte, falls n ungerade ist). Hier muss die Kugel genauso oft nach links wie nach rechts verzweigen. Die Anzahl der Kombinationen dafür ist (n,n/2), wobei (n,k) den im Abschnitt “Dynamisches Vergrößern von Arrays” eingeführten Binomialkoeffizienten bezeichnet. (Aus n Stellen, an denen die Kugel nach links verzweigen kann, sucht sie sich n/2 beliebig aus.) Allgemein gilt, dass die Kugel mit Wahrscheinlichkeit (n,k)2^-n in Röhre k landet. (Was wir nicht genau beweisen wollen.) Diese Zahl heißt Bernoulli-Wahrscheinlichkeit. Sie gibt die Wahrscheinlichkeit an, dass in einer Folge von n Münzwürfen genau k Mal „Kopf“ auftritt.

Wenn wir also insgesamt 2ⁿ Kugeln laufen lassen, dann sollte danach die Anzahl der Kugeln in den Röhren ungefähr den Binomialkoeffizienten aus dem Pascal'schen Dreieck entsprechen, das wir ebenfalls im Abschnitt “Dynamisches Vergrößern von Arrays” kennen gelernt haben.

Das folgende Programm benutzt eine Random Source im 1-Bit-Modus, um die Verzweigungen bzw. Münzwürfe zu simulieren. Bei n Schichten mit n+1 Röhren geht es von 2n+1 virtuellen Zwischenpositionen aus, die in Abbildung 2.19 unten durchnummeriert sind. Die Funktion let_it_roll() startet in der mittleren Zwischenposition und verzweigt dann n Mal nach links bzw. rechts, je nach dem Bit, das von der Random Source geliefert wurde. Sie liefert die Nummer der Röhre zurück, in die die Kugel gefallen ist. Die Nummerierung der Röhren beginnt dabei bei 0. Das Hauptprogramm lässt insgesamt 2ⁿ Kugeln laufen und gibt dann mit Hilfe der Funktion print_counters() die Anzahl der Kugeln in den einzelnen Röhren aus.

#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";
  }
}

Eine Ausgabe eines Laufes auf der Maschine des Autors war folgende:

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

Vergleichen wir das einmal mit der 9. Zeile der Ausgabe des Programms zur Berechnung des Pascal'schen Dreiecks, das wir im Abschnitt “Dynamisches Vergrößern von Arrays” implementiert haben!

Durch Definition einer Random Source

S(p);

mit nur einer Ganzzahl p als Argument wird diese in den Bit-Modus versetzt. Sie liefert dann bei jedem Aufruf des Operators >> eine ganze Zahl, deren letzte p Bits zufällig gesetzt sind; die höherwertigen Bits sind alle 0. p muss zwischen 1 und 31 liegen und wird als Präzision bezeichnet.

Mit der Methode

S.set_precision(p);

kann die Präzision nachträglich abgeändert werden. Darüber hinaus kann eine Zufallszahl mit einer bestimmten Präzision p auch direkt aus einer Random Source S durch den Aufruf

S(p);

erzeugt werden.

Obige Funktion let_it_roll() mit ihren virtuellen Zwischenpositionen ist natürlich unnötigerweise komplex. Da ihre Aufgabe lediglich darin besteht zu zählen, wie oft „Kopf“ in einer Folge von n Münzwürfen auftritt, tun wir doch einfach genau dies:

// 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;
}