Formel zum Würfeln (non-brute force)

14

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

SkySpiral7
quelle
1
Das ist eine interessante Frage. Ich denke, es sollte hier zum Thema werden. Danke für deine Rücksicht.
gung - Wiedereinsetzung von Monica
1
Obwohl die Einstellung interessant ist, haben Sie noch keine beantwortbare Frage gestellt: Die Idee der NP-Vollständigkeit hängt von einer Klasse von Problemen ab, während Sie nur eine beschrieben haben. Genau wie soll es verallgemeinern? Obwohl Sie darauf hinweisen, dass die Anzahl der Würfel variieren kann, sind verschiedene zusätzliche Optionen möglich, die unterschiedliche Antworten liefern können: Sie können die Anzahl der Gesichter, die Werte auf den Gesichtern, die Anzahl der Würfel und die Anzahl der abgeworfenen Würfel ändern auf verschiedene Weise mit verschiedenen Beziehungen zwischen ihnen.
Whuber
1
@whuber Sie kennt keine Komplexitätstheorie, aber ich denke, es ist klar, dass sie nach der Familie der Probleme fragt, die durch die Änderung der Anzahl der Würfel entstehen. Ich denke auch, dass ich einen effizienten Algorithmus dafür habe.
Andy Jones
2
@Andy Ich sehe am Ende, dass sie nach "einer allgemeineren Formel für die Anzahl X von Würfeln mit Y Seiten, wenn N von ihnen fallen gelassen werden" fragt.
whuber
@whuber Hah! Anscheinend nicht so klar wie ich damals dachte. Es tut mir leid.
Andy Jones

Antworten:

5

Lösung

Es gebe n=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 aller n - 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

(1)f(n,d,k)(x)=xk+xk+1++xd=xk1xdk+11x.

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, gleichXnk

(2)f(n,d,k)(x)n=xkn(1xdk+11x)n.

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 ,KkXK=k

(3)f(n,d,k)(x)nf(n,d,k+1)(x)n.

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 :n1XKk(1/d)n

(4)dnk=1dxk(f(n,d,k)(x)nf(n,d,k+1)(x)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=4d=6

Formel für die PGF von X bedingt durch K k ergibt(1)XKk

f(4,6,1)(x)=x+x2+x3+x4+x5+x6f(4,6,2)(x)=x2+x3+x4+x5+x6f(4,6,5)(x)=x5+x6f(4,6,6)(x)=x6f(4,6,7)(x)=0.

Das Erhöhen auf die Potenz wie in Formel ( 2 ) ergibtn=4(2)

f(4,6,1)(x)4=x4+4x5+10x6++4x23+x24f(4,6,2)(x)4=x8+4x9+10x10++4x23+x24f(4,6,5)(x)4=x20+4x21+6x22+4x23+x24f(4,6,6)(x)4=x24f(4,6,7)(x)4=0

Their successive differences in formula (3) are

f(4,6,1)(x)4f(4,6,2)(x)4=x4+4x5+10x6++12x18+4x19f(4,6,2)(x)4f(4,6,3)(x)4=x8+4x9+10x10++4x20f(4,6,5)(x)4f(4,6,6)(x)4=x20+4x21+6x22+4x23f(4,6,6)(x)4f(4,6,7)(x)4=x24.

The resulting sum in formula (4) is

64(x3+4x4+10x5+21x6+38x7+62x8+91x9+122x10+148x11+167x12+172x13+160x14+131x15+94x16+54x17+21x18).

For example, the chance that the top three dice sum to 14 is the coefficient of x14, equal to

64×160=10/81=0.123456790123456.

It is in perfect agreement with the probabilities quoted in the question.

By the way, the mean (as calculated from this result) is 15869/129612.244598765 and the standard deviation is 13612487/16796162.8468444.

A similar (unoptimized) calculation for n=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:

Figure

Since the minimum K 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 14001=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×1032 greater than 1399 and a standard deviation around 1.24×1031 less than 400×35/12.

whuber
quelle
1
Your answer is fast and is correct so I've marked it as the answer. Also in an edit I said it would also be nice to have frequencies if possible. For that you don't need to edit your answer since I can see that the 6^-4 multiplier is used to convert from frequency to probability.
SkySpiral7
6

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. Suppose Xn represents the nth die, and suppose Yn represents the sum of n dice. Then

p(Yn=a)=kp(Yn1=ak)p(Xn=k)

Now suppose Zn is the sum of n dice when one die is dropped. Then

p(Zn=a)=p(nth die is the smallest)p(Yn1=a)+p(nth die is not the smallest)kp(Zn1=ak)p(Xn=k)

If we define Mn to be distribution of the minimum of n dies, then

p(Zn=a)=p(XnMn1)p(Yn1=a|XnMn1)+p(Xn>Mn1)kp(Zn1=ak)p(Xn=k|Xn>Mn1)

and we can calculate Mn using

p(Mn=a)=p(XnMn1)p(Xn=a|XnMn1)+p(Xn>Mn1)p(Mn1=a|Xn>Mn1)

Anyway, together this all suggests a dynamic programming algorithm based on Yn,Zn and Mn. Should be quadratic in n.

edit: A comment has been raised on how to calculate p(XnMn1). Since Xn,Mn1 can each only take on one of six values, we can just sum over all possibilities:

p(XnMn1)=a,bp(Xn=a,Mn1=b,ab)

Similarly, p(Xn=k|Xn>Mn1) can be calculated by applying Bayes rule then summing over the possible values of Xn,Mn1.

Andy Jones
quelle
1
+1 This looks correct and you said that's it's quadratic. But it's been a few years since I took statistics (I'm primarily a programmer). So I'd like to fully understand this before marking it as the answer. Also I see you have p(nth is the smallest die) does this include if nth is tied with the smallest? Such as rolling all 3s.
SkySpiral7
Good catch. If the nth die rolled is the same as the current minimum, we can regard that die as the one to be dropped. In which case the distribution is Yn1. I've swapped some (<)s for ()s to reflect this.
Andy Jones
Thank you. If I understand this correctly I think your formulas are the answer. However I don't know how to calculate p(X(n) > M(n-1)) (or the negation of it) or p(X(n)=k|X(n) > M(n-1)) so I can't use this answer yet. I'll mark this as the answer but I'd like more information. Can you edit your answer to explain these or should I post it as another question?
SkySpiral7
Edited my answer.
Andy Jones
1
Sorry I know it's been a year and a half but I've finally gotten around to implementing this formula into code. However the p(Z(n)=a) formula appears incorrect. Suppose 2 dice with 2 sides (drop lowest), what are the chances of the result being 1? The chance of X(n) being the smallest or tied is 3/4 and p(Y(n-1)=1) is 1/2 so that Z(n) returns at least 3/8 even though the correct answer is 1/4. The Z formula looks correct to me and I don't know how to fix it. So if it's not too much to ask: what do you think?
SkySpiral7
1

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: Let XNdY 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 probability P(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.

Suppose S 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 calculate P(XNdY=S) in the following way:

P(XNdY=S)=(i=0k1(Xh=0i1chci))(j=0XN(ck+XNck+XNj)(sk1)j)YX

That's pretty messy, I know.

The product expression i=0k1 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 h=0i1ch.

The sum expression j=0XN 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 consider P[43d6=(5,4,4)]:

(s1,c1)=(5,1)
(s2,c2)=(4,2)

So using the formula above:

P[43d6=(5,4,4)]=(41)((33)30+(32)31)64=5162=0.0308641975¯

The formula breaks down on a domain issue when sk=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, and XNdY 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.

Riley John Gibbs
quelle
As a programmer it might be easier for me to understand your Python code (although I've never used Python so it might be the same). Posting the code here is off topic but you could post a link to github etc.
SkySpiral7
1
Your answer may be correct and it seems to reduce the complexity from O(Y^X) to O((Y+X-1)!/(X!*(Y-1)!)) but it still isn't as efficient as whuber's answer of O(c*X*log(X)). Thanks for your answer though +1.
SkySpiral7