Zeichnen Sie ganze Zahlen unabhängig und gleichmäßig zufällig von 1 bis mit fairem d6?

18

Ich möchte ganze Zahlen von 1 bis zu einem bestimmten zeichnen, indem ich eine Reihe von fairen sechsseitigen Würfeln würfle (d6). Eine gute Antwort erklärt, warum seine Methode einheitliche und unabhängige ganze Zahlen erzeugt.NN

Als anschauliches Beispiel wäre es hilfreich zu erläutern, wie eine Lösung für den Fall von funktioniert .N = 150N=150

Außerdem möchte ich, dass das Verfahren so effizient wie möglich ist: Wirf für jede generierte Zahl im Durchschnitt die geringste Anzahl von d6.

Umrechnungen von Senior auf Dezimal sind zulässig.


Diese Frage wurde von diesem Meta-Thread inspiriert .

Sycorax sagt Reinstate Monica
quelle

Antworten:

12

Die Menge Ω ( d , n )Ω(d,n) verschiedener identifizierbarer Ergebnisse in nn unabhängigen Walzen eines Würfels mit d = 6d=6 Flächen hat d ndn Elemente. Wenn der Würfel fair ist, bedeutet dies, dass jedes Ergebnis eines Wurfs eine Wahrscheinlichkeit von 1 / d hat,1/d und Unabhängigkeit bedeutet, dass jedes dieser Ergebnisse eine Wahrscheinlichkeit von ( 1 / d ) n hat :(1/d)n: Das heißt, sie haben eine gleichmäßige Verteilung P d , n .Pd,n.

Angenommen , Sie haben einige Verfahren entwickelt tt , dass entweder Ermittelt mm Ergebnisse einer c ( = 150 )c(=150) -sided die - das heißt, ein Element von Ω ( c , m )Ω(c,m) --oder sonst meldet eine Störung (das heißt , Sie zu wiederholen haben es, um ein Ergebnis zu erzielen). Das ist,

t : Ω ( d , n ) Ω ( c , m ) { Fehler } .

t:Ω(d,n)Ω(c,m){Failure}.

Lassen Sie FF die Wahrscheinlichkeit sein tt zu einem Fehler und beachten Sie, dass FF einige ganzzahligen Vielfachen ist d - n ,dn, sagen wir

F = Pr ( t ( ω ) = Failure ) = N Fd - n .

F=Pr(t(ω)=Failure)=NFdn.

(Beachten Sie als zukünftige Referenz, dass die erwartete Anzahl von Malen, die aufgerufen werden muss, bevor es nicht fehlschlägt, )t t1 / ( 1 - F ) .1/(1F).

Die Forderung , dass diese Ergebnisse in einheitlich und unabhängig seine bedingten auf nicht Ausfall bedeutet , dass die Berichterstattung Konserven Wahrscheinlichkeit in dem Sinne , dass für jede VeranstaltungΩ ( c , m ) Ω(c,m)t t AΩ ( c , m ) ,ttAΩ(c,m),

P d , n ( t A )1 - F =Pc,m(A)

Pd, n( tEIN)1 - F= Pc , m( A)(1)

wo

t ( A ) = { ω Ω t ( ω ) A }

t( A) = { ω Ω t ( ω ) A}

ist der Würfelwurfsatz, den die Prozedur dem Ereignis zuweistt tA .EIN.

Man betrachte ein atomares Ereignis , das die WahrscheinlichkeitLassen (würfelt mit zugehörigem ) haben Elemente. wirdA = { η } Ω ( c , m ) EIN= { η} Ω ( c , m )c - m . cm.t ( A )t(A) η ηN ηNη ( 1 )(1)

N η d - n1 - N F d - n = P d , n ( t A )1 - F =Pc,m(A)=c-m.

Nηdn1NFdn=Pd,n(tA)1F=Pc,m(A)=cm.(2)

Es ist unmittelbar, dass die alle gleich einer ganzen ZahlN & eegr;Nη N . N. Es bleibt nur die effizienteste Prozedur Die erwartete Anzahl von Nichtfehlern pro Rolle des seitigen Würfels beträgtt. t.cc

1m (1-F).

1m(1F).

Es gibt zwei unmittelbare und offensichtliche Auswirkungen. Eine ist, dass, wenn wir klein halten können, während groß wird, der Effekt der Meldung eines Fehlers asymptotisch Null ist. Das andere ist, dass wir für jedes gegebene (die Anzahl der Rollen des seitigen Würfels, die simuliert werden sollen) so klein wie möglich machen wollen .F Fm mm mc cFF

Schauen wir uns genauer an, indem wir die Nenner löschen:( 2 )(2)

N c m = d n - N F > 0.

Ncm=dnNF>0.

Dies macht es offensichtlich, dass in einem gegebenen Kontext (bestimmt durch ) so klein wie möglich gemacht wird, indem gleich dem größten Vielfachen von , das kleiner oder gleich ist Wir können dies in Form der größten Ganzzahlfunktion (oder "Etage") as schreibenc , d , n , m c,d,n,mF Fd n - N F dnNFc m cmd n . dn.*

N = d nc m.

N=dncm.

Schließlich ist klar, dass für höchste Effizienz so klein wie möglich sein sollte, da es die Redundanz in misst . Insbesondere ist die erwartete Anzahl von Rollen der seitigen Düse, die benötigt wird, um eine Rolle der seitigen Düse herzustellen, gleichN Nt d ctdc

N × nm ×11 - F .

N×nm×11F.

Unsere Suche nach hocheffizienten Verfahren sollte sich daher auf die Fälle konzentrieren, in denen gleich oder kaum größer als eine Potenzd n dnc m .cm.

Die Analyse endet damit, dass es für gegebenes und eine Folge von Vielfachen für die sich dieser Ansatz der perfekten Effizienz annähert. Dies läuft auf das Finden von für das sich im Grenzfall nähert (wobei automatisch garantiert wird ). Eine solche Sequenz wird erhalten, indem und bestimmt werdend dc , c,( n , m ) (n,m)( n , m ) (n,m)d n / c m1 dn/cm1N = 1 N=1F 0 F0n = 1 , 2 , 3 , n=1,2,3,

m = n log dlog c.

m=nlogdlogc.(3)

Der Beweis ist unkompliziert.

Dies alles bedeutet, dass wir, wenn wir bereit sind, den ursprünglichen seitigen Würfel eine ausreichend große Anzahl von Malen werfen damit rechnen können, nahezu Ergebnisse eines seitigen Würfels pro Wurf zu simulieren . Äquivalent dazud dn , n,log d / log c = log c d logd/logc=logcdcc

Es ist möglich, eine große Anzahl unabhängiger Walzen eines seitigen Würfels unter Verwendung eines fairen seitigen Würfels unter Verwendung eines Durchschnitts von rollt pro Ergebnis, wobei beliebig klein gemacht werden kann, indem ausreichend groß gewählt wird.m mc cd dlog ( c ) / log ( d ) + ϵ = log d ( c ) + ϵ log(c)/log(d)+ϵ=logd(c)+ϵϵ ϵmm


Beispiele und Algorithmen

In der Frage ist und woherd = 6 d=6c = 150 ,c=150,

log d ( c ) = log ( c )log ( d )2,796489.

logd(c)=log(c)log(d)2.796489.

Für das bestmögliche Verfahren sind daher durchschnittlich mindestens Rollen erforderlich, um jedes Ergebnis zu simulieren .2.7964892.796489d6d150

Die Analyse zeigt, wie das geht. Wir müssen nicht auf die Zahlentheorie zurückgreifen, um sie auszuführen: Wir können einfach die Potenzen und die Potenzen tabellieren und vergleichen, um herauszufinden, wo sind nah. Diese Brute-Force-Berechnung ergibt Paared n = 6 n dn=6nc m = 150 m cm=150mc md ncmdn ( n , m )(n,m)

( n , m ) { ( 3 , 1 ) , ( 14 , 5 ) , }

(n,m){(3,1),(14,5),}

zum Beispiel entsprechend den Zahlen

( 6 n , 150 m ) { ( 216 , 150 ) , ( 78364164096 , 75937500000 ) , } .

(6n,150m){(216,150),(78364164096,75937500000),}.

Im ersten Fall würde der Ergebnisse von drei von a bis Failure , und die anderen Ergebnisse würden jeweils einem einzelnen Ergebnis von a zugeordnet . t t216 - 150 = 66 216150=66150d6150d150

Im zweiten Fall würde der Ergebnisse von 14 a bis Failure - etwa 3,1% von allen - und andernfalls eine Folge von 5 Ergebnissen von a ausgeben .t t78364164096 - 759375000007836416409675937500000d6d150

Ein einfacher Algorithmus zum Implementieren vontt d 0 , 1 , , d - 1 c 0 , 1 , , c - 1. n n d . c . m m t beschriftet die Flächen des seitigen Chips mit den Ziffern und die Flächen des seitigen Chips mit den Ziffern Die Würfe des ersten Würfels werden als stellige Zahl in der Basis interpretiert Dies wird in eine Zahl in Basis Wenn es höchstens Ziffern hat, ist die Reihenfolge der letzten Ziffern die Ausgabe. Andernfalls gibt Failure zurück, indem es sich rekursiv aufruft.d0,1,,d1c0,1,,c1.nnd.c.mmt

Für viel längere Sequenzen können Sie geeignete Paare indem Sie jedes andere konvergente der fortgesetzten Bruchexpansion von berücksichtigen Die Theorie der fortgesetzten Brüche zeigt, dass diese Konvergenzien abwechselnd kleiner als und größer als sind (vorausgesetzt, ist nicht bereits rational). Wählen Sie diejenigen, die kleiner als( n , m ) (n,m)n / m n/mx = log ( c ) / log ( d ) . x=log(c)/log(d).x xx xx .x.

In der Frage sind die ersten paar solcher Konvergente

3 , 14 / 5 , 165 / 59 , 797 / 285 , 4301 / 1538 , 89043 / 31841 , 279.235 / 99.852 , 29.036.139 / 10.383.070 ... .

3,14/5,165/59,797/285,4301/1538,89043/31841,279235/99852,29036139/10383070.

Im letzten Fall ergibt eine Folge von 29.036.139 a-Rollen d6eine Folge von 10.383.070 a-Rollen d150mit einer Fehlerrate von weniger als bei einer von der asymptotischen Grenze unterscheidbaren Effizienz von .2 × 10 - 8 , 2×108,2,796492.79649

whuber
quelle
2
Wie immer erstaunlich, es sieht fast so aus, als wäre diese Antwort formatiert und vorbereitet worden, noch bevor die Frage gestellt wurde!
Łukasz Grad
1
Vielen Dank, @ ŁukaszGrad. Ich bin jedoch unschuldig an solchen Machenschaften, und ich bin sicher, dass scharfsichtige Leser Beweise für die Eile finden werden, mit der ich dies ausgeschrieben habe, für die ich mich im Voraus entschuldige.
whuber
Sollte nicht auch berücksichtigt werden, dass der Abtastraum in Teilmengen gleicher Wahrscheinlichkeit aufgeteilt werden kann , wenn nicht prim ist ? Zum Beispiel können Sie ein d6 als ein d2 oder ein d3 verwenden, und ein Probenraum mit 162 Elementen - näher an 150 als 216 - ist dann mit 4 Rollen erreichbar, 1d6 + 3d3. (Das ergibt die gleiche erwartete Anzahl an Würfeln wie bei der 3d6-Lösung, aber eine geringere Varianz.)ddΩ(d,1)Ω(d,1)
Scortchi - Reinstate Monica
@Scortchi Sie beschreiben eine etwas andere Einstellung, bei der Sie eine Auswahl an Würfeln verwenden können, um Ziehungen aus einer gleichmäßigen Verteilung zu simulieren. Eine ähnliche Analyse trifft zu - Sie werden es vielleicht amüsant finden, sie durchzuführen.
whuber
7

Für den Fall von führt das dreimalige Rollen eines d6 eindeutig zu Ergebnissen.N=150N=15063=21663=216

Das gewünschte Ergebnis kann folgendermaßen tabelliert werden:

  • Nehmen Sie einen d6 dreimal nacheinander auf. Dies ergibt die Ergebnisse . Das Ergebnis ist einheitlich, da alle Werte von gleich wahrscheinlich sind (die Würfel sind fair und wir behandeln jeden Wurf als unterschiedlich).a,b,ca,b,ca,b,ca,b,c
  • Jeweils 1 abziehen.
  • Dies ist eine ältere Zahl: Jede Ziffer (Stellenwert) geht von 0 bis 5 durch Potenzen von 6, sodass Sie die Zahl mit dezimal schreiben können(a1)×62+(b1)×61+(c1)×60
    (a1)×62+(b1)×61+(c1)×60
  • Addiere 1.
  • Wenn das Ergebnis 150 überschreitet, verwerfen Sie das Ergebnis und rollen Sie erneut.

Die Wahrscheinlichkeit, ein Ergebnis zu behalten, ist . Alle Würfe sind unabhängig und wir wiederholen den Vorgang bis zu einem "Erfolg" (ein Ergebnis von ), so dass die Anzahl der Versuche , einen Draw zwischen 1 und 150 zu generieren, als geometrische Zufallsvariable verteilt wird hat die Erwartung . Daher erfordert die Verwendung dieser Methode zum Generieren von 1 Draw das Würfeln von Würfeln im Durchschnitt (da jeder Versuch 3 Würfel würfelt).p=150216=2536p=150216=25361,2,,1501,2,,150p1=3625p1=36253625×3=4.323625×3=4.32


Wir danken @whuber dafür, dass er dies im Chat vorgeschlagen hat.

Sycorax sagt Reinstate Monica
quelle
Ich glaube, Henrys Methode führt nicht zu einer gleichmäßigen Verteilung. Das liegt daran, dass beim Recycling einige Ziffern bevorzugt werden. Da bin ich mir nicht ganz sicher, da ich nicht ganz verstehe, wie das Recycling durchgeführt werden soll.
whuber
1
@whuber AH! Ich verstehe jetzt Ihre Besorgnis. Ich habe gerade versucht, mir den Prozess zu erklären, und mir wurde klar, warum meine Intuition fehlerhaft war: Die Wahrscheinlichkeit, einen zusätzlichen Würfel zu werfen, kann die Zuordnung von Wahrscheinlichkeiten zu Dezimalzahlen ändern und sie ungleichmäßig machen, weil wir nicht im Voraus wissen, wie viele Würfel rollen wir.
Sycorax sagt Reinstate Monica
4

Hier ist eine noch einfachere Alternative zur Antwort von Sycorax für den Fall, dass N = 150 istN=150 . Da 150 = 5 × 5 × 6150=5×5×6 , können Sie das folgende Verfahren ausführen:

Generierung einer einheitlichen Zufallszahl von 1 bis 150:

  • Bilden Sie drei bestellte Rollen von 1D6 und bezeichnen Sie diese als R 1 , R 2 , R 3R1,R2,R3 .
  • Wenn einer der ersten beiden Würfe eine Sechs ist, wiederholen Sie den Vorgang, bis er nicht mehr 6 ist.
  • Die Zahl ( R 1 , R 2 , R 3 )(R1,R2,R3) ist eine einheitliche Zahl unter Verwendung der Positionsnotation mit einem Radix von 5-5-6. Somit können Sie die gewünschte Zahl wie folgt berechnen: X = 30 ( R 1 - 1 ) + 6 ( R 2 - 1 ) + ( R 3 - 1 ) + 1.
    X=30(R11)+6(R21)+(R31)+1.

Diese Methode kann auf ein größeres NN verallgemeinert werden , wird jedoch etwas umständlicher, wenn der Wert einen oder mehrere Primfaktoren größer als 6 hat6 .

Setzen Sie Monica wieder ein
quelle
1
Können Sie die Effizienz dieser Methode in Bezug auf die erwartete Anzahl der pro Ziehung erzeugten Rollen angeben und klären, warum das Ergebnis bei 1,2, ...., 150 einheitlich ist?
Sycorax sagt Reinstate Monica
Die Wahrscheinlichkeit, ein Ergebnis zu erzielen, das nicht erneut gewürfelt werden muss, beträgt 25/36 . Dies entspricht der Ihrer Antwort. Um zu verstehen, warum es einheitlich ist, beachten Sie, dass Sie effektiv nur eine einheitliche Zahl unter Verwendung der Positionsnotation mit dem Radix 5-5-6 erzeugen (dh die letzte Ziffer ist die Einheit, die vorletzte Ziffer ist die "Sechs" und die dritte -letzte Ziffer ist die "dreißiger Jahre"). 25/36
Setzen Sie Monica
1
Die Methode ist praktisch nur eine sehr geringfügige Abweichung von der Methode in Ihrer Antwort. In Ihrer Antwort erstellen Sie eine einheitliche Zahl auf der 6-6-6-Zahlenskala und verwerfen dann ungültige Werte, während Sie in meiner Antwort zuerst ungültige Werte verwerfen , um eine Zahl auf der 5-5-6-Skala zu generieren.
Setzen Sie Monica
3
+1 In der Praxis ist dies ein ansprechender Algorithmus. Es ist faszinierend und weist möglicherweise auf eine breitere Analyse hin, dass es einen endlichen Automaten implementiert, der von den Würfeln angetrieben wird. Es hat vier Zustände: {Start, A, B, Accept}. Beginnen Sie die Übergänge zu A nach dem Würfeln 1..5; A geht beim Würfeln nach B über 1..5; und B wechselt zu Accept, wenn etwas gewürfelt wird. Jeder Übergang speichert den Wert der Rolle, die ihn verursacht hat. Wenn Sie also Accept (Akzeptieren) erreichen, geben Sie diese Folge von drei gespeicherten Rollen aus und wechseln automatisch zurück zu Start.
whuber
4
Sie lehnen so oft wie @Sycorax ab, machen aber im Durchschnitt weniger Rollen. Das erwartete Nein. Rollen pro Variante ist 65 +65 +1=3,4. 65+65+1=3.4
Scortchi
2

Versuchen Sie zur Veranschaulichung eines Algorithmus, mit dem Sie unter Verwendung von sechsseitigen Würfeln einheitlich zwischen 150150 Werten wählen können , bei dem bei jedem Wurf die verfügbaren Werte mit 66 multipliziert werden und jeder der neuen Werte gleich wahrscheinlich wird:

  • Nach 00 Würfen haben Sie 11 Möglichkeit, nicht genug, um 150150 Werte zu unterscheiden
  • Nach 11 Rolle, haben Sie 66 Möglichkeiten, nicht genug zu unterscheiden 150150 Werte
  • Nach 22 Würfeln haben Sie 3636 Möglichkeiten, die nicht ausreichen, um 150150 Werte zu unterscheiden
  • Nach 33 Würfen haben Sie 216216 Möglichkeiten, genug, um 150150 Werte zu unterscheiden , aber mit 6666 verbleibenden Werten. Die Wahrscheinlichkeit, dass Sie jetzt aufhören, ist 150216150216
  • Wenn Sie nicht gestoppt haben, haben Sie nach 44 Würfen 396396 verbleibende Möglichkeiten, genug, um 150150 Werte auf zwei Arten zu unterscheiden, aber mit 9696 verbleibenden Werten. Die Wahrscheinlichkeit, dass Sie jetzt aufhören, ist 30012963001296
  • Wenn Sie nicht gestoppt haben, haben Sie nach 55 Würfen 576576 verbleibende Möglichkeiten, genug, um 150150 Werte auf drei Arten zu unterscheiden, aber mit 9696 verbleibenden Werten. Die Wahrscheinlichkeit, dass Sie jetzt aufhören, ist 45077764507776
  • Wenn Sie nicht gestoppt haben, haben Sie nach 66 Würfen 756756 verbleibende Möglichkeiten, genug, um 150150 Werte auf fünf Arten zu unterscheiden, aber mit 66 verbleibenden Werten. Die Wahrscheinlichkeit, dass Sie jetzt aufhören, ist 7504665675046656

Wenn Sie nach 6 Würfeln auf einem der 66 verbleibenden Werte sind, befinden Sie sich in einer ähnlichen Situation wie nach 1 Wurf. Sie können also auf die gleiche Weise fortfahren: Die Wahrscheinlichkeit, dass Sie nach 7 Würfeln aufhören , ist 06172799360279936 , nach88Rollen ist15016796161501679616 usw.

Addieren3.39614 Sie diese und Sie stellen fest, dass die erwartete Anzahl der benötigten Rollen bei 3.39614 liegt . Es bietet eine einheitliche Auswahl aus den 150150 , da Sie nur einen Wert zu einem Zeitpunkt auswählen, zu dem Sie jeden der 150150 mit gleicher Wahrscheinlichkeit auswählen können


Sycorax bat in den Kommentaren um einen expliziteren Algorithmus

  • Zuerst werde ich in base- 66 mit 150 10 = 410 6 arbeiten15010=4106
  • Zweitens subtrahiere ich statt der Zielwerte 1 616 bis 410 64106 einen, sodass die Zielwerte 0 606 bis 409 6 sind4096
  • Drittens sollte jeder Würfel die Werte 0 606 bis 5 6 haben56 , und beim Würfeln eines Würfels wird eine 6-6 stellige Basis zur rechten Seite der vorhandenen generierten Zahl hinzugefügt . Generierte Zahlen können führende Nullen haben, und ihre Anzahl von Ziffern ist die Anzahl der Rollen, die bisher ausgeführt wurden

Der Algorithmus besteht aus aufeinanderfolgenden Würfeln:

  • Wirf die ersten drei Würfel, um eine Zahl von 000 60006 bis 555 6 zu erhalten5556 . Da 1000 6 ÷ 410 6 = 1 6  Rest  150 610006÷4106=16 remainder 1506 , nehmen Sie den generierten Wert (der auch der Rest bei Division durch 410 6 ist4106 ), wenn der generierte Wert streng unter 1000 6 - 150 6 = 410 6 liegt,100061506=4106 und stoppen;

  • Wenn Sie fortfahren, werfen Sie den vierten Würfel, sodass Sie jetzt eine Zahl von 4100 641006 bis 5555 655556 generiert haben . Da 10000 6 ÷ 410 6 = 12 6  Rest  240 6100006÷4106=126 remainder 2406 , nehmen Sie den Rest des generierten Wertes bei Division durch 410 6,4106 wenn der generierte Wert genau unter 10000 6 liegt - 240 6 = 5320 6 und stoppen;

  • Wenn Sie fortfahren, werfen Sie den fünften Würfel, sodass Sie jetzt eine Zahl von 53200 6 bis 55555 6 generiert haben . Da 100000 6 ÷ 410 6 = 123 6  Rest  330 6 , wird der Rest des generierten Wertes bei Division durch 410 6 genommen, wenn der generierte Wert genau unter 100000 6 - 330 6 = 55230 6 liegt, und gestoppt.

  • Wenn Sie fortfahren, werfen Sie den sechsten Würfel, sodass Sie jetzt eine Zahl von 552300 6 bis 555555 6 generiert haben . Da 1000000 6 ÷ 410 6 = 1235 6  Rest  10 6 , wird der Rest des generierten Wertes bei Division durch 410 6 genommen, wenn der generierte Wert genau unter 1000000 6 - 10 6 = 555550 6 liegt, und gestoppt.

  • etc.

Henry
quelle
(+1) Diese Antwort wäre klarer, wenn Sie erklären würden, wie Sie die Ergebnisse von beispielsweise 4W6 oder 5W6 auf 1,2, ..., 150 abbilden.
Sycorax sagt Reinstate Monica
@Sycorax - Ich habe jetzt eine Basis 6- Zuordnung bereitgestellt
Henry
1
Überlegungen zur Entropie deuten darauf hin, dass Sie wesentlich bessere Ergebnisse erzielen können als mit diesem Algorithmus. Es bleibt auch zu zeigen, dass Ihr Algorithmus tatsächlich unabhängig verteilte Werte mit gleichmäßigen Verteilungen erzeugt.
whuber
@whuber - Mein Algorithmus erzeugt aus 150 Möglichkeiten genau eine ganze Zahl und zwar gleichmäßig, sofern die Würfel gleichmäßig und unabhängig sind. Bei jedem erreichten Schritt wird wahrscheinlich jeder der 150 Werte gleichermaßen ausgewählt. Es werden nicht mehrere Werte erzeugt (im Gegensatz zu Ihrer Antwort)
Henry
1
Ich habe falsch verstanden, was Sie damit gemeint haben: "Der Algorithmus besteht aus aufeinanderfolgenden Würfeln." (Ich hätte es genauer durchlesen sollen.) Dabei scheint es mir, dass Ihr Algorithmus keine einheitliche Verteilung erzeugt, aber ich bin mir nicht sicher, weil ich nicht herausgefunden habe, wozu der allgemeine Algorithmus gedacht ist Sein. Es wäre gut, eine Demonstration zu sehen, die einheitliche Werte hervorbringt.
whuber