Desenhe números inteiros independentemente e uniformemente aleatoriamente de 1 a usando d6?

Desejo desenhar números inteiros de 1 a algum específico , rolando um número razoável de dados de seis lados (d6). Uma boa resposta irá explicar por que seu método produz números inteiros uniformes e independentes .$N$

Como exemplo ilustrativo, seria útil explicar como uma solução funciona para o caso de .$N=150$

Além disso, desejo que o procedimento seja o mais eficiente possível: role o menor número de d6 em média para cada número gerado.

Conversões de senário para decimal são permitidas.

---

Esta pergunta foi inspirada por este segmento Meta .

O conjunto de resultados identificáveis ​​distintos em rolos independentes de um dado com faces possui elementos. Quando o dado é justo, isso significa que cada resultado de uma jogada tem probabilidade independência significa que cada um desses resultados terá probabilidade isto é, eles têm uma distribuição uniforme$\Omega(d,n)$$n$$d=6$$d^n$$1/d$$(1/d)^n:$$\mathbb{P}_{d,n}.$

Suponha que você tenha planejado algum procedimento que determine resultados de um dado de lado - ou seja, um elemento de - ou então relate falha (o que significa que você terá que repita para obter um resultado). Isso é,$t$$m$$c (=150)$$\Omega(c,m)$

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

Seja a probabilidade resulta em falha e observe que é algum múltiplo integral de digamos$F$$t$$F$$d^{-n},$

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

(Para referência futura, observe que o número esperado de vezes que deve ser chamado antes de não falhar é )$t$$1/(1-F).$

A exigência de que esses resultados em ser uniforme e independente condicional em não relatar meios de falha que conservas probabilidade no sentido de que para cada evento$\Omega(c,m)$t t Um ⊂ Ω ( 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}$$

Onde

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

é o conjunto de dados que o procedimento atribui ao evento$t$$\mathcal A.$

Considere um evento atômico , que deve ter probabilidadeDeixe (os dados associados a ) possuem elementos. torna-se$\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}$$

É imediato que os sejam todos iguais a um número inteiro$N_\eta$$N.$ Resta apenas encontrar os procedimentos mais eficientes O número esperado de falhas não por rolo do sided die seja$t.$c$c$

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

Existem duas implicações imediatas e óbvias. Uma é que, se podemos manter pequeno à medida que cresce, o efeito de relatar uma falha é assintoticamente zero. A outra é que, para qualquer dado (o número de jogadas do dado do lado para simular), queremos tornar o menor possível.$F$$m$$m$$c$$F$

Vamos dar uma olhada em limpando os denominadores:$(2)$

$$N c^m = d^n - N_F \gt 0.$$

Isso torna óbvio que, em um determinado contexto (determinado por ), seja o menor possível, tornando igual ao maior múltiplo de que seja menor ou igual a Podemos escrever isso em termos da maior função inteira (ou "piso") como$c,d,n,m$$F$$d^n-N_F$$c^m$$d^n.$$\lfloor*\rfloor$

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

Por fim, fica claro que deve ser o menor possível para obter maior eficiência, pois mede a redundância em . Especificamente, o número esperado de rolos da matriz do lado necessário para produzir um rolo da matriz do lado é$N$t d c$t$$d$$c$

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

Assim, nossa busca por procedimentos de alta eficiência deve focar nos casos em que é igual a, ou apenas pouco maior que, algum poder$d^n$$c^m.$

A análise termina mostrando que, para dados de e há uma sequência de múltiplos para a qual essa abordagem se aproxima da eficiência perfeita. Isso equivale a encontrar para o qual aproxima de no limite (garantindo automaticamente ). Uma dessas seqüências é obtida tomando e determinando$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}$$

A prova é direta.

Tudo isso significa que, quando estivermos dispostos a rolar o dado original com lados um número suficientemente grande de vezes podemos esperar simular quase resultados de um dado com lado por rolo . Equivalentemente,$d$$n,$$\log d / \log c = \log_c d$$c$

É possível simular um grande número de rolos independentes de um -sided morrer utilizando uma feira -sided morrer utilizando uma média de rola por resultado, onde pode ser arbitrariamente pequeno, escolhendo suficientemente grande.$m$$c$$d$$\log(c)/\log(d) + \epsilon = \log_d(c) + \epsilon$$\epsilon$$m$

---

Exemplos e algoritmos

Na questão, e donde$d=6$$c=150,$

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

Assim, o melhor procedimento possível exigirá, em média, pelo menos rolos de a para simular cada resultado.$2.796489$d6d150

A análise mostra como fazer isso. Não precisamos recorrer à teoria dos números para realizá-la: podemos apenas tabular as potências e as potências compará-las para descobrir onde estão próximos. Este cálculo da força bruta fornece pares$d^n=6^n$$c^m=150^m$$c^m \le d^n$$(n,m)$

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

por exemplo, correspondendo aos números

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

No primeiro caso iria associar dos resultados de três rolos da falha e os outros resultados que cada ser associado com um único resultado de um . $t$$216-150=66$150d6$150$d150

No segundo caso, associaria dos resultados de 14 de a a Failure - cerca de 3,1% de todos - e produziria uma sequência de 5 resultados de a .$t$$78364164096-75937500000$d6d150

Um algoritmo simples para implementar$t$ rotula as faces da matriz lado com os números e as faces da matriz lado com os números Os rolos do primeiro dado são interpretados como um número de dígitos na base Isso é convertido em um número na base Se tiver no máximo dígitos, a sequência dos últimos dígitos será a saída. Caso contrário, retorna Fail ao invocar-se recursivamente.$d$$0,1,\ldots, d-1$$c$$0,1,\ldots, c-1.$$n$$n$$d.$$c.$$m$$m$$t$

Para seqüências muito mais longas, é possível encontrar pares adequados considerando todos os outros convergentes da expansão contínua da fração de A teoria das frações contínuas mostra que esses convergentes alternam entre ser menor que e maior que ele (supondo que ainda não seja racional). Escolha aqueles que são menores que$(n,m)$$n/m$$x=\log(c)/\log(d).$$x$$x$$x.$

Na questão, os primeiros poucos convergentes são

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

No último caso, uma sequência de 29.036.139 jogadas de a d6produzirá uma sequência de 10.383.070 jogadas de a d150com uma taxa de falha menor que para uma eficiência de indistinguível do limite assintótico.$2\times 10^{-8},$$2.79649$

Para o caso de , rolar um d6 três vezes distintamente cria resultados.$N=150$$6^3=216$

O resultado desejado pode ser tabulado desta maneira:

• Grave um d6 três vezes sequencialmente. Isso produz os resultados . O resultado é uniforme porque todos os valores de são igualmente prováveis ​​(os dados são justos e estamos tratando cada jogada como distinta).$a,b,c$$a,b,c$
• Subtraia 1 de cada um.
• Este é um número senário: cada dígito (valor do local) varia de 0 a 5 com potências de 6, para que você possa escrever o número em decimal usando $$(a-1) \times 6^2 + (b-1) \times 6^1 + (c-1)\times 6^0$$
• Adicione 1.
• Se o resultado exceder 150, descarte o resultado e role novamente.

A probabilidade de manter um resultado é . Todos os testes são independentes e repetimos o procedimento até um "sucesso" (resultado em ), de modo que o número de tentativas para gerar 1 empate entre 1 e 150 seja distribuído como uma variável aleatória geométrica, que tem expectativa . Portanto, o uso desse método para gerar 1 empate requer rolar dados em média (porque cada tentativa lança 3 dados).$p=\frac{150}{216}=\frac{25}{36}$$1,2,\dots,150$p-1=36$p^{-1}=\frac{36}{25}$$\frac{36}{25}\times 3 =4.32$

---

Agradecemos a @whuber por sugerir isso no chat.

Aqui está uma alternativa ainda mais simples à resposta do Sycorax para o caso em que . Como você pode executar o seguinte procedimento:$N=150$$150 = 5 \times 5 \times 6$

Gerando número aleatório uniforme de 1 a 150:

• Faça três rolos ordenados de 1D6 e indique-os como .$R_1, R_2, R_3$
• Se um dos dois primeiros testes for seis, rolar novamente até que não seja 6.
• O número é um número uniforme usando notação posicional com uma raiz de 5-5-6. Assim, você pode calcular o número desejado como: $(R_1, R_2, R_3)$ $$X = 30 \cdot (R_1-1) + 6 \cdot (R_2-1) + (R_3-1) + 1.$$

Esse método pode ser generalizado para maior , mas se torna um pouco mais estranho quando o valor tem um ou mais fatores primos maiores que .$N$$6$

Como ilustração de um algoritmo para escolher uniformemente entre valores usando dados de seis lados, tente isso, que usa cada rolagem para multiplicar os valores disponíveis por e tornando igualmente provável cada um dos novos valores:$150$$6$

• Após lançamentos, você tem possibilidade, não o suficiente para distinguir valores$0$$1$$150$
• Após rolo, você tem possibilidades, insuficientes para distinguir valores$1$$6$$150$
• Após jogadas, você tem possibilidades, insuficientes para distinguir valores$2$$36$$150$
• Após lançamentos, você tem possibilidades, o suficiente para distinguir valores, mas com valores restantes; a probabilidade de você parar agora é$3$$216$$150$$66$$\frac{150}{216}$
• Se você não parou, depois de jogadas, você tem possibilidades restantes, o suficiente para distinguir valores de duas maneiras, mas com valores restantes; a probabilidade de parar agora é$4$$396$$150$$96$$\frac{300}{1296}$
• Se você não parou, depois de jogadas, você tem possibilidades restantes, o suficiente para distinguir valores de três maneiras, mas com valores restantes; a probabilidade de parar agora é$5$$576$$150$$96$$\frac{450}{7776}$
• Se você não parou, depois de jogadas, você tem possibilidades restantes, o suficiente para distinguir valores de cinco maneiras, mas com valores restantes; a probabilidade de parar agora é$6$$756$$150$$6$$\frac{750}{46656}$

Se você estiver em um dos valores restantes após jogadas, estará em uma situação semelhante à posição após rolagem. Portanto, você pode continuar da mesma maneira: a probabilidade de parar após jogadas é , depois de jogadas é etc.$6$$6$$1$$7$$\frac{0}{279936}$$8$$\frac{150}{1679616}$

Adicione-os e você descobrirá que o número esperado de rolos necessários é de cerca de . Ele fornece uma seleção uniforme dos , pois você só seleciona um valor no momento em que pode selecionar cada um dos com igual probabilidade$3.39614$$150$$150$

---

A Sycorax pediu nos comentários um algoritmo mais explícito

• Primeiro, trabalharei na base com$6$$150_{10}=410_6$
• Segundo, em vez dos valores-alvo a , subtrairei um para que os valores-alvo sejam a$1_6$$410_6$$0_6$$409_6$
• Terceiro, cada dado deve ter valores a , e rolar um dado envolve adicionar um dígito básico de dígitos no lado direito do número gerado existente. Os números gerados podem ter zeros à esquerda e o número de dígitos é o número de rolos até o momento$0_6$$5_6$$6$

O algoritmo consiste em sucessivos lançamentos de dados:

• os três primeiros dados para gerar um número de a . Desde você pega o valor gerado (que também é o restante na divisão por ) se o valor gerado estiver estritamente abaixo de e parar;$000_6$$555_6$$1000_6 \div 410_6 = 1_6 \text{ remainder } 150_6$$410_6$$1000_6-150_6=410_6$

• Se continuar, role o quarto dado para gerar um número de a . Como o restante do valor gerado na divisão é se o valor gerado estiver estritamente abaixo de e parar;$4100_6$$5555_6$$10000_6 \div 410_6 = 12_6 \text{ remainder } 240_6$$410_6$$10000_6-240_6=5320_6$

• Se continuar, role o quinto dado para gerar um número de a . Como o restante do valor gerado na divisão é se o valor gerado estiver estritamente abaixo de e parar;$53200_6$$55555_6$$100000_6 \div 410_6 = 123_6 \text{ remainder } 330_6$$410_6$$100000_6-330_6=55230_6$

• Se continuar, role o sexto dado para gerar um número de a . Como o restante do valor gerado na divisão é se o valor gerado estiver estritamente abaixo de e parar;$552300_6$$555555_6$$1000000_6 \div 410_6 = 1235_6 \text{ remainder } 10_6$$410_6$$1000000_6-10_6=555550_6$

• etc.