Formula untuk menjatuhkan dadu (gaya non-brute)

Pertama-tama saya tidak yakin di mana pertanyaan ini harus diposting. Saya bertanya apakah masalah statistik adalah NP-Lengkap dan jika tidak menyelesaikannya secara pemrograman. Saya memposting di sini karena masalah statistik adalah titik pusat.

Saya mencoba mencari formula yang lebih baik untuk menyelesaikan masalah. Masalahnya adalah: jika saya memiliki 4d6 (4 dadu 6 sisi biasa) dan menggulung semuanya sekaligus, mengeluarkan dadu dengan angka terendah (disebut "menjatuhkan"), lalu menjumlahkan 3 sisanya, berapakah probabilitas setiap hasil yang mungkin ? Saya tahu jawabannya adalah ini:

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

Rata-rata adalah 12,24 dan standar deviasi adalah 2,847.

Saya menemukan jawaban di atas dengan kekerasan dan tidak tahu bagaimana atau apakah ada formula untuk itu. Saya menduga masalah ini NP-Lengkap dan karena itu hanya dapat diselesaikan dengan kekerasan. Mungkin saja untuk mendapatkan semua probabilitas 3d6 (3 dadu bersisi 6 normal) kemudian condongkan masing-masing ke atas. Ini akan lebih cepat daripada brute force karena saya memiliki formula cepat ketika semua dadu disimpan.

Saya memprogram formula untuk menjaga semua dadu di perguruan tinggi. Saya telah bertanya kepada profesor statistik saya tentang hal itu dan dia menemukan halaman ini , yang kemudian dia jelaskan kepada saya. Ada perbedaan kinerja yang besar antara formula ini dan brute force: 50d6 membutuhkan waktu 20 detik tetapi penurunan terendah 8d6 terjadi setelah 40 detik (chrome kehabisan memori).

Apakah ini masalah NP-Complete? Jika ya tolong berikan bukti, jika tidak silakan berikan formula kekuatan non-brute untuk menyelesaikannya.

Perhatikan bahwa saya tidak tahu banyak tentang NP-Complete jadi saya mungkin berpikir tentang NP, NP-Hard, atau yang lainnya. Bukti untuk NP-Completeness tidak berguna bagi saya satu-satunya alasan mengapa saya memintanya adalah untuk mencegah orang menebak. Dan tolong beri tahu saya karena sudah lama sejak saya mengerjakan ini: Saya tidak ingat statistik dan saya mungkin perlu menyelesaikan ini.

Idealnya saya sedang mencari formula yang lebih umum untuk jumlah X dadu dengan sisi Y ketika N dari mereka dijatuhkan tetapi saya mulai dengan sesuatu yang jauh lebih sederhana.

Edit:

Saya juga lebih suka rumus untuk frekuensi keluaran tetapi hanya dapat diterima untuk probabilitas keluaran.

Bagi mereka yang tertarik, saya telah memprogram jawaban whuber di JavaScript pada GitHub saya (dalam melakukan ini hanya tes yang benar-benar menggunakan fungsi yang ditentukan).

Larutan

Biarkan ada $n=4$ dadu masing-masing memberikan peluang yang sama untuk hasil $1, 2, \ldots, d=6$ . Biarkan $K$ menjadi nilai minimum ketika semua $n$ dadu dilemparkan secara independen.

Pertimbangkan distribusi jumlah semua $n$ nilai tergantung pada $K$ . Biarkan $X$ menjadi jumlah ini. Fungsi pembangkit untuk sejumlah cara untuk membentuk nilai $X$ diberikan, mengingat minimumnya setidaknya $k$ , adalah

$$f_{(n,d,k)}(x) = x^k+x^{k+1} + \cdots + x^d = x^k\frac{1-x^{d-k+1}}{1-x}.\tag{1}$$

Karena dadu independen, fungsi pembangkit untuk sejumlah cara untuk membentuk nilai-nilai $X$ mana semua $n$ dadu menunjukkan nilai $k$ atau lebih besar adalah

$$f_{(n,d,k)}(x)^n = x^{kn}\left(\frac{1-x^{d-k+1}}{1-x}\right)^n.\tag{2}$$

Fungsi menghasilkan ini mencakup istilah untuk peristiwa di mana melebihi k , jadi kita perlu mengurangi mereka. Oleh karena itu fungsi menghasilkan untuk sejumlah cara untuk membentuk nilai-nilai X , mengingat K = k , adalah$K$$k$$X$$K=k$

$$f_{(n,d,k)}(x)^n - f_{(n,d,k+1)}(x)^n.\tag{3}$$

Memperhatikan bahwa jumlah dari nilai tertinggi adalah jumlah dari semua nilai minus terkecil, sama dengan X - K . Karena itu fungsi pembangkit perlu dibagi dengan k . Ini menjadi fungsi yang menghasilkan probabilitas setelah dikalikan dengan peluang bersama dari kombinasi dadu, ( 1 / d ) n :$n-1$$X-K$$k$$(1/d)^n$

$$d^{-n}\sum_{k=1}^dx^{-k}\left(f_{(n,d,k)}(x)^n - f_{(n,d,k+1)}(x)^n\right).\tag{4}$$

Karena semua produk dan kekuatan polinomial dapat dihitung dalam operasi (mereka adalah konvolusi dan karenanya dapat dilakukan dengan Fast Fourier Transform diskrit), upaya komputasi total adalah O ( $O(n\log n)$ . Secara khusus,ini adalah algoritma waktu polinomial.$O(k\,n\log n)$

---

Contoh

Mari kita bekerja melalui contoh dalam pertanyaan dengan dan d = 6 .$n=4$$d=6$

Formula untuk PGF dari X tergantung pada K ≥ k memberikan$(1)$$X$$K\ge k$

$$\eqalign{ f_{(4,6,1)}(x) &= x+x^2+x^3+x^4+x^5+x^6 \\ f_{(4,6,2)}(x) &= x^2+x^3+x^4+x^5+x^6 \\ \ldots \\ f_{(4,6,5)}(x) &= x^5+x^6 \\ f_{(4,6,6)}(x) &= x^6 \\ f_{(4,6,7)}(x) &= 0. }$$

Meningkatkannya ke kekuatan seperti pada rumus ( 2 ) menghasilkan$n=4$$(2)$

$$\eqalign{ f_{(4,6,1)}(x)^4 &= x^4 + 4x^5 + 10 x^6 + \cdots + 4x^{23} + x^{24} \\ f_{(4,6,2)}(x)^4 &= x^8 + 4x^9 + 10x^{10}+ \cdots + 4x^{23} + x^{24} \\ \ldots \\ f_{(4,6,5)}(x)^4 &=x^{20} + 4 x^{21} + 6 x^{22} + 4x^{23} +x^{24}\\ f_{(4,6,6)}(x)^4 &= x^{24}\\ f_{(4,6,7)}(x)^4 &= 0 }$$

Perbedaan berturut-turut dalam rumus adalah$(3)$

$$\eqalign{ f_{(4,6,1)}(x)^4 - f_{(4,6,2)}(x)^4 &= x^4 + 4x^5 + 10 x^6 + \cdots + 12 x^{18} + 4x^{19} \\ f_{(4,6,2)}(x)^4 - f_{(4,6,3)}(x)^4 &= x^8 + 4x^9 + 10x^{10} + \cdots + 4 x^{20} \\ \ldots \\ f_{(4,6,5)}(x)^4 - f_{(4,6,6)}(x)^4 &=x^{20} + 4 x^{21} + 6 x^{22} + 4x^{23} \\ f_{(4,6,6)}(x)^4 - f_{(4,6,7)}(x)^4 &= x^{24}. }$$

Jumlah yang dihasilkan dalam rumus adalah$(4)$

$$6^{-4}\left(x^3 + 4x^4 + 10x^5 + 21x^6 + 38x^7 + 62x^8 + 91x^9 + 122x^{10} + 148x^{11} + \\167x^{12} + 172x^{13} + 160x^{14} + 131x^{15} + 94x^{16} + 54x^{17} + 21x^{18}\right).$$

For example, the chance that the top three dice sum to $14$ is the coefficient of $x^{14}$, equal to

$$6^{-4}\times 160 = 10/81 = 0.123\,456\,790\,123\,456\,\ldots.$$

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

By the way, the mean (as calculated from this result) is $15869/1296 \approx 12.244598765\ldots$ and the standard deviation is $\sqrt{13\,612\,487/1\,679\,616}\approx 2.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:

Since the minimum $K$ is highly likely to equal $1$ and the sum $X$ will be extremely close to having a Normal$(400\times 7/2, 400\times 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\times 10^{-32}$ greater than $1399$ and a standard deviation around $1.24\times 10^{-31}$ less than $\sqrt{400\times 35/12}$.

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 $X_n$ represents the $n$th die, and suppose $Y_n$ represents the sum of $n$ dice. Then

$$p(Y_n = a) = \sum_k p(Y_{n-1} = a - k)p(X_n=k)$$

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

$$p(Z_n = a) = p(\text{$n$th die is the smallest})p(Y_{n-1} = a) + \\ p(\text{$n$th die is not the smallest})\sum_k p(Z_{n-1} = a - k)p(X_n=k)$$

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

$$p(Z_n = a) = p(X_n \leq M_{n-1})p(Y_{n-1} = a | X_n \leq M_{n-1}) + \\ p(X_n > M_{n-1})\sum_k p(Z_{n-1} = a - k)p(X_n=k | X_n > M_{n-1})$$

and we can calculate $M_n$ using

$$p(M_n = a) = p(X_n \leq M_{n-1})p(X_n = a |X_n \leq M_{n-1}) + p(X_n > M_{n-1})p(M_{n-1} = a|X_n > M_{n-1})$$

Anyway, together this all suggests a dynamic programming algorithm based on $Y_n, Z_n$ and $M_n$. Should be quadratic in $n$.

edit: A comment has been raised on how to calculate $p(X_n \leq M_{n-1})$. Since $X_n, M_{n-1}$ can each only take on one of six values, we can just sum over all possibilities:

$$p(X_n \leq M_{n-1}) = \sum_{a,b} p(X_n = a, M_{n-1} = b, a \leq b)$$

Similarly, $p(X_n = k | X_n > M_{n-1})$ can be calculated by applying Bayes rule then summing over the possible values of $X_n, M_{n-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 $X_NdY$ 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. $4_3d6$ 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(X_NdY = S)$ (or more specifically, $P(4_3d6 = 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, $s_0, s_1, ..., s_k$, such that $s_i > s_{i+1}$, and each $s_i$ has a count of $c_i$. For example, if $S = 3, 4, 4, 5$, then $(s_0,c_0) = (5,1)$, $(s_1,c_1) = (4,2)$, and $(s_2,c_2) = (3,1)$.

You can calculate $P(X_NdY = S)$ in the following way:

$$P(X_NdY = S) = \frac{ \left( \prod_{i=0}^{k-1} {X - \sum_{h=0}^{i-1} c_h \choose c_i} \right) \left( \sum_{j=0}^{X-N} { c_k+X-N \choose c_k+X-N-j} (s_k-1)^j \right)}{ Y^X }$$

That's pretty messy, I know.

The product expression $\prod_{i=0}^{k-1}$ 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 $s_0$, that's just $X \choose c_i$, but for $s_1$, we have to remove the $c_0$ dice that have already been set aside for $s_0$, and likewise for $s_i$ you must remove $\sum_{h=0}^{i-1}c_h$.

The sum expression $\sum_{j=0}^{X-N}$ is iterating through all the possibilities of how many of the dropped dice were equal to $s_k$, since that affects the possible combinations for the un-dropped dice with $s_k$ as their value.

By example, let's consider $P[4_3d6=(5,4,4)]$:

$$(s_1, c_1) = (5, 1)$$ $$(s_2, c_2) = (4, 2)$$

So using the formula above:

$$P[4_3d6=(5,4,4)] \\ = \frac{ {4 \choose 1} \left( {3 \choose 3} \cdot 3^0 + {3 \choose 2} \cdot 3^1 \right) }{ 6^4 } \\ = \frac{5}{162} = 0.0\overline{308641975}$$

The formula breaks down on a domain issue when $s_k=1$ and $j=0$ in the summation, leading to a first term of $0^0$, 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 $s_k = 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 $X_NdY$ 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 $\sum X_NdY$, and maybe I'll do that later.