Ist Ablehnungsabtastung der einzige Weg, um eine wirklich gleichmäßige Verteilung von Zufallszahlen zu erreichen?

21

Angenommen, wir haben einen Zufallsgenerator, der Zahlen im Bereich [0..R1] mit gleichmäßiger Verteilung ausgibt, und wir müssen Zufallszahlen im Bereich [0..N1] mit gleichmäßiger Verteilung generieren .

Angenommen, N<R und N teilen nicht gleichmäßig R; Um eine wirklich gleichmäßige Verteilung zu erhalten , können wir die Methode der Rückweisungsabtastung verwenden:

  • wenn k die größte ganze Zahl ist, so dass kN<R
  • wähle eine Zufallszahl r in [0..R1]
  • wenn r<kN ist, wird r ausgegebenrmodN , versuchen Sie es ansonsten mit anderen Zufallszahlen r ', r ", ..., bis die Bedingung erfüllt ist
Ist die Ablehnungsabtastung der einzige Weg, um eine wirklich gleichmäßige diskrete Verteilung zu erhalten?

Wenn die Antwort ja ist, warum?

Hinweis: Wenn die Idee dieselbe: eine Zufallszahl in , zum Beispiel wobei eine Zufallszahl im Bereichr ' [ 0 .. R m - 1 ] , R m > = N r ' = R ( . . . R ( R r 1 + r 2 ) . . . ) + R m r i [ 0 .. R - 1 ]N>Rr[0..Rm1],Rm>=Nr=R(...R(Rr1+r2)...)+rmri[0..R1]

Vor
quelle

Antworten:

13

Ja und nein, je nachdem, was Sie mit "der einzige Weg" meinen. Ja, da es keine Methode gibt, deren Beendigung garantiert ist, ist das Beste, was Sie tun können (für generische Werte von und R ), ein Algorithmus, der mit Wahrscheinlichkeit 1 endet. Nein, Sie können die "Verschwendung" so klein wie möglich machen wie es Dir gefällt.NR

Warum eine garantierte Kündigung generell unmöglich ist

Nehmen wir an, dass Sie eine deterministische Berechnung Engine haben (eine Turing - Maschine oder was auch immer Ihr Boot schwimmt) sowie ein Orakel , das zufällige Elemente des erzeugt -elementigen Satz [ 0 .. R - 1 ] . Ihr Ziel ist es, ein Element der N- Elementmenge [ 0 , N - 1 ] zu erzeugen . Die Leistung Ihres Motors hängt nur von der Reihenfolge der vom Orakel zurückgegebenen Werte ab. es ist eine Funktion f dieser potentiell unendlichen Folge ( r 0 , r 1 , r 2 , )R[0..R1]N[0,N1]f(r0,r1,r2,).

Angenommen, Ihr Motor ruft das Orakel höchstens Mal an. Es kann Spuren geben, für die das Orakel weniger als m- mal aufgerufen wird. Wenn dies der Fall ist, wird die Ausgabe nicht geändert, wenn das Orakel zusätzliche Male aufgerufen wird, sodass es immer genau m Mal aufgerufen wird . Ohne Verlust der Allgemeinheit nehmen wir also an, dass das Orakel genau m- mal genannt wird. Dann ist die Wahrscheinlichkeit des Ergebnisses x die Anzahl der Folgen ( r 0 , , r m - 1 ), so dass f ( r 0 , , r m -mmmmx(r0,,rm1). Da das Orakel ein einheitlicher Zufallsgenerator ist, ist jede Sequenz gleich wahrscheinlich und hat die Wahrscheinlichkeit1 / R m . Daher hat die Wahrscheinlichkeit jedes Ergebnisses die FormA / R m, wobeiAeine ganze Zahl zwischen0und R m ist .f(r0,,rm1)=x1/RmA/RmA0Rm

Wenn R m für einige m dividiert , können Sie eine gleichmäßige Verteilung über N Elemente erzeugen, indem Sie den Zufallsgenerator m- mal aufrufen (dies wird dem Leser als Übung überlassen). Andernfalls ist dies unmöglich: Es gibt keine Möglichkeit, ein Ergebnis mit der Wahrscheinlichkeit 1 / N zu erhalten . Beachten Sie, dass die Bedingung gleichbedeutend ist mit der Aussage, dass alle Primfaktoren von N auch Faktoren von R sind (dies ist toleranter als das, was Sie in Ihrer Frage geschrieben haben). Sie können beispielsweise ein zufälliges Element aus 4 mit einer 6-seitigen Fair auswählen sterben, obwohl 4 6) nicht teilt.NRmmNm1/NNR

Abfall reduzieren

In Ihrer Strategie, wenn , Sie müssen nicht sofort neu zeichnen. Intuitiv ist in [ k noch ein wenig Entropie übrigrkN das Sie im Mix behalten können.[kN..R1]

Nehmen Sie für einen Moment an, dass Sie tatsächlich für immer Zufallszahlen unter generieren und Sie generieren jeweils u davon, indem Sie d- Draws machen. Wenn Sie für diese gruppierte Generation eine einfache Stichprobe zur Zurückweisung durchführen, beträgt der Abfall über d draws R d - kNudd , dh der RestRdmodNudividiert durch die Anzahl der Ziehungen. Dies kann nurgcd(R,N) sein. WennRundNKoprime sind, können Sie die Verschwendung beliebig klein machen, indem Sie ausreichend große Werte fürd auswählen. Für allgemeine Werte vonRundNist die Berechnung komplizierter, da Sie die Erzeugung vongcd(R,N)undN/gcd(R)berücksichtigen müssenRdkNudRdmodNugcd(R,N)RNdRNgcd(R,N) getrennt, aber auch hier kann man den Abfall mit ausreichend großen Gruppen beliebig klein machen.N/gcd(R,N)

In der Praxis lohnt es sich auch bei relativ ineffizienten Zufallszahlen (z. B. in der Kryptographie) selten, etwas anderes als eine einfache Zurückweisungsabtastung durchzuführen, es sei denn, ist klein. Beispielsweise schreitet in der Kryptographie, wo R typischerweise eine Potenz von 2 und N typischerweise Hunderte oder Tausende von Bits ist, die Erzeugung einheitlicher Zufallszahlen gewöhnlich durch direktes Zurückweisungsabtasten in dem gewünschten Bereich voran.NRN

Gilles 'SO - hör auf böse zu sein'
quelle
Der erste Beweis ist fehlerhaft: Die Existenz von ist zu stark. Wir können eine Maschine haben, die beliebig viele Elemente verbraucht, aber immer terminiert. Grundsätzlich wollen wir eine Sequenz ausschließen (die niemals endende), aber Sie schließen alle bis auf endlich viele aus. m
Raphael
@Raphael Ich bin nicht sicher, ob ich verstehe, was du meinst. Können Sie ein Beispiel für eine solche Maschine geben?
Gilles 'SO- hör auf böse zu sein'
Ah, meine Sorge war zu allgemein. Hier haben Sie - mangels Input - Recht. Wenn alle Berechnungen enden, gibt es endlich viele (keine Eingabe, endliche Anzahl von Entscheidungen pro Schritt, ergo einen endlichen Baum), daher gibt es einen längsten, der Ihnen gibt . m
Raphael
@Raphael Ihr Kommentar lässt mich an eine bessere Präsentation für ein TCS-Publikum denken: Machen Sie das RNG zur Eingabe eines TM anstelle eines Orakels. Wir gehen davon aus, dass das TM terminiert (ansonsten ist der Algorithmus falsch). Wenn es ein , das unabhängig von der Eingabe höchstens m Eingabezellen betrachtet, kann <bla bla, teilbar durch R m bla, keine N gleichwahrscheinlichen Ergebnisse haben>. Andernfalls beträgt für alle m die Wahrscheinlichkeit, dass mindestens m Draws erforderlich sind, mindestens R - m . mmRmNmmRm
Gilles 'SO- hör auf böse zu sein'
1
@Raphael: König's Lemma zeigt, dass es tatsächlich eine Obergrenze für die Laufzeit gibt, wenn die Maschine immer terminiert. Dies funktioniert so lange, wie die Ausgabemenge des RNG endlich ist (und ansonsten ist sie trivial falsch).
Yuval Filmus
6

Shannons Quellcodierungssatz zeigt, dass Sie Stichproben (im Durchschnitt) vom Typ [ 0 , , R - 1 ] benötigen , um eine Zufallszahl vom Typ [ 0 , , N ] zu generieren - 1 ] . Genauer gesagt gibt Shannon einen (ineffizienten) Algorithmus an, der bei m Abtastwerten des ersten Typs m ausgibt ( log N / log R - ϵ ).logN/logR[0,,R1][0,,N1]mm(logN/logRϵ)Proben des zweiten Typs mit hoher Wahrscheinlichkeit. Er zeigt auch, dass die Ausgabe von Abtastwerten mit hoher Wahrscheinlichkeit unmöglich ist.m(logN/logR+ϵ)

Der Satz von Shannon funktioniert auch im allgemeineren Fall einer verzerrten Eingabeverteilung (und wahrscheinlich auch einer verzerrten Ausgabeverteilung). In diesem Fall müssen Sie den Logarithmus durch die Entropie ersetzen. Während der vom Theorem gegebene Algorithmus zufällig definiert wird, ist es in einigen Fällen möglich, ihn zu derandomisieren (auf Kosten einer etwas schlechteren Leistung).

Yuval Filmus
quelle
5

Nein, die Probenahme bei Ablehnung ist keineswegs die einzige Vorgehensweise. Bedauerlicherweise ist, wenn man bedenkt, dass Computer alle Informationen als Bits speichern und daher nur zufällige Informationsbits manipulieren können, jeder Algorithmus zum Zeichnen einer einheitlichen Zufallsvariablen des Bereichs unendlich, wenn die binäre Basisentwicklung von N unendlich ist.NN

Dieses Theorem ist ein klassisches Ergebnis von Knuth und Yao (1976), die das Gerüst von DDG-Bäumen (diskrete Verteilung erzeugende Bäume) entwickelt haben.

Die von Gilles offen gelegten Methoden sind die typische Vorgehensweise, um den Abfall zu verringern, der durch die Ablehnung entsteht. Wenn man jedoch folgende Knuth- und Yao-Bäume erzeugen kann, ist dies viel, viel effizienter - im Durchschnitt 96% der zufälligen Bits werden gerettet.

Weitere Informationen dazu habe ich im folgenden CStheory-Beitrag gegeben .

Jérémie
quelle