Tests von Zufallszahlengeneratoren
Konferenz Wiki: saswiki.org/wiki/KSFE_2008
Zusammenfassung
Bernd Paul Jäger, Institut für Biometrie und Medizinische Informatik, Universität Greifswald
Torsten Philipp, Fachhochschule Stralsund, Fachbereich Elektrotechnik und Informatik
Paul Eberhard Rudolph, Forschungsinstitut für die Biologie landwirtschaftlicher Nutztiere (FBN), Dummerstorf
Karl-Ernst Biebler, Institut für Biometrie und Medizinische Informatik, Universität Greifswald
Zahlreiche statistische Tests, darunter auch die Familie der Run-Tests (Abb.1.1-1.3), wurden ersonnen, um die ordnungsgemäße Funktion von Zufallszahlengeneratoren zu überprüfen, die (pseudo)gleichverteilte Zufallszahlen erzeugen. Ein einzelner Test prüft aber nur bestimmte Konstellationen ab, etwa die, dass eine Sequenz von Zufallszahlen nicht zu lange monoton wächst, dass die empirische Verteilung der Gleichverteilung entspricht oder dass Permutationen genau so häufig gefunden werden wie man erwartet. Deshalb ist es heute Standard, eine ganze Batterie von Tests [2] nacheinander anzuwenden, um Besonderheiten in vielfältiger Hinsicht zu erkennen.
Der so genannte Run-Test nach Knuth [1] untersucht Längen von streng monotonen Sequenzen innerhalb einer Folge von gleichverteilten Zufallszahlen aus dem Intervall [0, 1). Nachfolgend wird o.B.d.A. nur der Fall streng monoton fallender Sequenzen behandelt. Die Verteilungsfunktion der zufälligen Längen L der Sequenzen ist bekannt:
P(L = k) = k / (k + 1)!
L kann einerseits sämtliche natürliche Zahlen k als Werte annehmen, andererseits werden die Wahrscheinlichkeiten für größer werdende k rasch klein. Es gelten für den Erwartungswert E(L) = e – 1 ≈ 1.71828 und für die Varianz V(L) = 3e – e² ≈ 0.76579. Man wird folglich keine sehr langen Sequenzen beobachten.
Der Run-Test wird fälschlicherweise bereits in [1] und auch andernorts auf Zufallszahlengeneratoren für gleichverteilte ganze Zahlen angewandt. Für den Zufallszahlengenerator in SAS führt eine solche unkorrekte Bewertung zu einem Negativurteil.
In dieser Arbeit werden für gleichverteilte ganze Zahlen die exakte Verteilung der Längen L streng monoton wachsender Sequenzen angegeben, in einem SAS Makro berechnet so- wie ihre Grenzverteilung für n → ∞ ermittelt. Zur Anwendung wird diese asymptotische Verteilung nicht empfohlen. Der Zufallszahlengenerator in SAS besteht den unter Verwendung der exakten Verteilung von L durchgeführten Run-Test und ist somit nicht zu beanstanden.
Literatur:
1. Knuth, D.E. (1981): The art of computer programming, Vol. 2 Seminumerical Algorithms, 2. ed. Addison-Wesley, Reading, Mass.
2. Marsaglia, George: Diehard Battery of Tests of Randomness, http://stat.fsu.edu/pub/diehard/
3. SAS Institute Inc. (1999): SAS/STAT User’s Guide, Version 8, Cary, NC:SAS Institute Inc
4. SAS Institute Inc. (1999): SAS Macro Language: Reference, Version 8, Cary, NC: SAS Institute Inc.