An army of gamblers and a martingale

coin toss
Start flipping a coin. How long should you wait (on average) before observing the pattern {HHTHHTT} !? Easy you might say, that’s simply the hitting time of the state {H} starting from state {A} of the following Markov chain.

Indeed, one can solve this kind of problem using a first step analysis. In other words, if {a} is the expected number of steps before reaching {H} starting from {A}, {b} is the expected number of steps before reaching {H} starting from {B}, {c} is the expected number of steps before reaching {H} starting from {C}, etc… one can readily see that {a,b, \ldots, h} verify the system of equations

\displaystyle \begin{array}{rcl} a &=& 1 + \frac12(a+b), \quad b = 1 + \frac12(a+c), \quad c = 1 + \frac12(c+d) \\ d &=& 1 + \frac12(a+e), \quad e = 1 + \frac12(a+f), \quad f = 1 + \frac12(c+g) \\ g &=& 1 + \frac12(e+h), \quad h = 0. \end{array}

After a finite amount of time and coffee one then come up with the answer {a=128}. That was a little bit tedious and I don’t really want to know how long one should wait on average before observing the sequence {HHTHTTTHTHHHHTTHTHTTH}.

It turns out that there is a very neat way to approach this kind of problems without solving any linear system. Apparently, this trick was discovered in the 80s by Shuo-Yen Robert Li. As often in probability, this boils down to introducing a clever martingale. Suppose that one wants to know how long it takes on average before observing the magic coin pattern {x_1x_2 \ldots x_n} of length {n \geq 1} with {x_i \in \{H,T\}} for all {1 \leq i \leq n}. To this end, one will introduce an army of gamblers, a casino, a game of chance and a martingale. The martingale {M} describes the amount of money earned by the casino. At each round (starting at round {t=1}) the casino tosses a coin and the gamblers can make bets. If a gambler starts betting just before round {k}, he wins if the coin shows {x_1}. If he decides to bet again at round {k+1}, he wins if the coin shows {x_2}, etc… Suppose that there are infinitely many gamblers {G_0, G_1, G_2, \ldots} and that gambler {G_k} starts betting just before round {k+1}. The game is fair in the sense that if a gambler bets an amount {A}, with probability {1/2} he gets {2A} and with probability {1/2} he losses his bet. One supposes that gambler {G_k} starts betting {1} dollar just before round {k+1} and keeps reinvesting his total capital until he either losses everything (total loss equals {1} dollar) or observes the magic coin pattern {x_1x_2 \ldots x_n} (total earning equals {2^n-1}). Indeed, the amount of money earned by the casino is a martingale and {M_0=0}. For example, {M_1=1} if the first gambler {G_0} loses his bet and {M_1=-1} if the wins. Consider the time {\tau} when the magic coin pattern first appears. This is a stopping time and the optional stopping theorem for martingales shows that {\mathbb{E}[M_{\tau}] = 0}. Indeed, one can also compute this quantity another way. By time {\tau}, all the losers have given {1} dollar to the casino. Also, if the gambler {G_k} is still in the game he has won a total amount {2^{\tau-k}-1}. in other words,

\displaystyle M_{\tau} = \tau - \sum_{j=0}^{\tau-1} 2^{\tau-k} \, \delta_j

where {\delta_j=1} if the gambler {G_j} is still in the game after the round {\tau} and {\delta_j=0} otherwise. The fundamental remark is that the quantity {\sum_{j=1}^{\tau} 2^{\tau-k+1} \, \delta_j} is not random so that {\mathbb{E}[\tau] = \sum_{j=0}^{\tau-1} 2^{\tau-k} \, \delta_j}. Indeed, right after round {\tau} one can know with certainty whether {G_{k}} is still in the game or not. Gambler {G_{\tau-k}} is in the game only if the {k} last letters of the magic word {x_1x_2 \ldots x_n} are the same as the first {k} letters. For example, if the magic word is {HHTHHTH} then the gamblers who have seen the pattern {H},{HHTH} and {HHTHHTH} at time {\tau} are still in the game when the magic word first appear. In this case this shows that {\mathbb{E}[\tau] = 2^1+2^4+2^7}.

gambler

For example, this immediately shows that we have to wait on average {2^{21}+2^1} coin tosses before observing the pattern {HHTHTTTHTHHHHTTHTHTTH}.