Antes de mais nada, não tenho certeza de onde essa pergunta deve ser publicada. Estou perguntando se um problema estatístico é NP-Complete e se não é para resolvê-lo programaticamente. Estou postando aqui porque o problema das estatísticas é o ponto central.
Estou tentando encontrar uma fórmula melhor para resolver um problema. O problema é: se eu tenho 4d6 (4 dados comuns de 6 lados) e os rolar todos de uma vez, remova um dado com o número mais baixo (chamado "dropping") e, em seguida, some os 3 restantes, qual é a probabilidade de cada resultado possível ? Eu sei que a resposta é esta:
Sum (Frequency): Probability
3 (1): 0.0007716049
4 (4): 0.0030864198
5 (10): 0.0077160494
6 (21): 0.0162037037
7 (38): 0.0293209877
8 (62): 0.0478395062
9 (91): 0.0702160494
10 (122): 0.0941358025
11 (148): 0.1141975309
12 (167): 0.1288580247
13 (172): 0.1327160494
14 (160): 0.1234567901
15 (131): 0.1010802469
16 (94): 0.0725308642
17 (54): 0.0416666667
18 (21): 0.0162037037
A média é 12,24 e o desvio padrão é 2,847.
Encontrei a resposta acima por força bruta e não sei como ou se existe uma fórmula para isso. Suspeito que esse problema seja NP-Complete e, portanto, só pode ser resolvido com força bruta. Pode ser possível obter todas as probabilidades de 3d6 (3 dados normais de 6 lados) e inclinar cada uma delas para cima. Isso seria mais rápido que a força bruta, porque eu tenho uma fórmula rápida quando todos os dados são mantidos.
Programei a fórmula para manter todos os dados na faculdade. Eu perguntei ao meu professor de estatística e ele encontrou esta página , que ele me explicou. Há uma grande diferença de desempenho entre esta fórmula e a força bruta: 50d6 levou 20 segundos, mas 8d6 eliminou as falhas mais baixas após 40 segundos (o chrome fica sem memória).
Esse problema é NP-Completo? Se sim, forneça uma prova; se não, forneça uma fórmula de força não bruta para resolvê-lo.
Observe que eu não sei muito sobre o NP-Complete, portanto, posso estar pensando em NP, NP-Hard ou outra coisa. A prova da NP-Completeness é inútil para mim, a única razão pela qual peço é impedir as pessoas de adivinharem. E, por favor, fique comigo, pois já faz um longo tempo que não trabalhei nisso: não me lembro de estatísticas e preciso resolver isso.
Idealmente, estou procurando uma fórmula mais genérica para o número X de dados com os lados Y quando N deles forem descartados, mas estou começando com algo muito mais simples.
Editar:
Eu também preferiria a fórmula para emitir frequências, mas é aceitável apenas para probabilidades de saída.
Para os interessados, programei a resposta do whuber em JavaScript no meu GitHub (neste commit, apenas os testes realmente usam as funções definidas).
Respostas:
Solução
Seja dados, cada um dando chances iguais aos resultados 1 , 2 , … , d = 6 . Seja K o mínimo dos valores quando todos os n dados forem lançados independentemente.n=4 1,2,…,d=6 K n
Considere a distribuição da soma de todos os valores condicionais em K . Seja X essa soma. A função geradora para o número de maneiras de formar qualquer valor dado de X , considerando que o mínimo é pelo menos k , én K X X k
Como os dados são independentes, a função geradora para o número de maneiras de formar valores de onde todos os n dados mostram valores de k ou mais, éX n k
Essa função geradora inclui termos para os eventos em que excede k , portanto, precisamos subtraí-los. Portanto, a função geradora para o número de maneiras de formar valores de X , dado K = k , éK k X K=k
Notando que a soma do valores mais altos é a soma de todos os valores menos o menor, igual a X - K . A função geradora, portanto, precisa ser dividida por k . Torna-se uma função geradora de probabilidade ao multiplicar pela chance comum de qualquer combinação de dados, ( 1 / d ) n :n−1 X−K k (1/d)n
Como todos os produtos e potências polinomiais podem ser computados em operações (são convoluções e, portanto, podem ser executadas com a discreta Transformada rápida de Fourier), o esforço computacional total é O ( kO(nlogn) . Em particular,é um algoritmo de tempo polinomial.O(knlogn)
Exemplo
O trabalho de deixar passar o exemplo em questão, com e d = 6 .n=4 d=6
A fórmula para o PGF de X condicional em K ≥ k dá(1) X K≥k
Elevá-los à potência como na fórmula ( 2 ) produzn=4 (2)
Suas sucessivas diferenças na fórmula são(3)
The resulting sum in formula(4) is
For example, the chance that the top three dice sum to14 is the coefficient of x14 , equal to
It is in perfect agreement with the probabilities quoted in the question.
By the way, the mean (as calculated from this result) is15869/1296≈12.244598765… and the standard deviation is 13612487/1679616−−−−−−−−−−−−−−−−√≈2.8468444 .
A similar (unoptimized) calculation forn=400 dice instead of n=4 took less than a half a second, supporting the contention that this is not a computationally demanding algorithm. Here is a plot of the main part of the distribution:
Since the minimumK is highly likely to equal 1 and the sum X will be extremely close to having a Normal(400×7/2,400×35/12) distribution (whose mean is 1400 and standard deviation is approximately 34.1565 ), the mean must be extremely close to 1400−1=1399 and the standard deviation extremely close to 34.16 . This nicely describes the plot, indicating it is likely correct. In fact, the exact calculation gives a mean of around 2.13×10−32 greater than 1399 and a standard deviation around 1.24×10−31 less than 400×35/12−−−−−−−−−−√ .
fonte
6^-4
multiplier is used to convert from frequency to probability.Edit: @SkySpiral has had trouble getting the below formula to work. I currently don't have time to work out what the issue is, so if you're reading this it's best to proceed under the assumption it's incorrect.
I'm not sure about the general problem with varying numbers of dice, sides, and drops, but I think I can see an efficient algorithm for the drop-1 case. The qualifier is that I'm not completely sure that it's correct, but right now I can't see any flaws.
Let's start by not dropping any dice. SupposeXn represents the n th die, and suppose Yn represents the sum of n dice. Then
Now supposeZn is the sum of n dice when one die is dropped. Then
If we defineMn to be distribution of the minimum of n dies, then
and we can calculateMn using
Anyway, together this all suggests a dynamic programming algorithm based onYn,Zn and Mn . Should be quadratic in n .
edit: A comment has been raised on how to calculatep(Xn≤Mn−1) . Since Xn,Mn−1 can each only take on one of six values, we can just sum over all possibilities:
Similarly,p(Xn=k|Xn>Mn−1) can be calculated by applying Bayes rule then summing over the possible values of Xn,Mn−1 .
fonte
I have a reasonably efficient algorithm for this that, on testing, seems to match results of pure brute force while relying less heavily on enumerating all possibilities. It's actually more generalized than the above problem of 4d6, drop 1.
Some notation first: LetXNdY indicate that you are rolling X dice with Y faces (integer values 1 to Y ), and considering only the highest N dice rolled. The output is a sequence of dice values, e.g. 43d6 yields 3,4,5 if you rolled 1,3,4,5 on the four dice. (Note that I'm calling it a "sequence," but the order is not important here, particularly since all we care about in the end is the sum of the sequence.)
The probabilityP(XNdY=S) (or more specifically, P(43d6=S) ) is a simplified version of the original problem, where we are only considering a specific set of dice, and not all possible sets that add up to a given sum.
SupposeS has k distinct values, s0,s1,...,sk , such that si>si+1 , and each si has a count of ci . For example, if S=3,4,4,5 , then (s0,c0)=(5,1) , (s1,c1)=(4,2) , and (s2,c2)=(3,1) .
You can calculateP(XNdY=S) in the following way:
That's pretty messy, I know.
The product expression∏k−1i=0 is iterating through all but the lowest of the values in S , and calculating all the ways those values may be distributed among the dice. For s0 , that's just (Xci) , but for s1 , we have to remove the c0 dice that have already been set aside for s0 , and likewise for si you must remove ∑i−1h=0ch .
The sum expression∑X−Nj=0 is iterating through all the possibilities of how many of the dropped dice were equal to sk , since that affects the possible combinations for the un-dropped dice with sk as their value.
By example, let's considerP[43d6=(5,4,4)] :
So using the formula above:
The formula breaks down on a domain issue whensk=1 and j=0 in the summation, leading to a first term of 00 , which is indeterminate and needs to be treated as 1 . In such a case, a summation is not actually necessary at all, and can be omitted, since all the dropped dice will also have a value of sk=1 .
Now here's where I do need to rely on some brute force. The original problem was to calculate the probability of the sum being some value, andXNdY represents the individual dice left after dropping. This means you must add up the probabilities for all possible sequences S (ignoring ordering) whose sum is the given value. Perhaps there is a formula to calculate this across all such values of S at once, but I haven't even tried broaching that yet.
I've implemented this in Python first, and the above is an attempt to express it mathematically. My Python algorithm is accurate and reasonably efficient. There are some optimizations that could be made for the case of calculating the entire distribution of∑XNdY , and maybe I'll do that later.
fonte
O(Y^X)
toO((Y+X-1)!/(X!*(Y-1)!))
but it still isn't as efficient as whuber's answer ofO(c*X*log(X))
. Thanks for your answer though +1.