Robert Sedgewick: Algorithmen

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


35. Zufallszahlen



Test der Zufälligkeit

Oft kann man ermitteln, daß eine Folge nicht zufällig ist; der Nachweis, das eine Folge zufällig ist, ist dagegen eine wahrhaft schwierige Aufgabe. Wie bereits erwähnt wurde, kann keine von einem Computer erzeugte Folge wirklich zufällig sein, doch wir können eine Folge erhalten, die viele der Eigenschaften von Zufallszahlen aufweist. Leider ist es oft unmöglich, genau anzugeben, welche Eigenschaften von Zufallszahlen für eine spezielle Anwendung wichtig sind. Weiterhin ist es stets angebracht, für einen Zufallszahlengenerator eine Art Test auszuführen, um sicher zu sein, daß keine entarteten Situationen auftreten. Zufallszahlengeneratoren können sehr, sehr gut sein, doch wenn sie schlecht sind, hat das schreckliche Folgen.

Es wurden viele Tests entwickelt, um zu bestimmen, ob eine Folge verschiedene Eigenschaften mit einer echt zufälligen Folge gemeinsam hat. Die meisten dieser Tests beruhen in wesentlichem Umfang auf mathematischen Grundlagen, und es würde weit über den Rahmen dieses Buches hinausgehen, sie im einzelnen zu untersuchen. Ein statistischer Test jedoch, der Chi2 (Chi-Quadrat-Test), ist von grundlegender Natur, läßt sich sehr leicht implementieren und ist für verschiedene Anwendungen von Nutzen, so daß wir ihn eingehender betrachten wollen.

Der Grundgedanke des Chi2 -Tests besteht in der Prüfung, ob die erzeugten Zahlen sinnvoll verteilt sind oder nicht. Falls wir N positive Zahlen erzeugen, die kleiner als r sind, so können wir erwarten, daß wir für jeden Wert ungefähr N/r Zahlen erhalten. Jedoch, und das ist die entscheidende Tatsache, sollten die Häufigkeiten nicht genau die gleichen sein, denn das wäre wiederum nicht zufällig! Es erweist sich, daß die Berechnung, mit der bestimmt werden kann, ob eine Folge von Zahlen so gut verteilt ist wie eine zufällige Folge oder nicht, sehr einfach ist:

    function chisquare(N,r,s: integer): real;
      var i,t: integer;
          f: array[0..rmax] of integer;
      begin
      randinit(s);
      for i:=0 to rmax do f[i]:=0;
      for i:=1 to N do
        begin
        t:=randomint(r);
        f[t]:=f[t]+1;
        end;
      t:=0; for i:=0 to r-1 do t:=t+f[i]*f[i];
      chisquare:=((r*t/N) - N);
      end;

Wir berechnen einfach die Summe der Quadrate der Häufigkeiten, dividiert durch die zu erwartende Häufigkeit, und subtrahieren davon dann die Größe der Folge. Diese Zahl, die » Chi2-Statistik«, kann mathematisch in der Form

Formel

ausgedrückt werden. Falls die Chi2-Statistik nahe bei r liegt, sind die Zahlen zufällig; falls sie zu weit weg liegt, sind sie es nicht. Die Begriffe »nahe« und »weit weg« können exakter definiert werden; es existieren Tabellen, aus denen genau hervorgeht, wie die Statistik zu Eigenschaften zufälliger Folgen in Beziehung zu setzen ist. Für den einfachen Test, den wir ausführen, sollte die Statistik innerhalb eines Abstands von 2 sqrtr von r liegen. Dies gilt, falls N größer als etwa 10r ist; um sicherzugehen, sollte der Test mehrmals ausgeführt werden, da er ungefähr jedes zehnte Mal zu einem falschen Ergebnis führt.

Abbildung 35.2
Abbildung 35.2 Häufigkeit für drei Generatoren: rechte Bits, linke Bits, ungeeigneter Multiplikator.

Dieser Test läßt sich so leicht implementieren, daß er eigentlich in jeden Zufallszahlengenerator eingefügt werden sollte, einfach um abzusichern, daß nichts Unerwartetes ernsthafte Probleme verursachen kann. Alle »guten« Generatoren, die wir betrachtet haben, genügen diesem Test, die »schlechten« hingegen nicht. Wenn wir die obigen Generatoren verwenden, um tausend Zahlen zu erzeugen, die kleiner als 100 sind, erhalten wir eine Chi2-Statistik von 100,8 für die Methode der linearen Kongruenz und von 105,4 für die Methode der additiven Kongruenz, was beides sicher innerhalb des Abstands 20 von 100 liegt. Für den »schlechten« Generator dagegen, der die rechten Bits des Generators der linearen Kongruenz verwendet, hat die Statistik den Wert 0 (warum?), und für eine Methode der linearen Kongruenz mit einem ungeeigneten Multiplikator (101011) hat die Statistik den Wert 77,8, was deutlich außerhalb des zulässigen Bereichs liegt. Abbildung 35.2 zeigt die Häufigkeiten des Auftretens sämtlicher Werte, die kleiner als 100 sind, für die drei soeben erwähnten Varianten der Methode der linearen Kongruenz. Während die Benutzung der rechten Bits (oberstes Diagramm) offensichtlich ungünstig ist, ist es nicht leicht, den Unterschied zwischen dem mittleren und dem unteren Häufigkeitsdiagramm zu bemerken; die Chi2-Statistik gibt die Möglichkeit, den ungeeigneten Multiplikator zu identifizieren.


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