Pfeile, Würfel und Münzen: Diskrete Verteilungsalgorithmen

Ich habe Stack Overflow einmal eine Frage zur Datenstruktur für das Betrügen von Würfeln gestellt . Insbesondere interessierte mich die Antwort auf diese Frage: „Wenn wir einen n-Facettenknochen haben, dessen Gesicht ich wahrscheinlich herausfallen werde. Was ist die effektivste Datenstruktur zur Simulation der Rollen eines solchen Knochens? “

Diese Datenstruktur kann für viele Aufgaben verwendet werden. Sie können es beispielsweise verwenden, um ehrliche Hex-Würfe zu simulieren und die Wahrscheinlichkeit zuzuweisen $$$\ frac {1} {6}$ jede Seite des Knochens oder um eine faire Münze durch Nachahmung eines bilateralen Knochens zu simulieren, dessen Wahrscheinlichkeit, aus jeder Seite herauszufallen, gleich ist $$$\ frac {1} {2}$ . Sie können diese Datenstruktur auch verwenden, um die Summe zweier ehrlicher Hex-Knochen direkt zu simulieren, indem Sie einen 11-seitigen Knochen (mit den Flächen 2, 3, 4, ..., 12) erstellen, dessen Fläche jeweils ein Wahrscheinlichkeitsgewicht aufweist, das den Rollen zweier ehrlicher Knochen entspricht. Sie können diese Datenstruktur jedoch auch verwenden, um betrügerische Knochen zu simulieren. Wenn Sie beispielsweise Craps mit einem Knochen spielen, was, wie Sie wissen, nicht ganz ehrlich ist, können Sie diese Datenstruktur verwenden, um viele Knochenrollen zu simulieren und die optimale Strategie zu analysieren. Sie können auch versuchen, ein ähnlich unvollkommenes Roulette-Rad zu simulieren.

Wenn Sie über die Spiele hinausgehen, können Sie diese Datenstruktur bei der Simulation von Robotern anwenden, deren Sensoren bekannte Fehlerstufen aufweisen. Wenn ein Entfernungssensor beispielsweise eine Wahrscheinlichkeit von 95% hat, den korrekten Wert zurückzugeben, eine Wahrscheinlichkeit von 4% für einen zu kleinen Wert und eine Wahrscheinlichkeit von 1% für einen zu hohen Wert, können Sie diese Datenstruktur verwenden, um Lesesensoren zu simulieren, indem Sie ein zufälliges Ergebnis generieren und Sensormessungen simulieren Ergebnis.

Die Antwort auf Stack Overflow hat mich aus zwei Gründen beeindruckt. Erstens wurde mir in der Lösung empfohlen, eine leistungsstarke Technik namens Alias-Methode zu verwenden , die mit bestimmten vernünftigen Annahmen über das Modell der Maschine nach einer einfachen Phase der vorläufigen Vorbereitung in der Lage ist, Knochenrollen über die Zeit zu simulieren $$$O (1)$ . Zweitens war ich noch mehr überrascht, dass dieser Algorithmus seit Jahrzehnten bekannt ist, aber ich habe ihn nie getroffen! Angesichts des Rechenaufwands für die Simulation würde man erwarten, dass diese Technik viel bekannter ist. Einige Anfragen bei Google gaben mir viele Informationen zu dieser Technik, aber ich konnte keine einzige Website finden, auf der ein intuitives Verständnis und eine Erklärung dieser Technik zusammenkamen.

Dieser Artikel ist mein Versuch, einen kurzen Überblick über die verschiedenen Ansätze zur Simulation von Betrugsknochen zu geben, von einfachen und sehr unpraktischen Techniken bis zu einer sehr optimierten und effektiven Alias-Methode. Ich hoffe, dass ich in der Lage sein werde, verschiedene Wege zu vermitteln, um die Aufgabe intuitiv zu verstehen und wie jeder von ihnen einen neuen Aspekt der Simulation eines betrügerischen Knochens hervorhebt. Mein Ziel für jeden Ansatz ist es, eine motivierende Idee, einen grundlegenden Algorithmus, einen Treue-Beweis und eine Analyse der Laufzeit (in Bezug auf erforderliche Zeit, Speicher und Zufälligkeit) zu untersuchen.

Eintrag

Bevor wir zu den spezifischen Details der verschiedenen Techniken übergehen, standardisieren wir zunächst die Terminologie und Notation.

In der Einleitung des Artikels habe ich den Begriff „Betrugsknochen“ verwendet, um ein verallgemeinertes Szenario zu beschreiben, in dem es eine endliche Menge von Ergebnissen gibt, von denen jedes eine Wahrscheinlichkeit hat. Formal wird dies als diskrete Wahrscheinlichkeitsverteilung bezeichnet , und die Aufgabe, einen betrügerischen Knochen zu simulieren, wird als Abtastung aus einer diskreten Verteilung bezeichnet .

Um unsere diskrete Wahrscheinlichkeitsverteilung (Betrüger-Knochen) zu beschreiben, nehmen wir an, dass wir eine Menge von n Wahrscheinlichkeiten haben $$$p_0, p_1, ..., p_ {n - 1}$ im Zusammenhang mit den Ergebnissen $$$0, 1, ..., n - 1$ . Obwohl die Ergebnisse beliebig sein können (Adler / Schwänze, Zahlen auf Knochen, Farben usw.), werde ich das Ergebnis der Einfachheit halber als eine Art positive reelle Zahl betrachten, die einem bestimmten Index entspricht.

Das Arbeiten mit reellen Zahlen auf einem Computer ist die „Grauzone“ des Rechnens. Es gibt viele schnelle Algorithmen, deren Geschwindigkeit allein durch die Fähigkeit bereitgestellt wird, die Grundfunktion einer beliebigen reellen Zahl in einer konstanten Zeit zu berechnen , und numerische Ungenauigkeiten bei der Darstellung von Gleitkommazahlen können einige Algorithmen vollständig zerstören. Bevor ich mit der Diskussion von Algorithmen beginne, die mit Wahrscheinlichkeiten arbeiten, dh in die dunkle Welt der reellen Zahlen eintreten, muss ich daher klären, was ein Computer kann und was nicht.

Im Folgenden gehe ich davon aus, dass alle folgenden Operationen in konstanter Zeit ausgeführt werden können:

• Ergänzung. Subtraktion, Multiplikation, Division und Vergleich beliebiger reeller Zahlen . Wir müssen dies tun, um Wahrscheinlichkeiten zu manipulieren. Dies mag wie eine kühne Annahme erscheinen, aber wenn wir annehmen, dass die Genauigkeit einer reellen Zahl durch ein Polynom der Maschinenwortgröße begrenzt ist (zum Beispiel ein 64-Bit-Double auf einer 32-Bit-Maschine), halte ich dies nicht für zu unvernünftig.
• Erzeugung einer einheitlichen reellen Zahl im Intervall [0, 1). Um die Zufälligkeit zu simulieren, benötigen wir eine Quelle für Zufallswerte. Ich nehme an, wir können in konstanter Zeit eine reelle Anzahl willkürlicher Genauigkeit erzeugen. Dies übertrifft die Fähigkeiten eines echten Computers bei weitem, aber es scheint mir, dass dies für die Zwecke dieser Diskussion akzeptabel ist. Wenn wir uns bereit erklären, einen Teil der Genauigkeit zu opfern, indem wir sagen, dass sich ein beliebiges IEEE-754-Double im Intervall [0, 1] befindet, verlieren wir tatsächlich an Genauigkeit, aber das Ergebnis ist wahrscheinlich für die meisten Anwendungen genau genug.
• Berechnung des Integer Floor (Abrunden) einer reellen Zahl. Dies ist akzeptabel, wenn wir davon ausgehen, dass wir mit IEEE-754 double arbeiten, aber im Allgemeinen ist eine solche Anforderung an einen Computer nicht realisierbar.

Es lohnt sich, die Frage zu stellen - ist es vernünftig anzunehmen, dass wir all diese Operationen effektiv durchführen können. In der Praxis verwenden wir selten Wahrscheinlichkeiten, die mit einer solchen Genauigkeit angegeben sind, dass der Rundungsfehler des IEEE-754-Doppels schwerwiegende Probleme verursachen kann. Daher können wir alle oben genannten Anforderungen erfüllen, indem wir ausschließlich mit dem IEEE-Doppel arbeiten. Wenn wir uns jedoch in einer Umgebung befinden, in der die Wahrscheinlichkeiten genau als rationale Zahlen mit hoher Genauigkeit angegeben werden, können solche Einschränkungen unangemessen sein.

Ehrliche Knochensimulation

Bevor wir zum allgemeineren Fall des Werfens eines beliebigen betrügerischen Knochens übergehen, beginnen wir mit einem einfacheren Algorithmus, der als Baustein für die folgenden Algorithmen dient: Simulation eines ehrlichen Knochens mit n Gesichtern. Zum Beispiel können ehrliche sechseckige Würfelwürfe beim Spielen von Monopoly oder Risk oder das Werfen einer ehrlichen Münze (doppelseitige Würfel) usw. für uns nützlich sein.

Für diesen speziellen Fall gibt es einen einfachen, eleganten und effektiven Algorithmus zur Simulation des Ergebnisses. Der Algorithmus basiert auf der folgenden Idee: Nehmen wir an, wir können wirklich zufällige, gleichmäßig verteilte reelle Zahlen im Intervall erzeugen $$$[0, 1)$ . Dieses Intervall kann wie folgt dargestellt werden:


Nun, wenn wir aufhören wollen $$$n$ facettierter Knochen, dann besteht eine Möglichkeit darin, das Intervall aufzuteilen $$$[0, 1)$ auf $$$n$ gleich große Bereiche, von denen jeder eine Länge hat $$$\ frac {1} {n}$ . Es sieht so aus:


Als nächstes generieren wir eine zufällig ausgewählte reelle Zahl im Intervall $$$[0, 1)$ das fällt sicherlich in einen dieser kleinen Bereiche. Daraus können wir das Ergebnis der Knochenrolle berechnen, indem wir den Bereich betrachten, in den die Zahl gefallen ist. Zum Beispiel, wenn unser zufällig ausgewählter Wert an diese Stelle gefallen ist:


dann können wir sagen, dass 2 auf den Knochen gefallen sind (wenn wir annehmen, dass die Kanten des Knochens von Grund auf neu indiziert sind).

Es ist grafisch leicht zu erkennen, welche Region einen zufälligen Wert hat, aber wie codieren wir diesen in einem Algorithmus? Und hier nutzen wir die Tatsache, dass dies ein ehrlicher Knochen ist. Da alle Intervalle gleich groß sind, nämlich $$$\ frac {1} {n}$ Dann können wir sehen, was der größte Wert ist $$$i$ ist so, dass $$$\ frac {i} {n}$ nicht mehr als ein zufällig generierter Wert (nennen wir diesen Wert x). Sie können feststellen, dass, wenn wir den Maximalwert finden wollen, so dass $$$\ frac {i} {n} \ le x$ Dies ähnelt dem Ermitteln des Maximalwerts $$$n$ so dass $$$i \ le xn$ . Aber das bedeutet per Definition, dass $$$i = \ lfloor xn \ rfloor$ ist die größte positive ganze Zahl nicht größer als xn. Dies führt uns daher zu diesem (sehr einfachen) ehrlichen n-facettierten Knochensimulationsalgorithmus:

Algorithmus: Ehrliche Knochensimulation

1. Generieren Sie einen gleichmäßig verteilten Zufallswert $$$x$ im Bereich $$$[0, 1)$ .
2. Zurück $$$\ lfloor xn \ rfloor$ .

In Anbetracht unserer obigen Annahmen zu Berechnungen läuft dieser Algorithmus rechtzeitig $$$O (1)$ .

Aus diesem Abschnitt können zwei Schlussfolgerungen gezogen werden. Zunächst können wir das Intervall aufteilen $$$[0, 1)$ Zum Teil, damit sich eine gleichmäßig verteilte reelle Zufallszahl in diesem Intervall natürlich auf eine der vielen diskreten Optionen reduziert, die uns zur Verfügung stehen. Im Rest dieses Artikels werden wir diese Technik aktiv nutzen. Zweitens kann es schwierig sein zu bestimmen, zu welchem ​​bestimmten Intervall ein Zufallswert gehört, aber wenn wir etwas über die Teile wissen (in diesem Fall, dass sie alle gleich groß sind), können wir mathematisch einfach bestimmen, welcher Teil sich auf einen bestimmten bezieht Punkt.

Betrugsknochensimulation mit ehrlichem Knochen

Können wir einen ehrlichen Knochensimulationsalgorithmus anpassen, um einen betrügerischen Knochen zu simulieren? Interessanterweise lautet die Antwort ja, aber eine Lösung benötigt mehr Platz.

Aus dem vorherigen Abschnitt geht intuitiv hervor, dass es zur Simulation eines betrügerischen Knochenwurfs ausreicht, das Intervall zu teilen $$$[0, 1)$ in Stücke und bestimmen dann, welchen Teil wir treffen. Im allgemeinen Fall kann dies jedoch viel komplizierter sein, als es scheint. Nehmen wir an, wir haben ein Tetraeder mit Gesichtswahrscheinlichkeiten $$$\ frac {1} {2}$ , $$$\ frac {1} {3}$ , $$$\ frac {1} {12}$ und $$$\ frac {1} {12}$ (Wir können sicherstellen, dass dies die richtige Wahrscheinlichkeitsverteilung ist, weil $$$\ frac {1} {2} + \ frac {1} {3} + \ frac {1} {12} + \ frac {1} {12} = \ frac {6} {12} + \ frac {4 } {12} + \ frac {1} {12} + \ frac {1} {12} = \ frac {12} {12}$ ) Wenn wir das Intervall teilen $$$[0, 1)$ in vier Teile dieser Größen erhalten wir dann Folgendes:


Leider stecken wir bei diesem Schritt fest. Auch wenn wir im Intervall eine Zufallszahl kannten $$$[0, 1)$ Dann gibt es keine einfachen mathematischen Tricks, um automatisch zu bestimmen, in welchen Teil diese Zahl gefallen ist. Ich möchte nicht sagen, dass dies unmöglich ist - wie Sie sehen werden, können wir viele hervorragende Tricks anwenden -, aber keiner von ihnen hat die mathematische Einfachheit des ehrlichen Algorithmus zum Knochenwerfen.

Wir können jedoch die Technik, mit der ehrlicher Knochen verwendet wird, auch in diesem Fall anpassen. Nehmen wir als Beispiel den oben diskutierten Knochen. Die Wahrscheinlichkeit fallender Flanken ist $$$\ frac {1} {2}$ , $$$\ frac {1} {3}$ , $$$\ frac {1} {12}$ und $$$\ frac {1} {12}$ . Wenn wir dies so umschreiben, dass alle Mitglieder einen gemeinsamen Teiler haben, erhalten wir die Werte $$$\ frac {6} {12}$ , $$$\ frac {4} {12}$ , $$$\ frac {1} {12}$ und $$$\ frac {1} {12}$ . Daher können wir diese Aufgabe wie folgt wahrnehmen: Anstatt einen tetraedrischen Knochen mit gewichteten Wahrscheinlichkeiten zu werfen, werfen Sie doch einen 12-seitigen, ehrlichen Knochen, an dessen Rändern sich doppelte Werte befinden. Da wir wissen, wie man ehrlichen Knochen simuliert, ist dies analog zur Intervalltrennung $$$[0, 1)$ in Stücke auf diese Weise:


Dann ordnen wir sie wie folgt verschiedenen Ergebnissen zu:


Jetzt wird es sehr einfach sein, einen Knochenwurf zu simulieren - wir werfen einfach diesen neuen ehrlichen Knochen und schauen uns dann an, welches Gesicht gefallen ist und lesen seinen Wert. Dieser erste Schritt kann mit dem oben dargestellten Algorithmus ausgeführt werden, der uns eine ganze Zahl von Zahlen im Intervall gibt $$$0, 1, ..., 11$ . Um diese Ganzzahl an eine der Flächen des ursprünglichen Betrüger-Knochens zu binden, speichern wir eine Hilfsanordnung von zwölf Elementen, die jede dieser Zahlen mit dem ursprünglichen Ergebnis verbinden. Dies kann grafisch wie folgt dargestellt werden:


Um dies in Form eines Algorithmus zu formalisieren, beschreiben wir sowohl die Initialisierungsphase (Erhalten der Tabelle) als auch die Generierungsphase (Simulieren eines zufälligen Knochenwurfs). Diese beiden Schritte sind wichtig, um in diesem und den nachfolgenden Algorithmen berücksichtigt zu werden, da die Vorbereitungszeit ausgezeichnet sein sollte.

In der Initialisierungsphase suchen wir zunächst nach dem kleinsten gemeinsamen Vielfachen aller für die Knochenkanten angegebenen Wahrscheinlichkeiten (in unserem Beispiel beträgt die LCL 12). NOC ist hier nützlich, weil es dem kleinsten gemeinsamen Teiler entspricht, den wir für alle Brüche verwenden können, und daher der Anzahl der Gesichter des neuen ehrlichen Knochens, den wir rollen werden. Nachdem wir dieses NOC erhalten haben (wir bezeichnen es mit L), müssen wir bestimmen, wie viele Flächen des neuen Knochens auf jeder der Flächen des ursprünglichen Betrügerknochens verteilt werden. In unserem Beispiel das Gesicht mit Wahrscheinlichkeit $$$\ frac {1} {2}$ bekommt seitdem sechs Seiten des neuen Knochens $$$\ frac {1} {2} \ times 12 = 6$ . Ebenso die Partei mit Wahrscheinlichkeit $$$\ frac {1} {3}$ bekommt seitdem 4 Gesichter $$$\ frac {1} {3} \ times 12 = 4$ . In einer allgemeineren Form, wenn L eine LCL von Wahrscheinlichkeiten ist, und $$$p_i$ ist die Wahrscheinlichkeit eines Gesichts $$$i$ Knochen, dann markieren wir die Gesichter $$$i$ originaler Sharpieknochen $$$L \ cdot p_i$ Facetten des ehrlichen Knochens.

Hier ist der Pseudocode des obigen Algorithmus:

Algorithmus: Simulation von betrügerischem Knochen mit ehrlichem Knochen

• Initialisierung :
  
  1. Finden Sie das NOC der Nenner der Wahrscheinlichkeit $$$p_0, p_1, ..., p_ {n-1}$ ;; bezeichne es $$$L$
  2. Wählen Sie ein Array aus $$$A$ die Größe $$$L$ um die Ergebnisse von ehrlichen Knochenrollen mit den Rollen des ursprünglichen Knochens zu vergleichen.
  3. Für jedes Gesicht $$$i$ Vom Anfangsknochen führen wir Folgendes in beliebiger Reihenfolge durch:
     
     1. Wir weisen wie folgt zu $$$L \ cdot p_i$ Elemente $$$A$ Wert $$$i$ .
• Generation :
  
  1. Wir generieren einen ehrlichen Knochenwurf für $$$L$ -gesichtsknochen; ruf das Gesicht an $$$S$ .
  2. Zurück $$$A [S]$ .

Dieser Algorithmus mag einfach sein, aber wie effizient ist er? Die Erzeugung von Knochenrollen ist ziemlich schnell - jede Knochenrolle erfordert $$$O (1)$ Laufzeit, um einen zufälligen Würfelwurf mit dem vorherigen Algorithmus zu generieren, plus mehr $$$O (1)$ Arbeitszeit, um die Tabelle zu durchsuchen. Dies gibt uns die Gesamtarbeitszeit. $$$O (1)$ .

Der Initialisierungsschritt kann jedoch äußerst kostspielig sein. Damit dieser Algorithmus funktioniert, müssen wir einem Array Platz in der Größe des NLC der Nenner aller Eingabefraktionen zuweisen. In unserem Beispiel ( $$$\ frac {1} {2}$ , $$$\ frac {1} {3}$ , $$$\ frac {1} {12}$ , $$$\ frac {1} {12}$ ) ist es 12, für andere Eingabewerte können die Werte pathologisch schlecht sein. Schauen wir uns zum Beispiel Brüche an $$$\ frac {999999} {1,000,000}$ und $$$\ frac {1} {1000000}$ . Das NOC der Nenner entspricht einer Million, daher sollte unsere Tabelle eine Million Elemente enthalten!

Leider könnte es noch schlimmer werden. Im vorherigen Beispiel können wir zumindest „erwarten“, dass der Algorithmus viel Speicherplatz beansprucht, da beide Nenner von Brüchen gleich einer Million sind. Es kann jedoch sein, dass wir viele Wahrscheinlichkeiten haben, für die der NOC signifikant größer ist als jeder einzelne Nenner. Schauen wir uns zum Beispiel die Wahrscheinlichkeiten an $$$\ frac {1} {15}$ , $$$\ frac {1} {10}$ , $$$\ frac {5} {6}$ . Hier beträgt der NOC der Nenner 30, was mehr als jeder der Nenner ist. Das Design funktioniert hier weil $$$15 = 3 mal 5$ , $$$10 = 2 mal 5$ und $$$6 = 2 \ mal 3$ ;; Mit anderen Worten, jeder Nenner ist ein Produkt aus zwei Primzahlen, die aus einem Pool von drei Werten ausgewählt wurden. Daher ist ihr NOC das Produkt all dieser Primzahlen, da jeder Nenner ein Teiler des NOC sein muss. Wenn wir diese Konstruktion verallgemeinern und einen Satz von betrachten $$$k$ Primzahlen und nehmen Sie einen Bruchteil für jedes der paarweisen Produkte dieser Primzahlen, dann ist der NOC viel mehr als jeder einzelne Nenner. In der Tat wird eine der besten Obergrenzen, die wir für das NOC bekommen können, sein $$$O (\ prod_ {i = 0} ^ n {d_i})$ wo $$$d_i$ Ist der Nenner $$$i$ diese Wahrscheinlichkeit. Dies erlaubt nicht die Verwendung eines solchen Algorithmus unter realen Bedingungen, wenn die Wahrscheinlichkeiten im Voraus unbekannt sind, da der Speicher zum Speichern der Größentabelle erforderlich ist $$$O (\ prod_ {i = 0} ^ n {d_i})$ Es kann sich leicht herausstellen, dass es mehr als das Volumen ist, das in den RAM passt.

Mit anderen Worten, in vielen Fällen verhält sich dieser Algorithmus gut. Wenn alle Wahrscheinlichkeiten gleich sind, sind alle am Eingang erhaltenen Wahrscheinlichkeiten gleich $$$\ frac {1} {n}$ für einige $$$n$ . Dann sind die NOC-Nenner gleich $$$n$ Das heißt, als Ergebnis wird der ehrliche Knochen geworfen haben $$$n$ Gesichter, und jede Facette des ursprünglichen Knochens entspricht einer Facette des ehrlichen Knochens. Daher ist die Initialisierungszeit $$$O (n)$ . Dies kann grafisch wie folgt dargestellt werden:


Dies gibt uns die folgenden Informationen über den Algorithmus:

Algorithmus	Initialisierungszeit		Generationszeit		Speicher belegt
	Das Beste	Das Schlimmste	Das Beste	Das Schlimmste	Das Beste	Das Schlimmste
Ehrlichkeit Knochen schärfer Knochen	$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$	$$$\ Theta (1)$		$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$

Ein weiteres wichtiges Detail dieses Algorithmus: Es wird davon ausgegangen, dass wir bequeme Wahrscheinlichkeiten in Form von Brüchen mit guten Nennern erhalten. Wenn die Wahrscheinlichkeiten als IEEE-754 double angegeben werden, ist dieser Ansatz aufgrund kleiner Rundungsfehler wahrscheinlich katastrophal. Stellen Sie sich vor, wir haben die Wahrscheinlichkeiten 0,25 und 0,250000000001! Daher ist es wahrscheinlich besser, diesen Ansatz nicht zu verwenden, außer in besonderen Fällen, wenn sich die Wahrscheinlichkeiten gut verhalten und in einem Format angegeben sind, das Operationen mit rationalen Zahlen entspricht.

Asymmetrische Münzsimulation

Unsere Erklärung eines einfachen zufälligen Grundelements (ehrlicher Knochen) führte zu einem einfachen, aber möglicherweise furchtbar ineffektiven Algorithmus zur Simulation von Betrugsknochen. Vielleicht wird das Studium anderer einfacher zufälliger Grundelemente etwas Licht auf andere Ansätze zur Lösung dieses Problems werfen.

Eine einfache, aber überraschend nützliche Aufgabe besteht darin, eine asymmetrische Münze mit einem Zufallszahlengenerator zu simulieren. Wenn wir eine Münze mit der Wahrscheinlichkeit eines Adlers haben $$$p_ {Köpfe}$ Wie können wir dann den Wurf einer solchen asymmetrischen Münze simulieren?

Zuvor haben wir einen intuitiven Ansatz entwickelt: die Intervallpartitionierung $$$[0, 1)$ Auf einer Folge solcher Regionen erscheint diese bei Auswahl eines Zufallswerts im Intervall in einer Region mit einer Wahrscheinlichkeit, die der Größe der Region entspricht. Simulation einer asymmetrischen Münze unter Verwendung eines gleichmäßig verteilten Zufallswerts im Intervall $$$[0, 1)$ wir müssen das Intervall brechen $$$[0, 1)$ wie folgt:


Und dann erzeugen Sie einen gleichmäßig verteilten Zufallswert im Intervall $$$[0, 1)$ um zu sehen, in welchem ​​Bereich es sich befindet. Glücklicherweise haben wir nur einen Teilungspunkt, so dass es sehr einfach ist zu bestimmen, in welchem ​​Bereich sich der Punkt befindet. wenn der Wert kleiner ist $$$p_ {Köpfe}$ , dann fiel der Adler auf die Münze, sonst - Schwänze. Pseudocode:

Algorithmus: Simulieren Sie eine asymmetrische Münze

1. Generieren Sie einen gleichmäßig verteilten Zufallswert im Intervall $$$[0, 1)$ .
2. Wenn $$$x <p_ {Köpfe}$ , gib den "Adler" zurück.
3. Wenn $$$x \ ge p_ {Köpfe}$ , Schwänze zurückgeben.

Da können wir im Intervall einen gleichmäßig verteilten Zufallswert erzeugen $$$[0, 1)$ rechtzeitig $$$O (1)$ , und wir können auch reelle Zahlen für vergleichen $$$O (1)$ , dann läuft dieser Algorithmus rechtzeitig $$$O (1)$ .

Simulation ehrlicher Knochen mit asymmetrischen Münzen

Aus der vorherigen Diskussion wissen wir, dass wir einen Betrugsknochen mit ehrlichem Knochen simulieren können, wenn wir davon ausgehen, dass wir bereit sind, zusätzlichen Speicherplatz aufzuwenden. Da wir eine asymmetrische Münze als betrügerischen bilateralen Knochen wahrnehmen können, bedeutet dies, dass wir eine asymmetrische Münze mit Hilfe eines ehrlichen Knochens simulieren können. Es ist interessant, dass auch das Gegenteil getan werden kann - einen ehrlichen Knochen mit einer asymmetrischen Münze zu simulieren.Das Design ist einfach, elegant und kann leicht verallgemeinert werden, um einen betrügerischen Knochen mit einer Vielzahl asymmetrischer Münzen zu simulieren.

Das Design zur Simulation einer asymmetrischen Münze teilt das Intervall auf$$$[0, 1)$ in zwei Bereiche - den Bereich "Adler" und den Bereich "Schwänze", basierend auf der Wahrscheinlichkeit, dass die Adler auf die Knochen fallen. Wir haben bereits einen ähnlichen Trick gesehen, um ehrlich zu simulieren$$$n$ facettierter Knochen: Intervall$$$[0, 1)$ wurde unterteilt in$$$n$ gleiche Flächen. Wenn wir zum Beispiel einen tetraedrischen Knochen werfen, erhalten wir die folgende Trennung:


Nehmen wir nun an, wir möchten eine Rolle dieses ehrlichen Knochens mit einem Satz asymmetrischer Münzen simulieren. Eine Lösung lautet wie folgt: Stellen Sie sich vor, wir gehen diese Bereiche von links nach rechts um und fragen jedes Mal, ob wir im aktuellen Bereich anhalten möchten oder ob wir weitermachen. Nehmen wir zum Beispiel an, wir möchten einen dieser Bereiche zufällig auswählen. Ausgehend vom Bereich ganz links werfen wir eine asymmetrische Münze, die uns sagt, ob wir in diesem Bereich anhalten oder weitergehen sollen. Da müssen wir aus all diesen Bereichen mit Wahrscheinlichkeit einheitlich auswählen$$$\frac{1}{4}$ , dann können wir dies tun, indem wir eine asymmetrische Münze werfen, auf die die Adler mit Wahrscheinlichkeit fallen$$$\frac{1}{4}$ .Wenn ein Adler fällt, halten wir im aktuellen Bereich an. Ansonsten gehen wir zum nächsten Bereich.

Wenn die Münzen nach oben fallen, befinden wir uns im zweiten Bereich und fragen erneut, ob wir diesen Bereich erneut auswählen oder uns weiter bewegen sollen. Sie könnten denken, dass wir dafür eine weitere Münze mit der Wahrscheinlichkeit eines Adlers werfen müssen$$$\frac{1}{4}$ , aber eigentlich ist das nicht wahr! Um den Fehler in dieser Argumentation zu erkennen, müssen wir zu einer extremen Situation kommen - wenn wir in jedem Bereich eine Münze werfen, auf die der Adler mit Wahrscheinlichkeit fällt$$$\frac{1}{4}$ , das heißt, es besteht eine geringe Wahrscheinlichkeit, dass in jedem Bereich die Münze aus dem Schwanz fällt, das heißt, wir müssen alle Bereiche aufgeben. Wenn wir uns durch Regionen bewegen, müssen wir die Wahrscheinlichkeit, dass ein Adler auf eine Münze fällt, weiter erhöhen. Wenn wir uns in einer extremen Situation im letzten Bereich befinden, muss die Münze mit hoher Wahrscheinlichkeit einen Adler haben$$$1$ , denn wenn wir alle vorherigen Bereiche ablehnen würden, wäre die richtige Entscheidung, im letzten Bereich anzuhalten.

Um die Wahrscheinlichkeit zu bestimmen, mit der unsere asymmetrische Münze nach dem Überspringen des ersten Bereichs einen Adler werfen sollte, müssen wir beachten, dass nach dem Überspringen des ersten Bereichs nur noch drei übrig sind. Wenn wir einen ehrlichen Knochen rollen, müssen wir jeden dieser drei Bereiche mit Wahrscheinlichkeit auswählen$$$\frac{1}{3}$ . Intuitiv scheint es daher, dass wir einen zweiten Knochen haben sollten, auf den der Adler mit Wahrscheinlichkeit fällt $$$\frac{1}{3}$ . Unter Verwendung ähnlicher Überlegungen kann verstanden werden, dass, wenn ein Schwanz im zweiten Bereich des Gitters im dritten Bereich erscheint, die Münze mit hoher Wahrscheinlichkeit vom Adler fallen gelassen werden sollte $$$\frac{1}{2}$ und im letzten Bereich - mit Wahrscheinlichkeit$$$1$ .

Dieses intuitive Verständnis führt uns zu folgendem Algorithmus. Beachten Sie, dass wir die Richtigkeit oder den Irrtum dieses Algorithmus nicht erörtert haben. bald werden wir es tun.

Algorithmus: Simulation ehrlicher Knochen mit asymmetrischen Münzen

1. Für $$$i = 0$ bis$$$n - 1$ ::
   
   1. Wirf eine asymmetrische Münze mit der Wahrscheinlichkeit eines Adlers $$$\frac{1}{n - i}$ .
   2. Wenn der Adler fällt, kehren Sie zurück $$$i$ .

Dieser Algorithmus ist einfach und läuft im schlimmsten Fall rechtzeitig. $$$O (n)$ .Aber wie prüfen wir, ob es richtig ist? Um dies herauszufinden, benötigen wir den folgenden Satz:

Satz: Der obige Algorithmus gibt die Seite zurück$$$i$ mit Wahrscheinlichkeit$$$\frac{1}{n}$ für eine ausgewählte$$$i$ .

Beweis: Betrachten Sie jede Konstante$$$n \ge 0$ . Mit starker Induktion beweisen wir, dass jeder von $$$n$ Gesichter haben eine Wahrscheinlichkeit der Wahl$$$\frac{1}{n}$ .

In unserem Beispiel zeigen wir das Gesicht $$$0$ Würfel haben eine Wahrscheinlichkeit der Wahl$$$\frac{1}{n}$ . Dies folgt jedoch direkt aus dem Algorithmus selbst - wir wählen Gesicht 0, wenn auf einer asymmetrischen Münze mit der Wahrscheinlichkeit eines Adlers $$$\frac{1}{n}$ , $$$\frac{1}{n}$ .

$$$0, 1, 2, ..., k - 1$ , $$$\frac{1}{n}$ $$$k$ . $$$k$ wird ausgewählt, wenn und nur wennnichtausgewählt die erste$$$k$ Gesichter und auf einer Münze mit der Wahrscheinlichkeit eines Adlers$$$\frac{1}{n - k}$ . $$$k$ Gesichter haben eine Wahrscheinlichkeit der Wahl$$$\frac{1}{n}$ , , $$$k$ ist gegeben als$$$\frac{k}{n}$ . Dies bedeutet, dass die Wahrscheinlichkeit, dass der Algorithmus keine der ersten auswählt $$$k$ Gesichter sind gleich$$$1 - \frac{k}{n} = \frac{n}{n} - \frac{k}{n} = \frac{n - k}{n}$ . Das heißt, die Wahrscheinlichkeit, ein Gesicht zu wählen $$$k$ ist gegeben als$$$\frac{n - k}{n} \frac{1}{n - k} = \frac{1}{n}$ , das gezeigt werden soll. Somit wird jede Seite des Knochens gleichmäßig und zufällig ausgewählt.

Natürlich ist der Algorithmus ziemlich ineffizient - mit der ersten Technik können wir rechtzeitig einen Wurf ehrlicher Würfel simulieren $$$O(1)$ ! Dieser Algorithmus kann jedoch als Sprungbrett für einen ausreichend effektiven Algorithmus zur Simulation eines betrügerischen Knochens unter Verwendung asymmetrischer Münzen verwendet werden.

Shuler-Knochensimulation mit asymmetrischen Münzen

Der oben vorgestellte Algorithmus ist insofern interessant, als er uns einen einfachen Rahmen für die Simulation eines Knochens mit einem Satz Münzen bietet. Wir beginnen mit dem Werfen einer Münze, um zu bestimmen, ob die erste Facette des Knochens ausgewählt oder zum Rest übergegangen werden soll. In diesem Prozess müssen wir die Skala der verbleibenden Wahrscheinlichkeiten sorgfältig behandeln.

Mal sehen, wie Sie diese Technik verwenden können, um einen betrügerischen Knochenwurf zu simulieren. Wir verwenden unser Beispiel mit Wahrscheinlichkeiten$$$\frac{1}{2}$ , $$$\frac{1}{3}$ , $$$\frac{1}{12}$ , $$$\frac{1}{12}$ . Wenn Sie sich nicht erinnern, teilt er das Intervall $$$[0, 1)$ wie folgt:


Lassen Sie uns nun darüber nachdenken, wie man einen solchen betrügerischen Knochen mit asymmetrischen Münzen simuliert. Wir können beginnen, indem wir eine Münze mit der Wahrscheinlichkeit eines Adlers werfen$$$\frac{1}{2}$ , um zu bestimmen, ob wir Gesicht 0 zurückgeben sollen. Wenn ein Adler auf diese Münze fällt, dann gut! Wir sind fertig. Andernfalls müssen wir eine weitere Münze werfen, um zu entscheiden, ob die nächste Facette ausgewählt werden soll. Nach wie vor trotz der Tatsache, dass die nächste Facette eine Wahrscheinlichkeit der Wahl hat$$$\frac{1}{3}$ , wir wollen keine Münze werfen, auf die der Adler mit Wahrscheinlichkeit fällt$$$\frac{1}{3}$ , weil die Hälfte der „Masse“ der Wahrscheinlichkeiten verworfen wurde, wenn wir keine Linie mit ausgewählt haben$$$\frac{1}{2}$ . Da die Hälfte der Wahrscheinlichkeitsmasse verschwunden ist, erhalten wir aktualisierte Wahrscheinlichkeiten, wenn wir die verbleibenden Wahrscheinlichkeiten erneut normalisieren: $$$\frac{2}{3}$ , $$$\frac{1}{6}$ , $$$\frac{1}{6}$ . Daher muss die zweite Münze mit Wahrscheinlichkeit geworfen werden $$$\frac{2}{3}$ . Wenn diese Münze auch Schwänze ist, müssen wir zwischen zwei Seiten wählen $$$\frac{1}{12}$ . Da werden wir zu diesem Zeitpunkt los $$$\frac{5}{6}$ Massen von Wahrscheinlichkeiten, dann können wir die Wahrscheinlichkeiten der Parteien wieder normalisieren$$$\frac{1}{12}$ damit jeder eine Chance hat$$$\frac{1}{2}$ Tropfen eines Adlers, dh die dritte Münze hat eine Wahrscheinlichkeit$$$\frac{1}{2}$ . Die letzte Münze, falls sie jemals zu ihr kommt, sollte den Adler mit Wahrscheinlichkeit werfen $$$1$ da dies der jüngste Bereich ist.

Zusammenfassend sind die Wahrscheinlichkeiten von Münzen wie folgt:

1. Erste Rolle: $$$\frac{1}{2}$
2. Zweite Rolle: $$$\frac{2}{3}$
3. Dritte Rolle: $$$\frac{1}{2}$
4. Vierte Rolle: $$$1$

, , , . — . , , $$$1$ . $$$1 - p_0$ . $$$1 - p_0 - p_1$ . $$$k$ $$$1 - \sum_{i = 0}^{k - 1}{p_i}$ . , , , $$$k$ , , , $$$p_k$ , $$$\frac{p_k}{1 - \sum_{i = 0}^{k - 1}{p_i}}$ . ( ):

:

• :
  
  1. $$$p_i$ .
• :
  $$$mass = 1$
  For $$$i = 0$ to $$$n - 1$ ::
  
  1. $$$\frac{p_i}{mass}$ .
  2. , $$$i$ .
  3. $$$mass = mass - p_i$

, ? , :

: $$$i$ $$$p_i$ $$$i$ .

: $$$n \ge 0$ . , $$$n$ $$$p_i$ .

, $$$0$ $$$p_0$ . $$$0$ , , $$$\frac{p_0}{mass}$ . $$$mass$ $$$1$ , $$$\frac{p_0}{1} = p_0$ , 0 $$$p_0$ , .

, $$$0, 1, ..., k - 1$ $$$p_0, p_1, ..., p_{k-1}$ $$$k$ . $$$k$ , $$$k$ , $$$\frac{p_k}{mass}$ . $$$k$ , , $$$k$ $$$\sum_{i = 0}^{k - 1}{p_i}$ . , $$$k$ $$$1 - \sum_{i = 0}^{k - 1}{p_i}$ . , $$$k$ , $$$\frac{p_k}{mass}$ $$$k$ , $$$mass = 1 - \sum_{i = 0}^{k - 1}{p_i}$ . , $$$k$ $$$(1 - \sum_{i = 0}^{k - 1}{p_i})\frac{p_k}{1 - \sum_{i = 0}^{k - 1}{p_i}} = p_k$ , .

. , $$$\Theta(1)$ , , $$$\Theta(n)$ , ( , ). $$$\Theta(n)$ , .

, . , , . . , . $$$n$ .

. $$$X$ , . $$$\mathbb{P}[X = 1]$ , , $$$\mathbb{P}[X = 2]$ — , , .. $$$X$ , $$$\mathbb{E}[X]$ . ,

$$ $$\mathbb{E}[X] = \sum_{i = 1}^n{i \cdot \mathbb{P}[X = i]}$$

$$$\mathbb{P}[X = i]$ ? - . $$$0$ , . $$$1$ , — , $$$0$ , , $$$1$ . , $$$i$ , $$$i + 1$ : $$$i$ , , $$$i - 1$ , , , $$$i$ . , $$$i$ $$$p_i$ , ,

$$ $$\mathbb{E}[X] = \sum_{i = 1}^n{i \cdot \mathbb{P}[X = i]} = \sum_{i = 1}^n{i \cdot p_{i - 1}} = \sum_{i = 1}^n{((i - 1) p_{i - 1} + p_{i - 1})} = \sum_{i = 1}^n{((i - 1) p_{i - 1})} + \sum_{i = 1}^n{p_{i - 1}}$$

Beachten Sie, dass in der letzten Vereinfachung der erste Term äquivalent ist $$$\ sum_ {i = 0} ^ {n-1} {i \ cdot p_i}$ das ist gleichwertig $$$\ mathbb {E} [p]$ , das erwartete Ergebnis eines Würfelwurfs! Darüber hinaus ist der zweite Term gleich $$$1$ denn dies ist die Summe aller Wahrscheinlichkeiten. Das bedeutet das $$$\ mathbb {E} [X] = \ mathbb {E} [p] + 1$ . Das heißt, die erwartete Anzahl von Münzwürfen entspricht eins plus der mathematischen Erwartung eines Würfelwurfs!

Algorithmus	Initialisierungszeit		Generationszeit		Speicher belegt
	Das Beste	Das Schlimmste	Das Beste	Das Schlimmste	Das Beste	Das Schlimmste
Ehrlichkeit Knochen schärfer Knochen	$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$	$$$\ Theta (1)$		$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$
Schuler Knochen aus asymmetrischen Münzen	$$$\ Theta (n)$		$$$\ Theta (1)$	$$$\ Theta (n)$	$$$\ Theta (n)$

Verallgemeinerung asymmetrischer Münzen: Simulation eines betrügerischen Knochens

In dem oben gezeigten Beispiel konnten wir eine asymmetrische Münze effektiv simulieren, da wir nur einen Teilungspunkt berücksichtigen mussten. Wie können wir diese Idee effektiv auf einen betrügerischen Knochen verallgemeinern, bei dem die Anzahl der Gesichter beliebig sein kann?

Wie Sie sehen können, ist eine asymmetrische Münze ein betrügerischer Knochen mit nur zwei Gesichtern. Daher können wir eine asymmetrische Münze einfach als Sonderfall eines allgemeineren Problems wahrnehmen, das wir lösen möchten. Bei der Lösung des asymmetrischen Münzproblems teilen wir das Intervall $$$[0, 1)$ in zwei Bereiche - einen für den Adler, den zweiten für Schwänze - und um dann den Bereich zu finden, verwenden wir die Tatsache, dass es nur einen Teilungspunkt gibt. Wenn wir einen Knochen mit n Gesicht haben, gibt es mehr Bereiche und daher mehrere Trennpunkte. Nehmen wir zum Beispiel an, wir haben einen siebenseitigen Knochen mit Wahrscheinlichkeiten $$$\ frac {1} {4}$ , $$$\ frac {1} {5}$ , $$$\ frac {1} {8}$ , $$$\ frac {1} {8}$ , $$$\ frac {1} {10}$ , $$$\ frac {1} {10}$ , $$$\ frac {1} {10}$ . Wenn wir das Intervall teilen wollen $$$[0, 1)$ in sieben Teile, dann machen wir es wie folgt:


Beachten Sie, wo sich diese Bereiche befinden. Der erste Bereich beginnt mit $$$0$ und endet $$$\ frac {1} {4}$ . Der zweite Bereich beginnt mit $$$\ frac {1} {4}$ und endet in $$$\ frac {1} {4} + \ frac {1} {5} = \ frac {9} {20}$ . Allgemeiner, wenn die Wahrscheinlichkeiten gleich sind $$$p_0, p_1, ..., p_ {n - 1}$ , dann werden die Bereiche Intervalle sein $$$[0, p_0)$ , $$$[p_0, p_0 + p_1)$ , $$$[p_0 + p_1, p_0 + p_1 + p_2)$ usw. Das ist der Bereich $$$i$ durch Intervall begrenzt

$$ $$[\ sum_ {j = 0} ^ {i - 1} {p_j}, \ sum_ {j = 0} ^ {i} {p_j})$$

Beachten Sie, dass der Unterschied zwischen diesen beiden Werten ist $$$p_i$ Das heißt, die Gesamtfläche der Region beträgt $$$p_i$ nach Bedarf.

Jetzt wissen wir, wo die Gebiete sind. Wenn wir einen gleichmäßig verteilten Zufallswert wählen wollen $$$x$ im Bereich $$$[0, 1)$ Wie bestimmen wir dann, in welches Intervall es fällt? Wenn wir einen asymmetrischen Münzalgorithmus als Ausgangspunkt verwenden, lautet die Idee wie folgt: Gehen Sie vom Endpunkt der ersten Region aus ständig durch alle Bereiche nach oben, bis wir einen Endpunkt finden, dessen Wert größer als der Wert ist $$$x$ . Wenn wir dies tun, finden wir die erste Region, die den Punkt enthält $$$x$ und damit unser Wert. Zum Beispiel, wenn wir einen zufälligen Wert gewählt haben $$$x = \ frac {27} {40}$ Führen Sie dann die folgende Suche durch:


Daraus können wir schließen, dass Facette 3 mit Indexierung von Grund auf auf Würfel gefallen ist.

Ein solcher linearer Abtastalgorithmus gibt uns einen Zeitalgorithmus $$$O (n)$ um die ausgeworfene Kante des Knochens zu finden. Wir können jedoch die Ausführungszeit erheblich verbessern, indem wir die folgende Beobachtung verwenden: Eine Reihe von Endpunkten von Regionen bildet eine zunehmende Sequenz (da wir immer mehr Wahrscheinlichkeiten hinzufügen, von denen keine kleiner als Null sein kann). Daher möchten wir die folgende Frage beantworten: Mit einer zunehmenden Folge von Werten und einem Prüfpunkt müssen wir den ersten Wert in dem Intervall finden, das streng größer als der Prüfpunkt ist. Dies ist der perfekte Zeitpunkt, um die binäre Suche zu verwenden ! Hier ist beispielsweise eine binäre Suche im obigen Array, um den Bereich zu finden, zu dem es gehört $$$x = \ frac {39} {40}$ ::


Dies gibt uns einen Algorithmus im Laufe der Zeit. $$$\ Theta (\ log n)$ einen gleichmäßig verteilten Zufallswert im Intervall zu binden $$$[0, 1)$ an den Rand eines verlassenen Knochens. Darüber hinaus reicht die Vorverarbeitungszeit aus, um die Endpunkttabelle zu erstellen $$$\ Theta (n)$ ;; Wir berechnen einfach Teilsummen von Wahrscheinlichkeiten, wenn wir aufsteigen.

Dieser Algorithmus wird manchmal als Roulette-Rad-Auswahlalgorithmus bezeichnet , da er einen zufälligen Bereich mit einer Technik auswählt, die einem Roulette-Rad ähnelt. Er wirft einen Ball in ein Intervall und beobachtet, wo er anhält. Im Pseudocode sieht der Algorithmus folgendermaßen aus:

Algorithmus: Roulette-Radauswahl

• Initialisierung :
  
  1. Wählen Sie ein Array aus $$$A$ die Größe $$$n$
  2. Wir setzen $$$A [0] = p_0$ .
  3. Für jede Wahrscheinlichkeit $$$i$ von $$$1$ vorher $$$n - 1$ ::
     
     1. Wir setzen $$$A [i] = A [i - 1] + p_i$
  
  
• Generation :
  
  1. Generieren Sie einen gleichmäßig verteilten Zufallswert $$$x$ im Bereich $$$[0, 1)$
  2. Mit einer binären Suche finden wir den Index $$$i$ kleinstes Element $$$A$ das ist weniger $$$x$ .
  3. Zurück $$$i$ .

Der Vergleich zwischen diesem Algorithmus und dem zuvor angegebenen sieht ziemlich beeindruckend aus:

Algorithmus	Initialisierungszeit		Generationszeit		Speicher belegt
	Das Beste	Das Schlimmste	Das Beste	Das Schlimmste	Das Beste	Das Schlimmste
Ehrlichkeit Knochen schärfer Knochen	$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$	$$$\ Theta (1)$		$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$
Schuler Knochen aus asymmetrischen Münzen	$$$\ Theta (n)$		$$$\ Theta (1)$	$$$\ Theta (n)$	$$$\ Theta (n)$
Roulette-Radauswahl	$$$\ Theta (n)$		$$$\ Theta (\ log n)$		$$$\ Theta (n)$

Offensichtlich haben wir jetzt einen viel besseren Algorithmus als den ursprünglichen. Die Wahrscheinlichkeitsdiskretion schien zunächst nur vielversprechend, aber dieser neue Ansatz, der auf kontinuierlichem Wert und binärer Suche basiert, sieht viel besser aus. Es ist jedoch weiterhin möglich, diese Indikatoren durch den intelligenten Einsatz einer Reihe von Hybridtechniken zu verbessern, auf die wir weiter unten eingehen werden.

Ein interessantes Detail dieses Algorithmus ist, dass die Verwendung der binären Suche zwar die ungünstigste Zeit für die Erzeugung von Zufallszahlen garantiert $$$O (\ log n)$ Es erlaubt auch keine schnellere Suche. Das heißt, die Generierungszeit ist ebenfalls gleich $$$\ Omega (\ log n)$ . Kann es verbessert werden? Es stellt sich heraus, dass Sie können.

Angenommen, wir wechseln von einer binären Suche in einer Liste kumulativer Wahrscheinlichkeiten zur Verwendung eines binären Suchbaums . Mit den oben angegebenen Wahrscheinlichkeiten können wir beispielsweise den folgenden binären Suchbaum für ihre kumulative Verteilung erstellen:


Wenn wir nun eine Knochenrolle simulieren möchten, können wir eine gleichmäßig verteilte Zahl im Intervall erzeugen $$$[0, 1)$ und schauen Sie sich dann an, in welchem ​​Intervall es in diesem binären Suchbaum (BST) liegt. Da dies ein ausgeglichener binärer Suchbaum ist, ist die beste Suchzeit $$$O (1)$ und das Schlimmste $$$O (\ log n)$ .

Wenn wir jedoch mehr über die Wahrscheinlichkeitsverteilung wissen, können wir es viel besser machen. Angenommen, unsere Wahrscheinlichkeiten sind gleich $$$\ frac {99} {100}$ , $$$\ frac {1} {600}$ , $$$\ frac {1} {600}$ , $$$\ frac {1} {600}$ , $$$\ frac {1} {600}$ , $$$\ frac {1} {600}$ , $$$\ frac {1} {600}$ . Das heißt, die Wahrscheinlichkeitsverteilung ist extrem verzerrt und fast die gesamte Masse der Wahrscheinlichkeiten ist auf eine Seite konzentriert. Wir können eine ausgeglichene BST für diese Wahrscheinlichkeiten erstellen:


Obwohl dieser binäre Suchbaum perfekt ausbalanciert ist, ist er für unsere Aufgaben nicht sehr geeignet. Da wir wissen, dass in 99 von 100 Fällen der Zufallswert im Bereich liegt $$$[0, \ frac {99} {100})$ Dann macht es keinen Sinn, den Knoten für dieses Intervall zu speichern, in dem er sich jetzt befindet. In der Tat bedeutet dies, dass wir fast immer zwei unnötige Vergleiche mit den blauen und gelben Bereichen anstellen werden. Da wir mit sehr hoher Wahrscheinlichkeit als erste das größte Intervall prüfen sollten, wäre es logisch, den Baum aus dem Gleichgewicht zu bringen, um den Durchschnittsfall aufgrund der verbleibenden Intervalle viel besser zu machen. Dies wird hier gezeigt:


Jetzt werden wir die Suche höchstwahrscheinlich abschließen, indem wir nach dem ersten Versuch sofort den gewünschten Bereich finden. In dem sehr unwahrscheinlichen Fall, dass sich der gewünschte Bereich im verbleibenden befindet $$$(\ frac {99} {100}, 1]$ Wir gehen ruhig zum Ende des Baumes hinunter, der eigentlich gut ausbalanciert ist.

In einer verallgemeinerten Form wollen wir das folgende Problem lösen:

Suchen Sie bei einem bestimmten Satz von Wahrscheinlichkeiten einen binären Suchbaum für diese Wahrscheinlichkeiten, der die erwartete Suchzeit minimiert.

Glücklicherweise ist dieses Problem sehr gut untersucht und wird als optimales Problem des binären Suchbaums bezeichnet . Es gibt viele Algorithmen, um dieses Problem zu lösen. Es ist bekannt, dass die genaue Lösung rechtzeitig gefunden werden kann $$$O (n ^ 2)$ mit dynamischer Programmierung , und dass es gute lineare Zeitalgorithmen gibt, die ungefähre Lösungen finden können. Um einen konstanten Faktor für die optimale Lösung zu erhalten, können Sie außerdem die Spreizbaum- Datenstruktur (expandierender Baum) (selbstausgleichender binärer Suchbaum) verwenden.

Es ist interessant, dass der beste Fall für das Verhalten solcher optimierten binären Suchbäume auftritt, wenn die Wahrscheinlichkeitsverteilungen extrem verzerrt sind, weil wir einfach die Knoten, die die überwiegende Mehrheit der Wahrscheinlichkeitsmasse enthalten, zur Wurzel des Baums verschieben können, und der schlimmste Fall ist, wenn die Verteilung ausgeglichen ist, weil dann der Baum breit sein sollte und flach. Dies ist das Gegenteil des Verhaltens des vorherigen Algorithmus, bei dem ein ehrlicher verwendet wurde, um einen betrügerischen Knochen zu simulieren!

Im besten Fall haben wir einen betrügerischen Knochen, bei dem immer ein Gesicht herausfällt (dh es hat eine Wahrscheinlichkeit von 1 und alle anderen Gesichter haben eine Wahrscheinlichkeit von 0). Dies ist eine extreme Übertreibung unseres vorherigen Beispiels, aber in diesem Fall endet die Suche immer nach dem ersten Versuch. Im schlimmsten Fall sind alle Wahrscheinlichkeiten gleich und wir erhalten eine Standard-BST-Suche. Wir kommen zu folgendem:

Algorithmus	Initialisierungszeit		Generationszeit		Speicher belegt
	Das Beste	Das Schlimmste	Das Beste	Das Schlimmste	Das Beste	Das Schlimmste
Ehrlichkeit Knochen schärfer Knochen	$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$	$$$\ Theta (1)$		$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$
Schuler Knochen aus asymmetrischen Münzen	$$$\ Theta (n)$		$$$\ Theta (1)$	$$$\ Theta (n)$	$$$\ Theta (n)$
Roulette-Radauswahl	$$$\ Theta (n)$		$$$\ Theta (\ log n)$		$$$\ Theta (n)$
Optimale Auswahl an Roulette-Rädern	$$$O (n ^ 2)$		$$$\ Theta (1)$	$$$O (\ log n)$	$$$\ Theta (n)$

Dart werfen

Bisher haben wir zwei Grundelemente in Betracht gezogen, die uns geholfen haben, Algorithmen zur Simulation eines betrügerischen Knochens zu entwickeln: ehrlichen Knochen und asymmetrische Münze. Wir verwenden nur ehrlichen Knochen und kommen zu einem (leider unpraktischen) Algorithmus zum Betrügen von Knochen. Ausgehend von asymmetrischen Münzen konnten wir einen schnellen Algorithmus zum Betrügen von Knochen erfinden. Können diese beiden Ansätze kombiniert werden, um einen Algorithmus zu erstellen, der auf ehrlichen Knochen und asymmetrischen Münzen basiert? Es stellt sich heraus, dass ja, und tatsächlich ist der resultierende Algorithmus besser als diese beiden Ansätze.

Bis zu diesem Moment haben wir das Intervall visualisiert $$$[0, 1)$ und Wahrscheinlichkeiten von Knochenflächen als eindimensionales Intervall. Beide Algorithmen wählen einen Punkt im Intervall aus $$$[0, 1)$ und lege es auf ein gerades Liniensegment, dessen Länge einer Art Wahrscheinlichkeit entspricht. Je länger die von uns erstellten Segmente sind, desto größer ist die Wahrscheinlichkeit, dieses Segment auszuwählen. Aber was ist, wenn Sie versuchen, nicht in einer, sondern in zwei Dimensionen zu denken? Was ist, wenn wir die Wahrscheinlichkeit nehmen? $$$p_i$ nicht die Länge eines geraden Liniensegments, sondern die Fläche eines Rechtecks?

Kehren wir zunächst mit Wahrscheinlichkeiten zu unserem vorherigen Beispiel zurück $$$\ frac {1} {2}$ , $$$\ frac {1} {3}$ , $$$\ frac {1} {12}$ , $$$\ frac {1} {12}$ . Wir stellen diese Wahrscheinlichkeiten in Form von Rechtecken mit einer Breite dar $$$w$ (mit einigen willkürlichen $$$w> 0$ ) und Höhe $$$p_i$ (Somit ist die Fläche des Rechtecks ​​gleich $$$w \ cdot p_i$ ):


Beachten Sie, dass die Gesamtfläche dieser Rechtecke beträgt $$$w$ seit der Gegend

$$ $$\ sum_ {i = 0} ^ {n - 1} {w p_i} = w \ sum_ {i = 0} ^ {n - 1} {p_i} = w$$

Nehmen wir nun an, wir zeichnen ein Begrenzungsrechteck um diese Rechtecke, deren Breite ist $$$4w$ (da es vier Vierecke gibt), und die Höhe ist $$$\ frac {1} {2}$ (da das höchste Rechteck eine Höhe hat $$$\ frac {1} {2}$ ):


Wir können uns vorstellen, dass dieses Rechteck in fünf Bereiche unterteilt ist - vier Bereiche entsprechen unterschiedlichen Wahrscheinlichkeiten, und ein Bereich zeigt ungenutzten Raum an. In dieser Pause können wir uns den Simulationsalgorithmus für zufällige Würfelwürfe als ein Dartspiel vorstellen. Angenommen, wir werfen einen (perfekt gleichmäßig verteilten) Pfeil auf dieses Ziel. Wenn es in unbenutzten Raum fällt, nehmen wir den Pfeil heraus und werfen ihn erneut. Wiederholen Sie den Vorgang, bis wir in eines der Rechtecke gelangen. Je größer die Wahrscheinlichkeit, je größer das Rechteck, desto größer die Wahrscheinlichkeit, den Rand des Knochens zu werfen, desto höher ist die Wahrscheinlichkeit, in sein Rechteck zu fallen. Wenn wir die Bedingung festlegen, dass wir bereits in eine Art Rechteck gefallen sind, erhalten wir tatsächlich Folgendes:

$$ $$\ mathbb {P} [\ mbox {Trefferrechteck für Seite i} | \ mbox {treffe ein Rechteck}] = \ frac {\ mbox {Bereich des Rechtecks ​​für i}} {\ mbox {gesamte Rechteckfläche}} = \ frac {w p_i} {w} = p_i$$

Mit anderen Worten, wenn wir mit unserem gleichmäßig verteilten Pfeil schließlich in eine Art Rechteck fallen, wählen wir das Gesichtsrechteck aus $$$i$ Betrüger Knochen mit Wahrscheinlichkeit $$$p_i$ mit der Wahrscheinlichkeit, dass wir brauchen! Das heißt, wenn wir einen effektiven Weg finden, um das Werfen von zufälligen Pfeilen auf dieses Rechteck zu simulieren, haben wir einen effektiven Weg, um das Werfen von zufälligen Würfeln zu simulieren.

Eine Möglichkeit, Pfeilwürfe auf dieses Rechteck zu simulieren, besteht darin, zwei gleichmäßig verteilte Werte im Intervall auszuwählen $$$[0, 1)$ Skalieren Sie sie auf die entsprechende Breite und Höhe, und überprüfen Sie anschließend den Bereich unter dem Pfeil. Dies verursacht jedoch das gleiche Problem, das wir hatten, als wir versuchten, den eindimensionalen Bereich zu bestimmen, in dem sich der Zufallswert befindet. Es gibt jedoch eine wirklich wunderbare Reihe von Beobachtungen, dank derer die Bestimmung des Aufprallortes eine einfache, wenn nicht triviale Aufgabe sein kann.

Erste Beobachtung: Wir haben gezeigt, dass die Breite dieser Rechtecke beliebig gewählt werden kann, da alle gleich breit sind. Die Höhen hängen natürlich von den Wahrscheinlichkeiten der Gesichter der Knochen ab. Wenn wir jedoch alle Höhen gleichmäßig um eine positive reelle Zahl skalieren $$$h$ Dann sind die relativen Flächen aller Rechtecke gleich. In der Tat für jede positive reelle Zahl $$$h$ Gesamtfläche aller Rechtecke nach Skalierung ihrer Höhen um $$$h$ berechnet als

$$ $$\ sum_ {i = 0} ^ {n - 1} {w h p_i} = w h \ sum_ {i = 0} ^ {n - 1} {p_i} = w h$$

Nun werden wir die Wahrscheinlichkeit betrachten, ein einzelnes Rechteck auszuwählen, und uns auf die Bedingung beschränken, dass wir definitiv eine Art Rechteck treffen. Mit den gleichen Berechnungen erhalten wir Folgendes:

$$ $$\ mathbb {P} [\ mbox {Trefferrechteck für Seite i} | \ mbox {treffe ein Rechteck}] = \ frac {\ mbox {Bereich des Rechtecks ​​für i}} {\ mbox {gesamte Rechteckfläche}} = \ frac {w h p_i} {w h} = p_i$$

Das heißt, die Wahrscheinlichkeit, ein einzelnes Rechteck auszuwählen, ändert sich nicht, wenn wir sie linear und gleichmäßig skalieren.

Da wir einen geeigneten Skalierungsfaktor auswählen können, warum skalieren wir diese Rechtecke nicht so, dass die Höhe des Begrenzungsrahmens immer 1 beträgt? Da die Höhe des Begrenzungsrahmens durch den Maximalwert bestimmt wird $$$p_i$ Eingabewahrscheinlichkeiten, dann können wir beginnen, indem wir jedes der Rechtecke um einen Faktor skalieren $$$\ frac {1} {p_ {max}}$ wo $$$p_ {max}$ Ist die maximale Wahrscheinlichkeit aller Eingangswahrscheinlichkeiten. Dank dessen erhalten wir die Höhe von Rechteck 1. Da wir für die Rechtecke eine beliebige Breite wählen können, nehmen wir die Breite 1. Dies bedeutet, dass für $$$n$ Die Wahrscheinlichkeiten der Gesamtbreite des Begrenzungsrahmens sind $$$n$ und die Gesamthöhe ist 1. Dies ist in der Abbildung dargestellt:


Jetzt sind wir bereit darüber nachzudenken, wie wir einen zufälligen Pfeil in ein Rechteck werfen und bestimmen können, in was er gefallen ist. Das Wichtigste ist, dass wir das Rechteck so teilen können, dass es nicht aus mehreren kleineren Rechtecken und einem leeren Raum mit einer seltsamen Form besteht. Stattdessen wird der Bereich in eine Reihe von geschnitten $$$2n$ Rechtecke, jeweils zwei auf $$$n$ Eingabewahrscheinlichkeiten. Dies wird hier gezeigt:


Beachten Sie, wie sich dieses Rechteck bildet. Für jede Seite des Betrügerknochens haben wir eine Spalte mit einer Breite von 1 und einer Höhe von 1, die in zwei Felder unterteilt ist - ein halbes Leerzeichen "Ja", das einem Rechteck dieser Größe entspricht, und ein halbes Leerzeichen "Nein", das dem verbleibenden Teil der Spalte entspricht.

Lassen Sie uns nun darüber nachdenken, wie wir einen Pfeil werfen können. Ein perfekt gleichmäßiger Pfeil, der in dieses Rechteck geworfen wird, hat Komponenten $$$x$ und $$$y$ . Hier Komponente $$$x$ das sollte in der Pause sein $$$[0, 1)$ , entspricht der Spalte, auf die der Pfeil trifft. Komponente $$$y$ das sollte in der Pause sein $$$[0, 1)$ entspricht, wie hoch wir in der Spalte sind. Komponentenauswahl $$$x$ beeinflusst, welches Gesicht des Betrügerknochens wir in Betracht ziehen, und die Wahl der Komponente $$$y$ entspricht, ob wir diese Facette gewählt haben oder nicht. Aber warten Sie - wir kennen diese beiden Ideen bereits! Koordinatenauswahl $$$x$ entsprechend der Säule, ähnlich wie ein ehrlicher Knochen zu werfen, um über die Wahl der Säule zu entscheiden. Koordinatenauswahl $$$y$ entspricht dem Wurf einer asymmetrischen Münze, um zu bestimmen, ob ein Gesicht ausgewählt oder erneut geworfen werden soll! Diese Beobachtung ist so wichtig, dass wir sie absolut verständlich machen:

Die Wahl eines zufälligen Punktes in diesem Intervall ähnelt dem Werfen eines ehrlichen Knochens und dem Werfen einer asymmetrischen Münze.

Tatsächlich kann dieses Ergebnis als viel mächtigere Gelegenheit wahrgenommen werden. Um einen betrügerischen Knochen zu simulieren, bauen wir einen Satz asymmetrischer Münzen, eine für jede Seite des Knochens, und rollen dann einen ehrlichen Knochen, um zu bestimmen, welche Münze geworfen werden soll. Wenn basierend auf der Knochenrolle ein Adler auf die entsprechende Münze fällt, wählen wir das entsprechende Gesicht aus. Wenn die Schwänze fallen, werfen wir den Knochen erneut und wiederholen den Vorgang.

. -, — «» $$$\frac{p_i}{p_{max}}$ , «» $$$\frac{p_{max} - p_i}{p_{max}}$ . , 1. -, $$$1$ , . , : - , , ( , ). . , , . .

: /

• :
  
  1. $$$p_i$ ; $$$p_{max}$ .
  2. $$$Coins$ $$$n$ , «» .
  3. $$$i$ $$$0$ vorher $$$n - 1$ ::
     
     1. $$$Coins[i] = \frac{p_i}{p_{max}}$
  
  
• :
  
  1. :
     
     1. n- $$$i$ $$$[0, n)$ .
     2. , $$$Coins[i]$ .
     3. , $$$i$ .

. $$$O (n)$ , $$$O (n)$ $$$Coins$ , $$$O (n)$ . , $$$O(1)$ . ? , , - . , . , ( $$$\frac{1}{n}$ ), . , , , , - , . , $$$i$ $$$\frac{p_i}{p_{max}}$ , -

$$ $$\sum_{i = 0}^{n - 1}{(\frac{1}{n} \frac{p_i}{p_{max}})} = \frac{1}{n}\sum_{i = 0}^{n - 1}{\frac{p_i}{p_{max}}} = \frac{1}{n \cdot p_{max}}\sum_{i = 0}^{n - 1}{p_i} = \frac{1}{n \cdot p_{max}}$$

- , , , , , $$$n \cdot p_{max}$ . ? $$$p_{max}$ . $$$p_{max}$ $$$1$ ( ). $$$n$ , $$$n$ . , , , , . , $$$p_{max}$ $$$\frac{1}{n}$ , , . Wenn $$$p_{max} = \frac{1}{n}$ , 1. . Wenn $$$p_{max} = \frac{1}{n}$ , ( $$$\frac{1}{n}$ ), 1, , 1. , , .

, $$$p_{max}$ , , , . , , $$$n$ , , 1. , , «» $$$\frac{1}{p_{max}}$ , 1, $$$\frac{1}{p_{max}}$ . , «» $$$\frac{1}{n \cdot p_{max}}$ . , , «», $$$p_{max}$ . , , .

:

Algorithmus
	$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$	$$$\Theta(1)$		$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$
	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$	$$$\Theta(n)$
	$$$\Theta(n)$		$$$\Theta(\log n)$		$$$\Theta(n)$
	$$$O(n^2)$		$$$\Theta(1)$	$$$O(\log n)$	$$$\Theta(n)$
/	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$ ()	$$$\Theta(n)$

, . . ?

Alias-

, . , . , , «» , . , , , . - , , - , .

, , , . . $$$\frac{1}{2}$ , $$$\frac{1}{3}$ , $$$\frac{1}{12}$ , $$$\frac{1}{12}$ . , $$$\frac{1}{4}$ . , $$$\frac{1}{4}$ , $$$\frac{1}{2}$ ? , . $$$1$ , :


, $$$\frac{1}{4}$ 1. , , :


$$$1 \times 4$ . , :


, , $$$\frac{1}{2}$ und $$$\frac{1}{3}$ . ? , $$$\frac{1}{2}$ $$$\frac{1}{12}$ ? , - , :


, , . , $$$\frac{1}{2}$ und $$$\frac{1}{3}$ , . $$$\frac{1}{2}$ , . , :


, , :


. -, . , ; . , , . -, , , - , , . , . — , . , — , , . , . , , , - ( ).

alias- . -, , . , , . , , , .

, , ? , , . , , , , , . , . , - , , , ( ) , - . (alias) , «» - . - «alias» «alias-».

, , . - ( !), () , , alias- : $$$Prob$ alias $$$Alias$ . $$$n$ . , alias , ( ). , . - - $$$i$ . $$$Prob[i]$ . , , $$$i$ , , $$$Alias[i]$ . alias :

Alias

, $$$Alias$ und $$$Prob$ . , , :

• $$$(n \cdot p_i) \times 1$ $$$p_i$ ,
• $$$n$
  
  • , $$$1$ ,
  • , $$$i$ , $$$i$ .

, , . , $$$\frac{1}{2}$ , $$$\frac{1}{3}$ , $$$\frac{1}{12}$ , $$$\frac{1}{12}$ . ( $$$k = n = 4$ ), $$$1 = \frac{4}{4}$ . , alias, , . , 4, :


, , ( $$$\frac{1}{3}$ , $$$\frac{1}{3}$ ) 1. , - . ( ) :


- . , , , 1 ( $$$2$ und $$$\frac{4}{3}$ ) ; $$$\frac{4}{3}$ . $$$\frac{4}{3}$ , ; $$$\frac{2}{3}$ von $$$\frac{4}{3}$ , :


, . , $$$3$ , , , . , . , , $$$1$ , (, $$$\frac{2}{3}$ ) :


, - , 1, . ( $$$2$ ), $$$\frac{1}{3}$ von $$$2$ :


, . , - , 1 ( $$$\frac{1}{3}$ ), :


- $$$1$ , . — $$$\frac{5}{3}$ ::


, 1. , :


! .

, :

• - , 1, , $$$Prob$ .
• - , 1, , $$$Alias$ , .

, ? «», ? , . : , 1 ( $$$\frac{1}{n}$ , $$$n$ ) , , , , 1 ( ) 1 ( ). , . , ? , . , , . , .

:

: $$$k$ $$$h_0$ , $$$h_1$ , ..., $$$h_{k-1}$ , , $$$\sum_{i=0}^{k-1}{h_i} = k$ , $$$k$ , 1, , , $$$i$ - $$$i$ - .

: . , $$$k = 1$ , 1. $$$0$ - . , 1, , $$$0$ - $$$0$ - .

, - $$$k$ $$$k + 1$ $$$1$ $$$h_0$ , $$$h_1$ , ..., $$$h_{k}$ , , $$$\sum_{i = 0}^{k}{h_i} = k + 1$ . , $$$h_l$ , , $$$h_l \le 1$ , - $$$h_g$ (, $$$l \ne g$ ), , $$$h_g \ge 1$ . , , $$$h_l$ mit $$$h_l \le 1$ ; , $$$h_i > 1$ $$$i$ $$$0 \le i \le k$ . , $$$k + 1 = \sum_{i = 0}^k{h_i} > \sum_{i=0}^k{1} = k + 1$ , . , - $$$l$ , , $$$h_l \le 1$ . , $$$h_g$ ( $$$l \ne g$ ), , $$$h_g \ge 1$ . , $$$h_g < 1$ , ( ) $$$\sum_{i=0}^{k}{h_i} < k + 1$ . , $$$h_l \le 1$ und $$$h_g \ge 1$ .

. $$$h_l$ $$$l$ $$$1 - h_l$ in $$$l$ - $$$h_g$ ( , $$$0 \le 1 - h_l \le 1$ und $$$h_g \ge 1$ ) . $$$k$ , $$$k$ , $$$1$ , $$$k + 1$ . , $$$l$ , . , , $$$k$ in $$$k$ , . , $$$l$ , , , . .

, , alias, , . alias.

Alias

, alias-. 1 1, :

: Alias-

• :
  
  1. $$$p_i$ auf $$$n$ .
  2. $$$Alias$ und $$$Prob$ , $$$n$ .
  3. For $$$j = 1 \mbox{ to } n - 1$ ::
     
     1. $$$p_l$ , $$$p_l \le 1$ .
     2. $$$p_g$ ( $$$l \ne g$ ), $$$p_g \ge 1$
     3. $$$Prob[l] = p_l$ .
     4. $$$Alias[l] = g$ .
     5. $$$p_l$ .
     6. $$$p_g := p_g - (1 - p_l)$ .
     
     
  4. Lass $$$i$ , 1.
  5. $$$Prob[i] = 1$ .
  
  
• :
  
  1. $$$n$ - ; $$$i$ .
  2. , $$$Prob[i]$ .
  3. , $$$i$ .
  4. $$$Alias[i]$ .

, , $$$\Theta(1)$ . . -, $$$\Theta(n)$ $$$n$ , $$$O (n)$ . $$$\Theta(n)$ , $$$O (n)$ , . $$$O(n^2)$ . , :

Algorithmus
	$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$	$$$\Theta(1)$		$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$
	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$	$$$\Theta(n)$
	$$$\Theta(n)$		$$$\Theta(\log n)$		$$$\Theta(n)$
	$$$O(n^2)$		$$$\Theta(1)$	$$$O(\log n)$	$$$\Theta(n)$
/	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$ ()	$$$\Theta(n)$
Alias-	$$$O(n^2)$		$$$\Theta(1)$		$$$\Theta(n)$

alias- , . - (, $$$O (n)$ ), .

. , $$$O (n)$ . . $$$p_g$ und $$$p_l$ $$$O(\log n)$ , . Löschen $$$p_l$ $$$O(\log n)$ , $$$p_g$ $$$O(\log n)$ . :

: Alias-

• :
  
  1. $$$Alias$ und $$$Prob$ , $$$n$ .
  2. $$$T$ .
  3. $$$n \cdot p_i$ in $$$T$ $$$i$ .
  4. For $$$j = 1 \mbox{ to } n - 1$ ::
     
     1. $$$T$ ; $$$p_l$ .
     2. $$$T$ ; $$$p_g$ .
     3. $$$Prob[l] = p_l$ .
     4. $$$Alias[l] = g$ .
     5. $$$p_g := p_g - (1 - p_l)$ .
     6. $$$p_g$ zu $$$T$ .
     
     
  5. Lass $$$i$ , 1.
  6. $$$Prob[i] = 1$ .
  
  
• :
  
  1. $$$n$ - ; $$$i$ .
  2. , $$$Prob[i]$ .
  3. , $$$i$ .
  4. $$$Alias[i]$ .

. $$$Alias$ und $$$Prob$ - $$$O (n)$ , BST $$$T$ $$$\Theta(n \log n)$ . $$$\Theta(n)$ , $$$O(\log n)$ . $$$O(n \log n)$ ::

Algorithmus
	$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$	$$$\Theta(1)$		$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$
	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$	$$$\Theta(n)$
	$$$\Theta(n)$		$$$\Theta(\log n)$		$$$\Theta(n)$
	$$$O(n^2)$		$$$\Theta(1)$	$$$O(\log n)$	$$$\Theta(n)$
/	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$()	$$$\Theta(n)$
Alias-	$$$O(n^2)$		$$$\Theta(1)$		$$$\Theta(n)$
Alias-	$$$O(n \log n)$		$$$\Theta(1)$		$$$\Theta(n)$

, . , , , alias-. «A Linear Algorithm For Generating Random Numbers With a Given Distribution» , alias-.

: 1, 1. . «» , «» «». :

• «» 1.
• «» 1.
• .

, , , . , :

: () Alias-

: . .

• :
  
  1. $$$Alias$und $$$Prob$, $$$n$.
  2. , $$$Small$und $$$Large$.
  3. $$$n$.
  4. $$$p_i$::
     
     1. Wenn $$$p_i < 1$, $$$i$zu $$$Small$.
     2. ( $$$p_i \ge 1$) $$$i$zu $$$Large$.
     
     
  5. $$$Small$:
     
     1. $$$Small$; $$$l$.
     2. $$$Large$; $$$g$.
     3. $$$Prob[l] = p_l$.
     4. $$$Alias[l] = g$.
     5. $$$p_g := p_g - (1 - p_l)$.
     6. Wenn $$$p_g < 1$, $$$g$in $$$Small$.
     7. ($p_g \ge 1$) $$$g$in $$$Large$.
     
     
  6. $$$Large$:
     
     1. $$$Large$; $$$g$.
     2. $$$Prob[g] = 1$.
     
     
  
  
• :
  
  1. $$$n$- ; $$$i$.
  2. , $$$Prob[i]$.
  3. , $$$i$.
  4. $$$Alias[i]$.

(, ) : - $$$Small$$$$Large$, . . $$$Small$$$$Large$( $$$Small$, , ). $$$Large$1, $$$k$$$$Large$$$$k$, $$$Large$1, . 1, , , 1.

. , , , . .

, . $$$\frac{1}{4}$, $$$\frac{1}{5}$, $$$\frac{1}{8}$, $$$\frac{1}{8}$, $$$\frac{1}{10}$, $$$\frac{1}{10}$, $$$\frac{1}{10}$. , , $$$\frac{1}{8}$, $$$\frac{1}{5}$, $$$\frac{1}{10}$, $$$\frac{1}{4}$, $$$\frac{1}{10}$, $$$\frac{1}{10}$, $$$\frac{1}{8}$. :


$$$Small$, :


$$$Large$( ) . $$$\frac{7}{4} - \frac{1}{8} = \frac{13}{8} \ge 1$, $$$Large$::


. $$$Small$, $$$Large$::


:


, , , . , :


$$$Small$, :


$$$Small$, , :


, $$$Small$, .


alias .

, . , , IEEE-754 double, . , , :

1. , $$$Small$$$$Large$, . , , $$$n$, , $$$\frac{1}{n}$, $$$1$( $$$Small$, $$$Large$)
2. , , . , , $$$Large$, $$$Small$.

, $$$Small$$$$Large$. , , $$$Small$, $$$Large$.

, . , , , $$$Large$. -, , $$$1$, , $$$1$. , . :

: Alias-

• :
  
  1. $$$Alias$und $$$Prob$, $$$n$.
  2. , $$$Small$und $$$Large$.
  3. $$$n$.
  4. $$$p_i$::
     
     1. Wenn $$$p_i < 1$, $$$i$in $$$Small$.
     2. ( $$$p_i \ge 1$) $$$i$in $$$Large$.
     
     
  5. $$$Small$und $$$Large$: ( $$$Large$)
     
     1. $$$Small$; $$$l$.
     2. $$$Large$; $$$g$.
     3. $$$Prob[l] = p_l$.
     4. $$$Alias[l] = g$.
     5. $$$p_g := (p_g + p_l) - 1$. ( . )
     6. Wenn $$$p_g < 1$, $$$g$in $$$Small$.
     7. ( $$$p_g \ge 1$) $$$g$in $$$Large$.
     
     
  6. $$$Large$:
     
     1. $$$Large$; $$$g$.
     2. $$$Prob[g] = 1$.
     
     
  7. $$$Small$: - .
     
     1. $$$Small$; $$$l$.
     2. $$$Prob[l] = 1$.
     
     
  
  
• :
  
  1. $$$n$- ; $$$i$.
  2. , $$$Prob[i]$.
  3. , $$$i$.
  4. $$$Alias[i]$.

, — . $$$\Theta(n)$, . $$$\Theta(1)$, , . $$$O (n)$, () , . $$$O (n)$, $$$Large$und $$$Small$$$$O (n)$. $$$\Theta(n)$, ( ) :

Algorithmus
	$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$	$$$\Theta(1)$		$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$
	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$	$$$\Theta(n)$
	$$$\Theta(n)$		$$$\Theta(\log n)$		$$$\Theta(n)$
	$$$O(n^2)$		$$$\Theta(1)$	$$$O(\log n)$	$$$\Theta(n)$
/	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$()	$$$\Theta(n)$
Alias-	$$$O(n^2)$		$$$\Theta(1)$		$$$\Theta(n)$
Alias-	$$$O(n \log n)$		$$$\Theta(1)$		$$$\Theta(n)$
Alias-	$$$\Theta(n)$		$$$\Theta(1)$		$$$\Theta(n)$

! ! , . , (alias- ) , - .

alias- , , - , alias- Java , .

, !