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

18

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 .

Sycorax diz restabelecer Monica
fonte

Respostas:

12

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Ω(d,n)nd=6dn1/d(1/d)n:Pd,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 é,tmc(=150)Ω(c,m)

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

Seja a probabilidade resulta em falha e observe que é algum múltiplo integral de digamosFtFdn,

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

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

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Ω(c,m)t t UmΩ ( c , m ) ,ttAΩ(c,m),

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

Onde

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

é o conjunto de dados que o procedimento atribui ao eventotA.

Considere um evento atômico , que deve ter probabilidadeDeixe (os dados associados a ) possuem elementos. torna-seA={η}Ω(c,m)cm.t(A)ηNη(1)

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

É imediato que os sejam todos iguais a um número inteiroNηN. Resta apenas encontrar os procedimentos mais eficientes O número esperado de falhas não por rolo do sided die sejat.cc

1m(1F).

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.FmmcF

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

Ncm=dnNF>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") comoc,d,n,mFdnNFcmdn.

N=dncm.

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 éNt d ctdc

N×nm×11F.

Assim, nossa busca por procedimentos de alta eficiência deve focar nos casos em que é igual a, ou apenas pouco maior que, algum poderdncm.

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 determinandodc,(n,m)(n,m)dn/cm1N=1F0n=1,2,3,

(3)m=nlogdlogc.

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,dn,logd/logc=logcdc

É 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.mcdlog(c)/log(d)+ϵ=logd(c)+ϵϵm


Exemplos e algoritmos

Na questão, e donded=6c=150,

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

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

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 paresdn=6ncm=150mcmdn(n,m)

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

por exemplo, correspondendo aos números

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

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 . t216150=66150d6150d150

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 .t7836416409675937500000d6d150

Um algoritmo simples para implementart 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.d0,1,,d1c0,1,,c1.nnd.c.mmt

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/mx=log(c)/log(d).xxx.

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

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

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×108,2.79649

whuber
fonte
2
Por incrível que pareça, quase parece que essa resposta foi formatada e preparada mesmo antes da pergunta ser feita!
Łukasz Grad
1
Obrigado, @ ŁukaszGrad. No entanto, sou inocente de tais maquinações e tenho certeza de que os leitores de olhos atentos encontrarão evidências da pressa com que escrevi isso, pelas quais peço desculpas antecipadamente.
whuber
Também não deve ser levado em consideração que, quando não é primo, o espaço de amostra pode ser particionado em subconjuntos de igual probabilidade? Por exemplo, você pode usar um d6 como um d2 ou um d3, e um espaço de amostra com 162 elementos - mais perto de 150 do que o 216 é - é possível com 4 rolos, 1d6 + 3d3. (Isso dá o mesmo número esperado de rolos que a solução 3d6, mas uma variação menor.)Ω ( d , 1 )dΩ(d,1)
Scortchi - Reinstate Monica
@ Scortchi Você descreve uma configuração ligeiramente diferente na qual se pode escolher dados para simular empates de uma distribuição uniforme. Uma análise semelhante se aplica - você pode achar divertido executá-la.
whuber
7

Para o caso de , rolar um d6 três vezes distintamente cria resultados.N=15063=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,ca,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
    (a1)×62+(b1)×61+(c1)×60
  • 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=150216=25361,2,,150p-1=36p1=36253625×3=4.32


Agradecemos a @whuber por sugerir isso no chat.

Sycorax diz restabelecer Monica
fonte
Acredito que o método de Henry não produz uma distribuição uniforme. Isso ocorre porque a reciclagem fará com que alguns dígitos sejam favorecidos. Não tenho muita certeza disso, porque não entendo completamente como a reciclagem deve ser realizada.
whuber
1
@whuber AH! Eu entendo sua preocupação agora. Eu apenas tentei explicar o processo para mim mesmo e percebi por que minha intuição era falha: a probabilidade de rolar um dado adicional pode alterar a atribuição de probabilidades para números decimais e torná-lo não uniforme, porque não sabemos antecipadamente como muitos dados que estamos rolando.
Sycorax diz Restabelecer Monica
4

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

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

  • Faça três rolos ordenados de 1D6 e indique-os como .R1,R2,R3
  • 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: (R1,R2,R3)
    X=30(R11)+6(R21)+(R31)+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 .N6

Restabelecer Monica
fonte
1
Você pode indicar a eficiência desse método em termos do número esperado de jogadas por sorteio gerado e esclarecer por que o resultado é uniforme em 1,2, ...., 150?
Sycorax diz Restabelecer Monica
A probabilidade de obter um resultado que não requer relançamento é , o mesmo que na sua resposta. Para entender por que é uniforme, observe que você efetivamente está apenas gerando um número uniforme usando notação posicional com o radical 5-5-6 (ou seja, o último dígito são as unidades, o segundo último dígito é os "seis" e o terceiro último dígito são os "trinta"). 25/36
Restabeleça Monica
1
O método é efetivamente apenas uma variação muito pequena do método em sua resposta. Na sua resposta, você cria um número uniforme na escala de números 6-6-6 e descarta valores inválidos, enquanto na minha resposta você descarta valores inválidos primeiro para gerar um número na escala 5-5-6.
Restabeleça Monica
3
+1 Por uma questão prática, este é um algoritmo atraente. É intrigante, e talvez sugestivo de uma análise mais ampla, que implemente um autômato de estado finito acionado pelos rolos de matriz. Possui quatro estados, {Iniciar, A, B, Aceitar}. Inicie as transições para A ao rolar 1..5; A faz a transição para B após rolar 1..5; e B transita para Aceitar ao rolar qualquer coisa. Cada transição salva o valor do rolo que o causou, portanto, ao atingir Aceitar, você produz a sequência de três rolos armazenados e faz a transição automaticamente de volta para Iniciar.
whuber
4
Você rejeita tantas vezes quanto o @Sycorax, mas faz menos rolagens em média. O esperado não. rolos por variável é . 65+65+1=3.4
Scortchi - Restabelecer Monica
2

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:1506

  • Após lançamentos, você tem possibilidade, não o suficiente para distinguir valores01150
  • Após rolo, você tem possibilidades, insuficientes para distinguir valores16150
  • Após jogadas, você tem possibilidades, insuficientes para distinguir valores236150
  • Após lançamentos, você tem possibilidades, o suficiente para distinguir valores, mas com valores restantes; a probabilidade de você parar agora é321615066150216
  • 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 é4396150963001296
  • 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 é5576150964507776
  • 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 é6756150675046656

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.6617027993681501679616

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 probabilidade3.39614150150


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

  • Primeiro, trabalharei na base com615010=4106
  • Segundo, em vez dos valores-alvo a , subtrairei um para que os valores-alvo sejam a164106064096
  • 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 momento06566

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;0006555610006÷4106=16 remainder 15064106100061506=4106

  • 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;4100655556100006÷4106=126 remainder 240641061000062406=53206

  • 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;5320065555561000006÷4106=1236 remainder 3306410610000063306=552306

  • 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;5523006555555610000006÷4106=12356 remainder 106410610000006106=5555506

  • etc.

Henry
fonte
(+1) Essa resposta seria mais clara se você explicasse como mapeia os resultados de, digamos, 4d6 ou 5d6 para 1,2, ..., 150.
Sycorax diz Reinstate Monica
@Sycorax - Agora forneci um mapeamento de base6
Henry
1
Considerações sobre entropia indicam que você pode se sair substancialmente melhor que esse algoritmo. Resta também mostrar que seu algoritmo realmente produz valores distribuídos independentemente com distribuições uniformes .
whuber
@whuber - Meu algoritmo produz exatamente um número inteiro a partir de possibilidades e o faz de maneira uniforme, desde que os dados sejam uniformes e independentes. Em cada etapa, se atingido, é provável que cada um dos valores seja selecionado. Não produz múltiplos valores (ao contrário da sua resposta)150150150
Henry
1
Entendi mal o que você quis dizer, então, ao escrever "o algoritmo são sucessivos rolos de dados". (Eu deveria ter lido com mais cuidado.) Ao fazer isso, parece-me que seu algoritmo não produz uma distribuição uniforme, mas não tenho certeza porque não fui capaz de descobrir qual o objetivo do algoritmo geral. estar. Seria bom ver uma demonstração de que produz valores uniformes.
whuber