# a question related to two competing patterns in coin tossing

If I have a two-sided coin with probability $p$ showing head. I repeatedly toss it until either HTHTH or HTHH appears. Can you calculate

1) the probability when I got HTHTH, and

2) the expected value of the number of tosses before I stop?

Thanks.

-
So the answers in the previous question: math.stackexchange.com/questions/18093/… didn't help? I believe the approach in my answer there tackles this one too. You just need two accepting states in the DFA, one for HTHTH and one for HTTH. – Aryabhata Jan 21 '11 at 6:41
@Moron: to be honest, I am not familiar with DFA. Without a concrete worked example, I do not know how to carry out the calculation. Can you please give a detailed solution to this problem, some numbers/calculational steps please? – Qiang Li Jan 21 '11 at 6:54
@QIang: THat would require time which I don't have right now. Perhaps this link might help in the meantime: docs.google.com/… . As to what a DFA is, check the wiki for deterministic finite automaton. – Aryabhata Jan 21 '11 at 7:00
Maybe this will help too: cs.brown.edu/research/ai/dynamics/tutorial/Documents/… – Aryabhata Jan 21 '11 at 7:01
You also ought to be able to use a Markov chain approach similar to the accepted answer on the question to which Moron linked. – Isaac Jan 21 '11 at 9:51

Let $q$ be the probability of tails. Then the answers are

$$1) \frac{q}{1+q}$$

$$2) \frac{1+pq+p^2q+p^2q^2}{p^3q(1+q)}.$$

The ideas and notation in the following derivation are courtesy of Section 8.4 ("Flipping Coins") of Concrete Mathematics. See that section for more details and examples.

Imagine this as a contest in which Player A wins if HTHTH appears first and Player B wins if HTHH appears first. Let $S_A$ and $S_B$ denote the sum of the winning sequences of tosses for HTHTH and HTHH, respectively. (This is overloading the addition operator, but it works.) Let $N$ denote the sum of the sequences in which neither HTHTH nor HTHH has occurred yet. ($N$ includes the empty sequence.) Thus $$S_A = \text{HTHTH + THTHTH + HHTHTH + TTHTHTH + THHTHTH + HHHTHTH} + \cdots,$$ $$S_B = \text{HTHH + THTHH + HHTHH + TTHTHH + THHTHH + HHHTHH} + \cdots,$$ $$N = \text{1 + H + T + HH + HT + TH + TT} + \cdots.$$

Then, by substituting $p$ for H and $q$ for T, $S_A$, $S_B$, and $N$ become the probability that $A$ wins, the probability that $B$ wins, and the expected number of tosses until the game ends, respectively. The first two claims are straightforward. The third follows from the fact that if $X$ is a nonnegative random variable then $E[X] = \sum_{k=0}^{\infty} P(X > k).$

As sums of sequences, we also have $$N \text{ HTHTH} = S_A + S_A \text{ TH} + S_A \text{ THTH} + S_B \text{ THTH},$$ $$N \text{ HTHH} = S_A \text{ H} + S_A \text{ THH} + S_B + S_B \text{ THH}.$$

The idea behind the first equation is that the sequences of tosses obtained by appending HTHTH to $N$ must be a sequence of winning tosses for $A$ or $B$ plus possibly some extra tosses. In particular, each sequence in $N$ HTHTH must be exactly one of 1) a winning sequence for $A$, 2) a winning sequence for $A$ followed by TH, 3) a winning sequence for $A$ followed by THTH, or 4) a winning sequence for $B$ followed by THTH. These are all possibilities because they represent all ways in which part of the sequence HTHTH can begin (i.e., overlap) another occurrence of HTHTH or (in 4) in which HTHH can begin an occurrence of HTHTH. The idea behind the second equation is similar.

Then, substituting $p$ for H and $q$ for T we have $$N p^3q^2 = S_A + S_A pq + S_A p^2q^2 + S_B p^2q^2,$$ $$N p^3q = S_A p + S_A p^2 q + S_B + S_B p^2q.$$

Simultaneously solving these two equations with $S_A + S_B = 1$ yields $$S_A = \frac{q}{1+q},$$ $$S_B = \frac{1}{1+q},$$ $$N = \frac{1+pq+p^2q+p^2q^2}{p^3q(1+q)}.$$

Update, in response to OP's question in the comments: Why does substituting $p$ for H and $q$ for T and the fact that $E[X] = \sum_{k=0}^{\infty} P(X > k)$ for a nonnegative random variable all mean that $N$ is the expected number of tosses until the game ends?

Let $X$ be the number of tosses until the game ends. $P(X > 0)$ is just 1. $P(X > 1)$ is the probability that we haven't seen one of the patterns yet with a single toss; i.e., H + T, with $p$ subbed in for H and $q$ for T. $P(X > 2)$ is the probability that we haven't seen one of the patterns yet with two tosses, which is HH + HT + TH + TT, with $p$ subbed in for H and $q$ for T. $P(X > 3)$ is..., etc. This doesn't get interesting until we look at $P(X > 4)$, which would include all four-length sequences of H and T except for HTHH. Adding all those sequences in which neither HTHH nor HTHTH has occurred yet is exactly $N$, and subbing in $p$ for H and $q$ for T in $N$ thus gives $E[X]$.

See also the solution to Problem 8.21 in Concrete Mathematics, p. 578 (second edition).

-
I came back to this problem today. I am still wondering why "The third follows from the fact that if $X$ is a nonnegative random variable then $E[X]=\sum_{k=0}^\infty{P(X>k)}$." I know this identity, but I don't see how it can be applied to the situation described here. We have "$N$ denote the sum of the sequences in which neither HTHTH nor HTHH has occurred yet", and we need to get "the expected number of tosses until the game ends". How to bridge these two using the identity above? May thanks. – Qiang Li Feb 2 '11 at 4:42
@Qiang Li: I've updated my answer to address the question in your comment. – Mike Spivey Feb 2 '11 at 5:44

Assume that the coin tossing is infinite. Define the state at time $n$ to be the most recent $5$ outcomes when $n \geq 5$ and the $n$ most recent outcomes when $n <5$. This is a Markov chain. Now $\pi_{HTHTH}$(the limiting probability) is equal to the inverse of the mean time to go from state HTHTH to HTHTH. Thus $\pi_{HTHTH} = p^{3}q^2$ (probability of getting HTHTH) where $q=1-p$. So $1/(p^{3}q^2)$ is the mean time to go from HTHTH to HTHTH. Thus $$E(\text{time to get} \ HTHTH) = E(\text{time to get} \ HT)+ \frac{1}{p^{3}q^{2}}$$ $$= E(\text{time to get} \ H)+ \frac{1}{pq}+\frac{1}{p^{3}q^{2}} = \frac{1}{p}+\frac{1}{pq}+\frac{1}{p^{3}q^{2}}$$

-
Sorry, but does this actually answer either of the part of the problem? I'm (not very familiar with Markov chains and am) confused about what the mean time tells you. (And I'm assuming $q = 1 - p$; is that right?) – Ben Alpert Jan 22 '11 at 2:55
@Ben Alpert: It answers the probability of getting HTHTH which is $p^{3}q^2$ where $q=1-p$. – PEV Jan 22 '11 at 2:58
@PEV: So if that's a fair coin, you're saying the probability is $1/32$. Of course, that's the probability that a random flip sequence of length 5 is equal to HTHTH but doesn't seem to answer whether HTHTH or HTHH is more likely to appear first. – Ben Alpert Jan 22 '11 at 3:01
@Ben Alpert: The probability of obtaining HTHH is $p^{3}q$. – PEV Jan 22 '11 at 3:03
@PEV: I can't tell if I'm just being really stupid here, but I'm still unsure how that helps. For example, if with a fair coin you're looking for TH vs HH, it's much more likely ($3/4$ vs. $1/4$) that you'll see TH first because once you see a single T, it's impossible to get HH before seeing TH. How do we get the same answer using your method? (Presumably that would be $pq$ vs $p^2$.) – Ben Alpert Jan 22 '11 at 3:06

There is a direct, and rather automatic, way to compute the probability to hit A=HTHTH first rather than B=HTHH.

Both motives begin by HTH hence one can wait until HTH first appears. Then, either (1) the next letter is H, or (2) the two next letters are TH, or (3) the two next letters are TT. If (1) happens, B won. If (2) happens, A won. If (3) happens, one has to wait for more letters to know who won. The important fact in case (3) is that, since the last letters are TT, A or B must be entirely produced again.

Hence, $p_B=p_1+p_3p_B$ and $p_A=p_2+p_3p_A$, where $p_i$ for $i=$ 1, 2 and 3, is a shorthand for the conditional probability that ($i$) happens starting from the word HTH. Since $p_1=p$, $p_2=qp$ and $p_3=q^2$, one gets $p_B=p_1/(1-p_3)=p/(1-q^2)$, hence $$p_B=1/(1+q),\quad p_A=q/(1+q).$$ Similarly, a standard, and rather automatic, way to compute the mean number of tosses before this happens is to consider a Markov chain on the state space made of the prefixes of the words one wishes to complete.

Here, the states are 0 (for the empty prefix), 1=H, 2=HT, 3=HTH, B=HTHH, 4=HTHT and A=HTHTH. The transitions are from 0 to 1 and 0, from 1 to 2 and 1, from 2 to 3 and 0, from 3 to B and 4 and from 4 to A and 0. The transitions from B and from A are irrelevant. The next step is to compute $n_s$ the number of tosses needed to produce A or B starting from any state $s$ amongst 0, 1, 2, 3 and 4, knowing that one is in fact only interested in $n_0$.

The $n_s$ are solutions of a Cramér system which reflects the structure of the underlying Markov chain: $$n_0=1+pn_1+qn_0,\quad n_1=1+pn_1+qn_2,\quad n_2=1+pn_3+qn_0,$$ $$n_3=1+qn_4,\quad n_4=1+qn_0.$$ Solving this system of equations backwards, that is, going from the last equation back to the first one, yields $n_3$ in terms of $n_0$, then $n_2$ in terms of $n_0$, then $n_1$ in terms of $n_0$, and finally an equation for $n_0$ alone, which yields Mike's formula for $n_0$, namely: $$n_0=\frac{1+pq+p^2q+p^2q^2}{p^3q(1+q)}.$$ An accessible reference for these techniques (in the context of genomic sequence analysis) is the book DNA, Words and Models by Robin, Rodolphe and Schbath, at Cambridge UP.

-
+1: Just for the record, though, in Concrete Mathematics it is claimed that their method (the one in my answer) for calculating $n_0$ is simpler than solving the system of equations resulting from the Markov chain. The Markov chain approach is also the approach indicated by Moron in the first comment on the OP. – Mike Spivey Feb 2 '11 at 9:47
Mike: CM invokes simplicity for one motif. First, even in this case, I do not find them very convincing. Second, no such claim is made for two motives (see for instance equation (8.79) at the bottom of page 409 in CM second edition). Third, and more importantly to me, I must think to apply CM method correctly (for instance, should it be $S_AT$ or $S_A$ or something else in the RHS of the third equation of (8.78)?) and the Markov chain method is entirely automatic. But, as they say: Des goûts et des couleurs... :-) [Did you elucidate the $+p$ problem in the numerator?] – Did Feb 2 '11 at 10:28
@Didier: Fair enough. :) Unfortunately, I don't see the mistake in either of our solutions, yet; they both look right to me! Maybe I'll try again in the morning when my brain is less foggy. :) – Mike Spivey Feb 2 '11 at 11:02
Mike: Got it! When at prefix 1=H, either one moves to prefix 2=HT or one stays at prefix 1=H, right? Hence $n_1=1+pn_0+qn_1$ (instead of $n_1=1+pn_0+qn_2$ as I first wrote, erroneously). This yields your formula. I corrected my post. – Did Feb 2 '11 at 13:47
@Didier: That's it! I'm glad you found the resolution; it was bothering me that two correct approaches were yielding different answers. :) (FYI: If you preface your comments with @ then the addressee gets a notification that there is a new comment for them the next time he/she checks the site.) – Mike Spivey Feb 2 '11 at 19:59