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?
źródło
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 ≥ 0 N e ( N , M )(N,M) N≥M≥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 , 0 )(N,M+1) (N,0)
(2) Warunki podstawowe: już to określiłeś
i oczywiście
(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):
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)=2N+1−2M+1
co jest prawdziwe dla każdego i , QED.NM 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: pe(N,0)Ne(N,0)e(N,M)=p−N−p−M1−p p e(N,0) N e(N,0)
źródło
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órymfind_x
wywołuje się razy, podczas gdy program iteracyjny powiedziałby coś w styluy = 1; while n > 0 do begin y=2*y; n=n-1 end; return y
R
) wcale się nie różnią. (W jednym przypadku tworzysz, a następnie przetwarzasz wektor,1:n
aw drugim odkryjesz, żen:1
został 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.Aby rozwiązać ten problem, wykorzystam procesy stochastyczne, czasy zatrzymania i programowanie dynamiczne.
Po pierwsze, niektóre definicje:
Następnie zdefiniuj następujące czasy zatrzymania:
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:τN (XτN=N) (X0=M) M≤N
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
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
To daje ostateczną odpowiedź:
Jest to zgodne z czterema wymienionymi przypadkami testowymi. Przy tak prostej odpowiedzi może być łatwiejszy sposób na obliczenie tego.
źródło
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)
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≥N
$$ 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≥N
\ 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
\ end {przypadki} \ mathfrak {E} (M, N) = \ sum_ {m = N} ^ \ infty m \, s (M, N, m) $$ lub za liczbę dodatkowych kroków ...E ( M , N ) - M
źródło