Zufallszahlen (Kofler, 1.draft)

Zufallszahlen
Zufallszahlen werden auf vielen Gebieten der Naturwissenschaft und Technik bei stochastischen Simulationen
eingesetzt, um einerseits analytisch gewonnene Ergebnisse zu überprüfen und andererseits zu Aussagen über
das Verhalten von zufallsbeeinflussten Systemen auch dann zu gelangen, falls es nicht möglich ist, analytische
Ergebnisse zu berechnen. Bei diesen Simulationen werden stochastisch beeinflusste Eingabedaten durch einen
Zufallszahlengenerator nachgebildet. Hier wie in allen anderen Fällen kommt es darauf an, dass die
Simulation unbedingt zuverlässige Ergebnisse liefert. Die Qualität der getroffenen Aussagen hängt von der
Qualität der zugrundeliegenden Daten ab. Daher ist es notwendig, dass auch der verwendete Zufallsgenerator
wirklich zuverlässig ist.
Einsatzgebiete
•
•
•
•
•
•
•
•
•
Evelin Kofler
Generierung von Geheimnummern oder Transaktionsnummern
Verschlüsselung von Daten (z.B. für die Kommunikation im Internet)
Digitale Unterschriften
Direkte Verwendung für Monte-Carlo-Simulationen
Referenz für statistische Zufallszahlen-Tests
Numerische Lösung mathematischer Probleme
Steuerung/Test von Glücksspielautomaten
Generierung von Lottozahlen
usf.
Zufallszahlen – first draft
Seite 1
Bei der Erzeugung von Zufallszahlen unterscheidet man zwischen echten Zufallszahlen und PseudoZufallszahlen. Echte Zufallszahlen können z.B. durch Wurf mit einem (ungezinkten) Würfel (der einfachste
Zufallszahlengenerator für die Zahlen von 1 bis 6) oder durch Beobachtung physikalischer Vorgänge (z. B.
physikalischer Zerfall) gewonnen werden. Pseudo-Zufallszahlen werden durch spezielle deterministische
Algorithmen mit Hilfe des Computers erzeugt. Sie entstehen also nicht „zufällig“, wie die echten
Zufallszahlen, sondern sind streng determiniert.
Unter einem Zufallszahlengenerator versteht man nun ein Verfahren, welches eine Folge von Zahlen erzeugt,
die möglichst viele Eigenschaften einer Zufallszahlenfolge besitzt. Da die Folge durch ein Verfahren, also
einen deterministischen Algorithmus erzeugt wird, kann sie prinzipiell nicht zufällig angeordnet sein. Fast alle
Programmiersprachen verfügen über Sprachelemente zur Erzeugung von sogenannten Pseudo-Zufallszahlen.
Die Vorteile echter Zufallszahlen gegenüber von Zufallsgeneratoren erzeugter Pseudo-Zufallszahlen liegen auf
der Hand:
•
•
•
•
•
keine Periodizitäten
keine Vorhersagbarkeit der Zufallszahlen aufgrund vorangehender Sequenzen
keine irgendwie geartete Systematik (⇒ Daten können absolut sicher verschlüsselt werden)
Gewissheit, dass keine versteckten Korrelationen vorliegen
Gewissheit, dass die Schwankungen in der Gleichverteilung rein stochastisch sind (PseudoZufallszahlen weisen systematisch, d.h. unnatürliche Schwankungen in der Gleichverteilung auf)
Zufallszahlenfolgen kann man mit Würfeln, Losen oder Münzen erzeugen. Solchen physikalischen Verfahren
stehen algorithmische Verfahren gegenüber, die Zufallszahlen nach einer bestimmten Rechenvorschrift
Evelin Kofler
Zufallszahlen – first draft
Seite 2
berechnen. Die physikalischen Verfahren sind nur auf den ersten Blick besser. Sie haben Nachteile: Sie
bedürfen der Wartung und der Eichung, und man kann die erzeugten Zahlenfolgen nicht reproduzieren, was für
viele Experimente wünschenswert ist. Die algorithmischen Verfahren, welche heute praktisch benutzt werden,
haben diese Nachteile nicht. Sie liefern Zahlenfolgen mit guten statistischen Eigenschaften.
Alle praktisch bedeutenden Zufallszahlengeneratoren arbeiten rekursiv. Diese Generatoren erzeugen
•
•
•
zuerst eine gewisse Anfangsfolge,
danach einen nullten Zyklus: eine Folge, die
im ersten Zyklus exakt wiederholt wird usw.
Die Anzahl der Zahlen innerhalb eines Zyklus heißt Zykluslänge des Generators. Am Beginn der Arbeit muss
eine Zahl als Startpunkt gewählt werden. Diese erste Zahl einer Zufallszahlenfolge wird Anfangswert (engl.
seed) genannt.
Zufallsquellen in einem Modell müssen statistisch unabhängig sein, damit Änderungen eines Teils des Modells
keinen Einfluss auf das Verhalten anderer Teile haben.
Das kann man am Beispiel der Simulation eines Friseursalons erklären: Die Ankunft von Kunden sowie die
Dauer eines Haarschnitts (bzw. einer Rasur) sind Zufallsvariablen. Beim Experimentieren mit dem Modell
wird man sicherlich die Ankunftsrate, die Bedienungsrate oder beides verändern und sehen, was geschieht.
Würden die Zufallsvariablen mit demselben Pseudozufallszahlenstrom erzeugt werden, dann wären die beiden
Zufallsquellen nicht unabhängig. Man könnte z. B. nicht die Auswirkungen eines veränderten Kundenstroms
bei gleichbleibenden Bedienungszeiten untersuchen. Die Verwendung von zwei unabhängigen
Evelin Kofler
Zufallszahlen – first draft
Seite 3
Pseudozufallszahlenströmen ist zu bevorzugen. Wird diese Methode angewandt, können entweder die
Ankunfts- oder die Bedienungsrate unabhängig voneinander verändert werden, was das Experimentieren mit
dem zu modellierenden System erleichtert. Es gibt Softwareprodukte, welche den Einsatz von mehreren
Pseudozufallszahlenströmen gestatten (→ link zu GPSS).
Eine weitere Forderung ist eine schnelle Verfügbarkeit der Zufallszahlen während des Simulationsvorgangs.
Falls die Zufallszahlen zur Zeit der Benutzung laufend erzeugt werden sollen, muss die Generationsdauer
entsprechend kurz sein, wodurch jedoch in der Regel eine unzureichende Qualität der Zufallszahlen entsteht.
Um unabhängig von der Generierungsrate zu sein, kann man einen Tabellengenerator benutzen, bei dem die
Zufallszahlen vor der Benutzung erzeugt und abgespeichert worden sind. Werden die Zufallszahlen dann
benötigt, können sie schnell aus der Tabelle herausgelesen werden.
In der Praxis werden die Zufallszahlen häufig aus einer rekursiven Rechenvorschrift gewonnen, nach der aus
dem oder einigen Vorgängern eine weitere Zufallszahl gebildet wird. Die so erzeugten Sequenzen sind im
strengen Sinn nicht zufällig und werden daher als pseudozufällig bezeichnet, können aber als ausreichend
zufällig angesehen werden, falls sie die geforderten Qualitätsansprüche erfüllen. Hierzu beobachtet man eine
solche Sequenz, bestimmt ihren Mittelwert, Momente der Verteilung sowie die Korrelationen und andere
Eigenschaften und entscheidet dann, ob sie den gestellten Anforderungen genügt.
Physikalischer Zufallszahlengenerator: z. B. der Zufallszahlengenerator PURAN (→ link), ein
Rauschgenerator, welcher ein 1,5 GHz-Rauschsignal aus einer Halbleiterdiode erzeugt, um mit Hilfe einer aus
zwei Flipflops bestehenden Abtastschaltung Zufallsbits zu erzeugen, die einmalig aufgenommen und auf ein
geeignetes Speichermedium abgespeichert werden. Bei einer effektiven Generationsrate von 50 Kbit/s sind die
Abhängigkeiten der Bit untereinander so klein, dass sie nicht mehr nachgewiesen werden können.
Evelin Kofler
Zufallszahlen – first draft
Seite 4
→ link zu Excel-Lösung für „6 aus 45“ (zuger245.zip)
→ link zu C++-Lösung für „6 aus 45“
→ link zur Literaturliste von Dr. Richter
→ link zu zweigliedriger Markovkette
Evelin Kofler
Zufallszahlen – first draft
Seite 5
Zufallszahlen im Unterricht
Meine Schüler kommen erstmals in Kontakt mit dem Begriff der „Zufallszahl“, wenn sie folgende
Aufgabenstellung im Rahmen der Festigung der Kontrollstruktur IF-THEN-ELSE erhalten:
Zahlenraten(1): Der Benutzer versucht, eine vom System generierte Zufallszahl zu erraten. Das System teilt ihm
mit, ob er die Zahl erraten hat oder nicht.
Zur Generierung einer Zufallszahl stellt BorlandC die Funktion
random(Obergrenze);
⇒
liefert eine ganze Zahl x mit 0 <= x < Obergrenze
in der Bibliothek stdlib.h zur Verfügung stellt.
Zahlenraten(2): Erweitern Sie Zahlenraten(1) dahingehend, dass das System dem Benutzer mitteilt, ob sein Tipp
zu hoch oder zu niedrig gewesen ist.
Bei dieser Aufgabe stellen sich meist noch keine Fragen. Spätestens bei der Festigung der FOR-Schleife mit der
folgenden Aufgabe, welche auch zu einem späteren Zeitpunkt wieder aufgegriffen werden kann, wird der Begriff
der „Zufallszahl“ auch von den Schülern hinterfragt.
Lottosimulation(1): Erstellen Sie ein Programm, welches Ihnen mittels Zufallszahlengenerator einen Tipp für "6
aus 45" erstellt.
Evelin Kofler
Zufallszahlen – first draft
Seite 6
Lottosimulation(2): Erstellen Sie ein Programm, welches Ihnen mittels Zufallszahlengenerator drei Tipps für „6
aus 45“ erzeugt. Mittels Zufallszahlengenerator wird dann auch das Ergebnis einer Ziehung
simuliert.
Das Programm soll nun berechnen, wie viele Treffer Sie mit Ihren einzelnen Tipps erzielt
haben.
Setzen Sie dabei die Unterprogrammtechnik sinnvoll ein!
Bereits bei Lottosimulation(1) stellen die Schüler fest, dass sie den gleichen Tipp auf ihrem Bildschirm stehen
haben wie ihre Nachbarn. Auch bei einem neuerlichen Start des Programms ändert sich die Folge der
Zufallszahlen nicht. Diese Erkenntnis gibt Anlass dazu, zu Hinterfragen, was der Computer überhaupt unter
„Zufallszahlen“ versteht und wie sie generiert werden.
Die Schüler lernen dabei auch die Prozedur randomize(); (Bibliotheken: stdlib.h und time.h) kennen, welche vor
der Generierung der ersten Zufallszahl aufzurufen ist. Bei jedem Aufruf dieser Prozedur (also auch bei jedem
neuerlichen Programmstart) wird der Anfangswert (seed) für die Generierung der Zufallszahlen abhängig von der
Betriebssystemzeit neu wählt, wodurch sichergestellt wird, dass nicht bei jedem Programmstart die gleiche Folge
von Zufallszahlen erzeugt wird.
Ein Problem, welches der Befehl randomize(); nicht lösen kann, ist jenes, dass eine Zufallszahl mehr als einmal in
der generierten Zufallszahlenfolge auftauchen kann. Dieses Problem stellt eine gute Überleitung zur Einführung
der Datenstruktur Feld dar, da das Programm sich die bisher generierten Zahlen merken und bei Generierung einer
bereits existierenden Zahl diese verwerfen muss.
Evelin Kofler
Zufallszahlen – first draft
Seite 7
Kapitel 8 aus dem Turing-Omnibus: Random Numbers – The Chaitin-Kolmogoroff Theory
Das Wesen des Zufalls ist das Fehlen von Prozeduren und Mechanismen. Daher ist es fast ein Widerspruch,
Zufallszahlen und Computer im selben Atemzug zu erwähnen.
Wenn wir mittwochs oder samstags die Ziehung der Lottozahlen am Fernsehschirm mitverfolgen, stellen wir den
Zufall doch kaum in Frage, da nur die physikalischen Gesetze die Position der Bälle im Behälter bestimmen.
Zufallszahlengeneratoren der Programmiersprachen werden von ihren Benutzern auch kaum hinterfragt
(vergleiche Zahlenraten(1)). Sofern die generierten Zufallszahlen, die doch in mehreren Applikationen
Anwendung finden, zufällig wirken, wird ihre „Zufälligkeit“ auch nicht hinterfragt. Erst bei Implementierung der
Lottosimulation sind Bedenken aufgetreten.
Viele der in den modernen Rechnern eingebauten Generatoren verwenden die lineare kongruente Methode.
Hierbei wird (rekursiv) durch eine einfache Formel die nächste Zufallszahl anhand der aktuellen Zufallszahl
ermittelt:
x n +1 = (k ⋅ x n + c) mod m
Um den Prozess zu starten, wird ein Initialwert x0, seed genannt, gewählt. c wird offset genannt.
Nicht jede Kombination der Parameter k, c und m produziert Zahlen, die zufällig wirken:
z. B. erzeugt k = 19, c = 51, m = 100, x0 = 25 die Zahlenfolge
25, 26, 45, 6, 47, 44, 87, 4, 27, 64, 67, 24, 7, 84, 47, ...
Evelin Kofler
Zufallszahlen – first draft
Seite 8
Nachdem die verwendete Formel deterministisch ist, kann man leicht nachvollziehen, dass sich die
Zahlenfolge zwischen den beiden Werten 47 immer wieder wiederholen wird.
25, 26, 45, 6, 47, 44, 87, 4, 27, 64, 67, 24, 7, 84, 47, ...
Die Länge einer solchen Teilsequenz wird Periode genannt. Bei obiger Folge hat die Periode den Wert 10. Es
ist offensichtlich, dass sich jede Folge von Zahlen, die mit Hilfe dieser Methode generiert wird, sich früher
oder später wiederholen wird. Es erhebt sich nur die Frage, um wie viel besser man werden kann.
Die folgende Wahl der Parameter zeigt, dass man die Dinge etwas verbessern kann. Es zeigt aber auch, wie
sensibel der Generierungsprozess auf kleinste Parameteränderungen reagiert.
Ändern wir z. B. nur den Parameter m von 100 auf 101 ab, so erhalten wir die Zahlenfolge
25, 21, 46, 16, 52, 29, 97, 76, 81, 75, 62, 17, 71, 87, 88, 6, 64, 55, 86, 69, 49, 73, 24, 2, 89, 76, ...
Die Periode hat sich auf 18 vergrößert und beginnt auch um einiges später.
Noch mehr zufällige Zahlen können anscheinend durch die bestens bekannte logistische Formel, welche als
Illustration von Chaos in Dynamischen Systemen verwendet wird, erzeugt werden:
x n +1 = r ⋅ x n ⋅ (1 − x n )
Indem mit einem Startwert x0 begonnen wird, der zwischen 0 und 1 liegt, kann mit dieser Formel eine
überzeugend aussehende Folge von Zufallszahlen erzeugt werden. Der Startwert ist bei dieser Formel nicht
Evelin Kofler
Zufallszahlen – first draft
Seite 9
kritisch. Aber nach ein paar Iterationen wird die Folge der Zahlenwerte (übertrieben ausgedrückt) wie wild
geworden in einem Teilintervall [a, b]  [0, 1] hin und her hüpfen. Man kann dieses Übel aber beseitigen,
indem man auf xn die folgende Transformation anwendet, wodurch man eine neue „zufällige“ Zahl yn zwischen
0 und 1 erhält.
Die logistische Formel verhält sich nur für bestimmte Werte des Parameters r chaotisch. (→ 3.57 ≤ r ≤ 4)
Es wurden viele Theorien entwickelt, die sich mit der Zufälligkeit der von Zufallsgeneratoren erzeugten
Zufallszahlen beschäftigen. Aber da sie durch einen deterministischen Algorithmus erzeugt werden, können sie
immer nur sogenannte Pseudo-Zufallszahlen sein.
Eine dieser Theorien ist die von Gregory J. Chaitin und A. N. Kolmogoroff Mitte der Sechziger Jahre
unabhängig voneinander entwickelte Chaitin-Kolmogoroff Theory. Diese Theorie definiert die Zufälligkeit
einer endlichen Folge von Zahlen in Abhängigkeit von der Länge des kürzesten Programms, welche diese
Zahlenfolge generieren kann. Je länger dieses Programm sein muss, umso „zufälliger“ ist diese Zahlenfolge.
Offensichtlich braucht ein Programm, welches eine gegebene Zahlenfolge erzeugen soll, kaum länger als die
Folge selbst sein. Dies legt nahe, dass jene Folgen, welche Programme erfordern, die annähernd so lang sind
wie die Folge selbst, die „zufälligsten“ sind.
Beispiel: Welches ist das kürzeste Programm, das eine Zahlenfolge erzeugt, die aus m Wiederholungen der
Sequenz 01001 besteht?
Evelin Kofler
Zufallszahlen – first draft
Seite 10
Angenommen, wir verwenden folgende Pseudo-Programmiersprache,
for
i = 1 to m
output 0,1,0,0,1
so haben wir ein Programm, welches aus 23 ASCII-Zeichen (Blanks nicht mitgezählt) und einer
Variablen m besteht, die sich von einer Programmversion zur anderen ändern wird.
Für einen bestimmten Wert von m wird die Länge des vorliegenden Programms (in ASCII-Zeichen
gemessen) 23 + log m sein. Es erzeugt eine Zahlenfolge der Länge n = m·5 (5 ist die Periode, d.h.
Länge der Teilsequenz 01001).
Wie „zufällig“ ist nun die durch dieses Programm erzeugte Zahlenfolge? Eine Möglichkeit, die
Zufälligkeit zu messen, ist, das Verhältnis aus Programmlänge und Länge der Zahlenfolge zu
bilden:
r≤
23 + log m
5m
Für m → ∞ geht r gegen 0. Daraus kann man schließen, dass längere Zahlenfolgen immer weniger
„zufällig“ werden.
Das Problem bei dem ganzen ist, zu beweisen, dass es sich bei dem angegebenen Programm tatsächlich um das
kürzestmögliche handelt. Es ist unmöglich zu beweisen, dass eine bestimmte Folge zufällig ist, aber man kann
zeigen, dass die meisten Folgen zufällig sind. Aber darauf möchte ich hier nicht näher eingehen. Ich möchte
nur auf den berühmten Unvollständigkeitssatz von Gödel verweisen.
Evelin Kofler
Zufallszahlen – first draft
Seite 11