Combinatória Contagem do quebra-cabeça: rolo 20, dados de 8 lados, qual é a probabilidade de obter pelo menos 5 dados do mesmo valor

Question

Suponha que um jogo no qual se role 20 e 8 lados, para um número total de 8^20 possíveis resultados. Para calcular a probabilidade de ocorrer um evento específico, dividimos o número de maneiras pelas quais o evento pode ocorrer em 8^20.

Pode -se calcular o número de maneiras de obter exatamente 5 dados do valor 3. (20 Escolha 5) nos dá o número de pedidos de 3. 7^15 nos dá o número de maneiras de obter o valor 3 por 15 rolos .

number of ways to get exactly 5, 3's = (20 choose 5)*7^15.

A resposta também pode ser vista como quantas maneiras posso reorganizar a corda 3,3,3,3,3,0,0,0,0,0,0,0,0,0,0,0,0 , 0,0 (20 Escolha 5 vezes o número total de valores nós do zero (assumindo 7 valores legais) 7^15 (isso está correto).

• Pergunta 1: Como posso calcular o número de maneiras de obter exatamente 5 dados do mesmo valor (ou seja, para todos os valores de matriz). Nota: Se eu apenas uso ingenuamente minha primeira resposta acima e multiplico o BT 8, recebo uma quantidade enorme de contagem dupla?

  Entendo que eu poderia resolver para cada um dos casos (5 1's), (5, 2's), (5, 3's), ... (5, 8) os soma (mais simplesmente 8*(5 1's)). Em seguida, subtraia a soma do número de sobreposições (5 1's) e (5 2's), (5 1's) e (5 3) ... (5 1's) e (5, 2's) e ... e (5, 8's) Mas isso parece extremamente confuso. Eu faria uma generalização disso de uma maneira que escalaria um grande número de amostras e um grande número de classes.

• Como posso calcular o número de maneiras de obter pelo menos 5 dados do mesmo valor?

  Portanto, 11111100000000000000 ou 11110100000000000002 ou 11111100000001110000 ou 11011211222222223333, mas não 000000111122222233333444 ou 000511512252363347744.

Estou procurando respostas que expliquem a matemática ou apontem para uma biblioteca que suporta isso (módulos Python da ESP). Pontos extras para detalhes e exemplos.

Answer 1

A contagem dupla pode ser resolvida pelo uso do Princípio de inclusão/exclusão

Eu suspeito que sai para:

Choose(8,1)*P(one set of 5 Xs) 
- Choose(8,2)*P(a set of 5 Xs and a set of 5 Ys) 
+ Choose(8,3)*P(5 Xs, 5 Ys, 5 Zs) 
- Choose(8,4)*P(5 Xs, 5 Ys, 5 Zs, 5 As)

P(set of 5 Xs) = 20 Choose 5 * 7^15 / 8^20
P(5 Xs, 5 Ys) = 20 Choose 5,5 * 6^10 / 8^20

E assim por diante. Isso não resolve o problema diretamente de 'mais de 5 do mesmo', como se você simplesmente resumisse os resultados disso aplicados a 5,6,7..20; Você contaria demais os casos em que, digamos, 10 1 e 5 8.

Você provavelmente poderia aplicar a exclusão de inclusão novamente para obter essa segunda resposta; Então, P (de pelo menos 5) = P (um conjunto de 20) + ... + (P (um conjunto de 15) - 7*p (conjunto de 5 de 5 dados)) + ((P (um conjunto de 14) - 7*p (um conjunto de 5 de 6) - 7*p (um conjunto de 6 de 6)). Aumentando o código -fonte para isso está se mostrando mais difícil.

Answer 2

Sugiro que você passe um pouco de tempo escrevendo uma simulação de Monte Carlo e deixe -a correr enquanto resolve as contas à mão. Espero que a simulação de Monte Carlo convergirá antes de terminar as contas e você poderá verificar sua solução.

Uma opção um pouco mais rápida pode envolver a criação de um clone para perguntas matemáticas.

Answer 3

A distribuição de probabilidade exata FS, I de uma soma dos dados do lado do lado de si pode ser calculada como a convolução repetida da distribuição de probabilidade de moradia única consigo mesmo.

Onde para todos e 0 caso contrário.

http://en.wikipedia.org/wiki/dice

Answer 4

Esse problema é realmente difícil se você precisar generalizá -lo (obtenha a fórmula exata).

Mas, de qualquer forma, deixe -me explicar o algoritmo. Se você quer saber

o número de maneiras de obter exatamente 5 dados do mesmo valor

você tem que reformular seu problema anterior, como

Calcule o número de maneiras de obter exatamente 5 dados do valor 3 e nenhum outro valor pode ser repetido exatamente 5 vezes

Por uma questão de simplicidade, vamos chamar a função f (20,8,5) (5 dados, todos os valores) a primeira resposta e F (20,8,5,3) (5 dados, valor 3) o segundo. Temos que F (20,8,5) = F (20,8,5,3) * 8 + (Eventos quando mais de um valor é repetido 5 vezes)

Então, se conseguirmos obter f (20,8,5,3), deve ser bem simples, não é? Bem ... nem tanto ...

Primeiro, vamos definir algumas variáveis:X1, x2, x3 ..., xi, onde xi = número de vezes que temos os dados i

Então:

F(20,8,5)/20^8 = P(X1=5 or X2=5 or ... or X8=5, with R=20(rolls) and N=8(dice number))

, P (declaração) sendo a maneira padrão de escrever uma probabilidade.

nós continuamos:

F(20,8,5,3)/20^8 = P(X3=5 and X1<>5 and ... and X8<>5, R=20, N=8) 
F(20,8,5,3)/20^8 = 1 - P(X1=5 or X2=5 or X4=5 or X5=5 or X6=5 or X7=5 or X8=5, R=15, N=7)  
F(20,8,5,3)/20^8 = 1 - F(15,7,5)/7^15

recursivamente:

F(15,8,5) = F(15,7,5,1) * 7  
P(X1=5 or X2=5 or X4=5 or X5=5 or X6=5 or X7=5 or X8=5, R=15, N=7) = P(X1=5 and X2<>5 and X4<>5 and .. and X8<>5. R=15, N=7) * 7

---

F(15,7,5,1)/7^15 = 1 - F(10,6,5)/6^10 F(10,6,5) = F(10,6,5,2) * 6

---

F(10,6,5,2)/6^10 = 1 - F(5,5,5)/5^5
F(5,5,5) = F(5,5,5,4) * 5

Bem, então ... F (5,5,5,4) é o número de maneiras de obter 5 dados de valor 4 em 5 rolos, como nenhum outro dado se repete 5 vezes. Existe apenas uma maneira, de um total de 5^5. A probabilidade é então 1/5^5.

F (5,5,5) é o número de maneiras de obter 5 dados de qualquer valor (de 5 valores) em 5 rolos. É obviamente 5. A probabilidade é então 5/5^5 = 1/5^4.

F (10,6,5,2) é o número de maneiras de obter 5 dados de valor 2 em 10 rolos, como nenhum outro dado repete 5 vezes. F (10,6,5,2) = (1-f (5,5,5)/5^5) * 6^10 = (1-1/5^4) * 6^10

Bem ... eu acho que pode estar incorreto em alguma parte, mas de qualquer maneira, você entendeu. Espero poder tornar o algoritmo compreensível.

editar:Fiz alguns cheques e percebi que você precisa adicionar alguns casos quando você recebe mais de um valor repetido exatamente 5 vezes. Não tenho tempo para resolver essa parte ...

Answer 5

Aqui está o que estou pensando ...

Se você tivesse 5 dados, teria apenas oito maneiras de conseguir o que deseja.

Para cada uma dessas oito maneiras, todas as combinações possíveis dos outros 15 dados trabalham.

Então - acho que a resposta é: (8 * 815) / 820

(A resposta para pelo menos 5 da mesma forma.)

Answer 6

Eu acredito que você pode usar a fórmula de X ocorrências em n eventos como:

P = probabilidade^n * (n!/((N - x)! X!)))

Portanto, o resultado final será a soma dos resultados de 0 a n.

Eu realmente não vejo nenhuma maneira fácil de combiná -lo em um passo que seria menos confuso. De essa maneira, você também explica a fórmula no código. Você pode ter que escrever seu próprio método fatorial.

  float calculateProbability(int tosses, int atLeastNumber) {
    float atLeastProbability = 0;
    float eventProbability = Math.pow( 1.0/8.0, tosses);
    int nFactorial = factorial(tosses);

    for ( i = 1; i <= atLeastNumber; i++) {
      atLeastProbability += eventProbability * (nFactorial / (factorial(tosses - i) * factorial(i) );
    }
  }

Answer 7

Solução recursiva:

Prob_same_value(n) = Prob_same_value(n-1) * (1 - Prob_noone_rolling_that_value(N-(n-1)))