Rzuć kostką 6-stronne aż do całkowitego . Średnia ilość, o którą jest przekroczony?

Oto pytanie:

Rzucasz iteracyjnie uczciwymi 6-stronnymi kostkami, aż suma rzutów kostek będzie większa lub równa M. Jakie jest średnie i standardowe odchylenie sumy minus M, gdy M = 300?

Czy powinienem napisać kod, aby odpowiedzieć na tego rodzaju pytania?

Proszę dać mi kilka wskazówek na ten temat. dzięki!

self-study standard-deviation dice eli
źródło

Dodaj [self-study]tag i przeczytaj jego wiki . Następnie powiedz nam, co rozumiesz do tej pory, czego próbowałeś i gdzie utknąłeś. Podamy wskazówki, które pomogą Ci się odblokować.

Gung - Przywróć Monikę

Podejrzewam, że można odczytać jako „bardzo duże ”, ponieważ uważam, że lub dałoby prawie taki sam wynik. Co chciałbym zrobić, to znaleźć rozkład suma minus .

M = 300

$M=300$

M

$M$

M = 301

$M=301$

M = 999

$M=999$

M

$M$

Henry

Odpowiedzi:

Z pewnością możesz użyć kodu, ale nie symulowałbym.

Zignoruję część „minus M” (możesz to zrobić dość łatwo na końcu).

Można bardzo łatwo obliczyć prawdopodobieństwa rekurencyjnie, ale rzeczywistą odpowiedź (z bardzo wysokim stopniem dokładności) można obliczyć na podstawie prostego rozumowania.

Niech bułki być . Niech . $X_1, X_2, ...$ $S_t=\sum_{i=1}^t X_i$

Niech być najmniejszy wskaźnik gdzie . $\tau$ $S_\tau\geq M$

$P(S_\tau=M)=P(\text{got to }M-6\text{ at }\tau-1\text{ and rolled a }6) \\\qquad\qquad\qquad+ P(\text{got to }M-5\text{ at }\tau-1\text{ and rolled a }5)\\\qquad\qquad\qquad +\:\: \vdots\\\qquad\qquad\qquad+\:P(\text{got to }M-1\text{ at }\tau-1\text{ and rolled a }1)\\ \qquad\qquad\quad=\frac{1}{6}\sum_{j=1}^6 P(S_{\tau-1}=M-j)$

wprowadź opis zdjęcia tutaj

podobnie

$P(S_\tau=M+1)=\frac{1}{6}\sum_{j=1}^5 P(S_{\tau-1}=M-j)$

$P(S_\tau=M+2)=\frac{1}{6}\sum_{j=1}^4 P(S_{\tau-1}=M-j)$

$P(S_\tau=M+3)=\frac{1}{6}\sum_{j=1}^3 P(S_{\tau-1}=M-j)$

$P(S_\tau=M+4)=\frac{1}{6}\sum_{j=1}^2 P(S_{\tau-1}=M-j)$

$P(S_\tau=M+5)=\frac{1}{6} P(S_{\tau-1}=M-1)$

Równania podobne do pierwszego powyższego można następnie (przynajmniej w zasadzie) cofać, dopóki nie osiągniesz któregokolwiek z warunków początkowych, aby uzyskać algebraiczną zależność między warunkami początkowymi a oczekiwanymi prawdopodobieństwami (co byłoby uciążliwe i niezbyt pouczające) , lub możesz zbudować odpowiednie równania do przodu i uruchomić je z warunków początkowych, co jest łatwe do zrobienia numerycznie (i tak sprawdziłem moją odpowiedź). Możemy jednak tego wszystkiego uniknąć.

Prawdopodobieństwa punktów są ważonymi średnimi wcześniejszych prawdopodobieństw; te (geometrycznie szybko) wygładzą wszelkie zmiany prawdopodobieństwa z początkowego rozkładu (wszelkie prawdopodobieństwo w punkcie zero w przypadku naszego problemu). The

W przybliżeniu (bardzo dokładne) możemy powiedzieć, że do powinny być prawie równie prawdopodobne w czasie (naprawdę blisko), a więc z powyższego możemy zapisać, że prawdopodobieństwa będą bardzo bliscy bycia w prostych stosunkach, a ponieważ muszą być znormalizowane, możemy po prostu zapisać prawdopodobieństwa. $M-6$ $M-1$ $\tau-1$

Oznacza to, że widzimy, że gdyby prawdopodobieństwo przejścia od do było dokładnie równe, istnieje 6 jednakowo prawdopodobnych sposobów dotarcia do , 5 do i tak dalej do 1 sposób na dostanie się do . $M-6$ $M-1$ $M$ $M+1$ $M+5$

Oznacza to, że prawdopodobieństwa są w stosunku 6: 5: 4: 3: 2: 1 i sumują się do 1, więc są łatwe do zanotowania.

Dokładne obliczenie go (aż do skumulowanych błędów numerycznego zaokrąglenia) przez uruchomienie rekurencji prawdopodobieństwa do przodu od zera (zrobiłem to w R) daje różnice w kolejności .Machine$double.eps( na mojej maszynie) od powyższego przybliżenia (to znaczy: proste rozumowanie zgodnie z powyższymi wierszami daje efektywnie dokładne odpowiedzi, ponieważ są one tak bliskie odpowiedziom obliczonym na podstawie rekurencji, jak przypuszczalibyśmy, że dokładne odpowiedzi powinny być). $\approx$ 2.22e-16

Oto mój kod do tego (większość po prostu inicjuje zmienne, praca jest w jednym wierszu). Kod zaczyna się po pierwszym rzucie (aby zaoszczędzić mi wpisania komórki 0, co jest niewielką uciążliwością w R); na każdym kroku pobiera najniższą komórkę, którą można zająć, i przesuwa się do przodu za pomocą rzutu kostką (rozkładając prawdopodobieństwo tej komórki na kolejne 6 komórek):

 p = array(data = 0, dim = 305)
 d6 = rep(1/6,6)
 i6 = 1:6
 p[i6] = d6
 for (i in 1:299) p[i+i6] = p[i+i6] + p[i]*d6

(moglibyśmy użyć rollapply(z zoo), aby zrobić to bardziej wydajnie - lub wielu innych takich funkcji - ale łatwiej będzie to przetłumaczyć, jeśli będę to wyraźnie wyrażać)

Zauważ, że d6jest to dyskretna funkcja prawdopodobieństwa powyżej 1 do 6, więc kod wewnątrz pętli w ostatnim wierszu konstruuje średnie ważone z wcześniejszych wartości. To właśnie ta relacja sprawia, że prawdopodobieństwo wygładza się (aż do kilku ostatnich wartości, którymi jesteśmy zainteresowani).

Oto pierwsze 50 nieparzystych wartości (pierwsze 25 wartości oznaczone kółkami). Przy każdym wartość na osi y reprezentuje prawdopodobieństwo, które zgromadziło się w najbardziej tylnej komórce, zanim przetoczyliśmy ją do następnych 6 komórek. $t$

wprowadź opis zdjęcia tutaj

Jak widzisz, wygładza się (do , odwrotność średniej liczby kroków, które wykonuje każdy rzut kości) dość szybko i pozostaje stała. $1/\mu$

A kiedy trafimy w , te prawdopodobieństwa maleją (ponieważ nie przedstawiamy z kolei prawdopodobieństwa dla wartości w i dalej) $M$ $M$

wprowadź opis zdjęcia tutaj

Zatem oczywiste jest, że idea, że wartości od do powinny być równie prawdopodobne, ponieważ wahania warunków początkowych zostaną wygładzone. $M-1$ $M-6$

Ponieważ rozumowanie nie zależy od niczego, ale jest na tyle duże, że warunki początkowe wypłukują się, tak że do są prawie równie prawdopodobne w czasie , rozkład będzie zasadniczo taki sam dla każdego duże , jak sugerował Henry w komentarzach. $M$ $M-1$ $M-6$ $\tau-1$ $M$

Patrząc wstecz, wskazówka Henry'ego (która jest również w twoim pytaniu), aby pracować z sumą minus M zaoszczędziłaby trochę wysiłku, ale argument byłby bardzo podobny. Możesz kontynuować, pozwalając i pisać podobne równania dotyczące z poprzednimi wartościami i tak dalej. $R_t=S_t-M$ $R_0$

Z rozkładu prawdopodobieństwa średnia i wariancja prawdopodobieństw są wtedy proste.

Edycja: Przypuszczam, że powinienem podać średnią asymptotyczną i odchylenie standardowe pozycji końcowej minus : $M$

Średni asymptotyczny nadmiar wynosi a odchylenie standardowe to . Przy jest to dokładne w znacznie większym stopniu, niż możesz się tym przejmować. $\frac{5}{3}$ $\frac{2\sqrt 5}{3}$ $M=300$

Glen_b - Przywróć Monikę
źródło

+1 Nie w pełni zrozumiałem tę odpowiedź, dopóki nie opracowałem własnej, która teraz wydaje się zbędna. Może niektórzy czytelnicy zobaczą wartość na ilustracji i wynikach symulacji, więc zachowam odpowiedź.

whuber

@whuber Moja odpowiedź jest o wiele mniej konkretna, niż bym sobie tego życzył, ponieważ działałam w założeniu, że była to praca domowa (więc unikałam zbytniego wyprowadzania kodu źródłowego lub podawania kodu - bardziej miał na celu zarys). Trudno mi było jednoznacznie napisać odpowiedź na ten problem (w tym konkretność pomaga bardziej niż zwykle). Ponieważ udzieliłeś odpowiedzi zawierającej rzeczywiste liczby i kod (którą odpowiedź zdecydowanie uważam, że powinien zostać), czuję, że mogę zrobić pewne rzeczy, które, mam nadzieję, ułatwią zrozumienie mojej odpowiedzi (wyraźniej, podaj własny kod) .

Glen_b

Kilka lat temu napisałem znacznie lepsze wyjaśnienie tego rodzaju problemu. Jeśli pamiętam / wymyślę, jak poszło, postaram się zamieścić tutaj niektóre z nich.

Glen_b

@Glen_b trochę rozumiał równania. Jestem nowicjuszem. jak zacząć tak myśleć? Czy są jakieś książki, które możesz polecić w tym celu? Twoja odpowiedź byłaby bardzo pomocna.

Zwykły podejrzany

Zwykły podejrzany - napisałem równania, wyobrażając sobie planszę jak długą ścieżkę i idąc „jakie są sposoby, aby dostać się do tej przestrzeni w sposób, który pasuje do warunków problemu i z jakimi szansami?”; Zrobiłem to dla spacji oznaczonej „M”, następnie dla spacji po nim i tak dalej. Napisałem podobne obliczenia dla kodu, wyobrażając sobie, że jestem w pobliżu komórki początkowej i mówiąc: „gdybym tu był, czy byłbym następny, z jakimi szansami?”. Równania to tylko odpowiedzi na te pytania.

Glen_b

$\Omega$ $0$ $n$ $E_n$ $n$

E_{n} = {ω \in Ω | n \in ω} .

$E_n = \{\omega\in\Omega\,|\, n \in \omega\}.$

$X_M(\omega)$ $\omega$ $M$ $X_M-M$ $X_M$

$X_M(\omega) - M \in \{0, 1, 2, 3, 4, 5\}$ $X_M - M = k$ $\omega$ $p(i) = 1/6$ $i$ $i=1, 2, 3, 4, 5, 6$

Pr (X_{M} - M = k) = \sum_{j = k}^{6} Pr (E_{M + k - j}) p (j) = \frac{1}{6} \sum_{j = k}^{6} Pr (E_{M + k - j}) .

$\Pr(X_M - M = k) = \sum_{j=k}^6 \Pr(E_{M+k-j}) p(j) = \frac{1}{6} \sum_{j=k}^6 \Pr(E_{M+k-j}).$

W tym miejscu możemy heurystycznie argumentować, że w bardzo dobrym przybliżeniu dla wszystkich oprócz najmniejszych ,Wynika to z tego, że oczekiwana wartość rzutu wynosi a jej odwrotnością powinna być ograniczająca, stabilna długofalowa częstotliwość dowolnej wartości w . $M$

Pr (E_{i}) \approx 2 / 7.

$\Pr(E_i) \approx 2/7.$

(1 + 2 + 3 + 4 + 5 + 6) / 6 = 7 / 2

$(1+2+3+4+5+6)/6 = 7/2$

ω

$\omega$

Rygorystyczny sposób wykazania tego uwzględnia sposób, w jaki może wystąpić . Występuje albo a następny rzut to ; lub występuje, a kolejny rzut był wynikiem ; lub ... lub pojawia się a następny rzut to . To wyczerpujący podział możliwości, skąd $E_i$ $E_{i-1}$ $1$ $E_{i-2}$ $2$ $E_{i-6}$ $6$

Pr (E_{i}) = \sum_{j = 1}^{6} Pr (E_{i - j}) p (j) = \frac{1}{6} \sum_{j = 1}^{6} Pr (E_{i - j}) .

$\Pr(E_i) = \sum_{j=1}^6 \Pr(E_{i-j}) p(j) = \frac{1}{6} \sum_{j=1}^6 \Pr(E_{i-j}).$

Początkowe wartości tej sekwencji to

Pr (E_{0}) = 1; Pr (E_{- i}) = 0, i = 1, 2, 3, \dots .

$\Pr(E_0) = 1;\quad \Pr(E_{-i}) = 0, i = 1, 2, 3, \ldots .$

Rysunek: wykres E_i

Ten wykres stosunku do pokazuje, jak szybko szanse opadają do stałej , pokazanej poziomą przerywaną linią. $\Pr(E_i)$ $i$ $2/7$

Istnieje standardowa teoria takich sekwencji rekurencyjnych. Można go opracować za pomocą generowania funkcji, łańcuchów Markowa, a nawet manipulacji algebraicznych. Ogólny wynik jest taki, że istnieje formuła zamknięta dla . $\Pr(E_i)$ Będzie to liniowa kombinacja stałej i mocy pierwiastków wielomianu $i^\text{th}$

x^{6} - p (1) x^{5} - p (2) x^{4} - p (3) x^{3} \dots - p (6) = x^{6} - (x^{5} + x^{4} + x^{3} + x^{2} + x + 1) / 6.

$x^6 - p(1) x^5 - p(2) x^4 - p(3) x^3 \cdots - p(6) = x^6 - (x^5 + x^4+x^3+x^2+x+1)/6.$

Największa wielkość tych pierwiastków wynosi około . W reprezentacji zmiennoprzecinkowej podwójnej precyzji jest zasadniczo zerowy. Dlatego dla $\exp(-0.314368)$ $\exp(-36.05)$ $i \gg -36.05 / -0.314368 = 115$ $2/7$

W związku z tym dla , dla wszystkich praktycznych celów możemy przyjąć , skąd $M = 300 \gg 115$ $E_{M+k-j} = 2/7$

Pr (X_{M} - M = (0, 1, 2, 3, 4, 5)) = (\frac{2}{7}) (\frac{1}{6}) (6, 5, 4, 3, 2, 1) .

$\Pr(X_M - M = (0,1,2,3,4,5)) = \left(\frac{2}{7}\right)\left(\frac{1}{6}\right)(6,5,4,3,2,1).$

Obliczenie średniej i wariancji tego rozkładu jest proste i łatwe.

Oto Rsymulacja potwierdzająca te wnioski. Generuje prawie 100 000 sekwencji przez , zestawia wartości i stosuje test aby ocenić, czy wyniki są zgodne z powyższym. Wartość p (w tym przypadku) jest wystarczająco duża, aby wskazać, że są one spójne. $M+5 = 305$ $X_{300} - 300$ $\chi^2$ $0.1367$

M <- 300
n.iter <- 1e5
set.seed(17)
n <- ceiling((2/7) * (M + 3*sqrt(M)))
dice <- matrix(ceiling(6*runif(n*n.iter)), n, n.iter)
omega <- apply(dice, 2, cumsum)
omega <- omega[, apply(omega, 2, max) >= M+5]
omega[omega < M] <- NA
x <- apply(omega, 2, min, na.rm=TRUE)
count <- tabulate(x)[0:5+M]
(cbind(count, expected=round((2/7) * (6:1)/6 * length(x), 1)))
chisq.test(count, p=(2/7) * (6:1)/6)

Whuber
źródło