Martingales & Coins: Waiting for Heads-Tails-Heads |

Consider the following simple problem: let $X_1,X_2,..$ be a sequence of independent fair coin tosses. How many times do we have to toss the coin in expectation in order to observe the sequence HTH (H stands for heads and T for tails)? We will answer this question here with three different ways. The first way is based on defining an automaton which reaches a “dead-end” when the pattern HTH has been observed, the second one is martingales “under cover” and the third one is based on the the optional stopping theorem and the beautiful theory of martingales.

Random Walk:Consider the graph above. There are 4 different states/nodes and we start our random walk from state 0. The transitions are equally likely. The graph is constructed in such way that the first time we observe the sequence HTH in the sequence of our tosses we end up at state 3. Let $X_i$ be the number of steps/transitions needed to reach state 3 when starting at state $i$ . Clearly by simple “first step” conditioning we obtain the following equations:

$E(X_0) = 1 + \frac{1}{2} (E(X_1)+E(X_0))$

$E(X_1) = 1 + \frac{1}{2} (E(X_2)+E(X_1))$

$E(X_2) = 1 + \frac{1}{2} (E(X_3)+E(X_0)) =1+ \frac{1}{2}E(X_0)$

Solving the system of equations we obtain that $E(X_0)=10$ which is the expected number of tosses we have to make in order to observe the sequence Heads Tails Heads. Now we will describe a beautiful argument based on martingales.

Martingales “under cover”: Now we will make few crucial observations which will allow us to to obtain the same answer in a different way. We will that the casino is tossing the coin. At every time point a gambler enters the game. Each gambler plays in the following way:

In his first play he plays 1$ for Heads. If he loses he stops playing. If he wins he continues.
In his second play he plays 2$ for Tails. if he loses he stops playing. If he wins he continues.
In his third and last play, he plays 4$ for Heads. No matter what happens, this play is his last play.

We will reserve the symbol $P$ and $T$ to denote the profit of the casino and the stopping time, i.e., the step at which the last(red) Heads of the HTH appears. Observe that when a player has won in all of his three bets, the stopping time has arrived! That means also that every other player who left the game before the stopping time, did not win all the three games. By the way we defined the betting system, we can make few more crucial observations.

Observation 1: The expected net profit of the casino is 0, i.e., E(P)=0

Clearly the casino will pay with probability 1/2 the amount that the player will bet if he wins, or it will take that amount from the player if the coin decided that he loses. Therefore by the fairness of the coin and the betting system, we obtain that if P is the random variable describing the net profit of the casino, $E(P)=0$ . In other words, the casino “runs” a fair game.

Observation 2: If a person loses and leaves before the game ends, the casino earns a net profit of $1 from that person.

Observation 3: E(P)+E(T)=10.

The reason is that the profit P is equal to T-2 that the casino won from all players but for two players, the one that entered in T-2 and T. To those the casino had to pay 8$. Therefore $P = T-2-8$ and by taking the expectation we see that the observation 3 holds. By our observations, we obtain that $E(T)=10$ .

Martingales and the Optional Stopping theorem: Before we give the solution based on the optional stopping theorem, we provide some background and links. Consider $M_t$ to be a martingale with respect to the sequence of toss coins $X_1,X_2,..$ which is a sequence of independent, identically distributed (as defined by the fairness of the coin) coin tosses and define $\tau_{HTH} = inf\{ t \geq 3: X_{t-2}X_{t-1}X_t=HTH\}$ . Consider now a previsible sequence of random variables $A_t$ with respect to the coin tosses. By previsible we mean that $A_t=f_t(X_1,X_2,X_{t-1})$ . Think simply of $A_t$ as the amount of money that you will bet, and what previsible means is that you decide how much you bet just by looking the past, i.e., up to t-1 when you make the $t$ -th bet. A natural question to ask is whether you can adjust your bets, i.e., the sequence $(A_t)$ such that the expected amount of money you will make is greater than zero. The following theorem whose proof is simple but we omit here says that this is impossible.

Theorem: Consider the sequence $P_t = M_0 + \sum_{k=1}^t A_k (M_k-M_{k-1})$ . $P_t$ is a martingale with respect to the coin tosses.

Now observe that for a stopping time $\tau$ and any fixed t $min \{ t,\tau \}$ is a stopping time. The optional stopping theorem (one of its versions) states the following:

Optional Stopping Theorem : $M_{min \{ t,\tau \}}$ is a martingale and therefore $E(M_{min \{ t,\tau \}})=E(M_0)$ .

Now bearing all this into mind, and by defining the same game (casino and a gambler entering at every round) we want to compute the expected value of $\tau_{HTH}$ . Applying the optional stopping theorem to the sequence of of the profit of the s-th gambler in the t-th game $N_t^s$ we obtain that $E(N_{\tau}^s)=0 \rightarrow 10 - E(\tau_{HTH})=0$ (10 because the player who entered in $\tau-2$ will be paid 8 dollars and player who enters at $\tau$ will get 2 dollars.