Simulieren Sie einen fairen Würfel mit einem vorgespannten Würfel

Wie kann bei einem vorgespannten seitigen Die eine Zufallszahl im Bereich gleichmäßig erzeugt werden? Die Wahrscheinlichkeitsverteilung der Würfelflächen ist nicht bekannt. Es ist lediglich bekannt, dass jede Fläche eine Wahrscheinlichkeit ungleich Null aufweist und dass die Wahrscheinlichkeitsverteilung bei allen Würfen gleich ist (insbesondere sind die Würfe unabhängig). Dies ist die offensichtliche Verallgemeinerung von fairen Ergebnissen mit unfairen Folgen .$N$$[1,N]$

Computerwissenschaftlich ausgedrückt haben wir ein Orakel, das die Würfelwürfe darstellt: so dass ungleich Null und unabhängig von . Wir suchen nach einem deterministischen Algorithmus der durch parametrisiert ist (dh kann ), so dass . Der Algorithmus muss mit der Wahrscheinlichkeit 1 enden, dh der Wahrscheinlichkeit, dass mehr als$D : \mathbb{N} \to [1,N]$$p_i = P(D(k)=i)$$k$$A$$D$$A$$D$$P(A()=i) = 1/N$$A$$n$ Anrufe $D$ konvergieren muss $0$ als $n\to\infty$ .

Für $N=2$ (simulieren Sie eine faire Münze aus Münzwürfen mit einer voreingenommenen Münze) gibt es einen bekannten Algorithmus:

• Wiederholen Sie den Vorgang zweimal, bis die beiden Würfe unterschiedliche Ergebnisse liefern ((Kopf, Zahl) oder (Zahl, Zahl)). Mit anderen Worten, Schleife für $k = 0..\infty$ bis $D(2k+1) \ne D(2k)$
• Gibt 0 zurück, wenn das letzte Paar von Flips war (Heads, Tails) und 1, wenn es war (Tails, Heads). Mit anderen Worten, gebe $D(2k)$ wobei $k$ der Index ist, an dem die Schleife beendet wurde.

Ein einfacher Weg, um einen unverfälschten Würfel aus einem voreingenommenen Würfel zu machen, ist die Verwendung der Münzwurf-Unbiasing-Methode, um eine faire Münze zu erstellen, und einen fairen Würfel mit Ablehnungsabtastung, wie beim Unbiasing von Sequenzen . Aber ist das optimal (für generische Werte der Wahrscheinlichkeitsverteilung)?

Insbesondere ist meine Frage: Was ist ein Algorithmus, der die kleinste erwartete Anzahl von Anrufen an das Orakel erfordert ? Wenn die Menge der erreichbaren erwarteten Werte offen ist, wie lautet die untere Schranke und welche Klasse von Algorithmen konvergiert gegen diese untere Schranke?

Für den Fall, dass verschiedene Algorithmusfamilien für verschiedene Wahrscheinlichkeitsverteilungen optimal sind, konzentrieren wir uns auf fast faire Würfel: Ich suche einen Algorithmus oder eine Algorithmusfamilie, die für Verteilungen wie optimal ist p i - 1 / N | < $\forall i, \bigl|p_i - 1/N\bigr| \lt \epsilon$ für einige $\epsilon \gt 0$ .

Der folgende Aufsatz beantwortet eine nahe Variante dieser Frage: Die effiziente Konstruktion einer nicht voreingenommenen Zufallssequenz, Elias 1972 .

Die Frage scheint folgende zu sein: Wenn Sie Zugriff auf diese voreingenommene unabhängige Quelle haben, geben Sie eine Folge von Zufallszahlen in (beachten Sie den Unterschied zu Ihrer Frage, in der nur ein Ausgabesymbol angefordert wird). Da die Länge der gewünschten Ausgabe unendlich ist, ist die "Effizienz" des Schemas in der Arbeit (die wie eine natürliche Verallgemeinerung von Neumanns aussieht) gleich , was meiner Meinung nach bedeutet, dass eine Eingabe mit der Entropie in konvertiert wird eine Ausgabe der Entropie nähert sich .$[1,N]$$1$$h$$h$

Die Frage scheint sich bei dieser Formulierung viel besser zu verhalten, als eine einzelne Ausgangsziffer anzufordern, da zum Beispiel, wenn wir Abtastwerte zeichnen und am Ende eine Ausgabe mit vielen Informationen erhalten (zum Beispiel sind alle Eingangssymbole verschieden). Dann können wir all diese Informationen verwenden, um viele Ausgabesymbole zu erzeugen, während mit der hier formulierten Frage alle Informationen, die über die Informationen hinausgehen, die zur Erzeugung eines Ausgabesymbols verwendet wurden, verloren gehen.$N$$N$

Ich glaube, dass das Schema wiederholt Draws nimmt, sich die Sequenz ansieht und einige Ausgaben oder die leere Zeichenkette abbildet. Vielleicht gibt es eine Möglichkeit, das Schema für Ihre Frage zu verbessern, indem Sie sich Präfixe ansehen und anhalten, wenn wir "genug" Informationen haben, um ein Symbol auszugeben. Ich weiß es nicht.$N$

Die Methode, die Sie für verallgemeinert. Wir verwenden, dass alle Permutationen von auch mit einem vorgespannten Würfel gleich wahrscheinlich sind (da die Walzen unabhängig sind). Daher können wir so lange rollen, bis wir eine Permutation wie die letzten Rollen sehen und die letzte Rolle ausgeben.$N=2$$[1..N]$$N$

Eine allgemeine Analyse ist schwierig; Es ist jedoch klar, dass die erwartete Anzahl von Rollen in schnell da die Wahrscheinlichkeit, dass bei einem bestimmten Schritt eine Permutation auftritt, gering ist (und nicht unabhängig von den Schritten davor und danach, was schwierig ist). Es ist jedoch größer als für festes , sodass die Prozedur fast sicher (dh mit der Wahrscheinlichkeit ) beendet wird.$N$$0$$N$$1$

Für festes wir eine Markov-Kette über der Menge der Parikh-Vektoren konstruieren, die sich zu summieren , die Ergebnisse der letzten Würfe zusammenfassen und die erwartete Anzahl von Schritten bestimmen, bis wir zum ersten mal . Dies ist ausreichend, da alle Permutationen, die einen Parikh-Vektor gemeinsam haben, gleich wahrscheinlich sind. Die Ketten und Berechnungen sind auf diese Weise einfacher.$N$$\leq N$$N$$(1,\dots,1)$

Angenommen , wir im Zustand sind mit . Dann ist die Wahrscheinlichkeit , ein Element (dh der nächste Wurf ist ), immer gegeben durch$v=(v_1,\dots,v_N)$$\sum_{i=1}^n v_i \leq N$$i$$i$

$\qquad\displaystyle \operatorname{Pr}[\text{gain } i] = p_i$ .

Andererseits ist die Wahrscheinlichkeit gegeben , ein Element aus der Geschichte fallen zu lassen durch$i$

$\qquad\displaystyle \operatorname{Pr}_v[\text{drop } i] = \frac{v_i}{N}$

Immer wenn (und sonst ), weil alle Permutationen mit dem Parikh-Vektor gleich wahrscheinlich sind. Diese Wahrscheinlichkeiten sind unabhängig (da die Rollen unabhängig sind), sodass wir die Übergangswahrscheinlichkeiten wie folgt berechnen können:$\sum_{i=1}^n v_i = N$$0$$v$

$\qquad\begin{align*} &\operatorname{Pr}[v \to (v_1,\dots,v_j + 1,\dots,v_N)] \\ &\qquad=\begin{cases} \operatorname{Pr}[\text{gain } j] &, \sum v < N \\ 0 &, \text{ else} \end{cases}\;,\\[3ex] &\operatorname{Pr}[v \to (v_1,\dots,v_i - 1, \dots v_j + 1,\dots,v_N)] \\ &\qquad=\begin{cases} 0 &, \sum v < N \lor v_i=0 \lor v_j=N \\ \operatorname{Pr}_v[\text{drop } i] \cdot \operatorname{Pr}[\text{gain } j] &, \text{ else} \end{cases}\;\text{ and}\\[3ex] &\operatorname{Pr}[v \to v] \\ &\qquad=\begin{cases} 0 &, \sum v < N \\ \sum_{v_i \neq 0} \operatorname{Pr}_v[\text{drop } i] \cdot \operatorname{Pr}[\text{gain } i] &, \text{ else} \end{cases}\;; \end{align*}$

Alle anderen Übergangswahrscheinlichkeiten sind Null. Der einzelne absorbierende Zustand ist , der Parikh-Vektor aller Permutationen von .$(1,\dots,1)$$[1..N]$

Für die resultierende Markov-Kette¹$N=2$

^{[ Quelle ]}

mit der erwarteten Anzahl von Schritten bis zur Absorption

$\qquad\displaystyle \mathbb{E}\,\text{steps} = 2 p_0 p_1 \cdot 2 + \sum_{i\geq 3} (p_0^{i-1}p_1 + p_1^{i-1}p_0)\cdot i = \frac{1 - p_0 + p_0^2}{p_0-p_0^2}\;,$

zur Vereinfachung gilt . Wenn nun, wie vorgeschlagen, für etwas , dann$p_1=1-p_0$$p_0 = \frac{1}{2} \pm \epsilon$$\epsilon \in [0,\frac{1}{2})$

$\qquad\displaystyle \mathbb{E}\,\text{steps} = \frac{3 + 4\epsilon^2}{1 - 4\epsilon^2}$ .

Für und Gleichverteilungen (der beste Fall) habe ich die Berechnungen mit Computeralgebra² durchgeführt; da der zustandsraum schnell explodiert, sind größere werte schwer zu bewerten. Die Ergebnisse (aufgerundet) sind$N \leq 6$

^{Plots zeigen als Funktion von ; links eine regelmäßige und rechts eine logarithmische Darstellung.$\mathbb{E}\,\text{steps}$$N$}

Das Wachstum scheint exponentiell zu sein, aber die Werte sind zu klein, um gute Schätzungen zu liefern.

In Bezug auf die Stabilität gegen Störungen des wir die Situation für :$p_i$$N=3$

^{Der Plot zeigt als Funktion von und ; natürlich ist .$\mathbb{E}\,\text{steps}$$p_0$$p_1$$p_2 = 1 - p_0 - p_1$}

Unter der Annahme, dass ähnliche Bilder für größere (Kernel stürzt ab und berechnet symbolische Ergebnisse auch für ), scheint die erwartete Anzahl von Schritten für alle außer den extremsten Auswahlen ziemlich stabil zu sein (fast alle oder keine Masse bei einigen ).$N$$N=4$$p_i$

Zum Vergleich ist es höchstens erforderlich , eine durch ein beeinflusste Münze zu simulieren (z. B. indem die Ergebnisse so gleichmäßig wie möglich auf und werden), um eine faire Münze zu simulieren und schließlich eine bitweise Zurückweisungsabtastung durchzuführen$\epsilon$$0$$1$

$\qquad\displaystyle 2\lceil \log N \rceil \cdot \frac{3 + 4\epsilon^2}{1 - 4\epsilon^2}$

Würfel rollen in Erwartung - du solltest dich wahrscheinlich daran halten.

1. Da die Kette in absorbiert, werden die grau unterlegten Kanten niemals durchlaufen und beeinflussen die Berechnungen nicht. Ich füge sie nur der Vollständigkeit halber und zur Veranschaulichung hinzu.$(11)$
2. Implementierung in Mathematica 10 ( Notebook , Bare Source ); Entschuldigung, es ist das, was ich für diese Art von Problemen weiß.

Nur eine kurze Bemerkung zum Fall . Nimm eine große Anzahl und probiere Würfe des Würfels. Wenn Sie Köpfe haben, können Sie Bits extrahieren . Unter der Annahme , die Form wird vorgespannt ist , ist die durchschnittliche Menge von Informationen Um diese Schätzung zu erhalten, verwenden Sie die Tatsache, dass die Binomialvariable zusammen mit der Schätzung um konzentriert ist . Wenn größer wird, erhalten wir die optimale Rate von$N = 2$$m$$m$$k$$\log \binom{m}{k}$$p$

Sie können dieselbe Methode für allgemeines , und Sie werden wahrscheinlich dasselbe . Diese Algorithmen sind nur im Grenzbereich optimal, und es kann Algorithmen geben, die den Grenzbereich schneller erreichen als diese. Tatsächlich habe ich es versäumt, die Geschwindigkeit der Konvergenz zu berechnen - es könnte eine interessante Übung sein.$N$$H(\vec{p})$

Ich würde die folgende Antwort riskieren.

Der spezielle Fall von 2, den Sie oben erwähnt haben, ist der spezielle Fall der Erweiterung (wobei prob von Kopf und prob von Schwanz ist), der Ihnen einen Term Dies bedeutet, dass Sie für einen Fall und erhalten können für den anderen fall. Sie müssen die Abtastung wiederholen, bis entweder oder (Kopf-Schwanz oder Schwanz-Kopf) angezeigt wird. Wenn Sie diese als Simulation verwenden, geben Sie die gleiche Wahrscheinlichkeit an.$(p + q)^2$$p$$q$$2pq$$pq$$qp$$pq$$qp$

Wenn , haben Sie die Erweiterung die Ihnen den Term . In diesem Fall tun Sie dasselbe, indem Sie in drei aufeinanderfolgenden Versuchen alle drei Ergebnisse , , in einer bestimmten Reihenfolge abtasten .$N=3$$(p + q + r)^3$$pqr$$q$$p$$r$

Gleiches gilt für den allgemeinen Fall. Wenn ich sorgfältig überlege, muss ich sagen, dass der Fall 2 der beste Fall ist, in dem man die Dinge in der Erweiterung herausarbeiten kann. Wenn gibt es 6 verschiedene Sequenzen für und es gibt viele andere Terme in der Erweiterung. Ich würde mich mit anderen Begriffen, bei denen es viel mehr Ergebnisse gibt, ziemlich unwohl fühlen.$N=3$$pqr$

.

Extra:

Dies bringt mich dazu, über die Idee nachzudenken, einfach eine Menge abzutasten, um die Wahrscheinlichkeit jedes Würfelergebnisses abzuschätzen. In diesem einfachsten Fall eines Ein-Schicht-Modells ohne versteckte Schicht (ein bekanntes Modell) können wir eine Grenze ausarbeiten, um zu folgern, dass die Schätzung schnell konvergiert. Tatsächlich zeigt uns die Chernoff-Grenze, dass der Fehler exponentiell abnimmt, wenn die Abtastung (linear) zunimmt.

Nun, da eine gute Schätzung der Wahrscheinlichkeiten für jede Seite der Würfel bekannt ist, gibt es viele Optionen. Eine Möglichkeit besteht darin, dass wir die obige Erweiterung erneut durchführen können, aber dieses Mal können wir möglicherweise viele andere Begriffe in der Erweiterung verwenden, die denselben Wert haben wie (oder ein beliebiger Begriff, der diesen Wert hat) Sie verwenden als basierte Sequenz). Dies wird ein bisschen effizienter sein, da mehr Begriffe in der Erweiterung verwendet werden. Aber ich gebe zu, ich weiß nicht, ob dies die geringste Anzahl von Anrufen beim Orakel zur Folge hat, um eine Garantie für die jeweiligen Voraussetzungen (z. B. Vertrauensparameter) zu erhalten, sofern diese gegeben sind.$\prod_{i=1}^{i=n} p_i$

Trotzdem ist dieser Ansatz eine Antwort auf verschiedene Aspekte der Frage. Die Frage stellt die Frage nach einer garantierten vollkommenen Unparteilichkeit auf Kosten einer potenziell großen Stichprobe (obwohl die Wahrscheinlichkeit gering ist). Bei diesem Ansatz wird nur die endliche Stichprobe mit dem Parameter "An das Vertrauen gebunden" verwendet. Daher halte ich diesen Ansatz nicht für angemessen, obwohl er sehr interessant ist.