Czas poświęcony na uderzenie wzorem głów i ogonów w serię rzutów monetą

Zainspirowany przemową Petera Donnelly'ego na TED , w której omawia on, jak długo zajmie pojawienie się określonego wzoru w serii rzutów monetą, stworzyłem następujący skrypt w R. Biorąc pod uwagę dwa wzory „hth” i „htt”, to oblicza, ile czasu zajmuje średnio (tj. ile rzutów monetą), zanim trafisz jeden z tych wzorów.

coin <- c('h','t')

hit <- function(seq) {
    miss <- TRUE
    fail <- 3
    trp  <- sample(coin,3,replace=T)
    while (miss) {
        if (all(seq == trp)) {
            miss <- FALSE
        }
        else {
            trp <- c(trp[2],trp[3],sample(coin,1,T))
            fail <- fail + 1
        }
    }
    return(fail)
}

n <- 5000
trials <- data.frame("hth"=rep(NA,n),"htt"=rep(NA,n))

hth <- c('h','t','h')
htt <- c('h','t','t')

set.seed(4321)
for (i in 1:n) {
    trials[i,] <- c(hit(hth),hit(htt))    
}
summary(trials)

Statystyki podsumowujące są następujące,

      hth             htt        
 Min.   : 3.00   Min.   : 3.000  
 1st Qu.: 4.00   1st Qu.: 5.000  
 Median : 8.00   Median : 7.000  
 Mean   :10.08   Mean   : 8.014  
 3rd Qu.:13.00   3rd Qu.:10.000  
 Max.   :70.00   Max.   :42.000 

W wykładzie wyjaśniono, że średnia liczba rzutów monetą byłaby różna dla obu wzorów; jak widać z mojej symulacji. Mimo kilkukrotnego oglądania rozmowy wciąż nie rozumiem, dlaczego tak się dzieje. Rozumiem, że „hth” nakłada się na siebie i intuicyjnie sądzę, że trafiłbyś „hth” wcześniej niż „htt”, ale tak nie jest. Byłbym bardzo wdzięczny, gdyby ktoś mi to wyjaśnił.

Pomyśl o tym, co dzieje się za pierwszym razem, gdy dostajesz H, a następnie T.

Przypadek 1: szukasz HTH i zobaczyłeś HT po raz pierwszy. Jeśli następnym rzutem jest H, skończyłeś. Jeśli to T, wrócisz do punktu wyjścia: ponieważ dwa ostatnie rzuty to TT, teraz potrzebujesz pełnego HTH.

Przypadek 2: szukasz HTT i zobaczyłeś HT po raz pierwszy. Jeśli następnym rzutem jest T, skończyłeś. Jeśli jest to H, jest to wyraźnie niepowodzenie; jednak jest niewielki, ponieważ masz teraz H i potrzebujesz tylko -TT. Jeśli następnym rzutem jest H, sytuacja nie pogorszy się, a T sprawi, że będzie lepiej i tak dalej.

Innymi słowy, w przypadku 2 pierwsza H, którą widzisz, zajmuje 1/3 drogi i od tego momentu nigdy nie musisz zaczynać od zera. Nie jest to prawdą w przypadku 1, w którym TT usuwa wszystkie poczynione postępy.

$8n+2$$n$$n$$HTH$$HTH$

Innym sposobem spojrzenia na to jest to, że po osiągnięciu „HT”, „T” odeśle „HTH” z powrotem na start, podczas gdy „H” rozpocznie przejście do możliwego „HTT”.

$k$$k$$2^k$$2+0+8=10$$0+0+8=8$

$5$

Jest coraz gorzej: w grze Penney wybierasz wzór wyścigu, a następnie wybieram inny. Jeśli wybierzesz „HTH”, wtedy wybiorę „HHT” i mam szanse wygranej 2: 1; jeśli wybierzesz „HTT”, ponownie wybiorę „HHT” i nadal mam szanse 2: 1 na moją korzyść. Ale jeśli wybierzesz „HHT”, wtedy wybiorę „THH” i będę miał szanse 3: 1. Drugi gracz zawsze może polaryzować szanse, a najlepsze wybory nie są przechodnie.

Lubię rysować.

Te diagramy są automatami skończonymi (FSA). Są to małe gry dla dzieci (takie jak zsypy i drabiny ), które „rozpoznają” lub „akceptują” odpowiednio sekwencje HTT i HTH, przenosząc token z jednego węzła do drugiego w odpowiedzi na odwrócenie monety. Token zaczyna się w górnym węźle, na który wskazuje strzałka (linia i ). Po każdym rzucie monetą token jest przenoszony wzdłuż krawędzi oznaczonej wynikiem tej monety (H lub T) do innego węzła (który nazywam odpowiednio „węzłem H” i „węzłem T”). Gdy token wyląduje na węźle końcowym (brak wychodzących strzałek, oznaczonych na zielono) gra się kończy, a FSA zaakceptowała sekwencję.

Pomyśl o każdym FSA jako postępującym pionowo w dół po torze liniowym. Rzut „prawidłową” sekwencją głów i ogonów powoduje, że żeton postępuje w kierunku miejsca docelowego. Podrzucenie „niewłaściwej” wartości powoduje, że token wykonuje kopię zapasową (lub przynajmniej stoi w miejscu). Token tworzy kopię zapasową do najbardziej zaawansowanego stanu odpowiadającego najnowszym rzutom. Na przykład HTT FSA na linii ii pozostaje ustawiony na linii ii po zobaczeniu głowy, ponieważ ta głowa może być początkową sekwencją ewentualnego HTH. To ma nie przejść całą drogę z powrotem do początku, bo to by skutecznie ignorują ten ostatni głowę całkowicie.

Po zweryfikowaniu tych dwóch gier rzeczywiście odpowiadają one HTT i HTH, jak twierdzono, i porównanie ich linia po linii, i teraz powinno być oczywiste, że HTH jest trudniejszy do wygrania . Różnią się one strukturą graficzną tylko na linii iii , gdzie H przenosi HTT z powrotem do linii ii (a T akceptuje), ale w HTH T przenosi nas z powrotem do linii i (a H akceptuje). Kara na linii iii w grze HTH jest surowsza niż kara w grze HTT.

Można to określić ilościowo. Oznaczyłem węzły tych dwóch FSA oczekiwaną liczbą rzutów potrzebnych do akceptacji. Nazwijmy je węzłem „wartościami”. Etykietowanie zaczyna się od

(1) zapisanie oczywistej wartości 0 w węzłach akceptujących.

Niech prawdopodobieństwo głów wynosi p (H), a prawdopodobieństwo ogonów wynosi 1 - p (H) = p (T). (Dla uczciwej monety oba prawdopodobieństwa są równe 1/2.) Ponieważ każde rzucie monetą dodaje jeden do liczby rzutów,

(2) wartość węzła jest równa jeden plus p (H) razy wartość węzła H plus p (T) razy wartość węzła T.

Te zasady określają wartości . Jest to szybkie i pouczające ćwiczenie, aby sprawdzić, czy oznaczone wartości (przy założeniu uczciwej monety) są prawidłowe. Jako przykład rozważ wartość HTH w linii ii . Reguła mówi, że 8 musi być o 1 więcej niż średnia z 8 (wartość węzła H na linii i ) i 6 (wartość węzła T na linii iii ): na pewno 8 = 1 + (1/2) * 8 + (1/2) * 6. Równie łatwo można sprawdzić pozostałe pięć wartości na ilustracji.

Kilka świetnych odpowiedzi. Chciałbym zająć się nieco innym podejściem i zająć się kwestią sprzeczności z intuicją. (Zgadzam się, BTW)

Oto jak to rozumiem. Wyobraź sobie kolumnę losowych wyników losowego losowania monet wydrukowanych na papierowej taśmie, składających się z liter „H” i „T”.

Arbitralnie oderwij fragment tej taśmy i zrób identyczną kopię.

Na danej taśmie sekwencja HTH i sekwencja HTT będą występować tak często, jeśli taśma jest wystarczająco długa.

Ale czasami instancje HTH będą działać razem, tj. HTHTH. (lub nawet bardzo rzadko HTHTHTH)

To nakładanie się nie może wystąpić w instancjach HTT.

Użyj zakreślacza, aby wybrać „paski” udanych wyników, HTH na jednej taśmie i HTT na drugiej. Kilka pasków HTH będzie krótszych z powodu nakładania się. W związku z tym przerwy między nimi będą średnio nieco dłuższe niż na drugiej taśmie.

To trochę jak czekanie na autobus, kiedy średnio co pięć minut. Jeśli autobusy mogą się na siebie nakładać, interwał będzie średnio nieco dłuższy niż pięć minut, ponieważ kiedyś dwa miną razem.

Jeśli przyjedziesz w dowolnym momencie, będziesz średnio czekał nieco dłużej na następny (do ciebie, pierwszy) autobus, jeśli mogą się one nakładać.

Szukałem intuicji w tym przypadku w przypadku liczb całkowitych (gdy przerzucam Intro Ross'a do modeli prawdopodobieństwa). Więc myślałem o liczbach całkowitych. Odkryłem, że to pomogło:

$A$

$B$

$A=B$$P(A \cap \tilde{B})=0$

$A \ne B$$P(A \cap \tilde{B}) \ge 0$

Wyobraźmy sobie więc, że mam szansę dokończyć wzór podczas następnego losowania. Rysuję następny symbol i nie kończy wzoru. W przypadku, gdy mój wzór nie zachodzi na siebie, narysowany symbol może nadal pozwolić mi zacząć budować wzór od początku.

W przypadku nakładania się symbol, którego potrzebowałem, aby ukończyć częściowy wzór, był taki sam jak symbol, którego potrzebowałem, aby rozpocząć odbudowę. Więc nie mogę tego zrobić i dlatego na pewno będę musiał poczekać do następnego losowania, aby ponownie zacząć budować.