Back in November 2017, I had an interview with a prop trading firm and I was asked the following question: “What are the expected number of coin flips before you observe three heads in a row?”. I was asked the same question, 2 months later, this time on a homework problem for MATH 180B - Introduction to Stochastic Processes at UC San Diego. If only those events had occured in the opposite direction… Anyway, this blog post will be giving a brief introduction to discrete time markov chains using its applications in analyzing and modelling sequences of coin flips. Assumed knowledge: conditional probability and expectation. For reference, read: Conditional Expectation and Markov chains.

### Markov chains

By definition, a markov process is “a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event.” A markov process can be defined using a state space (the values that the random variable can take on in the process), an initial distribution and a stochastic matrix. Here’s a simple example of a markov process: Consider an ant starting at the origin, moves uniformly either one step to it’s left (to -1) or one step to it’s right (to +1), and once it gets to -1 or +1, it is forced to return to the origin. Then the state space is defined as $S = \{-1, 0, 1\}$, the initial state is $X_0 = 0$ and the probability matrix is:

$$\left[ \begin{array}{c|lcr} & \text{-1} & \text{0} & \text{1} \\ \hline -1 & 0 & 1 & 0 \\ 0 & 0.5 & 0 & 0.5 \\ 1 & 0 & 1 & 0 \end{array} \right]$$

where the states apear on the left and on top of the matrix, and an entry in the matrix represents the probability of going from State i (labeled on the row) to State j (labeled on the column) after one time period (one step on the line, in our case). As mentioned in the process, after reaching state 1 or state -1, the ant is forced to go to state 0, and as seen in the probability matrix, the probability of going from -1 to 0 and 1 to 0 after one step, is indeed 1. That is, $P(X_{t+1} = 0 | X_{t} = -1) = 1$. It is important to note that the values of $X_0, X_1, \ldots X_{t-1}$ do not effect the probability distribution of $X_{t+1}$ once $X_t$ is known. More formally, $P(X_{t+1} = j | X_t = i_t, X_{t-1} = i_{t-1}, \ldots, X_0 = i_0) = P(X_{t+1} = j | X_t = i_t)$ - known as the markov property.

### Expectation and absorbing states

Let’s alter the example from the previous paragraph, keeping everything the same, except that if the ant reaches the state $1$ it can never leave it. Now our probability matrix looks like:

$$\left[ \begin{array}{c|lcr} & \text{-1} & \text{0} & \text{1} \\ \hline -1 & 0 & 1 & 0 \\ 0 & 0.5 & 0 & 0.5 \\ 1 & 0 & 0 & 1 \end{array} \right]$$

It is easy to see that if the ant reaches state $1$ it can never exit it. This is called an absoring state. Very often, it is useful to find expected number of steps in the process until absorption using recurrence relations. For the following calculation(s), we will be using the lemma:

Lemma: Let $(X_n)$ be a time-homogeneous Markov chain with countable state space $S$, let $A ⊆ S$, and let $T = inf \{n ≥ 0 : X_n ∈ A\}$ be the first time that the Markov chain reaches a state in $A$. Then for each $i ∈ S \backslash A$, we have $E[T | X_0 = i] = 1 + \sum_{j ∈ S \backslash A} P(X_1 = j | X_0 = i) E[T | X_0 = j]$. Now, let’s calculate the number of expected steps that the ant will take until it gets absorbed. We define $T = min \{t >= 0 \vert X_t = 1\}$ and $\phi(i) = E[T \vert X_0 = i]$ then we have

$$\begin{cases} \phi(-1) = 1 + \phi(0) \\[2ex] \phi(0) = 1 + \frac{\phi(-1)}{2} + \frac{\phi(1)}{2} \\[2ex] \phi(1) = 0 \end{cases}$$

and solving this system of equations we get

$$\begin{cases} \phi(-1) = 4 \\[2ex] \phi(0) = 3 \\[2ex] \phi(1) = 0 \end{cases}$$

That is, if we start at state $i$ it will, on average, take $\phi(i)$ steps to get absorbed. Let’s see how we can apply this to sequences of coin flips.

### Three heads in a row

The trickiest part of finding the number of flips until $HHH$ is observed is defining the state space and stochastic matrix. Here’s the best approach: Let’s define $S = \{0, H, HH, HHH\}$ where $H$ represents only the last flip being a head, $HH$ represents the last two flips being heads, $HHH$ represents the last three flips being heads, which is also an absorbing state, and $0$ representing anything else. It is important to understand that these 4 states are disjoint. That is, if the last two flips were heads, the random variable will take on $HH$ and $HH$ only. Now our stochastic matrix looks like -

$$\left[ \begin{array}{c|lcr} & \text{0} & \text{H} & \text{HH} & \text{HHH} \\ \hline 0 & 0.5 & 0.5 & 0 & 0\\ H & 0.5 & 0 & 0.5 & 0 \\ HH & 0.5 & 0 & 0 & 0.5\\ HHH & 0 & 0 & 0 & 1 \end{array} \right]$$

and our system of equations for expectation (using similar calculations as in the previous paragraph is

$$\begin{cases} \phi(0) = 1 + \frac{\phi(0)}{2} + \frac{\phi(H)}{2} \\[2ex] \phi(H) = 1 + \frac{\phi(0)}{2} + \frac{\phi(HH)}{2} \\[2ex] \phi(HH) = 1 + \frac{\phi(0)}{2} + \frac{\phi(HHH)}{2} \\[2ex] \phi(HHH) = 0 \end{cases}$$

and solving this system of equations gives us our answer $\phi(0) = 14$ as required (since we start at state 0).

### A counter-intuitive comparison

We just looked at the number of expected flips until $HHH$ is observed. What about $HHT$? The transition probability matrix for $HHT$ looks like -

$$\left[ \begin{array}{c|lcr} & \text{0} & \text{H} & \text{HH} & \text{HHT} \\ \hline 0 & 0.5 & 0.5 & 0 & 0\\ H & 0.5 & 0 & 0.5 & 0 \\ HH & 0 & 0 & 0.5 & 0.5\\ HHT & 0 & 0 & 0 & 1 \end{array} \right]$$

Solving this system gives us $\phi(0) = 8$, which means that on average, it will take lesser (6, to be precise) coin flips to observe $HHT$ than $HHH$. The reason for this difference is that once the process reaches the state $HH$ it can never go back to $0$ or $H$, but only either stay at $HH$ or move into $HHT$ in the former case.

Summary
Markov chains are simple and beautiful.

References
 Professor David Meyer at the UC San Diego mathematics department.