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

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$

Jako przykład ilustrujący pomocne byłoby wyjaśnienie, jak działa rozwiązanie dla przypadku .$N=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 .

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

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

$$t:\Omega(d,n)\to\Omega(c,m)\cup\{\text{Failure}\}.$$

Niech $F$ będzie prawdopodobieństwem $t$ skutkującym awarią i zwróć uwagę, że $F$ jest , powiedzmy , jakąś integralną wielokrotnością $d^{-n},$

$$F = \Pr(t(\omega)=\text{Failure}) = N_F\, d^{-n}.$$

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

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$\Omega(c,m)$$t$$t$$\mathcal{A}\subset\Omega(c,m),$

$$\frac{\mathbb{P}_{d,n}\left(t^{*}\mathcal{A}\right)}{1-F}= \mathbb{P}_{c,m}\left(\mathcal{A}\right) \tag{1}$$

gdzie

$$t^{*}\left(\mathcal A\right) = \{\omega\in\Omega\mid t(\omega)\in\mathcal{A}\}$$

jest zestawem rzutów matryc, które procedura przypisuje do zdarzenia$t$.$\mathcal A.$

Rozważmy zdarzenie atomowe , które musi mieć prawdopodobieństwoNiech (rzuty kostką związane z ) mają elementy . staje się$\mathcal A = \{\eta\}\subset\Omega(c,m)$$c^{-m}.$$t^{*}\left(\mathcal A\right)$$\eta$$N_\eta$$(1)$

$$\frac{N_\eta d^{-n}}{1 - N_F d^{-n}} = \frac{\mathbb{P}_{d,n}\left(t^{*}\mathcal{A}\right)}{1-F}= \mathbb{P}_{c,m}\left(\mathcal{A}\right) = c^{-m}.\tag{2}$$

Natychmiastowe jest, że są równe jakiejś liczbie całkowitej$N_\eta$$N.$ Pozostaje tylko znaleźć najbardziej efektywne procedury Oczekiwana liczba nie-awarii na zwoju kostka IS$t.$$c$

$$\frac{1}{m}\left(1 - F\right).$$

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.$F$$m$$m$$c$$F$

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

$$N c^m = d^n - N_F \gt 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”) as$c,d,n,m$$F$$d^n-N_F$$c^m$$d^n.$$\lfloor*\rfloor$

$$N = \lfloor \frac{d^n}{c^m} \rfloor.$$

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ści$N$$t$$d$$c$

$$N \times \frac{n}{m} \times \frac{1}{1-F}.$$

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 mocy$d^n$$c^m.$

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ąc$d$$c,$$(n,m)$$(n,m)$$d^n/c^m \ge 1$$N=1$$F\to 0$$n=1,2,3,\ldots$

$$m = \lfloor \frac{n\log d}{\log c} \rfloor.\tag{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żnie$d$$n,$$\log d / \log c = \log_c d$$c$

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.$m$$c$$d$$\log(c)/\log(d) + \epsilon = \log_d(c) + \epsilon$$\epsilon$$m$

---

Przykłady i algorytmy

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

$$\log_d(c) = \frac{\log(c)}{\log(d)} \approx 2.796489.$$

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

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

$$(n,m) \in \{(3,1), (14,5), \ldots\}$$

na przykład odpowiadający liczbom

$$(6^n, 150^m) \in \{(216,150), (78364164096,75937500000), \ldots\}.$$

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

W drugim przypadku $t$ kojarzyłoby $78364164096-75937500000$ 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 $t$ etykiet twarze $d$ -sided umiera z liczb $0,1,\ldots, d-1$ i powierzchniami $c$ -sided umiera z liczb $0,1,\ldots, c-1.$$n$ rzutów z pierwszej kości jest interpretowanych jako liczba $n$ cyfrowa w podstawie $d.$ To jest konwertowane na liczbę w bazie $c.$ Jeśli ma co najwyżej $m$ cyfr, sekwencja ostatniego $m$ cyfr, jest to wynik. Inaczej,$t$ zwraca błąd, wywołując rekurencyjnie.

W przypadku znacznie dłuższych sekwencji można znaleźć odpowiednie pary $(n,m)$ , biorąc pod uwagę każdą inną zbieżną $n/m$ kontynuacji rozszerzenia ułamka $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ż $x$ i większym niż to (zakładając, że $x$ nie jest już racjonalny). Wybierz te, które są mniejsze niż $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 \ldots.$$

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\times 10^{-8},$ for an efficiency of $2.79649$--indistinguishable from the asymptotic limit.

For the case of $N=150$, rolling a d6 three times distinctly creates $6^3=216$ outcomes.

The desired result can be tabulated in this way:

• Record a d6 three times sequentially. This produces results $a,b,c$. The result is uniform because all values of $a,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 $$(a-1) \times 6^2 + (b-1) \times 6^1 + (c-1)\times 6^0$$
• Add 1.
• If the result exceeds 150, discard the result and roll again.

The probability of keeping a result is $p=\frac{150}{216}=\frac{25}{36}$. All rolls are independent, and we repeat the procedure until a "success" (a result in $1,2,\dots,150$) so the number of attempts to generate 1 draw between 1 and 150 is distributed as a geometric random variable, which has expectation $p^{-1}=\frac{36}{25}$. Therefore, using this method to generate 1 draw requires rolling $\frac{36}{25}\times 3 =4.32$ dice rolls on average (because each attempt rolls 3 dice).

---

Credit to @whuber to for suggesting this in chat.

Here is an even simpler alternative to the answer by Sycorax for the case where $N=150$. Since $150 = 5 \times 5 \times 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 $R_1, R_2, R_3$.
• If either of the first two rolls is a six, reroll it until it is not 6.
• The number $(R_1, R_2, R_3)$ is a uniform number using positional notation with a radix of 5-5-6. Thus, you can compute the desired number as: $$X = 30 \cdot (R_1-1) + 6 \cdot (R_2-1) + (R_3-1) + 1.$$

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

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 $\frac{150}{216}$
• 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 $\frac{300}{1296}$
• 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 $\frac{450}{7776}$
• 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 $\frac{750}{46656}$

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 $\frac{0}{279936}$, after $8$ rolls is $\frac{150}{1679616}$ 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 $150_{10}=410_6$
• Second, rather than target values $1_6$ to $410_6$, I will subtract one so the target values are $0_6$ to $409_6$
• Third, each die should have values $0_6$ to $5_6$, 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 $000_6$ to $555_6$. Since $1000_6 \div 410_6 = 1_6 \text{ remainder } 150_6$ you take the generated value (which is also its remainder on division by $410_6$) if the generated value is strictly below $1000_6-150_6=410_6$ and stop;

• If continuing, roll the fourth die so you have now generated a number from $4100_6$ to $5555_6$. Since $10000_6 \div 410_6 = 12_6 \text{ remainder } 240_6$ you take the remainder of the generated value on division by $410_6$ if the generated value is strictly below $10000_6-240_6=5320_6$ and stop;

• If continuing, roll the fifth die so you have now generated a number from $53200_6$ to $55555_6$. Since $100000_6 \div 410_6 = 123_6 \text{ remainder } 330_6$ you take the remainder of the generated value on division by $410_6$ if the generated value is strictly below $100000_6-330_6=55230_6$ and stop;

• If continuing, roll the sixth die so you have now generated a number from $552300_6$ to $555555_6$. Since $1000000_6 \div 410_6 = 1235_6 \text{ remainder } 10_6$ you take the remainder of the generated value on division by $410_6$ if the generated value is strictly below $1000000_6-10_6=555550_6$ and stop;

• etc.