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 ,d−n, sagen wir
F = Pr ( t ( ω ) = Failure ) = N Fd - n .F=Pr(t(ω)=Failure)=NFd−n.
(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/(1−F).
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( t∗EIN)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 . c−m.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ηd−n1−NFd−n=Pd,n(t∗A)1−F=Pc,m(A)=c−m.(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(1−F).
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=dn−NF>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 dn−NFc 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×11−F.
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 m ≥ 1 dn/cm≥1N = 1 N=1F → 0 F→0n = 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.796489d6
d150
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 m ≤ d ncm≤dn ( 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 216−150=66150d6
150d150
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 - 7593750000078364164096−75937500000d6
d150
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,…,d−1c0,1,…,c−1.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 d6
eine Folge von 10.383.070 a-Rollen d150
mit einer Fehlerrate von weniger als bei einer von der asymptotischen Grenze unterscheidbaren Effizienz von .2 × 10 - 8 , 2×10−8,2,796492.79649
Für den Fall von führt das dreimalige Rollen eines d6 eindeutig zu Ergebnissen.N=150N=150 63=21663=216
Das gewünschte Ergebnis kann folgendermaßen tabelliert werden:
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=2536 1,2,…,1501,2,…,150 p−1=3625p−1=3625 3625×3=4.323625×3=4.32
Wir danken @whuber dafür, dass er dies im Chat vorgeschlagen hat.
quelle
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:
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 .
quelle
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:
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 06 1 7 2799360279936 , nach88 Rollen 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
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,10006−1506=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.
quelle