Gleichverteilte Zufallszahlen in Polynomialzeit generieren

Hallo!

Eine randomisierte Turingmaschine kann ja bekanntlich gleichverteilte zufällige Nullen und Einsen ziehen. Ich möchte mir nun eine gleichverteilte Zufallszahl basteln, die zwischen 0 und n-1 liegt.

Wenn n eine Zweierpotenz ist, dann ziehe ich einfach log2(n) zufällige Bits und bastele mir daraus die Zahl zusammen. Die ist dann auch gleichverteilt.

Wenn n aber keine Zweierpotenz ist, was tue ich dann?
Ich sehe zwei Möglichkeiten:

1.) Auf die nächste Zweierpotenz aufrunden und so lange Zahlen ziehen, bis ich eine kriege, die < n ist. Das kann aber (in der Theorie) beliebig lange dauern. Beispiel für n = 513. Da müsste ich 10 Bits ziehen (bis 1023) und könnte fast die Hälfte der Zahlen wegwerfen.

2.) Ich ziehe n-1 Bits und addiere sie. Das ist aber nicht mehr in Polynomialzeit in Bezug auf die Eingabelänge machbar (denn mit n Bits kriege ich 2^n Zahlen).

Fällt euch da was Kluges ein?

PS: Modulo rechnen ist natürlich keine Lösung, weil damit die Gleichverteilung weg ginge.

Was ich immer benutze ist:

double uniform_deviate (int seed) {
    return seed * (1.0 / (RAND_MAX + 1.0));
}
int r = uniform_deviate (rand()) * N;

Hat natürlich auch seine Grenzen...

SeppJ

Ich fürchte mit Nummer 1) hast du bereits die übliche Methode beschrieben. Zumindest ist das die, die man in der Praxis verwendet, wenn modulo nicht reicht.

edit: @Tim: Deine Methode hat das gleiche Problem wie die Modulomethode. Du machst dir durch kleine Unterschiede beim Binning (=Cast von double auf int) die perfekte Gleichverteilung kaputt. Ist in der Praxis natürlich nur sehr selten relevant, aber hier gaht's ja anscheinend um theoretische Informatik.

Meine Frage ist eher theoretisch gemeint.
Wie man das in sinnvollen Grenzen in der Praxis machen kann, ist mir schon klar.
Deine Lösung erreicht keine Gleichverteilung. Denn dein Zufall basiert auf rand(), das z.B. Zahlen zwischen 0 und 32767 liefert, also 32768 verschiedene Zahlen. Wenn meine obere Grenze aber jetzt keine Zweierpotenz ist, dann gibt es keine Möglichkeit diese 32768 verschiedenen Zahlen gleichmäßig auf mein Intervall abzubilden. Natürlich wird die Ungleichmäßigkeit mit großem RAND_MAX sehr klein, aber es ist eben doch keine Gleichverteilung.

SeppJ schrieb:

edit: @Tim: Deine Methode hat das gleiche Problem wie die Modulomethode. Du machst dir durch kleine Unterschiede beim Binning (=Cast von double auf int) die perfekte Gleichverteilung kaputt. Ist in der Praxis natürlich nur sehr selten relevant, aber hier gaht's ja anscheinend um theoretische Informatik.

O.K. auch wenn es off-topic ist hätte ich das gerne erklärt, so ganz klar ist mir deine Antwort nicht.

Edit: Meinst du, dass ich über das generierte Intervall (sagen wir mal) wiederholend immer wieder einzelne Zahlen häufiger auftreten würden?

Hmm, ist meine zweite "Lösung" überhaupt korrekt?
Ich glaube nicht, denn z.B. für die 0 gibt es nur eine einzige Möglichkeit, wie sie zustande kommen kann, nämlich wenn ich nur Nullen ziehe. Für eine 1 gibt es hingegen viel mehr Möglichkeiten.
Also keine Gleichverteilung!

SeppJ

Tim schrieb:

O.K. auch wenn es off-topic ist hätte ich das gerne erklärt, so ganz klar ist mir deine Antwort nicht.

Klar. Mal angenommen RAND_MAX ist 3 und wir wollen Zahlen zwischen 0 und 2 (also N=3) ziehen. Das ist natürlich ein sehr vereinfachtes Beispiel, aber man kann es leicht auf RAND_MAX 2^32 und Zahlen zwischen 0 und 100 übertragen, ist dann aber nicht mehr übersichtlich.

Dein uniform_derivate() kann dann folgende Werte liefern: 0, 0.25, 0.5, 0.75, jeweils für die vier möglichen Zufallswerte 0, 1, 2, 3.

Dann ist N*uniform_derivate aus der Menge 0, 0.75, 1.5, 2.25.

Und jetzt casten wir diese Zahlen zu int:

0     -> 0
0.75  -> 0
1.5   -> 1
2.25  -> 2

Und daher ist hier die Null wahrscheinlicher als die anderen Zahlen. Das Problem ist aber nicht der Cast. Versuchen wir's mal mit kaufmännischem Runden:

0     -> 0
0.75  -> 1
1.5   -> 1
2.25  -> 2

Jetzt ist die 1 wahrscheinlicher. Das Problem ist die Zuteilung von 4 Zahlen auf 3 andere. Das geht nunmal nicht gleichmäßig. Genauso wenn man 2^32 Zahlen auf 1000 Zahlen aufteilen will. Ein paar davon sind dann immer ein kleines bisschen wahrscheinlicher als die anderen.

O.K. dann verstehen wir uns.

Jester

Asteroid schrieb:

2.) Ich ziehe n-1 Bits und addiere sie. Das ist aber nicht mehr in Polynomialzeit in Bezug auf die Eingabelänge machbar (denn mit n Bits kriege ich 2^n Zahlen).

Und gleichverteilt ist das auch nicht mehr... 0 ist viel unwahrscheinlicher als n/2 mit dieser Technik.

@Jester: Ja, siehe meinen letzten Beitrag. Hab's schon selber gemerkt.

Zu dem Thema gab es mal einen sehr ausführlichen und sehr schönen Artikel im Foren-Magazin.

Jester

Mups schrieb:

Zu dem Thema gab es mal einen sehr ausführlichen und sehr schönen Artikel im Foren-Magazin.

Der sich allerdings nicht mit derselben Fragestellung beschäftigt... er will weder Zahlen wegwerfen, weil das zumindest theoretisch lange dauern darf, noch will er viel mehr also die echt nötige Anzahl an Bits ziehen.

Vielleich erstmal ne einfachere Frage, wie erzeugt man Zahlen 0,1,2 zufällig und gleichverteilt wenn man nur 0en und 1en ziehen darf?

Bashar

Gar nicht. Wenn man nur beschränkt viele Ziehungen zulässt, ist die Wahrscheinlichkeit für jedes Ereignis eine Summe aus Zweierpotenzen (und 1/3 ist keine solche).