Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


35. Zufallszahlen



Bei unserer nächsten Gruppe von Algorithmen handelt es sich um Methoden zur Verwendung eines Computers zur Erzeugung von Zufallszahlen. Obwohl wir im Verlaufe dieses Buches schon im Zusammenhang mit unterschiedlichen Fragen Zufallszahlen erwähnt haben, wollen wir nun versuchen, eine bessere Vorstellung davon zu erhalten, was dies eigentlich ist.

In der Umgangssprache wird oft der Begriff zufällig gebraucht, wenn in Wirklichkeit beliebig gemeint ist. Wenn man nach einer beliebigen Zahl fragt, meint man, daß es eigentlich nicht von Bedeutung ist, welche Zahl man erhält; nahezu jede Zahl ist geeignet. Im Gegensatz dazu ist Zufallszahl ein exakt definierter mathematischer Begriff: Jede Zahl sollte mit gleicher Wahrscheinlichkeit auftreten. Eine Zufallszahl wird jemanden befriedigen, der eine beliebige Zahl braucht, doch die Umkehrung gilt nicht.

Damit die Formulierung »jede Zahl sollte mit gleicher Wahrscheinlichkeit auftreten« sinnvoll ist, müssen wir die Zahlen, die verwendet werden sollen, auf einen bestimmten endlichen Bereich begrenzen. Man kann nicht eine zufällige ganze Zahl schlechthin betrachten, sondern nur eine zufällige ganze Zahl in einem bestimmten Bereich; man kann nicht eine zufällige reelle Zahl betrachten, sondern nur einen zufälligen Bruch mit vorgegebener Auflösung und in einem bestimmten Bereich.

Fast immer liegt der Fall vor, daß nicht nur eine Zufallszahl, sondern eine Folge von Zufallszahlen benötigt wird (andernfalls würde eine beliebige Zahl genügen). An dieser Stelle kommt die Mathematik ins Spiel: Es ist möglich, viele Eigenschaften von Folgen von Zufallszahlen zu beweisen. Zum Beispiel können wir in einer sehr langen Folge von Zufallszahlen aus einem kleinen Bereich erwarten, daß jeder Wert ungefähr gleich häufig auftritt. Zufällige Folgen modellieren viele natürliche Situationen, und über ihre Eigenschaften ist sehr viel bekannt. Der üblichen Ausdrucksweise folgend, wollen wir Zahlen aus zufälligen Folgen als Zufallszahlen bezeichnen.

Es gibt keine Möglichkeit, echte Zufallszahlen auf einem Computer (oder irgendeinem anderen deterministischen Gerät) zu erzeugen. Wenn das Programm einmal erstellt ist, können die Zahlen, die es erzeugen wird, abgeleitet werden; wie sollten sie also zufällig sein? Das Optimum sind Programme, die Folgen von Zahlen erzeugen, die viele der Eigenschaften von Zufallszahlen haben. Derartige Zahlen werden gewöhnlich Pseudo-Zufallszahlen genannt; sie sind nicht wirklich zufällig, doch sie können als Näherungen für Zufallszahlen von Nutzen sein, etwa so, wie Gleitkommazahlen als Näherungen für reelle Zahlen von Nutzen sind. (Manchmal ist es zweckmäßig, noch eine weitere Unterscheidung zu treffen: In gewissen Situationen sind einige Eigenschaften von Zufallszahlen von entscheidender Bedeutung, während andere unwesentlich sind. In derartigen Situationen kann man Quasi-Zufallszahlen erzeugen, die mit Sicherheit die interessierenden Eigenschaften besitzen, jedoch andere Eigenschaften von Zufallszahlen wahrscheinlich nicht aufweisen. Für manche Anwendungen läßt sich beweisen, daß Quasi-Zufallszahlen Pseudo-Zufallszahlen vorzuziehen sind.)

Es ist leicht einzusehen, daß das Approximieren der Eigenschaft »jede Zahl tritt mit gleicher Wahrscheinlichkeit auf« in einer langen Folge nicht ausreichend ist. Zum Beispiel tritt jede ganze Zahl aus dem Intervall [1,100] in der Folge (1, 2,..., 100) einmal auf, doch diese Folge ist sicher als Approximation einer zufälligen Folge nicht brauchbar. In Wirklichkeit werden in einer zufälligen Folge der Länge 100 von Zahlen aus dem Intervall [1,100] wahrscheinlich einige Zahlen mehr als einmal auftreten, andere überhaupt nicht. Wenn dies bei einer Folge von Pseudo-Zufallszahlen nicht der Fall ist, so stimmt mit dem Zufallszahlengenerator etwas nicht. Für Zufallszahlengeneratoren wurden viele komplizierte Tests entwickelt, die auf speziellen Beobachtungen wie dieser beruhen. Diese sollen überprüfen, ob eine lange Folge von Pseudo-Zufallszahlen eine bestimmte Eigenschaft besitzt, die Zufallszahlen haben würden. Die Zufallszahlengeneratoren, die wir untersuchen wollen, zeigen bei solchen Tests ein sehr gutes Verhalten. Im vorliegenden Kapitel betrachten wir einen der wichtigsten dieser Tests, den Chi2 -Test (Chi-Quadrat-Test).

Wir haben bisher ausschließlich über gleichverteilte Zufallszahlen gesprochen (und werden auch künftig nur über sie sprechen), bei denen jeder Wert gleich wahrscheinlich ist. Es kommt auch häufig vor, daß man es mit Zufallszahlen zu tun hat, die einer bestimmten anderen Verteilung gehorchen, bei der manche Werte wahrscheinlicher sind als andere. Pseudo-Zufallszahlen, die nicht gleichverteilt sind, erhält man gewöhnlich, indem man mit gleichverteilten Zufallszahlen gewisse Operationen ausführt. Bei den meisten Anwendungen in diesem Buch werden gleichverteilte Zufallszahlen benutzt. Wie wir sehen werden, ist es schwierig genug, sich davon zu überzeugen, daß die Zahlen, die wir erzeugen, »alle« Eigenschaften von Zufallszahlen haben; das Problem wird noch viel komplizierter, wenn es um andere Verteilungen geht.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]