Oczekiwana liczba rzutów monetą, aby uzyskać N z rzędu, biorąc pod uwagę M z rzędu

Interviewstreet miał swój drugi CodeSprint w styczniu, który zawierał poniższe pytanie. Odpowiedź programowa jest opublikowana, ale nie zawiera wyjaśnienia statystycznego.

(Możesz zobaczyć oryginalny problem i opublikowane rozwiązanie, logując się na stronie Interviewstreet przy użyciu danych Google, a następnie przechodząc do problemu Monety na tej stronie ).

Monety Monety

Masz bezstronną monetę, którą chcesz podrzucać, dopóki nie zdobędziesz N kolejnych głów. Rzuciłeś monetą M razy i, co zaskakujące, wszystkie rzuty doprowadziły do głów.

Jaka jest oczekiwana liczba dodatkowych rzutów potrzebnych do zdobycia N kolejnych głów?

Dane wejściowe:
pierwszy wiersz zawiera liczbę przypadków T. Każda kolejna linia T zawiera dwie liczby N i M.

Dane wyjściowe:
linie wyjściowe T zawierające odpowiedź dla odpowiedniego przypadku testowego. Wydrukuj odpowiedź w zaokrągleniu do dokładnie 2 miejsc po przecinku.

Przykładowe dane wejściowe:
4
2 0
2 1
3 3
3 2

Wyjście próbki:
6,00
4,00
0,00
8,00

Przykładowe objaśnienia:
Jeśli N = 2, a M = 0, musisz ciągle podrzucać monetę, aż otrzymasz 2 kolejne głowy. Nietrudno wykazać, że potrzeba średnio 6 rzutów monetą.
Jeśli N = 2 i M = 1, potrzebujesz 2 kolejnych głów i masz już 1. Musisz rzucić jeszcze raz, bez względu na wszystko. W pierwszym rzucie, jeśli zdobędziesz głowy, to koniec. W przeciwnym razie musisz zacząć od nowa, ponieważ kolejne liczniki są zerowane, i musisz w dalszym ciągu podrzucać monetę, dopóki nie otrzymasz N = 2 kolejnych głów. Oczekiwana liczba rzutów monetą wynosi zatem 1 + (0,5 * 0 + 0,5 * 6) = 4,0. Jeśli N = 3 i M = 3, masz już 3 głowy, więc nie potrzebujesz już więcej rzutów.

Wszystkie matematyczne równania, które wymyśliłem, miały poprawne odpowiedzi dla przykładowych danych wejściowych wymienionych powyżej, ale były niepoprawne dla wszystkich innych zestawów wejściowych (które nie są znane). Wydaje się, że ich programowe rozwiązanie rozwiązuje problem zupełnie inaczej niż w mojej metodzie „próbuj wymyślić równanie”. Czy ktoś może wyjaśnić, jak wymyślić równanie, które to rozwiązałoby?

probability stochastic-processes markov-process

— Polshgiant
źródło

Zobacz także tutaj, gdzie również znajduje się wynik podany przez Daniela Johnsona poniżej.

2^{N + 1} - 2^{M + 1}

$2^{N+1}-2^{M+1}$

— Dilip Sarwate

Odpowiedzi:

To ćwiczenie obliczeniowe, więc pomyśl rekurencyjnie . Obecny stan rzutu monetą zależy od uporządkowanej pary z . Niech spodziewana liczba rzutów do osiągnięcia kolejnych głów będzie równa : $(N,M)$ $N\ge M\ge 0$ $N$ $e(N,M)$

(1) Istnieje 50% szansy, że następne uderzenie będzie głową, zabierając cię do stanu , a 50% szansy, że następne uderzenie będzie ogonem, zabierając cię do stanu . To kosztuje jedno odwrócenie. Dlatego oczekiwania (rekurencyjnie) podaje $(N,M+1)$ $(N,0)$

e (N, M) = \frac{1}{2} e (N, M + 1) + \frac{1}{2} e (N, 0) + 1.

$e(N,M) = \frac{1}{2} e(N,M+1) + \frac{1}{2} e(N,0) + 1.$

(2) Warunki podstawowe: już to określiłeś

e (N, 0) = 2^{N + 1} - 2

$e(N,0) = 2^{N+1}-2$

i oczywiście

e (N, N) = 0

$e(N,N) = 0$

(nie trzeba już więcej przewracać).

Oto odpowiedni program Mathematica (w tym buforowanie wyników pośrednich w celu przyspieszenia rekurencji, co skutecznie czyni z niego dynamiczne rozwiązanie programistyczne):

e[n_, m_] /; n > m > 0 := e[n, m] = 1 + (e[n, m + 1] + e[n, 0])/2 // Simplify
e[n_, 0] := 2^(n + 1) - 2
e[n_, n_] := 0

Program wyglądałby podobnie w innych językach programowania obsługujących rekurencję. Matematycznie możemy zweryfikować, że po prostu sprawdzając rekurencję, ponieważ oczywiście dotyczy to przypadków podstawowych: $e(N,M) = 2^{N+1} - 2^{M+1}$

2^{N + 1} - 2^{M + 1} = 1 + (2^{N + 1} - 2^{M + 2} + 2^{N + 1} - 2) / 2,

$2^{N+1} - 2^{M+1} = 1 + (2^{N+1} - 2^{M+2} + 2^{N+1} - 2)/2,$

co jest prawdziwe dla każdego i , QED. $M$ $N$

Mówiąc bardziej ogólnie , to samo podejście ustali, że gdy moneta ma prawdopodobieństwo głów. Trudną częścią jest wypracowanie warunku podstawowego . Odbywa się to poprzez wyparcie rekurencji z kroków, aż w końcu zostanie wyrażone w kategoriach siebie i rozwiązanie: $e(N,M) = \frac{p^{-N} - p^{-M}}{1-p}$ $p$ $e(N,0)$ $N$ $e(N,0)$

\begin{aligned} e (N, 0) & = 1 + p e (N, 1) + (1 - p) e (n, 0) \\ = 1 + p (1 + p e (N, 2) + (1 - p) e (N, 0)) + (1 - p) e (N, 0) \\ \dots \\ = 1 + p + p^{2} + \dots + p^{N - 1} + (1 - p) [1 + p + \dots + p^{N - 1}] e (N, 0); \\ e (N, 0) & = \frac{1 - p^{N}}{1 - p} + (1 - p^{N}) e (N, 0); \\ e (N, 0) & = \frac{p^{- N} - 1}{1 - p} . \end{aligned}

$\eqalign{ e(N,0) &= 1 + p e(N,1) + (1-p) e(n,0) \\ &= 1 + p\left(1 + p e(N,2) + (1-p) e(N,0)\right) + (1-p) e(N,0) \\ \cdots \\ &= 1 + p + p^2 + \cdots + p^{N-1} + (1-p)[1 + p + \cdots + p^{N-1}]e(N,0);\\ e(N,0) &= \frac{1-p^N}{1-p} + (1-p^N)e(N,0); \\ e(N,0) &= \frac{p^{-N}-1}{1-p}. }$

— Whuber
źródło

Być może lepiej byłoby pracować iteracyjnie niż rekurencyjnie ? Masz co daje a więc i tak dalej dającLub równanie różnicy można rozwiązać „teoretycznie” zamiast iteracyjnie.

e (N, M) = \frac{1}{2} e (N, M + 1) + \frac{1}{2} e (N, 0) + 1

$e(N,M)=\frac{1}{2}e(N,M+1)+\frac{1}{2}e(N,0)+1$

e (N, M + 1) = 2 e (N, M) - 2^{N + 1}

$e(N,M+1)=2e(N,M)-2^{N+1}$

\begin{aligned} e (N, 1) & = 2 e (N, 0) - 2^{N + 1} = 2 (2^{N + 1} - 2) - 2^{N + 1} = 2^{N + 1} - 4 \\ e (N, 2) & = 2 e (N, 1) - 2^{N + 1} = 2 (2^{N + 1} - 4) - 2^{N + 1} = 2^{N + 1} - 8 \end{aligned}

$\begin{align*}e(N,1)&=2e(N,0)-2^{N+1}=2(2^{N+1}-2)-2^{N+1}=2^{N+1}-4\\e(N,2)&=2e(N,1)-2^{N+1}=2(2^{N+1}-4)-2^{N+1}=2^{N+1}-8\end{align*}$

e (N, M) = 2^{N + 1} - 2^{M + 1} .

$e(N,M)=2^{N+1}-2^{M+1}.$

— Dilip Sarwate

@Dilip Wnioski, które wyciągasz zarówno w „co daje”, jak i „itd.” Są rekurencyjne. O jakiej metodzie rozwiązania myślisz, „rozwiązując teoretycznie”?

— whuber

Moim zdaniem różnica między rekurencyjnym a iteracyjnym polega na metodzie działania. Dla relacji rekurencja oblicza jako podczas gdy iteracja mówi „Teoretycznie” oznaczało rozwiązanie równania różniczkowego poprzez znalezienie charakterystycznego wielomianu, określenie jego pierwiastków, a następnie dopasowanie ogólnego rozwiązania do warunków początkowych, zamiast prostych obliczeń jak powyżej.

x (n) = 2 x (n - 1), x (0) = 1,

$x(n)=2x(n-1),~~ x(0)=1,$

x (n)

$x(n)$

x (n) = 2 x (n - 1) = 2 (2 x (n - 2)) = 2 (2 (2 x (n - 3))) = \dots = 2 (2 (\dots 2 x (0) \dots) = 2^{n}

$x(n)=2x(n-1)=2(2x(n-2))=2(2(2x(n-3)))=\cdots=2(2(\cdots 2x(0)\cdots)=2^n$

x (0) = 1 \Rightarrow x (1) = 2 x (0) = 2 \Rightarrow x (2) = 2 x (1) = 2^{2} \Rightarrow \dots x (n) = 2 x (n - 1) = 2 \cdot 2^{n - 1} = 2^{n} .

$x(0)=1\Rightarrow x(1)=2x(0)=2\Rightarrow x(2)=2x(1)=2^2\Rightarrow \cdots x(n)=2x(n-1)=2\cdot 2^{n-1}=2^n.$

— Dilip Sarwate

Z punktu widzenia programowania program find_x(n)jest rekurencyjny, jeśli mówi coś takiego, if n=0 return 1 else return 2*find_x(n-1)w którym find_xwywołuje się razy, podczas gdy program iteracyjny powiedziałby coś w stylu

n

$n$ y = 1; while n > 0 do begin y=2*y; n=n-1 end; return y

— Dilip Sarwate

Jeśli spojrzysz na to, jak te programy są w rzeczywistości zaimplementowane na komputerze, @Dilip, w wielu środowiskach (takich jak R) wcale się nie różnią. (W jednym przypadku tworzysz, a następnie przetwarzasz wektor, 1:naw drugim odkryjesz, że n:1został on umieszczony na stosie i przetworzony w odwrotnej kolejności). Ale część mojego punktu była konceptualna : twój początkowy komentarz mówił o „pracy iteracyjnej”. Dotyczyło to analizy, a nie żadnego programu komputerowego. Ale są to trywialne, styczne punkty, których dyskusja nie uzasadnia przedłużenia tego komentarza.

— whuber

Aby rozwiązać ten problem, wykorzystam procesy stochastyczne, czasy zatrzymania i programowanie dynamiczne.

Po pierwsze, niektóre definicje:

X_{n} ≐ # (of consecutive heads after the nth flip)

$X_n \doteq \#\text{(of consecutive heads after the nth flip)}$ również wartość dla oznaczającą liczbę kolejnych głowic przed rozpoczęciem. Tak więc, dla i sekwencji odwrotności HHTHHHTHTTHH, odpowiednie wartości wynoszą 120123010012. Gdybyśmy mieli , wartości X byłyby (M + 1) (M + 2) 0123010012.

X_{0}

$X_0$

X_{0} = 0

$X_0 = 0$

X

$X$

X_{0} = M

$X_0 = M$

Następnie zdefiniuj następujące czasy zatrzymania:

τ_{N} ≐ min {k : X_{k} = N} and τ_{0} ≐ min {k > 1 : X_{k} = 0}

$\tau_N \doteq \min\{k: X_k = N\} \text{ and } \tau_0 \doteq \min\{k > 1: X_k = 0\}$

wartość jest oczekiwaną wartością , liczby potrzebnych do zaobserwowania N kolejnych przerzutów , biorąc pod uwagę, że już zaobserwowaliśmy M kolejnych . Załóżmy, że ponieważ w przeciwnym razie odpowiedź brzmi 0. Obliczamy: $\tau_N$ $(X_{\tau_N} = N)$ $(X_0 = M)$ $M \leq N$

E [τ_{N} | X_{0} = M] = E [τ_{N} 1_{{τ_{N} < τ_{0}}} + τ_{N} 1_{{τ_{N} > τ_{0}}} | X_{0} = M]

$E[\tau_N|X_0 =M] = E[\tau_N\boldsymbol{1}_{\{\tau_N < \tau_0\}} + \tau_N\boldsymbol{1}_{\{\tau_N > \tau_0\}}|X_0 =M]$

= (N - M) (\frac{1}{2})^{N - M} + E [τ_{0} | τ_{N} > τ_{0}, X_{0} = M] + (1 - (\frac{1}{2})^{N - M}) E [τ_{N} | X_{0} = 0]

$= (N-M)(\frac{1}{2})^{N-M} + E[\tau_0|\tau_N > \tau_0,X_0 =M] + (1 - (\frac{1}{2})^{N-M})E[\tau_N|X_0 = 0]$ To pozwala nam obliczyć dwa ostatnie oczekiwania warunkowe.

Pierwszy odpowiada oczekiwanej liczbie przewrotów przed uzyskaniem ogona, przy założeniu, że ogon zostanie obrócony przed obserwowaniem N kolejnych głów, zakładając, że zaczniemy od M kolejnych głów. Nietrudno to dostrzec

E [τ_{0} | τ_{N} > τ_{0}, X_{0} = M] = \sum_{j = 1}^{N - M} (j) (\frac{1}{2})^{j} = 2 - (N - M + 2) (\frac{1}{2})^{N - M}

$E[\tau_0|\tau_N > \tau_0,X_0 =M] = \sum^{N-M}_{j=1}(j)(\frac{1}{2})^j = 2 - (N-M+2)(\frac{1}{2})^{N-M}$

Teraz wszystko, co musimy zrobić, to obliczyć drugie oczekiwanie warunkowe, które odpowiada oczekiwanej liczbie przerzutów potrzebnych do zaobserwowania N kolejnych główek, zaczynając od 0. Przy podobnych obliczeniach widzimy, że

E [τ_{N} | X_{0} = 0] = E [τ_{N} 1_{{τ_{N} < τ_{0}}} + τ_{N} 1_{{τ_{N} > τ_{0}}} | X_{0} = 0]

$E[\tau_N|X_0 = 0] = E[\tau_N\boldsymbol{1}_{\{\tau_N < \tau_0\}} + \tau_N\boldsymbol{1}_{\{\tau_N > \tau_0\}}|X_0 =0]$

= N (\frac{1}{2})^{N} + E [τ_{0} | τ_{N} > τ_{0}, X_{0} = 0] + (1 - (\frac{1}{2})^{N}) E [τ_{N} | X_{0} = 0]

$= N(\frac{1}{2})^{N} + E[\tau_0|\tau_N > \tau_0,X_0 =0] + (1 - (\frac{1}{2})^N)E[\tau_N|X_0 = 0]$

= 2^{N} {N (\frac{1}{2})^{N} + (2 - (N + 2) (\frac{1}{2})^{N})}

$= 2^N\lbrace N(\frac{1}{2})^{N} + (2 - (N+2)(\frac{1}{2})^{N})\rbrace$

= 2^{N + 1} - 2

$= 2^{N+1} - 2$

To daje ostateczną odpowiedź:

E [τ_{N} | X_{0} = M] = (N - M) (\frac{1}{2})^{N - M} + 2 - (N - M + 2) (\frac{1}{2})^{N - M} + (1 - (\frac{1}{2})^{N - M}) (2^{N + 1} - 2)

$E[\tau_N|X_0 =M] = (N-M)(\frac{1}{2})^{N-M} + 2 - (N-M+2)(\frac{1}{2})^{N-M} + (1 - (\frac{1}{2})^{N-M})(2^{N+1} - 2)$

= 2^{N + 1} - 2^{M + 1}

$= 2^{N+1}-2^{M+1}$

Jest to zgodne z czterema wymienionymi przypadkami testowymi. Przy tak prostej odpowiedzi może być łatwiejszy sposób na obliczenie tego.

— Daniel Johnson
źródło

Jest to trudniejszy sposób na rozwiązanie tego problemu niż wymieniony powyżej pomysł rekurencyjny, ale niezwykle przydatne jest połączenie obu podejść. Większość ludzi nie docenia sposobu, w jaki metody zatrzymywania czasu mogą być stosowane również w przypadku małych, praktycznych problemów.

— ely

Ostrzeżenie: poniższe odpowiedzi nie mogą być uważane za właściwą odpowiedź, ponieważ nie zapewniają zamkniętego formularza rozwiązania pytania, szczególnie. w porównaniu z poprzednimi odpowiedziami . Uważam jednak, że podejście to jest wystarczająco interesujące, aby wypracować rozkład warunkowy.

Rozważ wstępne pytanie o wyciągnięcie sekwencji głów z rzutów, z prawdopodobieństwem . Jest to podane przez wzór rekurencji Rzeczywiście, moje rozumowanie jest takie, że żadne kolejne głów z losowań nie mogą zostać rozłożone zgodnie z pierwszym wystąpieniem ogona z pierwszego rzuca. Uwarunkowanie tego, czy ten pierwszy ogon występuje przy pierwszym, drugim, ..., tym pociągnięciu prowadzi do tej relacji nawrotu. $N$ $k$ $1-p(N,k)$

p (N, k) = {\begin{cases} 1 & if k < N \\ \sum_{m = 1}^{N} \frac{1}{2^{m}} p (N, k - m) & else \end{cases}

$p(N,k) = \begin{cases} 1 &\text{if } k<N\\ \sum_{m=1}^{N} \frac{1}{2^m}p(N,k-m) &\text{else}\\ \end{cases}$

N

$N$

k

$k$

N

$N$

N

$N$

Następnie prawdopodobieństwo otrzymania pierwszych kolejnych N głów w rzutach wynosi $$ q (N, m) = \ begin {przypadkach} \ dfrac {1} {2 ^ N} i \ text {if} m = N \ $m\ge N$

     p(N,m-N-1) \dfrac{1}{2^{N+1}} &\text{if } N<m<2N+1
     \end{cases}

$$ Pierwszy przypadek jest oczywisty. drugi przypadek odpowiada ogonowi występującemu podczas losowania , a następnie głów, a ostatni przypadek zabrania kolejnych głów przed losowaniem . (Dwa ostatnie przypadki można połączyć w jeden, oczywiście!) $m-N-1$ $N$ $N$ $m-N-1$

Prawdopodobieństwo otrzymania głów jako pierwszych i pierwszych kolejnych głów w dokładnie rzutach (i nie mniej) wynosi $$ r (M, N, m) = \ begin {przypadkach} 1/2 ^ N & \ text {if} m = N \ $M$ $N$ $m\ge N$

     0 &\text{if } N<m\le N+M\\

      \dfrac{1}{2^{M}}\sum_{r=M+1}^{N}\dfrac{1}{2^{r-M}}q(N,m-r)&\text{if } N+M<m

\ end {przypadki} s (M, N, m) = \ begin {skrzynki} 1 / {2 ^ {NM}} i \ text {if} m = N \ 0 & \ text {if} N \ sum_ {r = M + 1} ^ {N} \ dfrac {q (N, mr)} {2 ^ {rM }} i \ text {if} N + M

H e n c e t h e c o n d i t i o n a l p r o b a b i l i t y o f w a i t i n g $ m $ s t e p s t o g e t $ N $ c o n s e c u t i v e h e a d s g i v e n t h e f i r s t $ M $ c o n s e c u t i v e h e a d s i s

$Hence the conditional probability of waiting $m$ steps to get $N$ consecutive heads given the first $M$ consecutive heads is$

\ end {przypadki} \ mathfrak {E} (M, N) = \ sum_ {m = N} ^ \ infty m \, s (M, N, m) $$ lub za liczbę dodatkowych kroków ...

T h e e x p e c t e d n u m b e r o f d r a w s c a n t h e n b e d e r i v e d b y

$The expected number of draws can then be derived by$

E (M, N) - M

$\mathfrak{E}(M,N)-M$

— Xi'an
źródło