Der gezinkte Würfel aus dem vorigen Abschnitt mag uns vielleicht Glück im Spiel gebracht haben, Glück in der Liebe kann er uns niemals bescheren. Falls wir in dieser misslichen Lage sind, sollten wir keinesfalls versuchen, unseren Kummer durch alkoholhaltige Getränke herunterzuspülen, denn sonst kann unser Heimweg aussehen wie in Abbildung 2.20.

Abbildung 2.20. Ein zufälliger Spaziergang (Random Walk)

Was wir hier sehen, ist der mehr oder weniger zufällige Spaziergang (engl. random walk) eines Betrunkenen. Bei jedem Schritt vorwärts geht der Betrunkene zufällig einen Schritt nach links oder rechts und torkelt so seiner rettenden Ruhestätte entgegen. Nun wollen wir annehmen, dass sein Gedächtnis und seine Entscheidungsfähigkeit nicht völlig außer Gefecht gesetzt sind, sondern dass er noch zu Gedanken der folgenden Form fähig ist: „Ich glaube, ich bin gerade nach links gegangen, ich sollte jetzt mal wieder nach rechts gehen, oder doch nicht? Ach, ist doch alles egal...“ Mit anderen Worten: Wenn er gerade nach links gegangen ist, sollte die Wahrscheinlichkeit, dass er im nächsten Schritt wieder nach links geht, kleiner werden; bei einem Schritt nach rechts entsprechend umgekehrt.

Wenn wir einen solchen zufälligen Spaziergang simulieren wollen, benötigen wir offenbar eine Zufallsvariable für die Torkelrichtungen „Links“ und „Rechts“, deren Wahrscheinlichkeiten sich dynamisch anpassen lassen. Genau dies leistet die LEDA-Klasse dynamic_random_variate.

In der Simulation stellen wir uns vor, dass wir auf dem Zahlenstrahl stehen. Wir starten bei 0. Im ersten Schritt laufen wir mit gleicher Wahrscheinlichkeit nach links oder nach rechts. Jedesmal, wenn wir in eine Richtung gelaufen sind, verdoppeln wir das Gewicht der jeweils anderen Richtung. (Das bedeutet nicht, dass die entsprechende Wahrscheinlichkeit verdoppelt wird!) Insgesamt machen wir eine Million Schritte. (Ein tatsächlicher Nach-Hause-Weg ist hoffentlich nicht so lang.) Wir zählen in einem Array mit, wie oft wir bei welcher Zahl waren und geben am Schluss die Zählerstände aus.

#include <LEDA/random_variate.h>
#include <LEDA/array.h>
#include <iostream>

using leda::dynamic_random_variate;
using leda::array;

enum direction {LEFT, RIGHT};

array<int> weight(LEFT, RIGHT);

inline void double_weight(dynamic_random_variate&, direction);


int main() 
{
  weight[LEFT] = weight[RIGHT] = 1; 

  dynamic_random_variate DRV(weight);

  array<int> counter(-1,1);
  counter[0] = 1; // Start at position 0
  counter[-1] = counter[1] = 0;

  const int num_walks = 1000000;
  int cur_pos = 0;

  // Do random walk
  for(int i = 0; i < num_walks; i++) {
    int dir = DRV.generate();
    if(dir == LEFT) { // Walk to the left
      cur_pos--;
      if(cur_pos < counter.low())
        counter.resize(counter.low() * 2, counter.high());
      counter[cur_pos]++;
      double_weight(DRV, RIGHT);
    }
    else { // Walk to the right
      cur_pos++;
      if(cur_pos > counter.high())
        counter.resize(counter.low(), counter.high() * 2);
      counter[cur_pos]++;
      double_weight(DRV, LEFT);
    }
  }

  // Find boundaries of walk
  int lbound = counter.low();
  while(counter[lbound] == 0) lbound++;

  int ubound = counter.high();
  while(counter[ubound] == 0) ubound--;

  // Print statistics
  for(int i = lbound; i <= ubound; i++) {
    std::cout.width(2);
    std::cout << i << ": " << counter[i] << "\n";
  }

}


inline void double_weight(dynamic_random_variate& DRV, direction dir) {
  int otherdir = 1 - dir;
  if(weight[otherdir] > 1) {
    weight[otherdir] /= 2;
    DRV.set_weight(otherdir, weight[otherdir]);
  }
  else {
    weight[dir] *= 2;
    DRV.set_weight(dir, weight[dir]);
  }
}

Ein Beispiellauf erzeugt folgende Ausgabe:

-6: 2
-5: 147
-4: 2499
-3: 21527
-2: 95324
-1: 228021
 0: 304723
 1: 228780
 2: 94966
 3: 21386
 4: 2482
 5: 139
 6: 5

Das zeigt, dass wir immer schön um die 0 herum schwanken. Je weiter wir von der Mitte abgewichen sind, desto unwahrscheinlicher wird es, dass wir noch weiter abweichen.

Wie die die Klasse random_variate benötigt auch die Klasse dynamic_random_variate bei der Definition ein Array, in dem die Gewichte der zu erzeugenden Zufallswerte stehen:

dynamic_random_variate DRV(weight);

Im Unterschied zu ersterer können aber die einzelnen Gewichte zur Laufzeit durch einen Aufruf der Methode

DRV.set_weight(i, w);

abgeändert werden. Hierbei bezieht sich i auf den entsprechenden Index des Gewichts-Arrays und w ist das neue Gewicht des i-ten Zufallswertes.

Obiges Programm ist gleichzeitig ein Beispiel für eine sinnvolle Verwendung der Methode resize() von LEDA-Arrays und dafür, dass LEDA-Arrays auch negative Indizes haben dürfen. Die ursprünglichen Array-Grenzen sind -1 bzw. 1. Wenn wir über diese Grenzen hinauslaufen, verdoppeln wir die Array-Grenze in die entsprechende Richtung. Diese Verdoppelungsstrategie gibt uns genug „Luft“ bis zur nächsten Verdoppelung, d. h. amortisiert gesehen bedeutet sie einen konstanten Zeitaufwand.

Bei der Verdoppelung der Gewichte in der Funktion double_weight() bedienen wir uns eines Tricks: Wir können nicht einfach jedesmal das entsprechende Gewicht verdoppeln, weil wir sonst sehr bald (je nach Maschinenarchitektur nach 31 oder 63 Verdoppelungen) über den Definitionsbereich des Typs int hinauskämen. Statt dessen machen wir die Beobachtung, dass bei nur zwei möglichen Zufallswerten das relative Gewicht eines Wertes auch dadurch verdoppelt werden kann, dass das Gewicht des anderen halbiert wird. Ist also das jeweils andere Gewicht größer als 1, so halbieren wir dieses, ansonsten verdoppeln wir. Hierbei ist nochmals anzumerken, dass die Gewichte der Klassen random_variate und dynamic_random_variate immer ganzzahlig sein müssen!