Es dauerte einige Zeit, um in einer Reihe von Münzwürfen ein Muster aus Kopf und Zahl zu treffen

Inspiriert von Peter Donnellys Vortrag bei TED , in dem er bespricht, wie lange es dauern würde, bis ein bestimmtes Muster in einer Reihe von Münzwürfen erscheint, habe ich das folgende Skript in R erstellt. Bei zwei Mustern 'hth' und 'htt' berechnet, wie lange es im Durchschnitt dauert (dh wie viele Münzwürfe), bis Sie eines dieser Muster treffen.

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)

Die zusammenfassenden Statistiken lauten wie folgt:

      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 

In dem Vortrag wird erklärt, dass die durchschnittliche Anzahl der Münzwürfe für die beiden Muster unterschiedlich ist. wie aus meiner simulation hervorgeht. Obwohl ich den Vortrag ein paar Mal gesehen habe, verstehe ich immer noch nicht genau, warum dies der Fall sein sollte. Ich verstehe, dass sich 'hth' überschneidet und ich würde intuitiv denken, dass Sie 'hth' früher als 'htt' treffen würden, aber dies ist nicht der Fall. Ich würde mich sehr freuen, wenn mir jemand dies erklären könnte.

Überlegen Sie, was passiert, wenn Sie zum ersten Mal ein H gefolgt von einem T erhalten.

Fall 1: Sie suchen nach HTH und haben HT zum ersten Mal gesehen. Wenn der nächste Wurf H ist, sind Sie fertig. Wenn es T ist, sind Sie wieder auf dem ersten Platz: Da die letzten beiden Würfe TT waren, benötigen Sie jetzt die volle HTH.

Fall 2: Sie suchen nach HTT und haben HT zum ersten Mal gesehen. Wenn der nächste Wurf T ist, sind Sie fertig. Wenn es H ist, ist dies eindeutig ein Rückschlag; Es ist jedoch eine kleinere, da Sie jetzt das H haben und nur -TT benötigen. Wenn der nächste Wurf H ist, verschlechtert sich Ihre Situation nicht, wohingegen T die Situation verbessert und so weiter.

Anders ausgedrückt, in Fall 2 nimmt das erste H, das Sie sehen, ein Drittel des Weges in Anspruch, und von diesem Punkt an müssen Sie nie wieder bei Null anfangen. Dies gilt nicht für Fall 1, in dem ein TT alle von Ihnen erzielten Fortschritte löscht.

Angenommen, Sie werfen die Münze Mal und zählen, wie oft Sie ein "HTH" -Muster (einschließlich Überlappungen) sehen. Die erwartete Anzahl ist . Es ist aber auch für "HTT". Da sich und "HTT" nicht überschneiden können, ist mit einer stärkeren Verklumpung von "HTH" zu rechnen, was die erwartete Zeit für das erste Auftreten von . n n H T H H T $8n+2$$n$$n$$HTH$$HTH$

Eine andere Sichtweise ist, dass nach Erreichen von "HT" ein "T" "HTH" zum Start zurücksendet, während ein "H" zu einem möglichen "HTT" fortschreitet.

Sie können die beiden erwarteten Zeiten mit dem Conway-Algorithmus [glaube ich] berechnen, indem Sie sich die Überlappungen ansehen: Wenn die ersten Würfe des Musters mit dem letzten übereinstimmen , dann addieren Sie . Für "HTH" erhalten Sie also als Erwartung und für "HTT" erhalten Sie , was Ihre Simulation bestätigt.k 2 k 2 + 0 + 8 = 10 0 + 0 + 8 = $k$$k$$2^k$$2+0+8=10$$0+0+8=8$

Die Seltsamkeit hört hier nicht auf. Wenn Sie ein Rennen zwischen den beiden Mustern haben, ist die Wahrscheinlichkeit, dass sie zuerst auftreten, gleich hoch und die erwartete Zeit bis zum Erscheinen eines Musters beträgt (eine Zeit mehr als erwartet, um "HT" zu erhalten, danach muss eines von ihnen erscheinen). . $5$

Es wird schlimmer: In Penneys Spiel wählst du ein Muster für das Rennen und dann wähle ich ein anderes. Wenn Sie "HTH" wählen, wähle ich "HHT" und habe eine Gewinnchance von 2: 1. Wenn Sie "HTT" wählen, wähle ich wieder "HHT" und habe immer noch 2: 1 Quoten zu meinen Gunsten. Aber wenn du "HHT" wählst, dann wähle ich "THH" und habe eine Quote von 3: 1. Der zweite Spieler kann die Gewinnchancen immer voreingenommen machen, und die besten Entscheidungen sind nicht transitiv.

Ich male gerne Bilder.

Diese Diagramme sind Finite-State-Automaten (FSAs). Es sind winzige Kinderspiele (wie Rutschen und Leitern ), die die HTT- bzw. HTH-Sequenzen "erkennen" oder "akzeptieren", indem sie als Reaktion auf die Münzwürfe einen Spielstein von einem Knoten zum anderen bewegen. Das Token beginnt am oberen Knoten, auf den ein Pfeil (Linie i ) zeigt. Nach jedem Münzwurf wird der Spielstein entlang der mit dem Ergebnis dieser Münze gekennzeichneten Kante (entweder H oder T) zu einem anderen Knoten bewegt (den ich als "H-Knoten" bzw. "T-Knoten" bezeichne). Wenn der Token auf einem Endknoten landet (keine abgehenden Pfeile, grün markiert), ist das Spiel beendet und die FSA hat die Sequenz akzeptiert.

Stellen Sie sich jede FSA so vor, als würde sie sich vertikal entlang einer linearen Spur bewegen. Das Werfen der "richtigen" Folge von Kopf und Zahl bewirkt, dass sich der Spielstein seinem Ziel nähert. Wenn Sie einen "falschen" Wert eingeben, wird das Token gesichert (oder steht zumindest still). Das Token wird auf den neuesten Stand gesichert, der den letzten Würfen entspricht. Zum Beispiel bleibt die HTT-FSA in Zeile ii beim Erkennen eines Kopfes in Zeile ii , da dieser Kopf die Anfangssequenz einer eventuellen HTH sein könnte. Es geht nicht den ganzen Weg zurück zum Anfang, weil das diesen letzten Kopf insgesamt effektiv ignorieren würde.

Nach der Überprüfung dieser beiden Spiele, die in der Tat HTT und HTH entsprechen, wie behauptet, und dem zeilenweisen Vergleich, sollte es nun offensichtlich sein, dass HTH schwerer zu gewinnen ist . Sie unterscheiden sich in ihrer grafischen Struktur nur in Zeile iii , wo ein H HTT zurück zu Zeile ii bringt (und ein T akzeptiert), aber in HTH bringt ein T uns zurück zu Zeile i (und ein H akzeptiert). Die Strafe an der Linie III beim Spielen von HTH ist schwerwiegender als die Strafe beim Spielen von HTT.

Dies kann quantifiziert werden. Ich habe die Knoten dieser beiden FSAs mit der erwarteten Anzahl der für die Akzeptanz erforderlichen Würfe gekennzeichnet . Nennen wir diesen Knoten "Werte". Die Beschriftung beginnt mit

(1) Schreiben des offensichtlichen Wertes 0 an den akzeptierenden Knoten.

Die Wahrscheinlichkeit von Köpfen sei p (H) und die Wahrscheinlichkeit von Schwänzen sei 1 - p (H) = p (T). (Für eine faire Münze sind beide Wahrscheinlichkeiten gleich 1/2.) Da jeder Münzwurf einen zur Anzahl der Würfe addiert,

(2) Der Wert eines Knotens ist gleich eins plus p (H) mal dem Wert des H-Knotens plus p (T) mal dem Wert des T-Knotens.

Diese Regeln bestimmen die Werte . Es ist eine schnelle und informative Übung, um zu überprüfen, ob die angegebenen Werte (unter der Annahme einer fairen Münze) korrekt sind. Betrachten Sie als Beispiel den Wert für HTH in Zeile ii . Die Regel besagt, dass 8 1 mehr als der Durchschnitt von 8 (der Wert des H-Knotens in Zeile i ) und 6 (der Wert des T-Knotens in Zeile iii ) sein muss: Sicher genug, 8 = 1 + (1/2) * 8 + (1/2) * 6. Genauso einfach können Sie die restlichen fünf Werte in der Abbildung überprüfen.

Einige gute Antworten. Ich würde gerne eine etwas andere Richtung einschlagen und mich mit der Frage der Gegenintuitivität befassen. (Ich stimme ganz zu, BTW)

So verstehe ich es. Stellen Sie sich eine Spalte mit zufälligen, aufeinanderfolgenden Münzwurfergebnissen vor, die auf ein Papierband gedruckt sind und aus den Buchstaben "H" und "T" bestehen.

Reißen Sie einen Abschnitt dieses Bandes willkürlich ab und erstellen Sie eine identische Kopie.

Auf einem bestimmten Band werden die Sequenz HTH und die Sequenz HTT jeweils so oft vorkommen, wenn das Band lang genug ist.

Aber gelegentlich laufen die HTH-Instanzen zusammen, dh HTHTH. (oder sogar gelegentlich HTHTHTH)

Diese Überlappung kann bei HTT-Instanzen nicht auftreten.

Verwenden Sie einen Textmarker, um die "Streifen" erfolgreicher Ergebnisse, HTH auf einem Band und HTT auf dem anderen, herauszusuchen. Einige der HTH-Streifen sind aufgrund der Überlappung kürzer. Folglich sind die Lücken zwischen ihnen im Durchschnitt etwas länger als auf dem anderen Band.

Es ist ein bisschen so, als würde man auf einen Bus warten, wenn es im Durchschnitt alle fünf Minuten einen gibt. Wenn sich die Busse überlappen dürfen, ist das Intervall im Durchschnitt etwas länger als fünf Minuten, da manchmal zwei zusammen vorbeiziehen.

Wenn Sie zu einer beliebigen Zeit ankommen, werden Sie im Durchschnitt etwas länger auf den nächsten (zu Ihnen ersten) Bus warten, wenn er sich überlappen darf.

Ich suchte nach der Intuition für diesen ganzzahligen Fall (während ich mich durch Ross 'Intro. To Probability Models bewege). Also habe ich über ganzzahlige Fälle nachgedacht. Ich fand das hilfreich:

$A$

$B$

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

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

Stellen Sie sich vor, ich hätte die Chance, das Muster bei der nächsten Ziehung zu beenden. Ich zeichne das nächste Symbol und es beendet das Muster nicht. Falls sich mein Muster nicht überlappt, kann ich mit dem gezeichneten Symbol das Muster möglicherweise noch einmal von vorne erstellen.

Im Falle einer Überlappung war das Symbol, das ich zum Fertigstellen meines Teilmusters benötigte, dasselbe wie das Symbol, das ich für den Wiederaufbau benötigte. Also kann ich das auch nicht und muss auf jeden Fall bis zur nächsten Auslosung warten, um wieder mit dem Bauen zu beginnen.