gleichverteilte Zufallszahlen

[wolfgke]

...unter der Voraussetzung, dass du einen vernünftigen Zufallsgenerator hast.

Ein Professor, den ich in Informatik hatte, würde sagen: die Nichtkonvergenz ist derart unwahrscheinlich "so etwas gibt es gar nicht in der Praxis".

Jemand, mit dem ich in Mathematik zu tun hatte, würde eher so reagieren: es gibt keine garantierte obere Schranke für die benötigte Anzahl an Schritten. Man sollte also mit der Verwendung in der Praxis vorsichtig sein (also Code einbauen, wenn eine bestimmte Anzahl Schritte überschritten wird etc.).

Ich stehe auf der Seite der Mathematiker-Fraktion

[Korbinian]

wolfgke schrieb:

Ein Professor, den ich in Informatik hatte, würde sagen: die Nichtkonvergenz ist derart unwahrscheinlich "so etwas gibt es gar nicht in der Praxis".

Der BBS Generator soll recht gut sein...

[Taurin]

Jester schrieb:

Die erwartete Anzahl Schritte ist: $\Sigma_{k=1}^{\infty}k (\frac{1}{2})^2$

Und das ist nach einer kurzen Rechnung, wenn ich mich nicht vertan habe 2. Das heißt im Mittel terminiert Dein Verfahren bereits nach 2 Schritten.

Du hast dich bei der Reihe verschrieben... da muss eigentlich ein "hoch k" stehen. Dann kommt auch 2 heraus.

[Taurin]

wolfgke schrieb:

...unter der Voraussetzung, dass du einen vernünftigen Zufallsgenerator hast.

Ein Professor, den ich in Informatik hatte, würde sagen: die Nichtkonvergenz ist derart unwahrscheinlich "so etwas gibt es gar nicht in der Praxis".

Jemand, mit dem ich in Mathematik zu tun hatte, würde eher so reagieren: es gibt keine garantierte obere Schranke für die benötigte Anzahl an Schritten. Man sollte also mit der Verwendung in der Praxis vorsichtig sein (also Code einbauen, wenn eine bestimmte Anzahl Schritte überschritten wird etc.).

Ich stehe auf der Seite der Mathematiker-Fraktion

Wenn wir das Ding programmieren, benutzen wir "nur" einen Pseudo-Zufallsgenerator für die 0en und 1en. Dann bilde ich mir folgenes ein (jedenfalls hab ich noch irgendsowas dunkel im Hinterkopf): Wenn das ein ordentlich modelierter Zufallsgenerator ist, kommt jede mögliche 0,1-Teilfolge der Länge k vor. Wir können uns also sicher sein, dass es nicht schief geht.

[Jester]

Taurin schrieb:

Jester schrieb:

Die erwartete Anzahl Schritte ist: $\Sigma_{k=1}^{\infty}k (\frac{1}{2})^2$

Und das ist nach einer kurzen Rechnung, wenn ich mich nicht vertan habe 2. Das heißt im Mittel terminiert Dein Verfahren bereits nach 2 Schritten.

Du hast dich bei der Reihe verschrieben... da muss eigentlich ein "hoch k" stehen. Dann kommt auch 2 heraus.

Stimmt, ist ein Tippfehler. Sonst wär's nicht konvergent.

[Christoph]

Taurin schrieb:

Wenn das ein ordentlich modelierter Zufallsgenerator ist, kommt jede mögliche 0,1-Teilfolge der Länge k vor. Wir können uns also sicher sein, dass es nicht schief geht.

Spätestens, wenn k größer als Periode des Generators ist, kann das IMHO schiefgehen.

[Jester]

---

[Turing]

Du kannst doch einfach eine Folge von binären Werten generieren und dies als Ganzzahl interpretieren, die Du als Startwert für z.B. Lineare Kongruenz Methode nimmst. Damit ist eigentlich alles erledigt (evtl. noch ein Modulo für ein Mapping auf n-1). Allerdings sind diese Sequenzen auch immer "pseudo-random".

[Jester]

Das mit dem modulo bringt doch auch wieder ähnliche Probleme mit sich.

Einfaches Beispiel: ich erzeuge Zufallszahlen von 0 bis 2. Möchte aber nur 0 und 1 haben. Also modulo 2. Und schon erzeuge ich die 0 doppelt so wahrscheinlich wie die 1. Für größere Zahlen ist der Effekt nicht mehr ganz so dramatisch, aber ganz gleichverteilt isses nicht.

MfG Jester

[Turing]

Klar, das 1. Modulo für die lineare Kongruenzmethode sollte möglichst groß gewählt werden, was zudem (wenn ich es richtig in Erinnerung habe) den Vorteil hat, dass die Zufallssequenzen größere Periodenlängen haben.

Ob eine Zufallszahlensequenz wirklich gleichverteilt ist, kann man sowieso recht schwer beweisen, da man dies erst sieht, wenn man das Zufallsexperiment unendlich oft wiederholt.

Die Aussage "Ich kann 0 und 1 gleichverteilt erzeugen" ist meiner Meinung nach nur eine Behauptung, die man nicht beweisen kann.

Ich denke es reicht, wenn man weiß, dass alle Zahlen nahezu gleichwahrscheinlich auftreten. Die genannte Methode wurde lange untersucht und erfüllt diese Eigenschaft, wenn man sie mit den richtigen Werten anwendet.

[Christoph]

Turing schrieb:

Die Aussage "Ich kann 0 und 1 gleichverteilt erzeugen" ist meiner Meinung nach nur eine Behauptung, die man nicht beweisen kann.

Ich wüsste gerade keine prinzipiellen Gründe, die gegen einen solchen Beweis sprechen, sofern du keine Blackbox meinst. Die Mathematik gestattet auch Aussagen über unendlich oft ausgeführte Algorithmen.
Bei der linearen Kongruenz ist die Gleichverteilung bestimmt längst gezeigt bzw. widerlegt worden, laut Wikipedia ist die Gleichverteilung sogar für den Mersenne-Twister-Algorithmus in gewissen Grenzen bewiesen.

[Turing]

Man kann die Zufälligkeit nur testen und dann eine Aussage darüber machen, mit welcher Wahrscheinlichkeit die Realisierung den Annahmen genügt.

[Jester]

Wieso sollte ich bei einer bestimmten Realisierung deren Aufbau ich kenne nicht auch direkt etwas über die Eigenschaften aussagen können?

Ich weiß doch auch, daß 1 + 1/2 + 1/4 + 1/8 + ... als Grenzwert 1 hat. Dazu muß ich auch nicht solange addieren bis mal 2 rauskommt (was nach endlich vielen Schritten nie der Fall ist).

[dooya]

Jester schrieb:

Wieso sollte ich bei einer bestimmten Realisierung deren Aufbau ich kenne nicht auch direkt etwas über die Eigenschaften aussagen können?

Ich weiß doch auch, daß 1 + 1/2 + 1/4 + 1/8 + ... als Grenzwert 1 hat. Dazu muß ich auch nicht solange addieren bis mal 2 rauskommt (was nach endlich vielen Schritten nie der Fall ist).

Entschuldige die dumme Frage, aber warum ist der Grenzwert dieser Folge 1? Ich hätte spontan auf 2 getippt.

[Turing]

Das erinnert mich irgendwie jetzt an die Geschichte bei der man sich seinem Ziel immer um genau die Hälfte nähert aber doch nie ankommt...

Aber zurück zum Thema: Was für Aussage außer statistischen Momenten kannst Du denn machen? Und für statistische Momente brauchst Du nunmal Realisierungen.

Bei Pseudo-Zufallszahlen magst Du recht haben, dass ich eine Art "Pseudo-Gleichverteilung" nachweise, indem ich z.B. im Falle der Linearen Kongruenz mit allen möglichen Startwerten solange Zufallszahlen erzeuge bis sie sich wiederholen und dann histogrammmäßig anschaue. Wenngleich ein solche Beweis nur niederdimensional und eher theoretischer Natur ist.

[PeterTheMaster]

die 1 ist ein typo, jester schreibt doch spaeter selbst 2.

[Erhard Henkes]

..

[:D]

Erhard Henkes schrieb:

class Random_aus_Stdlib_geklaut

göttlich

[camper]

schrieb:

Erhard Henkes schrieb:

class Random_aus_Stdlib_geklaut

göttlich

Erhard Henkes schrieb:

return(((seed_ = seed_ * 214013L + 2531011L) >> 16) & 0x7fff);

grottig

[MrBesserwisser]

Greif Dir doch einfach die Systemzeit ab. Ist die gerade -> 0 bei ungerade -> 1. Das dürfte wohl mit das einfachste sein.