Formuła do rzucania kostkami (siła nie brutalna)

Przede wszystkim nie jestem pewien, gdzie należy zadać to pytanie. Pytam, czy problem statystyczny jest NP-Complete i czy nie mam go rozwiązać programowo. Zamieszczam go tutaj, ponieważ problem statystyczny jest punktem centralnym.

Próbuję znaleźć lepszą formułę rozwiązania problemu. Problem polega na tym: jeśli mam 4k6 (4 zwykłe 6-stronne kości) i rzucam je wszystkie naraz, usuń kość o najniższej liczbie (zwanej „upuszczeniem”), a następnie zsumuj pozostałe 3, jakie jest prawdopodobieństwo każdego możliwego wyniku ? Wiem, że odpowiedź brzmi:

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

Średnia wynosi 12,24, a odchylenie standardowe wynosi 2,847.

Znalazłem powyższą odpowiedź brutalną siłą i nie wiem, jak i czy istnieje na to formuła. Podejrzewam, że ten problem jest NP-Complete i dlatego można go rozwiązać jedynie brutalną siłą. Możliwe jest uzyskanie wszystkich prawdopodobieństw 3d6 (3 normalne 6-stronne kości), a następnie przekrzywienie każdego z nich w górę. Byłoby to szybsze niż brutalna siła, ponieważ mam szybką formułę, gdy wszystkie kości są trzymane.

Zaprogramowałem formułę przechowywania wszystkich kości na studiach. Zapytałem o to mojego profesora statystyki, a on znalazł tę stronę , którą mi następnie wyjaśnił. Istnieje duża różnica w wydajności między tą formułą a brutalną siłą: 50d6 zajęło 20 sekund, ale 8d6 upuściło najniższe awarie po 40 sekundach (chrome zabrakło pamięci).

Czy to jest problem NP-Complete? Jeśli tak, proszę przedstawić dowód, a jeśli nie, proszę podać formułę bez użycia siły, aby go rozwiązać.

Zauważ, że niewiele wiem o NP-Complete, więc mogę myśleć o NP, NP-Hard lub o czymś innym. Dowód kompletności NP jest dla mnie bezużyteczny, jedynym powodem, dla którego o to proszę, jest zapobieganie zgadywaniu. I proszę, obnażcie się ze mną, bo od dawna nad tym pracuję: nie pamiętam statystyk tak dobrze, jak być może będę musiał to rozwiązać.

Idealnie szukam bardziej ogólnej formuły dla liczby X kości ze stronami Y, gdy N zostanie upuszczonych, ale zaczynam od czegoś znacznie prostszego.

Edytować:

Wolałbym również ten wzór od częstotliwości wyjściowych, ale dopuszczalne są tylko prawdopodobieństwa wyjściowe.

Dla zainteresowanych zaprogramowałem odpowiedź Whubera w JavaScript na moim GitHub (w tym zatwierdzeniu tylko testy faktycznie używają zdefiniowanych funkcji).

dice np

— SkySpiral7
źródło

To interesujące pytanie. Myślę, że tutaj powinno być na temat. Dziękuję za uwagę.

— gung - Przywróć Monikę

Chociaż ustawienie jest interesujące, nie zadałeś jeszcze pytania, na które można odpowiedzieć: idea kompletności NP zależy od posiadania klasy problemów, podczas gdy opisałeś tylko jeden. Dokładnie jak chcesz to uogólnić? Chociaż sugerujesz, że liczba kości może się różnić, możliwe są różne dodatkowe opcje i mogą one dać różne odpowiedzi: możesz zmienić liczbę twarzy, wartości na twarzach, liczbę kości i liczbę upuszczonych kości, wszystko na różne sposoby, z różnymi relacjami między nimi.

— whuber

@whuber Nie zna żadnej teorii złożoności, ale myślę, że jasne jest, że pyta o rodzinę problemów generowanych przez zmianę liczby kości. Myślę też, że mam do tego wydajny algorytm.

— Andy Jones,

@Andy, widzę na końcu, że prosi o „bardziej ogólną formułę dla liczby X kości z bokami Y, gdy N zostanie upuszczonych”.

— whuber

@whuber Hah! Najwyraźniej nie tak jasne, jak myślałem wtedy. Przepraszam moja wina.

— Andy Jones,

Odpowiedzi:

Rozwiązanie

Niech będzie kości, z których każda daje równe szanse na wyniki . Niech będzie minimalną wartością, gdy wszystkie kości są rzucane niezależnie. $n=4$ $1, 2, \ldots, d=6$ $K$ $n$

Rozważmy rozkład sumy wszystkich wartości warunkowych na . Niech będzie tą sumą. Funkcja generująca liczbę sposobów formowania dowolnej wartości , biorąc pod uwagę, że minimum wynosi co najmniej , wynosi $n$ $K$ $X$ $X$ $k$

\begin{matrix} (1) & f_{(n, d, k)} (x) = x^{k} + x^{k + 1} + \dots + x^{d} = x^{k} \frac{1 - x^{d - k + 1}}{1 - x} . \end{matrix}

$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}$

Ponieważ kości są niezależne, funkcja generująca liczbę sposobów formowania wartości gdzie wszystkie kości wykazują wartości lub większe, wynosi $X$ $n$ $k$

\begin{matrix} (2) & f_{(n, d, k)} (x)^{n} = x^{k n} {(\frac{1 - x^{d - k + 1}}{1 - x})}^{n} . \end{matrix}

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

Ta funkcja generująca obejmuje terminy dla zdarzeń, w których przekracza , więc musimy je odjąć. Dlatego funkcja generująca liczbę sposobów tworzenia wartości , przy danym , wynosi $K$ $k$ $X$ $K=k$

\begin{matrix} (3) & f_{(n, d, k)} (x)^{n} - f_{(n, d, k + 1)} (x)^{n} . \end{matrix}

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

Zauważyć, że suma najwyższych wartości jest sumą wszystkich wartości ujemnych najmniejsza, równa . Funkcję generującą należy zatem podzielić przez . Staje się funkcją generującą prawdopodobieństwo po pomnożeniu przez wspólną szansę dowolnej kombinacji kości, : $n-1$ $X-K$ $k$ $(1/d)^n$

\begin{matrix} (4) & d^{- n} \sum_{k = 1}^{d} x^{- k} (f_{(n, d, k)} (x)^{n} - f_{(n, d, k + 1)} (x)^{n}) . \end{matrix}

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

Ponieważ wszystkie produkty i moce wielomianowe można obliczyć w operacjach (są one zwojami, a zatem można je przeprowadzić za pomocą dyskretnej szybkiej transformaty Fouriera), całkowity wysiłek obliczeniowy wynosi $O(n\log n)$ . W szczególnościjest to algorytm wielomianowy. $O(k\,n\log n)$

Przykład

Praca Załóżmy, poprzez przykład, w kwestii z , a . $n=4$ $d=6$

Wzór dla PGF zależnego od daje $(1)$ $X$ $K\ge k$

\begin{aligned} 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} \\ \dots \\ f_{(4, 6, 5)} (x) & = x^{5} + x^{6} \\ f_{(4, 6, 6)} (x) & = x^{6} \\ f_{(4, 6, 7)} (x) & = 0. \end{aligned}

$\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. }$

Zwiększenie ich do mocy jak we wzorze daje $n=4$ $(2)$

\begin{aligned} f_{(4, 6, 1)} (x)^{4} & = x^{4} + 4 x^{5} + 10 x^{6} + \dots + 4 x^{23} + x^{24} \\ f_{(4, 6, 2)} (x)^{4} & = x^{8} + 4 x^{9} + 10 x^{10} + \dots + 4 x^{23} + x^{24} \\ \dots \\ f_{(4, 6, 5)} (x)^{4} & = x^{20} + 4 x^{21} + 6 x^{22} + 4 x^{23} + x^{24} \\ f_{(4, 6, 6)} (x)^{4} & = x^{24} \\ f_{(4, 6, 7)} (x)^{4} & = 0 \end{aligned}

$\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 }$

Ich kolejne różnice we wzorze są $(3)$

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

$\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}. }$

Wynikowa suma we wzorze wynosi $(4)$

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

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

Na przykład szansa, że pierwsze trzy kości sumują się do to współczynnik równy $14$ $x^{14}$

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

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

Jest to całkowicie zgodne z prawdopodobieństwami przytoczonymi w pytaniu.

Nawiasem mówiąc, średnia (obliczony na podstawie tego wyniku) wynosi i odchylenie standardowe jest $15869/1296 \approx 12.244598765\ldots$ . $\sqrt{13\,612\,487/1\,679\,616}\approx 2.8468444$

Podobne (niezoptymalizowane) obliczenie dla kości zamiast zajęło mniej niż pół sekundy, potwierdzając twierdzenie, że nie jest to algorytm wymagający obliczeń. Oto wykres głównej części dystrybucji: $n=400$ $n=4$

Ponieważ minimalne jest bardzo prawdopodobnie równy , a suma będzie bardzo blisko mający normalną dystrybucji (którego średnia wynosi i odchylenie standardowe wynosi około ), przy czym średnia musi być bardzo bliska a odchylenie standardowe bardzo blisko . To ładnie opisuje fabułę, wskazując, że prawdopodobnie jest poprawna. W rzeczywistości dokładne obliczenia dają średnią około $K$ $1$ $X$ $(400\times 7/2, 400\times 35/12)$ $1400$ $34.1565$ $1400-1=1399$ $34.16$ większa niż , a odchylenie standardowe około mniej niż $2.13\times 10^{-32}$ $1399$ $1.24\times 10^{-31}$ . $\sqrt{400\times 35/12}$

— Whuber
źródło

Twoja odpowiedź jest szybka i poprawna, dlatego oznaczyłem ją jako odpowiedź. Również w edycji powiedziałem, że byłoby miło mieć częstotliwości, jeśli to możliwe. W tym celu nie musisz edytować swojej odpowiedzi, ponieważ widzę, że 6^-4mnożnik służy do konwersji częstotliwości na prawdopodobieństwo.

— SkySpiral7,

Edycja: @SkySpiral miał problem z uruchomieniem poniższej formuły. Obecnie nie mam czasu, aby dowiedzieć się, na czym polega problem, więc jeśli czytasz to, najlepiej postępować przy założeniu, że jest to nieprawidłowe.

Nie jestem pewien ogólnego problemu z różną liczbą kości, boków i upuszczeń, ale myślę, że widzę wydajny algorytm dla przypadku drop-1. Kwalifikator polega na tym, że nie jestem całkowicie pewien, czy jest poprawny, ale w tej chwili nie widzę żadnych wad.

$X_n$ $n$ $Y_n$ $n$

p (Y_{n} = a) = \sum_{k} p (Y_{n - 1} = a - k) p (X_{n} = k)

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

$Z_n$ $n$

p (Z_{n} = a) = p (n th die is the smallest) p (Y_{n - 1} = a) + p (n th die is not the smallest) \sum_{k} p (Z_{n - 1} = a - k) p (X_{n} = k)

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

$M_n$ $n$

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

$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})$

$M_n$

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

$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})$

$Y_n, Z_n$ $M_n$ $n$

$p(X_n \leq M_{n-1})$ $X_n, M_{n-1}$

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

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

$p(X_n = k | X_n > M_{n-1})$ $X_n, M_{n-1}$

— Andy Jones
źródło

+1 To wygląda poprawnie i powiedziałeś, że to kwadrat. Ale minęło kilka lat, odkąd wziąłem statystyki (jestem przede wszystkim programistą). Chciałbym więc to w pełni zrozumieć, zanim oznaczysz to jako odpowiedź. Widzę też, że masz p (n-ta jest najmniejszą kością). Czy to obejmuje, jeśli n-ta jest powiązana z najmniejszą? Takich jak rzut wszystkie 3.

— SkySpiral7,

n

$n$

Y_{n - 1}

$Y_{n-1}$

(<)

$(<)$

(\leq)

$(\leq)$

Dziękuję Ci. Jeśli dobrze to rozumiem, myślę, że twoje formuły są odpowiedzią. Nie wiem jednak, jak obliczyć p (X (n)> M (n-1)) (lub jego negacja) lub p (X (n) = k | X (n)> M (n-1) )), więc nie mogę jeszcze użyć tej odpowiedzi. Oznaczę to jako odpowiedź, ale chciałbym uzyskać więcej informacji. Czy możesz edytować swoją odpowiedź, aby je wyjaśnić, czy powinienem opublikować ją jako kolejne pytanie?

— SkySpiral7

Edytowałem moją odpowiedź.

— Andy Jones,

Przepraszam, wiem, że minęło półtora roku, ale w końcu udało mi się wdrożyć tę formułę do kodu. Jednak formuła p (Z (n) = a) wydaje się niepoprawna. Załóżmy, że 2 kości z 2 stronami (najniższy spadek), jakie są szanse na wynik 1? Szansa, że X (n) będzie najmniejsza lub powiązana, wynosi 3/4, a p (Y (n-1) = 1) wynosi 1/2, więc Z (n) zwraca co najmniej 3/8, mimo że poprawna odpowiedź to 1/4 Formuła Z wygląda dla mnie poprawnie i nie wiem, jak to naprawić. Więc jeśli nie jest zbyt wiele, aby zapytać: co myślisz?

— SkySpiral7

Mam do tego dość wydajny algorytm, który podczas testowania wydaje się odpowiadać wynikom czystej brutalnej siły, a mniej polegać na wyliczaniu wszystkich możliwości. Jest właściwie bardziej uogólniony niż powyższy problem 4d6, upuść 1.

$X_NdY$ $X$ $Y$ $1$ $Y$ $N$ $4_3d6$ $3, 4, 5$ $1, 3, 4, 5$ na czterech kostkach. (Zauważ, że nazywam to „sekwencją”, ale kolejność nie jest tutaj ważna, szczególnie, że na końcu zależy nam na sumie).

$P(X_NdY = S)$ $P(4_3d6 = S)$

$S$ $k$ $s_0, s_1, ..., s_k$ $s_i > s_{i+1}$ $s_i$ $c_i$ $S = 3, 4, 4, 5$ $(s_0,c_0) = (5,1)$ $(s_1,c_1) = (4,2)$ $(s_2,c_2) = (3,1)$

$P(X_NdY = S)$

P (X_{N} d Y = S) = \frac{(\prod_{i = 0}^{k - 1} (\binom{X - \sum_{h = 0}^{i - 1} c_{h}}{c_{i}})) (\sum_{j = 0}^{X - N} (\binom{c_{k} + X - N}{c_{k} + X - N - j}) (s_{k} - 1)^{j})}{Y^{X}}

$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 }$

To dość niechlujne, wiem.

$\prod_{i=0}^{k-1}$ $S$ $s_0$ $X \choose c_i$ $s_1$ $c_0$ $s_0$ $s_i$ $\sum_{h=0}^{i-1}c_h$

$\sum_{j=0}^{X-N}$ $s_k$ $s_k$

$P[4_3d6=(5,4,4)]$

(s_{1}, c_{1}) = (5, 1)

$(s_1, c_1) = (5, 1)$

(s_{2}, c_{2}) = (4, 2)

$(s_2, c_2) = (4, 2)$

Korzystając z powyższego wzoru:

P [4_{3} d 6 = (5, 4, 4)] = \frac{(\binom{4}{1}) ((\binom{3}{3}) \cdot 3^{0} + (\binom{3}{2}) \cdot 3^{1})}{6^{4}} = \frac{5}{162} = 0.0 \bar{308641975}

$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}$

$s_k=1$ $j=0$ $0^0$ $1$ $s_k = 1$

$X_NdY$ $S$ $S$

$\sum X_NdY$

— Riley John Gibbs
źródło

Jako programista może mi łatwiej zrozumieć Twój kod Pythona (chociaż nigdy nie korzystałem z Pythona, więc może być taki sam). Zamieszczanie kodu tutaj jest nie na temat, ale możesz opublikować link do github itp.

— SkySpiral7 31.10.16

Twoja odpowiedź może być poprawna i wydaje się zmniejszać złożoność z O(Y^X)do, O((Y+X-1)!/(X!*(Y-1)!))ale nadal nie jest tak skuteczna jak odpowiedź Whubera O(c*X*log(X)). Dziękuję za odpowiedź przez +1.

— SkySpiral7,