Zufallszahlen skalieren

03/08/2008 - 06:03 von ram | Report spam
Ein Generator, liefere eine Zahl aus der Menge {0,1,2} so, daß
die Wahrscheinlichkeit für jede Zahl und jede endliche Folge
von Zahlen gleich ist. Er brauche eine Sekunde, um eine Zahl
zu liefern.

Nun soll aus der anderen Menge {0,1} jeweils eine Zahl
zufàllig ausgewàhlt werden, so daß die Wahrscheinlichkeit für
jede Zahl und jede endlich Folge von Zahlen gleich ist.

Dazu kann der vorhandene Generator eingesetzt werden: Man
wàhle »0«, wenn dieser »0« lieferte und »1«, wenn dieser »1«
lieferte. Falls er »2« ergibt, dann rufe man den nàchsten Wert
ab, bis man »0« oder »1« erhàlt.

Dabei fàllt nun auf, daß dieser Algorithmus nicht garantieren
kann, in n Sekunden zu terminieren, da der Generator ja n + 1
Mal eine »2« liefern kann. Die Wahrscheinlichkeit dafür ist zwar
nur ( 1 / 3 )^ n, aber nicht 0. Ich bin mir auch nicht sicher,
ob man so überhaupt sagen kann, daß dieser Algorithmus terminiert.

Wenn man dies auch als nur theoretisches Problem ansieht, so
kann man doch auch in der Praxis beobachten, daß der
Algorithmus im Mittel nur alle 1,5 Sekunden eine Zahl liefert
- also langsamer ist als der Generator.

Sieht jemand noch eine Möglichkeit aus diesem Generator
gleichverteilte Zufallszahlen aus der Menge {0,1} zu erzeugen,
die schneller ist oder die mit Sicherheit (nach einer
bestimmten Zeit) terminiert oder irgendwelche anderen Vorteile
hat?

Gibt es einen Namen für dieses Problem oder verwandte Probleme?

Weitere Gedanken:

Werden k Werte des Generators in einer endlichen Folge
gesammelt, gibt es 3^k Möglichkeiten für diese Folge. Wenn man
damit jetzt einmal eine Zweierpotenz 2^m treffen würde
(3^k=2^m), dann könnte man daraus m Zufallszahlen aus dem
Bereich {0,1} erzeugen. Ersatzweise kann man durch Annàherung
an eine Zweierpotenz, die Wahrscheinlichkeit für die
Notwendigkeit des Werteverwurfs (wie bei »2« im obigen
Algorithmus) verkleinern, aber dafür muß man auch lànger Werte
sammeln.

Um die Symmetrie (Gleichverteilung) zu erhalten, muß dieser
Algorithmus anscheinen dissipieren (Information ignorieren),
was bei einem Generator, der Ziffern aus der Menge {0,1,2,3}
gleichverteilt liefert, aber wiederum nicht nötig wàre.

Gibt es eine grundlegendere Gesetzmàßigkeit, die sich hier
widerspiegelt?
 

Lesen sie die antworten

#1 earthnut
03/08/2008 - 10:39 | Warnen spam
Stefan Ram wrote:

Ein Generator, liefere eine Zahl aus der Menge {0,1,2} so, daß
die Wahrscheinlichkeit für jede Zahl und jede endliche Folge
von Zahlen gleich ist. Er brauche eine Sekunde, um eine Zahl
zu liefern.

Nun soll aus der anderen Menge {0,1} jeweils eine Zahl
zufàllig ausgewàhlt werden, so daß die Wahrscheinlichkeit für
jede Zahl und jede endlich Folge von Zahlen gleich ist.

Dazu kann der vorhandene Generator eingesetzt werden: Man
wàhle »0«, wenn dieser »0« lieferte und »1«, wenn dieser »1«
lieferte. Falls er »2« ergibt, dann rufe man den nàchsten Wert
ab, bis man »0« oder »1« erhàlt.

Dabei fàllt nun auf, daß dieser Algorithmus nicht garantieren
kann, in n Sekunden zu terminieren, da der Generator ja n + 1
Mal eine »2« liefern kann. Die Wahrscheinlichkeit dafür ist zwar
nur ( 1 / 3 )^ n, aber nicht 0. Ich bin mir auch nicht sicher,
ob man so überhaupt sagen kann, daß dieser Algorithmus terminiert.

Wenn man dies auch als nur theoretisches Problem ansieht, so
kann man doch auch in der Praxis beobachten, daß der
Algorithmus im Mittel nur alle 1,5 Sekunden eine Zahl liefert
- also langsamer ist als der Generator.

Sieht jemand noch eine Möglichkeit aus diesem Generator
gleichverteilte Zufallszahlen aus der Menge {0,1} zu erzeugen,
die schneller ist oder die mit Sicherheit (nach einer
bestimmten Zeit) terminiert oder irgendwelche anderen Vorteile
hat?

Gibt es einen Namen für dieses Problem oder verwandte Probleme?



Harte Echtzeitsysteme fordern gerade, dass ein Algorithmus die Lösung
eines Problems garantiert innerhalb einer gewissen endlichen Zeitgrenze
angibt.

<http://de.wikipedia.org/wiki/Echtze...htzeit>
<http://de.wikipedia.org/wiki/Echtze...htzeit>

Das Verfahren, dass du zur Generierung deiner Zufallszahlen einsetzt,
ist übrigens eine diskrete Variante der Acceptance-Rejection Methode.

<http://en.wikipedia.org/wiki/Reject...mpling>

Bei der Notation aus Wikipedia braucht man im Schnitt M versuche um
einen Zufallswert zu erhalten und die tatsàchliche Anzahl ist
geometrisch verteilt.

Weitere Gedanken:

Werden k Werte des Generators in einer endlichen Folge
gesammelt, gibt es 3^k Möglichkeiten für diese Folge. Wenn man
damit jetzt einmal eine Zweierpotenz 2^m treffen würde
(3^k=2^m), dann könnte man daraus m Zufallszahlen aus dem
Bereich {0,1} erzeugen. Ersatzweise kann man durch Annàherung
an eine Zweierpotenz, die Wahrscheinlichkeit für die
Notwendigkeit des Werteverwurfs (wie bei »2« im obigen
Algorithmus) verkleinern, aber dafür muß man auch lànger Werte
sammeln.



3^k = 2^m wird nie passieren (außer für k=m=0), da lins eine ungerade
und rechts eine gerade Zahl steht. Ein anderes Problem des Ansatzes ist,
dass nun (fast?) keine einzelne Ziffer mehr Gleichverteilt auf {0,1}
ist.

Um die Symmetrie (Gleichverteilung) zu erhalten, muß dieser
Algorithmus anscheinen dissipieren (Information ignorieren),
was bei einem Generator, der Ziffern aus der Menge {0,1,2,3}
gleichverteilt liefert, aber wiederum nicht nötig wàre.

Gibt es eine grundlegendere Gesetzmàßigkeit, die sich hier
widerspiegelt?



Teilbarkeit?

Bastian

Ähnliche fragen