Wilfried Rohm, HTBL Saalfelden

Mathematische Inhalte:

Anwendung:

Kurzzusammenfassung:

Lehrplanbezug:

Mediales Umfeld:

Anmerkungen:

1. Ein verblüffendes Experiment - der RUN-Test

Probieren Sie es selbst einmal: Denken Sie sich eine "möglichst zufällige" Folge von 50 Zufallszahlen aus, die den Münzwurf simulieren soll (Wappen 0, Zahl 1). Anschließend führen Sie das Experiment tatsächlich durch. Sie erhalten also 2 Serien von je 50 0/1-Folgen, die beispielsweise so aussehen könnten:

1101010100101100111010111001001000101011010011101

0011100010111111010010000101011100000101011001110

Nach kurzer Zeit kann man (mit einer Erfolgswahrscheinlichkeit, die erfahrungsgemäß bei 70-80% liegt) "erraten", welche der beiden Folgen die gedachte und welche die tatsächliche Zufallszahlenfolge ist.

Dieses "Experiment" führe ich seit Jahren im Unterricht durch, um zu demonstrieren, daß selbst sogenannte "Zufallszahlen" gewissen Gesetzmäßigkeiten gehorchen, nämlich den Gesetzen der Statistik. Es ist dies meist das erste Mal, daß die Schüler mit der Statistik in engeren Kontakt geraten, und dies auf empirische Weise. Gleichzeitig wird gezeigt, daß das menschliche Gehirn - aus welchen Gründen auch immer - einen Zufallsprozeß nur höchst unvollkommen nachahmen kann.

Die Auswertung ist zunächst nicht streng mathematisch, für die Schüler dafür aber leichter nachvoll-ziehbar und - was mir wesentlich erscheint - verblüffend:

Natürlich gibt es Schüler, die einen "hereinlegen" wollen und daher möglichst gleich viele "0"-er und "1"-er in der gedachten Folge produzieren. In Wirklichkeit werden jedoch die Anzahl der in der Folge vorkommenden "Blöcke" (engl. Runs) gleicher Ziffern gezählt. Im obigen Beispiel kommen wir zu folgenden Ergebnis:

Auf Grund dieses Ergebnisses würde ich keine Sekunde zögern und behaupten, die erste Folge ist die gedanklich produzierte Folge, während die zweite die "echte" Zufallszahlenfolge repräsentiert.

Das obige Beispiel ist nun typisch für das "übliche" Schülerverhalten: Wenn man sich besonders anstrengt, den Zufall nachzubilden, produziert man meist mehr "Wechsel" zwischen 0 und 1 als es den Regeln der Statistik entspricht. Man kann dies zum Beispiel der Klasse demonstrieren, indem der Mittelwert der Runs der gedachten und tatsächlichen Zufallszahlenfolgen errechnet wird. Ohne entsprechende Vorkenntnisse der Schüler wird jener der gedachten Folgen meist um einiges größer sein als jener der "tatsächlichen" Folgen. (Alles andere wäre typisches "Lehrerpech" gemäß dem berühmten "Vorführeffekt").

Bei der "Auswertung" gehe ich folgendermaßen vor:

Die Begründung für diese Vorgangsweise liefert das Programm von der Diskette (Programmteil RUNTEST) : Die Simulation (Menüpunkte Mehrfachsimulation und/oder Gesetz der großen Zahlen) zeigt, daß die Anzahl der Runs bei einer 0-1-Zufallsfolge mit n=50 gegen 25,5 strebt. Ein Ergebnis, das näher dem Erwartungswert 25,5 liegt, ist also "wahrscheinlicher" als ein anderes.

(® Abb.2 bis Abb.5 im ANHANG)

Verteilung der Anzahl der Runs und Berechnung des Erwartungswert E(Rn)

Die Anzahl der Runs bei n Versuchen mit Zufallszahlen aus dem Bereich {0,1} folgt einer Binomialverteilung. Dies könnte auf einer höheren Stufe (3.Jahrgang) wie folgt nachgewiesen werden.(nach [5]) :

 Erfahrungen mit dem RUN-Test:

2. Algorithmen zur Erzeugung von Pseudozufallszahlen

In der Anfangszeit der Computertechnik versuchte man mit rein physikalischen Prozessen (zB. radio-aktiver Zerfall), "echte" Zufallszahlen zu erzeugen. Doch schon bald setzten sich Verfahren durch, nach denen der Computer - ausgehend von einer Startzahl - rein rechnerisch Zahlen erzeugt, die dem Zufall "im Prinzip" (d.h. gemäß den statistischen Gesetzen) entsprechen sollten. Da diese Zahlen natürlich nicht wirklich zufällig sind (wenn man die 1.Zahl kennt, kann man alle folgenden voraussagen), werden diese so erzeugten Zahlen Pseudozufallszahlen genannt.

Quadratmittenmethode

Diese Methode wird heute nicht mehr verwendet, ist aber aus historischen und didaktischen Gründen interessant. Sie stammt von J.v.NEUMANN aus dem Jahr 1946:

Man startet mit einer beliebigen n-stelligen Zahl, bildet das Quadrat, wählt als nächstes Folgenglied die durch die mittleren n Ziffern gebildete Zahl usw.

Beispiel :
 

Daß unter Umständen nur sehr kurze "Zufallszahlenfolgen" erzeugt werden (in der Fachsprache: die Periode ist zu kurz), zeigt das folgende Beispiel - das ist auch der Grund, weshalb diese Technik heute nicht mehr verwendet wird:

Lineare Kongruenzmethode

Diese Methode wird man in der Literatur am häufigsten antreffen, die Idee stammt von D.H. LEHMER, 1948. Man wähle die Parameter a,c und den Modul p (groß!) und gehe nach folgender Vorschrift vor :

x1 ... Startwert (vorgeben oder zb. aus momentaner Zeit errechnen)

Über  erhält man sodann Pseudozufallszahlen, die in [0,1] gleichverteilt sein sollten.

Die Frage ist nun, welche Werte von a,c,und p "gute" Zufallszahlen ergeben. Wählt man ohne Überlegung irgendwelche Zahlen, so erhält man fast immer einen ungeeigneten Zufallszahlengenerator. In der (mir vorliegenden) Literatur findet man dazu unterschiedliche Angaben; dazu einige Beispiele:

"In der Praxis sollte p möglichst groß, a zwischen  und p und c ungerade gewählt werden." ([1])

In [6] werden einige Regeln nach D.E.Knuth wiedergegeben:

In anderen Publikationen wird z.T. auf die Bedeutung von Primzahlen zur Erzeugung von guten Zufallszahlen hingewiesen.

Auch bei der Linearen Kongruenzmethode können so wie bei der Quadratmittenmethode bei un-günstiger Wahl der Paramter a,c und p "sinnlose" Zahlenfolgen entstehen. Zum Beispiel führt die Wahl von a=19,c=1 und p=381 mit der Startzahl 0 zur Folge 0,1,20,0,1,20,..., was ebenfalls eine nicht sehr zufällige Folge darstellt.

Im Programmteil POKERTEST besteht die Möglichkeit, neben dem eingebauten Zufallszahlen-generator einen selbstdefinierten zu wählen. Dieser arbeitet nach der Linearen Kongruenzmethode mit folgenden Werten:

a = 897 ; c = 2111 ; p = 123456 (Die Zahlen sind [2] entnommen)

Interessant ist, daß dieser Zufallszahlengenerator "auf den ersten Blick" ganz brauchbare Zufallszahlen liefert, der im nächsten Abschnitt besprochene Pokertest zeigt aber schließlich, daß diese Folge nur "schlecht" den Zufall simuliert.

Es gibt keine ganz zuverlässige Methode zur Herstellung von Zufallsziffern. Daher müssen die Ziffern nach der Herstellung geprüft werden. Es genügt nicht, daß die Häufigkeiten der einzelnen Ziffern stimmen. Es müssen auch die Häufigkeiten aller Ziffernblöcke stimmen. Eine scharfe - und in der Praxis auch angewendete - Prüfung ist der Poker-Test.

3. Ein scharfer Test für Zufallszahlen - der POKERTEST

Die Idee dieses Tests ist der Vergleich der Häufigkeiten der verschiedenen Arten von 5er-Blöcken von Pseudozufallszahlen mit den theoretischen Wahrscheinlichkeiten. Die dabei betrachteten Möglichkeiten von 5er-Blöcken entsprechen im Prinzip möglichen Ausgängen beim Pokern. Die folgende Tabelle bietet eine entsprechende Übersicht :
 

Die oben angeführten Wahrscheinlichkeiten lassen sich nach der Laplace-Regel zur Bestimmung von Wahrscheinlichkeiten () und der Kombinatorik errechnen.

Der Programmteil "Pokertest" ermöglicht eine tabellarische und graphische Übersicht, indem die durch Simulation ermittelten Werte mit den theoretischen Wahrscheinlichkeiten vergleichen werden. Daraus ergeben sich auf anschauliche Weise folgende Feststellungen:

Auf einer höheren Stufe (möglich im 3. bzw. 4.Jahrgang) kann man mit Hilfe von statistischen Tests auch rechnerisch überprüfen, ob ein bestimmter Zufallszahlengenerator brauchbare Ergebnisse liefert oder nicht. Dazu bietet sich der Chiquadrat-Test an, der auf sehr anschauliche Weise das Prinzip eines statistischen Tests aufzeigt:

Der Chiquadrat-Test

Dieser Test überprüft, ob die Summe der (relativen) Abweichungen zwischen den beobachteten Werten (Bi) und den erwarteten Werten (Ei - diese ergeben sich aus den theoretischen Wahrscheinlichkeiten gemäß obiger Tabelle) im Rahmen des Zufalls liegt oder ungewöhnlich groß ist. Gemäß Testtheorie wird das folgendermaßen formuliert:

Nullhypthese H0 : Die Abweichungen sind nur zufällig.

Die Irrtumswahrscheinlichkeit (d.i. die irrtümliche Ablehnung der Nullhypothese H0 = Fehler 1.Art) beträgt a = 1-Pa. (je nach gewähltem Niveau also 5%, 1% oder 0,1%)

Hinweise zum Programmablauf

Beim Menüpunkt POKERTEST/CHI-QUADRAT-TEST kann durch wiederholtes Drücken der Taste "V" (Versuch) der Test ständig mit neuen Zahlen wiederholt werden.

· Durch wiederholte Simulation kann der Begriff der Aussagewahrscheinlichkeit Pa bzw. der Irrtumswahrscheinlichkeit a =1-Pa veranschaulicht werden : Es wird der Wert  in 5% der Fälle auch dann durch die Prüfgröße überschritten, wenn die Pseudo-Zufallszahlen in Ordnung sind (wie dies bei Verwendung des internen Zufallgenerators der Fall ist).

Mit anderen Worten: Jedes 20.Mal (im Schnitt gesehen) kommt es zu einer Warnung, jedes 100.Mal zu einer Ablehnung von H0 mit a =1%. Dies kann (natürlich im Rahmen der statistischen Schwankungen) recht gut beobachtet werden.

· Der Freiheitsgrad liefert einen Anhaltspunkt, welcher c 2-Wert unter H0 zu erwarten ist und wird daher mit ausgegeben.

· Verwendet man den "selbstdefinierten" (schlechten,2.) Zufallsgenerator, kann man durch wiederholtes Durchführen des Testes feststellen, wie die Schärfe des Tests mit größer werdendem N deutlich zunimmt. (® Text zu Abb.13 , ANHANG-9)

· In Abhängigkeit vom Ergebnis werden unterschiedliche Folgerungen ausgegeben:
 

	H0 wird angenommen - d.h. "es gibt keinen ersichtlichen Grund, an der Qualität des Zufallgenerators zu zweifeln"
	Warnung: "es besteht ein Verdacht, daß die Zufallszahlen schlecht sind"
	H0 wird abgelehnt, d.h. die Zufallszahlen gelten als "unbrauchbar" mit Irrtumswahrscheinlichkeit a £ 1%.
	H0 wird abgelehnt, d.h. die Zufallszahlen gelten als "unbrauchbar" mit Irrtumswahrscheinlichkeit a £ 0,1%.

 

Erfahrungen mit dem Pokertest:

Ich habe den Pokertest erstmals bei einem Vortrag von L.Rade in Klagenfurt (1980) kennengelernt (siehe [4]) und seither im Mathematik- und/oder EDV-Unterricht mehrere "Generationen" von PC´s (bzw. Programmiersprachen) mit ihren eingebauten Zufallsgeneratoren danach getestet, wie "gut" die erzeugten Zufallsfolgen sind. Einige davon lieferten ganz "katastrophale" Ergebnisse, d.h. die erzeugten Zufallszahlen waren sehr schlecht. Dies galt beispielsweise für den ("seligen") TI 99/4A (einen der ersten Homecomputer), aber auch für die ältere Version des SHARP Pocket-Computer (PC-1401). Generell ist zu beobachten, daß die Zufallsgeneratoren "immer besser" werden, leider geht aber aus den Handbüchern in keinem mir bekannten Fall die Formel für den Pseudo-Zufallszahlengenerator hervor (bestenfalls ein Hinweis, daß die Zufallszahlen nach der "Linearen Kongruenzmethode" erzeugt werden).

Da die heute gebräuchlichen Geräte bzw. Programmiersprachen offenbar weitgehend "gute" Zufallszahlengeneratoren implementiert haben, wurde zum Vergleich im Programmteil POKERTEST die Möglichkeit eingebaut, einen vergleichsweise "schlechten" Zufallszahlengenerator auszuwählen. Führt man mit diesem den Pokertest mit unterschiedlichem N (zB. N=100, 500, 1000) durch, erkennt man auch sehr gut, daß der Pokertest mit zunehmendem N deutlich schärfer wird (dies ist im übrigen ein allgemeines Ergebnis der Testtheorie).

5. Literatur

[1] A.Engel: Wahrscheinlichkeitsrechnung und Statistik, Band 1, Ernst Klett Verlag,1973.
[2] Duden "Informatik": Bibliographisches Institut & F.A.Brockhaus AG, 1989.
[3] H.Müller (Hrsg.): Lexikon der Stochastik, Akademie-Verlag Berlin,1980.
[4] W.Dörfler und R.Fischer (Hrsg.) : Stochastik im Schulunterricht (Beiträge zum 3. interna-tionalen Symposium für Didaktik der Mathematik) , Schriftenreihe "Didaktik der Mathematik" der Universität für Bildungswissenschaften in Klagenfurt, Band 3, Hölder-Pichler-Tempsky, 1981.
[5] F.Österreicher: Vorlesungsunterlagen "Stochastische Modellbildung", Universität Salzburg, 1993.
[6] R.SEDGEWICK: Algorithmen in C++, Addison-Wesley, 1992.

ANHANG

Hinweise zum Programmablauf

Zum Herunterladen werden 2 Versionen angeboten:

RO-STATC.EXE : Variante mit Verwendung von Farben als unterstützendes, optisches Hilfsmittel.

RO-STATM.EXE: Variante, die auf die Benützung der BMUK-Laptops und Overheaddisplays im Klassenraum zugeschnitten ist und daher weitgehend auf Farben verzichtet.

Auf der ersten Menüebene besteht die Wahl zwischen den beiden (unabhängigen) Programmteilen

Die folgenden Untermenüs bieten als ersten Menüpunkt jeweils eine kurze Erklärung des betreffenden Programmteiles an.

Das Programm ist durchgehend so aufgebaut, daß auf der jeweiligen Menüebene die einzelnen Menüpunkte über Cursortasten oder mittels Anfangsbuchstaben aufgerufen werden können. Nach der Abarbeitung eines Menüpunktes (Simulation) bestehen stets zwei Möglichkeiten, die links unten eingeblendet werden :

Versuch - Buchstabe "V" drücken ... erneute Durchführung einer Simulation

Abbildungen aus dem Programmablauf (Kopiervorlagen) auf den folgenden Seiten

Es folgen auf den nächsten Seiten einige ausgewählte Bildschirmkopien aus dem Programmablauf. Diese sollen zeigen, welche Möglichkeiten das Programm bietet und auf der anderen Seite zum eigenen Experimentieren anregen.

Abb.1 : RUNTEST / EINZELNE VERSUCHE : Typischer Bildschirmausschnitt, der zeigt, daß (gar nicht so selten) sehr lange RUNS vorkommen

Abb. 2 : RUNTEST / GESETZ DER GROSSEN ZAHLEN : Es wird gezeigt, daß für große n die mittlere Anzahl der RUNS von je 50 {0,1}-Zufallsfolgen gegen 25,5 strebt.


Abb.3 u. 4: RUNTEST / AUSWERTUNG VON MEHREREN VERSUCHEN: Je niedriger n ist, desto "ausgefranster" ist die empirische Verteilung der Runs von je 50 {0,1}-Zufallszahlen .

 
Abb..5 : RUNTEST / AUSWERTUNG VON MEHREREN VERSUCHEN: Für n=10000 erhält man für die Anzahl der Runs eine empirische Verteilung ähnlich der Normalverteilung; die die tatsächliche Verteilung bereits sehr gut annähert - diese ist eine Binomialverteilung, wie im Abschnitt 1 (Seite 3 dieses Artikels) hergeleitet wurde.
Ferner fällt (wie schon in Abbildung 3 bzw. 4) auf, daß manchmal - und zwar häufiger, als man gemeinhin annimmt - sehr lange RUNS auftreten. Deswegen werden jeweils die Maximallängen mit ausgegeben.
Der Bereich [22-29] entspricht [m ± s ] und wird mit ausgegeben, um das Denken in Bereichen (Zufallsstreubereiche,...) entsprechend einzuführen. Mit Hilfe der Binomialverteilung (siehe Seite 3 dieses Artikels) kann die Wahrscheinlichkeit, daß die Anzahl der Runs im Bereich [22-29] liegt, auch berechnet werden; man erhält:

G(x) ist dabei die Verteilungsfunktion der Binomialverteilung mit den Parametern (n-1)=49 und p=0.5.

Abb. 6 : POKERTEST / TABELLE
Durchführung einer Simulation mit N=1000 Würfen von je 5 "zehnseitigen Würfeln" unter Ver-wendung des eingebauten (internen) Zufallgenerators.
Die "theoretischen" bzw. zu erwartendenen Werte errechnen sich aus den jeweiligen Wahrschein-lichkeiten (siehe Tabelle auf Seite 6 dieses Beitrags) mal der Versuchszahl N.

Abb. 7 : POKERTEST/DIAGRAMM bzw. CHI-QUADRAT-TEST
Die Werte aus obiger Tabelle wurden im Häufigkeitsdiagramm dargestellt. Es stellt sich die Frage, ob die beobachteten Abweichungen zwischen den Werten der Simulation und den zu erwartenden (theoretisch berechneten) Werten nur "zufällig" sind.
Diese Frage beantwortet rechnerisch der Chi-Quadrat-Test: Da die Prüfgröße kleiner als der "Tabellenwert" (auf allen drei Niveaus) ist, gibt es "keinen ersichtlichen Grund", an der Zufälligkeit der beobachteten Abweichungen zu zweifeln.
Übliche Sprechweisen: H0 ("die Abwechungen sind zufällig") wird angenommen.
H0 kann nicht abgelehnt werden.
Die beobachteten Abweichungen sind nicht signifikant.

Abb. 8 : POKERTEST / DIAGRAMM bzw. CHIQUADRAT-TEST
Gegenüberstellung eines Ergebnisses mit N=1000 unter Verwendung des "selbstdefinierten" (schlechten) Zufallgenerators. Ergebnis des Chiquadrattestes : H0 ("die Abwechungen sind zufällig") wird abgelehnt, die Abweichungen sind als signifikant zu bezeichnen.

Abb. 9/10: POKERTEST / DIAGRAMM : Starke Schwankungen bei mehreren Versuchen mit kleinem N

Abb.11/12: POKERTEST/DIAGRAMM : Die Schwankungsbreite ist bei größerem N wesentlich geringer.

Abb.13 : POKERTEST / DIAGRAMM