Zunächst bin ich mir nicht sicher, wo diese Frage veröffentlicht werden soll. Ich frage, ob ein Statistikproblem NP-Complete ist und ob es nicht programmgesteuert gelöst werden soll. Ich poste es hier, weil das Statistikproblem der Mittelpunkt ist.
Ich versuche eine bessere Formel zu finden, um ein Problem zu lösen. Das Problem ist: Wenn ich 4W6 (4 gewöhnliche 6-seitige Würfel) habe und alle auf einmal würfle, entferne ich einen Würfel mit der niedrigsten Zahl (genannt "Fallenlassen") und summiere dann die verbleibenden 3, was ist die Wahrscheinlichkeit für jedes mögliche Ergebnis ? Ich weiß, die Antwort lautet:
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
Der Durchschnitt liegt bei 12,24 und die Standardabweichung bei 2,847.
Ich habe die obige Antwort mit roher Gewalt gefunden und weiß nicht, wie oder ob es eine Formel dafür gibt. Ich vermute, dass dieses Problem NP-vollständig ist und daher nur mit brachialer Gewalt gelöst werden kann. Es könnte möglich sein, alle Wahrscheinlichkeiten von 3d6 (3 normale 6-seitige Würfel) zu erhalten und diese dann nach oben zu verschieben. Dies wäre schneller als rohe Gewalt, weil ich eine schnelle Formel habe, wenn alle Würfel behalten werden.
Ich habe die Formel so programmiert, dass alle Würfel im College bleiben. Ich hatte meinen Statistikprofessor danach gefragt und er fand diese Seite , die er mir dann erklärte. Es gibt einen großen Leistungsunterschied zwischen dieser Formel und Brute Force: 50W6 dauerte 20 Sekunden, aber der niedrigste Absturz von 8W6 war nach 40 Sekunden zu verzeichnen (Chrom hat nicht mehr genügend Arbeitsspeicher).
Ist das Problem NP-Complete? Wenn ja, legen Sie bitte einen Beweis vor, wenn nein, legen Sie bitte eine gewaltfreie Formel zur Lösung vor.
Beachten Sie, dass ich nicht viel über NP-Complete weiß, also denke ich vielleicht an NP, NP-Hard oder etwas anderes. Der Beweis für die NP-Vollständigkeit ist für mich nutzlos. Der einzige Grund, warum ich danach frage, ist, zu verhindern, dass Menschen raten. Und bitte machen Sie mit, es ist lange her, dass ich daran gearbeitet habe: Ich kann mich nicht mehr an Statistiken erinnern, so wie ich das möglicherweise lösen muss.
Im Idealfall suche ich nach einer allgemeineren Formel für die Anzahl X von Würfeln mit Y Seiten, wenn N von ihnen fallengelassen werden, aber ich beginne mit etwas viel Einfacherem.
Bearbeiten:
Ich würde auch die Formel vorziehen, um Frequenzen auszugeben, aber es ist akzeptabel, nur Wahrscheinlichkeiten auszugeben.
Für Interessierte habe ich whubers Antwort in JavaScript auf programmiert meinem GitHub (bei diesem Commit verwenden nur die Tests tatsächlich die definierten Funktionen).
Antworten:
Lösung
Es geben=4 Würfel, die den Ergebnissen gleiche Chancen geben 1,2,…,d=6 . Sei K das Minimum der Werte, wenn alle n Würfel unabhängig voneinander geworfen werden.
Betrachten wir die Verteilung der Summe allern - Werte abhängig K . Sei X diese Summe. Die Erzeugungsfunktion für die Anzahl der Möglichkeiten, einen gegebenen Wert von X , vorausgesetzt, das Minimum ist mindestens k , ist
Da die Würfel unabhängig sind, ist die Erzeugungsfunktion für die Anzahl von Wegen, um Werte von zu bilden, wobei alle n Würfel Werte von k oder größer zeigen, gleichX n k
Diese Erzeugungsfunktion enthält Terme für die Ereignisse, bei denen k überschreitet , so dass wir sie abziehen müssen. Daher wird die Erzeugungsfunktion für die Anzahl von Arten von Werten zu bilden , X , da K = k , ist ,K k X K=k
Feststellung , dass die Summe der höchsten Werte ist die Summe aller Werte minus dem kleinsten gleich X - K . Die Erzeugungsfunktion muss daher durch k geteilt werden . Es wird eine wahrscheinlichkeitserzeugende Funktion durch Multiplikation mit der gemeinsamen Wahrscheinlichkeit einer beliebigen Kombination von Würfeln ( 1 / d ) n :n−1 X−K k (1/d)n
Da alle Polynomprodukte und Potenzen in -Operationen berechnet werden können (sie sind Faltungen und können daher mit der diskreten schnellen Fouriertransformation ausgeführt werden), ist der gesamte Rechenaufwand O ( k)O(nlogn) . Insbesondere handeltes sich um einen polynomiellen Zeitalgorithmus.O(knlogn)
Beispiel
Lassen Sie uns das Beispiel in der Frage mit und d = 6 durcharbeiten .n=4 d=6
Formel für die PGF von X bedingt durch K ≥ k ergibt(1) X K≥k
Das Erhöhen auf die Potenz wie in Formel ( 2 ) ergibtn=4 (2)
Their successive differences in formula(3) are
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−−−−−−−−−−√ .
quelle
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 .
quelle
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.
quelle
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.