What is the probability of getting a sequence of THHT when flipping a coin ten times?

Question

The specific question is in the title but I'd also like to know how to calculate such probabilities of subsequences in general. I know I need to use the inclusion/exclusion principle but I don't know how to apply it in such cases.

Any and all advice is appreciated. :)

Answer 1

There are four positions you are interested in:

• Nothing useful so far: let's call the probability of being here after $n$ flips $A_n$; you start with $A_0=1$
• Latest flip T but never achieved THHT: let's call the probability $B_n$ with $B_0=0$
• Latest flips TH but never achieved THHT: let's use $C_n$ with $C_0=0$
• Latest flips THH but never achieved THHT: let's use $D_n$ with $D_0=0$
• THHT achieved at some stage: let's use $P_n$ with $P_0=0$

You then have recurrences (which you could instead write as a Markov chain transition matrix):

• $A_{n+1}= \frac12 A_n+\frac12 D_n$
• $B_{n+1}= \frac12 A_n+\frac12 B_n + \frac12 C_n$
• $C_{n+1}= \frac12 B_n$
• $D_{n+1}= \frac12 C_n$
• $P_{n+1}= \frac12 D_n + P_n$

You can work through these to find $P_{10} = \frac{393}{1024}$ here

Other 4-flip target patterns may have different recurrences and slightly different values of $P_{10}$

Answer 2

Here is a mechanical way. This is identical to Henry's answer, just shows the FSM & matrix explicitly.

Create an FSM that represents the desired sequence such as the one below:

We want to compute the probability that the state is $4$ after an input of length $10$.

Write the transition chain for the corresponding Markov chain:

$P= \begin{bmatrix} {1 \over 2} & 0 & 0 & {1 \over 2} & 0 \\ {1 \over 2} & {1 \over 2} & {1 \over 2} & 0 & 0 \\ 0 & {1 \over 2} & 0 & 0 & 0 \\ 0 & 0 & {1 \over 2} & 0 & 0 \\ 0 & 0 & 0 & {1 \over 2} & 1 \end{bmatrix} $

Start in the $0$ state with probability 1, $x_0 = (1,0,0,0,0)$. Compute $P^{10} x_0= {1 \over 1024} (97, 293, 157, 84, 393)$, then the answer is the last value ${393 \over 1024}$.

Answer 3

Here's an alternative solution that uses the principle of inclusion-exclusion. For $i\in\{1,\dots,7\}$, let property $P_i$ be that flips $i,i+1,i+2,i+3$ are THHT. By inclusion-exclusion, the probability that a 10-flip sequence has at least one property is \begin{align} &\sum_{i=1}^7 \mathbb{P}[P_i] - \left( \sum_{(i,j)\in\{(1,5),(1,6),(1,7),(2,6),(2,7),(3,7)\}} \mathbb{P}[P_i \land P_j] + \sum_{(i,j)\in\{(1,4),(2,5),(3,6),(4,7)\}} \mathbb{P}[P_i \land P_j] \right) +\sum_{(i,j,k)\in\{(1,4,7)\}} \mathbb{P}[P_i \land P_j \land P_k] \\ &=\sum_{i=1}^7 2^{-4} - \left( \sum_{(i,j)\in\{(1,5),(1,6),(1,7),(2,6),(2,7),(3,7)\}} 2^{-4} 2^{-4} + \sum_{(i,j)\in\{(1,4),(2,5),(3,6),(4,7)\}} 2^{-7} \right) +\sum_{(i,j,k)\in\{(1,4,7)\}} 2^{-10} \\ &= \frac{7}{16} - \left( \frac{6}{256} + \frac{4}{128} \right) +\frac{1}{1024}\\ &=\frac{393}{1024} \end{align}