Diskussion:Zwölferregel

Die Löschung der Seite „Zwölferregel“ wurde ab dem 11. November 2018 diskutiert und abgelehnt. Für einen erneuten Löschantrag müssen gemäß den Löschregeln neue Argumente vorgebracht werden.

Konvolutionsalgorithmus

Ist der sog. "Konvolutionsalgorithmus" das gleiche bzw. eine Verallgemeinerung der Zwölferregel? Falls ja, Verlinkung?

Unabhängigkeit der Xi

Hallo 132.199.18.195, Absatz hierher verschoben. Was ist Spektraltest, warum 4 bis 7? -- Anton 22:03, 19. Dez 2005 (CET)

---

Stark ins Gewicht fällt die Forderung der Unabhängigkeit der zwölf $X_{i}$, die von normalen Pseudozufallszahlen nicht garantiert wird. Im Gegenteil wird vom Spektraltest meist nur die Unabhängigkeit von maximal vier bis sieben der $X_{i}$ garantiert. Für numerische Simulationen ist die Zwölferregel daher sehr bedenklich! Andere genauso leicht zu programmierende Verfahren sind unbedingt vorzuziehen!

---

Im Artikel ist nur undeutlich erwähnt, dass die Anwendung der Zwölferregel (Zr) die Unabhängigkeit der 12 einzelnen Zufallszahlen voraussetzt.

Die Zufallszahlen müssen irgendwie gewonnen werden. Wenn man keinen physikalischen Mechanismus (Radioaktivität, echter Würfel) an den Rechner anschließt, geschieht das in der Regel mit Pseudozufallszahlengeneratoren.

Stand der Technik sind die sog. LKG (lineare Kongruenzgeneratoren mit der Formel x = (a x + c) % m und festen Konstanten a, c, m).

Die Unabhängigkeit der generierten Zufallszahlen wird mit dem erwähnten Spektraltest getestet. (Ungetestete Generatoren sollten sowieso nie verwendet werden.)

Der Spektraltest liefert als Ergebnis, wieviele aufeinanderfolgene Zahlen noch als unabhängig gelten können und wie gut sie unabhängig sind. Das geschieht mit n2, n3, n4, n5... (eigentlich griechisch nü statt n) die für jeweils 2, 3, 4, 5, ... aufeinanderfolgende Zufallszahlen deren Qualität angeben.

Der Kehrwert 1/ni ist dabei der kleinste Abstand der (i-1)-dimensionalen Hypergitterebenen (was ein Wort) im i-dimensionalen Raum von aufeinanderfolgenden i-tupeln der gegerierten Zahlen.

Typisches Beispiel: Generator mit m = 10000000000 = 10^10; a = 3141592621; c = 1; x0 = 0:

n2 = 67654; n3 = 1017; n4 = 249; n5 = 42; n6 = 23; n7 = 23

Die Zahlen sagen direkt etwas über die Genauigkeit der erhaltenen Zufallszahlen aus: Wenn man in einer Rechnung immer zwei Zufallszahlen benötigt, kann man die Ergebnisse maximal mit einer Genauigkeit von 1/n2 = 1/67654 = 0.0000148 < 10^-4 = 4 Dezimalstellen angeben.

Wenn man drei pro Rechnung benötigt sind das 1/n3 = 1/1017 = 0.000938 < 10^-3 = 3 Dezimalstellen.

Bei vier pro Rechnung ergibt sich 1/n4 = 1/249 = 0.00402 < 10^-2 = 2 Dezimalstellen

Die Zwölferregel benötigt für ein Ergebnis 12 unabhängige Zahlen. Die Genauigkeit der Ergebnisse ist also (der Spektraltest wird derzeit bis maximal n7 ausgewertet, da er für größere i sowieso miserable Ergebnisse liefert)

1/n12 > 1/n7 = 1/23 = 0.0435 > 10-^2 = weniger als 2 Dezimalstellen.

• ^ wahrscheinlich (wurde nicht gerechnet, ist aber zu erwarten!)

Warum also mit der Zr und 12 abhängigen Zahlen ein Ergebnis mit wahrscheinlich nicht einmal einer Dezimalstellen errechnen, wenn z.B. die Methode von Box-Muller mit 2 benötigten Zufallszahlen ein 6-stelliges Ergebnis garantiert???

(Übrigens: diese gravierende Ungenauigkeit kann man den angegebenen Ergebnissen entnehmen, jedoch nicht der im Artikel beigefügten Graphik!)

Dein Kommentar scheint plausibel; leider kann ich die n_i nicht nachvollziehen, damit auch nicht die erforderliche Minimalperiodizität. Ebenso nicht, wie aus den wenigen Zahlen auf schlechte Zufallsverteilung schließt.

Deine Anmerkung wäre ein schönes Beispiel für die Beschränktheit von Pseudozufallszahlen, vielleicht kannst du es genauer ausführen?

Ich kenne niemanden, der sich mit der Zwölferregel Zufallsverteilungen generiert. Die Regel stammt aus einer Zeit, wo das Rechnen noch Arbeit machte (s.: Varianz=1).

Nun, einfach nachzuvollziehen sind sie wirklich nicht. In der Bibel über dieses Thema (Knuth: The Art of Computer Programming, Vol 2) steht die Theorie im Kapitel 3.3.4 zwischen Seite 93 und Seite 118. Auf Seite 106 werden die Ergebnisse für verschiedene LKG diskutiert.

Nimm die Zahlen einfach als Rechenergebnisse. Wenn dein Taschenrechner sin (40°) = 0.6427876097 ausspuckt, glaubst du es vermutlich auch ohne genau wissen zu müssen wie es zustande kommt.

Wichtig ist die Interpretation der Ergebnisse: Und die ergibt, das die meisten und praktisch alle verwendeten LKG mit der Zwölferregel eigentlich keine Dezimalstelle Genauigkeit der berechneten normalverteilten Zufallsvariable garantieren können. Mit der Box-Muller-Methode jedoch immerhin 6 Dezimalstellen.

Und die Zwölferregel spukt leider immer noch in vielen Lehrbüchern herum ud auch (weil sie so einfach ist) in wahrscheinlich viel zu vielen Programmen.

Auf ihren Nachteil kann man gar nicht oft genug hinweisen. In diesem Artikel sollte der von mir eingefügte Hinweis nicht fehlen.

Ich habe übrigens den hier schnell geschriebenen Text leicht modifiziert in einem Artikel über den Spektraltest untergebracht, den es bisher in der dt. Wikipedia noch nicht gab.

Und eines hänge ich noch dran: Mit Genauigkeit ist nicht gemeint, dass die erzeugte Zufallsvariable exakt oder nicht exakt auf der "Glockenkurve" liegt, sondern wie gut sie mit der gewünschten Verteilung streut. Die Aussage "sie hat 2 Stellen Genauigkeit" heißt also, dass die ersten zwei Dezimalstellen gut und zufällig die geschünschte Verteilung wiedergeben. Die restlichen (bei double mit 16 Stellen sind das 14 Dezimalstellen) sind voneinander abhängig und eben nicht zufällig. Das kann vieles heißen: sie sind immer gerade; sie sind immer gleich oder zyklisch; ...

Ich würde übrigens noch den folgenden Absatz unterbringen:

Nach dem zentralen Grenzwertsatz ist die Summe xi, i = 1..n normalverteilt mit Erwartungswert m und Varianz s = S / sqrt (n), wenn die Einzelvariablen xi unabhängig sind und wenn ihre Verteilung einen Erwartungswert m und eine Varianz S hat.

Da im Intervall [a, b) gleichverteilte unabhängige Zufallsvariable xi den Erwartungswert m = (a+b)/2 und die Varianz S = (b-a)/(2*sqrt(3)) haben, treffen die genannten Voraussetzungen zu.

Prinzipiell kann man jedes n verwenden und größere n ergeben nach dem zentr. Gr.w.satz besser normalverteilte Zufallszahlen.

Der spezielle Wert n=12 der Zwölferregel erklärt sich aus der einfachen Varianz der annähernd normalverteilten Summe: s = S / sqrt (12) = (wegen gleichverteilung) (b-a)/2/sqrt(3)/sqrt(12) = (b-a)/12. Kurz: mit n=12 wird man die Wurzel im Nenner los.

KOnvolutionsalgorithmus

Literatur?

Gibt es eine Quelle zu dieser Regel und diesen Namen, die nicht von hier abgeschrieben hat? --2003:A:1517:8900:A0CD:14E7:9623:B542 13:44, 27. Sep. 2018 (CEST)