Ist die Ablehnung der Probenahme der einzige Weg ist, um eine wirklich gleichmäßige Verteilung der Zufallszahlen?

Question

Angenommen, wir haben einen Zufallsgenerator, der Ausgänge zahlen im Bereich $[0..R-1]$ mit gleichmäßige Verteilung und wir müssen die Zufallszahlen im Bereich $[0..N-1]$ mit uniform Verteilung.

Angenommen, $N < R$ und $N$ nicht gleichmäßig aufteilen $R$;um eine wirklich gleichmäßige Verteilung wir verwenden können die rejection sampling Methode:

• wenn $k$ die größte ganze Zahl, so dass $k N < R$
• wählen Sie eine zufällige Zahl $r$ in $[0..R-1]$
• wenn $r < k N$ Ausgabe $r \mod N$, ansonsten halten Sie versuchen, mit anderen zufälligen zahlen r', r", ...bis die Bedingung erfüllt ist

Ist die Ablehnung der Probenahme der einzige Weg ist, um eine wirklich gleichmäßige diskrete Verteilung?

Wenn die Antwort ja ist, warum?

Hinweis:wenn $N > R$ die Grundidee ist die gleiche:generieren Sie eine zufällige Zahl $r$ in $[0..R^m-1], R^m >= N$, zum Beispiel $r' = (R...R(R-r_1 + r_2)...)+r_m$, wobei $r_i$ ist eine Zufallszahl im Bereich $[0..R-1]$

Answer 1

Ja und Nein, je nachdem, was meinen Sie mit "der einzige Weg".Ja, es gibt keine Methode, die ist garantiert, um zu beenden, das beste, was Sie tun können (für Allgemeine Werte von $N$ und $R$) ist ein Algorithmus, der wird mit Wahrscheinlichkeit 1.Nein, dass können Sie machen die "Abfälle" als kleine, wie Sie möchten.

Warum garantiert der Kündigung wird im Allgemeinen unmöglich

Angenommen, Sie haben eine deterministische Berechnung engine (eine Turing-Maschine oder was auch immer schwimmt Ihr Boot), plus ein Orakel, das generiert zufällige Elemente von $R$-element-set $[0..R-1]$.Ihr Ziel ist es, erzeugen Sie ein element des $N$-element-set $[0,N-1]$.Die Leistung von Ihre Motor hängt nur von der Reihenfolge der Werte, die von der oracle-Datenbank.es ist eine Funktion $f$ von, dass potenziell unendliche Sequenz $(r_0, r_1, r_2, \ldots)$.

Angenommen, dass Ihr Motor ruft die oracle-höchstens $m$ mal.Es könnte Spuren, für die die oracle genannt wird weniger als $m$ mal;wenn dem so ist, ruft die oracle-extra mal so, dass es wird immer dann aufgerufen, genau $m$ mal nicht ändern die Ausgang.So können Sie ohne Verlust der Allgemeinheit gehen wir davon aus, dass Sie die oracle heißt genau $m$ mal.Dann ist die Wahrscheinlichkeit, dass das Ergebnis $x$ ist die Anzahl der Sequenzen $(r_0, \ldots, r_{m-1})$, so dass $f(r_0, \ldots, r_{m-1}) = x$.Da das Orakel ist eine einheitliche random generator, jede Sequenz ist gleichwahrscheinlichen und hat die Wahrscheinlichkeit $1/R^m$.Damit die Wahrscheinlichkeit jedes Ergebnisses ist von der form $A/R^m$, wobei $A$ ist eine ganze Zahl zwischen $0$ und $R^m$.

Wenn $N$ teilt $R^m$ für einige $m$, dann können Sie erzeugen eine gleichmäßige Verteilung über $N$ - Elemente durch Aufruf der Zufallsgenerator $m$ mal (das ist Links als übung für den Leser).Anders ist das unmöglich:es gibt keine Möglichkeit zu erhalten ein Ergebnis mit einer Wahrscheinlichkeit von $1/N$.Beachten Sie, dass die Bedingung ist äquivalent zu sagen, dass alle $N$'s prime Faktoren sind auch Faktoren von $R$ ist (dies ist weniger restriktiv als das, was du geschrieben hast in deiner Frage;zum Beispiel, können Sie wählen Sie eine zufällige element unter 4 mit einer 6-seitigen fairen sterben, obwohl 4 nicht teilen 6).

Die Verringerung der Abfälle

In Ihrer Strategie, wenn $r \ge k\,N$, die Sie nicht haben, um re-ziehen Sie sofort.Intuitiv, es ist ein bisschen Entropie Links in $[k:\, N ..R-1]$, die Sie können halten in der Mischung.

Übernehmen für einen moment, dass Sie tatsächlich halten, erzeugen von Zufallszahlen unter $N$, für immer, und generieren Sie $u$ an einem Zeit durch $d$ zieht.Wenn Sie eine einfache Ablehnung der Probenahme auf dieser gruppiert generation, die Abfälle, die über $d$ zieht, ist $\dfrac{R^d - k\,N^u}{d}$, D. H.der Rest $R^d \mathbin{\mathrm{mod}} N^u$ geteilt durch die Anzahl der Ziehungen.Dies kann so wenig wie $\gcd(R,N)$.Wenn $R$ und $N$ sind coprime, können Sie die Abfälle beliebig kleine durch die Auswahl von hinreichend große Werte von $d$.Für Allgemeine Werte von $R$ und $N$, die Berechnung ist komplizierter, da Sie die Notwendigkeit zu berücksichtigen, die Generierung von $\gcd(R,N)$ und $N/\gcd(R,N)$ getrennt, aber wieder können Sie die Abfälle beliebig klein, mit ausreichend großen Gruppen.

In der Praxis, auch mit relativ ineffizient Zufallszahlen (z.B.in der Kryptographie), ist es selten Wert, etwas zu tun, aber einfache Ablehnung Probenahme, es sei denn, $N$ klein ist.Zum Beispiel in der Kryptographie, wobei $R$ ist normalerweise eine Potenz von 2 ist und $N$ ist in der Regel Hunderte oder Tausende von bits, uniform random number generation in der Regel Erlöse, die durch gerade rejection sampling-in den gewünschten Bereich.

Answer 2

Shannons Quellcodierungssatz zeigt, dass Sie in gewisser Weise $ log n/ log r $ Samples (im Durchschnitt) des Typs $ [0, ldots, R-1] $ benötigen, um eine zufällige Anzahl von der zu generieren Geben Sie $ [0, ldots, n-1] $ ein. Genauer gesagt gibt Shannon einen (ineffizienten) Algorithmus an, der $ M $ -Modples des ersten Typs angegeben ist, $ m ( log n/ log r - epsilon) $ $ proben des zweiten Typs mit hoher Wahrscheinlichkeit ausgibt. Er zeigt auch, dass die Ausgabe von $ m ( log n/ log r + epsilon) $ $ proben mit hoher Wahrscheinlichkeit unmöglich ist.

Shannons Theorem arbeitet auch im allgemeineren Fall einer verzerrten Eingangsverteilung (und wahrscheinlich auch verzerrte Ausgangsverteilung). In diesem Fall müssen Sie den Logarithmus durch die Entropie ersetzen. Während der vom Theorem angegebene Algorithmus zufällig definiert ist, ist es in einigen Fällen möglich, ihn zu derandomisieren (auf Kosten einer etwas schlechteren Leistung).

Answer 3

Tatsächlich, nein, die Ablehnungsabtastung ist weit davon entfernt, die einzige Möglichkeit des Fortfahrens zu finden. In Anbetracht der Tatsache, dass Computer alle Informationen als Bits speichern und daher nur zufällige Informationsbits manipulieren können, ist jeder Algorithmus, um eine einheitliche Zufallsvariable von $ n $ zu zeichnen, unendlich, wenn die binäre Basisentwicklung von $ n $ unendlich ist.

Dieser Satz ist ein klassisches Ergebnis von Knuth und Yao (1976), die den Rahmen von DDG-Bäumen (diskrete Verteilung erzeugen Bäume) entwickelt haben.

Die von Killes ausgesetzten Methoden sind die typische Art von Dingen, die durchgeführt wurden, um den durch Abstoßung entstandenen Abfälle zu mildern. Wenn man jedoch nach Knuth und Yaos Bäumen erzeugen kann, ist dies viel, viel effizienter - durchschnittlich 96% der zufälligen Bits sind gerettet.

Ich habe im Folgenden weitere Informationen dazu gegeben CStheory Post.