Czy losujesz liczby całkowite niezależnie i równomiernie losowo od 1 do przy użyciu sprawiedliwego d6?

18

Chciałbym narysować liczby całkowite od 1 do określonego , rzucając pewną liczbą uczciwych sześciościennych kości (d6). Dobra odpowiedź wyjaśni, dlaczego jej metoda daje jednolite i niezależne liczby całkowite.N.N

Jako przykład ilustrujący pomocne byłoby wyjaśnienie, jak działa rozwiązanie dla przypadku .N = 150N=150

Ponadto chciałbym, aby procedura była jak najbardziej wydajna: rzuć średnio najmniejszą liczbą d6 dla każdej wygenerowanej liczby.

Dopuszczalne są konwersje z trybu zmysłowego na dziesiętny.


To pytanie zostało zainspirowane tym wątkiem Meta .

Sycorax mówi Przywróć Monikę
źródło

Odpowiedzi:

12

Zestaw Ω ( d , n )Ω(d,n) na różnych zidentyfikowania wyniki w nn niezależne rolki matrycy o d = 6d=6 powierzchniach ma d ndn elementów. Gdy kość jest sprawiedliwa, oznacza to, że każdy wynik jednego rzutu ma prawdopodobieństwo 1 / d,1/d a niezależność oznacza, że ​​każdy z tych wyników będzie miał prawdopodobieństwo ( 1 / d ) n :(1/d)n: to znaczy, że mają one jednolity rozkład P d , n .Pd,n.

Załóżmy, że opracowałeś procedurę t,t która określa mm wyniki matrycy jednostronnej c ( = 150 )c(=150) - to znaczy element Ω ( c , m ) -Ω(c,m) lub w innym przypadku zgłasza awarię (co oznacza, że ​​będziesz musiał powtórzyć w celu uzyskania wyniku). To jest,

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

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

Niech FF będzie prawdopodobieństwem tt skutkującym awarią i zwróć uwagę, że FF jest , powiedzmy , jakąś integralną wielokrotnością d - ndn,

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

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

(W celu odniesienia w przyszłości należy pamiętać, że oczekiwana liczba razy musi zostać wywołana przed niepowodzeniem to )t t1 / ( 1 - F ) .1/(1F).

Wymaganie, że te wyniki w jest jednolite i niezależne uzależnione od niezgłoszenie środki awaryjnych, które konserwy prawdopodobieństwa w tym sensie, że dla każdego przypadkuΩ ( c , m )Ω(c,m)t tt tAΩ ( c , m ) ,AΩ(c,m),

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

Pd,n(tA)1F=Pc,m(A)(1)

gdzie

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

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

jest zestawem rzutów matryc, które procedura przypisuje do zdarzeniat t.A.

Rozważmy zdarzenie atomowe , które musi mieć prawdopodobieństwoNiech (rzuty kostką związane z ) mają elementy . staje sięA = { η } Ω ( c , m ) A={η}Ω(c,m)c - m . cm.t ( A )t(A) η ηN ηNη ( 1 )(1)

N η d - n1NFdn=Pd,n(tA)1F=Pc,m(A)=cm.

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

Natychmiastowe jest, że są równe jakiejś liczbie całkowitejNηNηN.N. Pozostaje tylko znaleźć najbardziej efektywne procedury Oczekiwana liczba nie-awarii na zwoju kostka ISt.t.cc

1m(1F).

1m(1F).

Istnieją dwie bezpośrednie i oczywiste implikacje. Jednym z nich jest to, że jeśli możemy utrzymać małą, gdy rośnie, to efekt zgłoszenia awarii jest asymptotycznie zerowy. Drugim jest to, że dla dowolnego danego (liczby rzutów matrycy po stronie do symulacji) chcemy, aby jak najmniejsze.FFmmmmccFF

Przyjrzyjmy się bliżej , usuwając mianowniki:(2)(2)

Ncm=dnNF>0.

Ncm=dnNF>0.

To pokazuje, że w danym kontekście (określonym przez ), jest tak małe, jak to możliwe, czyniąc równą największej wielokrotności która jest mniejsza lub równa Możemy napisać to w kategoriach największej liczby całkowitej (lub „floor”) asc,d,n,mc,d,n,mFFdnNFdnNFcmcmdn.dn.

N=dncm.

N=dncm.

Wreszcie, oczywiste jest, że powinna być jak najmniejsza dla najwyższej wydajności, ponieważ mierzy redundancję w . W szczególności, oczekiwana liczba walców -sided formy potrzebne do wytworzenia jednego zwoju -sided dyszowej mieściNNttddcc

N×nm×11F.

N×nm×11F.

Dlatego nasze poszukiwania procedur o wysokiej wydajności powinny koncentrować się na przypadkach, w których jest równe lub tylko nieco większe od pewnej mocydndncm.cm.

Analiza kończy się wykazaniem, że dla danych i istnieje ciąg wielokrotności dla którego to podejście jest zbliżone do idealnej wydajności. Sprowadza się to do znalezienia dla którego zbliża się do w limicie (automatycznie gwarantując ). Jedną taką sekwencję uzyskuje się, przyjmując i określającddc,c,(n,m)(n,m)(n,m)(n,m)dn/cm1dn/cm1N=1N=1F0F0n=1,2,3,n=1,2,3,

m=nlogdlogc.

m=nlogdlogc.(3)

Dowód jest prosty.

To, że wszystkie środki, które, gdy są gotowe do użycia oryginalnego -sided die wystarczająco dużą liczbę można oczekiwać, aby symulować prawie EFEKTY -sided umiera na rolce . Równoważnieddn,n,logd/logc=logcdlogd/logc=logcdcc

Jest możliwe, aby symulować duża ilość niezależnych rolkach o -sided matrycy z wykorzystaniem sprawiedliwego -sided matrycy z wykorzystaniem średnio rzutuje na wynik, gdzie może być dowolnie mały, wybierając odpowiednio duży.mmccddlog(c)/log(d)+ϵ=logd(c)+ϵlog(c)/log(d)+ϵ=logd(c)+ϵϵϵmm


Przykłady i algorytmy

Na pytanie, i skądd=6d=6c=150,c=150,

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

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

Zatem najlepsza możliwa procedura będzie wymagała średnio co najmniej rolek a, aby zasymulować każdy wynik.2.7964892.796489d6d150

Analiza pokazuje, jak to zrobić. Aby tego dokonać, nie musimy uciekać się do teorii liczb: możemy po prostu zestawić moce d n = 6 ndn=6n i moce c m = 150 mcm=150m i porównać je, aby znaleźć, gdzie c md ncmdn są bliskie. To obliczenie brutalnej siły daje ( n(n,m)pary , m )

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

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

na przykład odpowiadający liczbom

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

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

W pierwszym przypadku tt kojarzyłoby 216 - 150 = 66216150=66 wyników trzech rzutów a d6do porażki, a pozostałe 150150 wyników byłoby związane z jednym wynikiem a d150.

W drugim przypadku tt kojarzyłoby 78364164096 - 759375000007836416409675937500000 wyników 14 rzutów zd6awarią - około 3,1% wszystkich - i w innym przypadku dałoby sekwencję 5 wyników ad150.

Proste do wykonania algorytmu tt etykiet twarze dd -sided umiera z liczb 0 , 1 , ... , d - 10,1,,d1 i powierzchniami Cc -sided umiera z liczb 0 , 1 , ... , C - 1. 0,1,,c1.nn rzutów z pierwszej kości jest interpretowanych jako liczba n-n cyfrowa w podstawie d . d. To jest konwertowane na liczbę w bazie c . c. Jeśli ma co najwyżej mm cyfr, sekwencja ostatniego mm cyfr, jest to wynik. Inaczej, tt zwraca błąd, wywołując rekurencyjnie.

W przypadku znacznie dłuższych sekwencji można znaleźć odpowiednie pary ( n , m )(n,m) , biorąc pod uwagę każdą inną zbieżną n / mn/m kontynuacji rozszerzenia ułamka x = log ( c ) / log ( d ) . x=log(c)/log(d). Teoria ciągłych ułamków pokazuje, że te zbieżności występują naprzemiennie między byciem mniejszym niż xx i większym niż to (zakładając, że xx nie jest już racjonalny). Wybierz te, które są mniejsze niż x .x.

In the question, the first few such convergents are

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

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

In the last case, a sequence of 29,036,139 rolls of a d6 will produce a sequence of 10,383,070 rolls of a d150 with a failure rate less than 2×108,2×108, for an efficiency of 2.796492.79649--indistinguishable from the asymptotic limit.

whuber
źródło
2
Amazing as always, it almost looks like this answer was formatted and prepared even before the question was asked!
Łukasz Grad
1
Thank you, @ŁukaszGrad. However, I am innocent of any such machinations and I'm sure sharp-eyed readers will find evidence of the haste with which I have written this out, for which I apologize in advance.
whuber
Shouldn't it also be taken into account that when dd isn't prime, the sample space Ω(d,1)Ω(d,1) can be partitioned into subsets of equal probability? For example, you can use a d6 as a d2 or a d3, & a sample space with 162 elements - closer to 150 than 216 is - is then achievable with 4 rolls, 1d6+3d3. (That gives the same expected no. rolls as the 3d6 solution, but a lower variance.)
Scortchi - Reinstate Monica
@Scortchi You describe a slightly different setting in which one has a choice of dice to use to simulate draws from a uniform distribution. A similar analysis applies--you might find it amusing to carry it out.
whuber
7

For the case of N=150N=150, rolling a d6 three times distinctly creates 63=21663=216 outcomes.

The desired result can be tabulated in this way:

  • Record a d6 three times sequentially. This produces results a,b,ca,b,c. The result is uniform because all values of a,b,ca,b,c are equally likely (the dice are fair, and we are treating each roll as distinct).
  • Subtract 1 from each.
  • This is a senary number: each digit (place value) goes from 0 to 5 by powers of 6, so you can write the number in decimal using (a1)×62+(b1)×61+(c1)×60
    (a1)×62+(b1)×61+(c1)×60
  • Add 1.
  • If the result exceeds 150, discard the result and roll again.

The probability of keeping a result is p=150216=2536p=150216=2536. All rolls are independent, and we repeat the procedure until a "success" (a result in 1,2,,1501,2,,150) so the number of attempts to generate 1 draw between 1 and 150 is distributed as a geometric random variable, which has expectation p1=3625p1=3625. Therefore, using this method to generate 1 draw requires rolling 3625×3=4.323625×3=4.32 dice rolls on average (because each attempt rolls 3 dice).


Credit to @whuber to for suggesting this in chat.

Sycorax says Reinstate Monica
źródło
I believe Henry's method does not produce a uniform distribution. That's because the recycling will cause some digits to be favored. I'm not completely sure about that because I don't completely understand how the recycling is intended to be performed.
whuber
1
@whuber AH! I understand your concern now. I just tried to explain the process to myself and I realized why my intuition was flawed: the probability of rolling an additional die may change the assignment of probabilities to decimal numbers and make it non-uniform because we don't know ahead of time how many dice we're rolling.
Sycorax says Reinstate Monica
4

Here is an even simpler alternative to the answer by Sycorax for the case where N=150N=150. Since 150=5×5×6150=5×5×6 you can perform the following procedure:

Generating uniform random number from 1 to 150:

  • Make three ordered rolls of 1D6 and denote these as R1,R2,R3R1,R2,R3.
  • If either of the first two rolls is a six, reroll it until it is not 6.
  • The number (R1,R2,R3)(R1,R2,R3) is a uniform number using positional notation with a radix of 5-5-6. Thus, you can compute the desired number as: X=30(R11)+6(R21)+(R31)+1.
    X=30(R11)+6(R21)+(R31)+1.

This method can be generalised to larger NN, but it becomes a bit more awkward when the value has one or more prime factors larger than 66.

Reinstate Monica
źródło
1
Can you state the efficiency of this method in terms of the expected number of rolls per draw generated, and clarify why the outcome is uniform on 1,2,....,150?
Sycorax says Reinstate Monica
The probability of getting an outcome that requires no re-rolling is 25/3625/36, which is the same as in your answer. To understand why it is uniform, note that you are effectively just generating a uniform number using positional notation with radix 5-5-6 (i.e., the last digit is the units, the second-last digit is the "sixes" and the third-last digit is the "thirties").
Reinstate Monica
1
The method is effectively just a very slight variation on the method in your answer. In your answer you create a uniform number on the 6-6-6 number scale an then discard invalid values, whereas in my answer you discard invalid values first to generate a number on the 5-5-6 scale.
Reinstate Monica
3
+1 As a practical matter this is an appealing algorithm. It is intriguing, and perhaps suggestive of a broader analysis, that it implements a finite state automaton driven by the die rolls. It has four states, {Start, A, B, Accept}. Start transitions to A upon rolling 1..5; A transitions to B upon rolling 1..5; and B transitions to Accept upon rolling anything. Each transition saves the value of the roll that caused it, so upon reaching Accept you output that sequence of three stored rolls and transition automatically back to Start.
whuber
4
You reject as often as @Sycorax, but make fewer rolls on average. The expected no. rolls per variate is 65+65+1=3.4.
Scortchi - Reinstate Monica
2

As an illustration of an algorithm to choose uniformly between 150 values using six-sided dice, try this which uses each roll to multiply the available values by 6 and making each of the new values equally likely:

  • After 0 rolls, you have 1 possibility, not enough to distinguish 150 values
  • After 1 roll, you have 6 possibilities, not enough to distinguish 150 values
  • After 2 rolls, you have 36 possibilities, not enough to distinguish 150 values
  • After 3 rolls, you have 216 possibilities, enough to distinguish 150 values but with 66 remaining values; the probability you stop now is 150216
  • If you have not stopped, then after 4 rolls you have 396 remaining possibilities, enough to distinguish 150 values two ways but with 96 remaining values; the probability you stop now is 3001296
  • If you have not stopped, then after 5 rolls you have 576 remaining possibilities, enough to distinguish 150 values three ways but with 96 remaining values; the probability you stop now is 4507776
  • If you have not stopped, then after 6 rolls you have 756 remaining possibilities, enough to distinguish 150 values five ways but with 6 remaining values; the probability you stop now is 75046656

If you are on one of the 6 remaining values after 6 rolls then you are in a similar situation to the position after 1 roll. So you can continue in the same way: the probability you stop after 7 rolls is 0279936, after 8 rolls is 1501679616 etc.

Add these up and you find that the expected number of rolls needed is about 3.39614. It provides a uniform selection from the 150, as you only select a value at a time when you can select each of the 150 with equal probability


Sycorax asked in the comments for a more explicit algorithm

  • First, I will work in base-6 with 15010=4106
  • Second, rather than target values 16 to 4106, I will subtract one so the target values are 06 to 4096
  • Third, each die should have values 06 to 56, and rolling a die involves adding a base 6 digit to the right hand side of the existing generated number. Generated numbers can have leading zeros, and their number of digits is the number of rolls so far

The algorithm is successive rolls of dice:

  • Roll the first three dice to generate a number from 0006 to 5556. Since 10006÷4106=16 remainder 1506 you take the generated value (which is also its remainder on division by 4106) if the generated value is strictly below 100061506=4106 and stop;

  • If continuing, roll the fourth die so you have now generated a number from 41006 to 55556. Since 100006÷4106=126 remainder 2406 you take the remainder of the generated value on division by 4106 if the generated value is strictly below 1000062406=53206 and stop;

  • If continuing, roll the fifth die so you have now generated a number from 532006 to 555556. Since 1000006÷4106=1236 remainder 3306 you take the remainder of the generated value on division by 4106 if the generated value is strictly below 10000063306=552306 and stop;

  • If continuing, roll the sixth die so you have now generated a number from 5523006 to 5555556. Since 10000006÷4106=12356 remainder 106 you take the remainder of the generated value on division by 4106 if the generated value is strictly below 10000006106=5555506 and stop;

  • etc.

Henry
źródło
(+1) This answer would be more clear if you explained how you map the outcomes of, say, 4d6 or 5d6 to 1,2, ..., 150.
Sycorax says Reinstate Monica
@Sycorax - I have now provided a base 6 mapping
Henry
1
Entropy considerations indicate you can do substantially better than this algorithm. It also remains to show that your algorithm actually produces independently distributed values with uniform distributions.
whuber
@whuber - My algorithm produces exactly one integer from 150 possibilities and does so uniformly providing the dice rolls are uniform and independent. At each step if reached, each of the 150 values is equally likely to be selected. It does not produce multiple values (unlike your answer)
Henry
1
I misunderstood what you meant, then, in writing "the algorithm is successive rolls of dice." (I should have read through more carefully.) In doing so, it seems to me your algorithm does not produce a uniform distribution, but I'm not sure because I haven't been able to figure out what the general algorithm is intended to be. It would be good to see a demonstration that it does produce uniform values.
whuber