Zufallszahlengenerator

Author: Hans Lohninger

In klassischen Statistiklehrbüchern werden Zufallszahlen erhoben, indem nummerierte Kugeln aus einer Schachtel mit einer bekannten Anzahl von Kugeln gezogen werden. Während dieser Vorgang mit kleinen Kugelmengen durchführbar ist, wird er mit zunehmender Kugelzahl immer unhandlicher. Außerdem taucht ein anderes Problem auf, das oft übersehen wird: Es ist zweifelhaft, ob das Ziehen der Kugeln aus einer großen Schachtel wirklich ein Zufallsprozess mit gleichen Chancen für alle Kugeln ist.

Aus diesen und anderen Gründen wurden Zufallszahlengeneratoren für Computer entwickelt. Tatsächlich bietet jede höhere Programmiersprache zumindest eine Art von Zufallszahlengenerator an. Die Erzeugung von Zufallszahlen ist trotzdem keine einfache Aufgabe für den Computer, da der Computer eine deterministische Maschine ohne eingebaute Zufälligkeiten ist (obwohl man manchmal daran zweifeln möchte). Daher ist es unmöglich, echte Zufallszahlen ohne zusätzliche Hardware zu erzeugen.

Es können jedoch Pseudozufallszahlen erzeugt werden, die sich nahezu wie Zufallszahlen verhalten, aber nach einer gewissen (meist sehr langen) Zeit wiederholt werden. Diese Pseudozufallszahlen werden mit linearen Kongruenzgeneratoren (engl. linear congruential generators, LCG) generiert. Das Prinzip eines LCG ist sehr einfach: Eine neue Zufallszahl wird auf der Basis der vorangegangenen Zufallszahl erzeugt, indem ein bestimmter Offset addiert wird. Überschreitet das Resultat eine bestimmte Grenze, wird der Wert auf den Anfang der Zahlenskala abgebildet. Der Vorgang kann durch folgende Gleichung dargestellt werden:

Der mod-Operator berechnet den Rest der Division von (a+bx_i-1)/c.

Von einem LCG berechnete Pseudozufallszahlen haben Vor- und Nachteile:

Rasche Berechnung: Die Berechnung kann mit wenigen Ganzzahloperationen durchgeführt werden. Das ist der Grund, warum LCGs in Computern nahezu universell eingesetzt werden.
Die "Zufallszahlen" können exakt wiederholt werden. Das kann von großem Vorteil sein, wenn man nach einem Fehler in einem Programm sucht, das sich auf Zufallszahlen verlässt.
Die niederwertigen Bits der Zufallszahlen müssen überhaupt nicht zufällig sein. Im Allgemeinen sollte man niemals Teile einer Pseudozufallszahl als weitere Zufallszahl benützen.
Einige Teilkombinationen treten möglicherweise niemals auf. Wenn die Konstanten a,b und c der oberen Formel nicht sorgfältig ausgewählt werden, decken die Zufallszahlen vielleicht nicht den ganzen Bereich der möglichen Zahlen ab.
Da die Abfolge der Pseudozufallszahlen festgelegt ist, besteht eine Korrelation zwischen aufeinander folgenden Zufallszahlen. Dieser Effekt kann sich als großes Problem erweisen, wenn man Zufallszahlen zur Erzeugung von Punkten im k-dimensionalen Raum einsetzt (wie bei der Monte-Carlo-Methode). Die Punkte füllen den Raum nicht aus, sondern reihen sich auf n-dimensionalen Hyperebenen. Die Zahl der Hyperebenen entsprechen ungefähr der k-ten Wurzel der Konstante c.

Wenn Sie sich für diese Aspekte interessieren, können Sie das folgende interaktive Beispiel starten.