Skip to main content


Zutaten: Zucker, Kakaomasse (50%), Milchzucker, Weizenmehl, Vollmilchpulver, Magermilchpulver, Butterreinfett, Sahnepulver, Butter (1,4%)
Kann Spuren von Analysis und Geometrie enthalten.

IV_20_titel_panomara_berlin-bei-nacht

Wie Ben Zufallszahlen berechnet

Rike und Ben wollen gern mal Berlin von oben sehen. Fernsehturm? Aussichtsterrasse des Park Inn am Alex? Sie entscheiden sich für die Aussichtsterrasse.

Ben Boah, ist das schön! Die vielen Lichter! Was meinst Du, Rike, bilden die ein Muster?

Rike Naja, die meisten sind deterministisch angebracht und eingeschaltet.

Ben Rike, dann schreib‘ mir doch mal eine Formel dafür auf!

Rike Bist Du verrückt?

Ben Siehste, dann kann man das doch ganz gut mit dem Zufall simulieren. Ach, Rike, nenn‘ mir doch mal eine zufällige Zahl zwischen 1 und 10!

Rike 10

Ben Und noch eine?

Rike 10

Ben Und noch eine?

Rike 10

Ben Und noch eine, eine zufällige? Hast Du schlechte Laune?

Rike Hab keine Lust mehr!

Ben Rike, dann bist Du gerade durch den Zufallszahlentest von Knuth gefallen!

Rike Hab ich mir gedacht! Ich bin kein Zufallszahlengenerator! Hast Du denn einen coolen?

Die knuthschen Kongruenz-Methode

Ben Klar. Eigentlich liebe ich den einfachsten Algorithmus - die knuthsche Kongruenz-Methode. Die geht so:

Wenn wir gleichmäßig verteilte Zufallszahlen zwischen 1 und 10 haben wollen, nehmen wir

m\;=\;10

Du startest dann mit einer Anfangszahl X0 und wählst Zahlen a und c:

X_0,\; a,\; c\; \in \;\mathbf{N}

Die Zufallszahlen Xi kannst Du dann nach der knuthschen Formel berechnen:

X_{i+1}\;=\;a X_i\;+\;c\;\mathrm{ mod} \; m,\; i\; \in \mathbf{N}

Rike Hört sich ganz einfach an! Ich nehme mal

X_0\;=\;0

a\;=\;c\;=\;1

Dann kriege ich

X_{i+1}\;=\;X_i\;+\;1\; \mathrm{ mod} \; m,

also

1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, ...

IV_20_zufall_Knuth_trivial_03
Zufallszahlen nach der knuthschen Formel für m\;=\;10,\; X_0\;=\;0,\; a\;=\;c\;=\;1.

Wo ist denn da der Zufall?

Ben Erstmal ist das die Formel zur Berechnung, die ist wirklich einfach. Leider müssen ein paar Bedingungen erfüllt sein, damit diese Zahlen wirklich zufällig wirken.

Rike Ja, es wäre auch schön, wenn Außenstehende die Formel nicht erraten können. Hier sieht man zum Beispiel, dass sich die Ziffern nach 10 Zahlen wiederholen.

Ben Stimmt. Da haben wir das 1. Problem. Wir rechnen mit Restklassen. Wenn wir Zahlen zwischen 1 und 10 oder, was fast das Gleiche ist, zwischen 0 und 9 haben wollen, sollten wir m = 10 wählen, aber m ist gleichzeitig die Periode der Zufallszahlen. Für unseren Test ist sie viel zu klein!

Rike Hm.

Ben Aber das können wir ganz einfach lösen, wir nehmen eine große Periodendauer m und machen eine kleine zusätzliche Rechnung und berechnen aus den Zufallszahlen von 0 bis m-1 welche von 0 bis 9.

Rike Okay. Welche Bedingungen gibt es denn?

Ben Warte mal, ich muss das nachschauen,…, hier,

Theorem A

Die lineare Kongruenzfolge hat die Periode m genau dann, wenn die drei Bedingungen erfüllt sind:
(a) c ist teilerfremd zu m
(b) b = a - 1 ist Vielfaches von jeder Primzahl p, die m teilt
(c) b ist Vielfaches von 4, wenn m Vielfaches von 4 ist.

Knuth schreibt, dass die Ideen dazu schon 100 Jahre alt sind und schließlich 1962 bewiesen worden. Das kannst Du ja mal nachprüfen. Welche Periode wollen wir wählen?

Rike Na, 1000 Zufallszahlen hätte ich schon gerne.

Ben Okay, man nimmt für m gern 2er Potenzen, lass uns mal

m\;=\;2^{10}\;=\;1024

nehmen.

Rike Ja, gut, das ist gleich die Primfaktorzerlegung. Außerdem ist m durch 4 teilbar. Dann muss b durch 4 teilbar sein. Die Bedingung (b) ist dann gleich mit erfüllt. b könnte 4, 8, 12, … sein. Für c könnten wir jede ungerade Zahl wählen.

Ben Gut. Eben hatten wir schlechte Erfahrungen mit kleinen Zahlen 0 und 1. Lass uns a und c so wählen, dass sie Primzahlen sind.

b\;=\;12

a\;=\;13

Okay?

Rike Gut, ich schlage dann

c\;=\;421

vor.
Ben Und ich nehme

X_0\;=\;99\; 991

Rike Okay! Lass mich das mal ausrechnen:

848, 181, 726, 643, 588, 897, ...

Ben Schön. Wollen wir für die Zufallszahlen zwischen 0 und 9 einfach die Hunderterstelle nehmen? Also

8, 1, 7, 6, 5, 8, ...

Kannst Du das ausrechen?

Rike Klar, hier schau mal:

IV_20_zufall_Knuth_04
1000 Zufallszahlen von 0 bis 9. Berechnet mit der knuthschen Kongruenz-Methode, m\;=\;1024,\; X_0\;=\;99\;991,\; a\;=\;13,\; c\;=\;421 und einer "Nachrechnung"

Erwartungswert und Varianz

Okay, gefällt mir. Wie ist denn der Erwartungswert? Warte:

E(X)\;=\;\sum_{i=1}^N \;X_i\;\frac{1}{N}

\;=\;4,62.

Ben Und die mittlere Abweichung davon?

Rike Die Varianz? Die ist

\sigma(X)\;=\;\sqrt{\; \sum_{i=1}^N \;(X_i\;-\;E(X))^2\;\frac{1}{N} }

    \;=\;2,97

Ben Ich find's toll! Obwohl es einige Kritik an dem Algorithmus gibt, habe ich ja immer noch die volle Kontrolle. Die Zahlen von 0 bis 9 sind relativ gleichmäßig verteilt, es bildet sich kein periodisches Muster. Natürlich ist m = 1024 noch etwas klein. Kannst Du mal eine Standard-Zufallsfunktion aufrufen? Eine, die mit dem Mersenne-Twister-Verfahren berechnet wurde?

Vergleich mit dem Mersenne-Twister-Verfahren

Rike Klar, kann ich machen, mit

\mathrm{randint}(0, 9)

in Phyton und der Wahl einer Anfangszufallszahl:

\mathrm{seed}(n),

die verrate ich aber nicht!, kriege ich 1000 Zufallszahlen:

IV_20_zufall_twister_03
1000 Zufallszahlen von 0 bis 9 nach dem Mersenne-Twister-Verfahren

Ben Was kriegst Du für den Erwartungswert?

Rike

E(X)\;=\;4,45

Ben Und die Varianz?

Rike

\sigma(X)\;=\;2,91

Vergleich mit der Gleichverteilung

Ben Schön, für eine Gleichverteilung der Zahlen 0 bis 9 kriegen wir den Erwartungswert

E(X)\;=\;4,5

und eine mittlere quadratische Abweichung von

\sigma(X)\;=\;2,87

Das passt ja schon ganz gut. Mein Lieblingsalgorithmus hat das fast so gut wie der Twister gemacht!

Rike Sag Du mir doch mal eine Zufallszahl von 1 bis 10?

Ben Hahaha.

***

Übungsaufgabe

Vergleiche die beiden Verfahren an Beispielen!

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.

Wir freuen uns, dass Du einen Kommentar hinterlassen möchtest. Denk bitte daran, dass Du dich durch das Abschicken des Kommentars mit unseren Nutzungsbedingungen einverstanden erklärst.