[math] \newcommand{\NA}{{\rm NA}} \newcommand{\mat}[1]{{\bf#1}} \newcommand{\exref}[1]{\ref{##1}} \newcommand{\secstoprocess}{\all} \newcommand{\NA}{{\rm NA}} \newcommand{\mathds}{\mathbb}[/math]

A coin is tossed repeatedly. We are interested in finding the expected number of tosses until a particular pattern, say B = HTH, occurs for the first time. If, for example, the outcomes of the tosses are HHTTHTH we say that the pattern B has occurred for the first time after 7 tosses. Let [math]T^B[/math] be the time to obtain pattern B for the first time. Li gives the following method for determining [math]E(T^B)[/math]. We are in a casino and, before each toss of the coin, a gambler enters, pays 1 dollar to play, and bets that the pattern B = HTH will occur on the next three tosses. If H occurs, he wins 2 dollars and bets this amount that the next outcome will be T. If he wins, he wins 4 dollars and bets this amount that H will come up next time. If he wins, he wins 8 dollars and the pattern has occurred. If at any time he loses, he leaves with no winnings. Let A and B be two patterns. Let AB be the amount the gamblers win who arrive while the pattern A occurs and bet that B will occur. For example, if A = HT and B = HTH then AB = 2 + 4 = 6 since the first gambler bet on H and won 2 dollars and then bet on T and won 4

dollars more. The second gambler bet on H and lost. If A = HH and B = HTH, then AB = 2 since the first gambler bet on H and won but then bet on T and lost and the second gambler bet on H and won. If A = B = HTH then AB = BB = 8 + 2 = 10.

Now for each gambler coming in, the casino takes in 1 dollar. Thus the casino takes in [math]T^B[/math] dollars. How much does it pay out? The only gamblers who go off with any money are those who arrive during the time the pattern B occurs and they win the amount BB. But since all the bets made are perfectly fair bets, it seems quite intuitive that the expected amount the casino takes in should equal the expected amount that it pays out. That is, [math]E(T^B)[/math] = BB.

Since we have seen that for B = HTH, BB = 10, the expected time to reach the pattern HTH for the first time is 10. If we had been trying to get the pattern B = HHH, then BB [math]= 8 + 4 + 2 = 14[/math] since all the last three gamblers are paid off in this case. Thus the expected time to get the pattern HHH is 14. To justify this argument, Li used a theorem from the theory of martingales (fair games).

We can obtain these expectations by considering a Markov chain whose states are the possible initial segments of the sequence HTH; these states are HTH, HT, H, and [math]\emptyset[/math], where [math]\emptyset[/math] is the empty set. Then, for this example, the transition matrix is

[[math]] \bordermatrix{ &\mbox{HTH} & \mbox{HT} & \mbox{H} & \emptyset \cr \mbox{HTH} & 1 & 0 & 0 & 0 \cr \mbox{HT} & .5 & 0 & 0 & .5 \cr \mbox{H} & 0 & .5 & .5 & 0 \cr \emptyset & 0 & 0 & .5 & .5 }\ , [[/math]]

and if B = HTH, [math]E(T^B)[/math] is the expected time to absorption for this chain started in state [math]\emptyset[/math].

Show, using the associated Markov chain, that the values [math]E(T^B)[/math] = 10 and [math]E(T^B)[/math] = 14 are correct for the expected time to reach the patterns HTH and HHH, respectively.

Notes