# Expected number of tosses until 3 heads in a row - via Martingale method

(Quant job interviews - questions and answers - Question 3.8)

For a fair coin, what is the expected number of tosses to get 3 heads in a row

The answer is stated as :

We gamble in such a way that we make money on heads but such that if we get a T on toss $n$, our position is $-n$. We therefore gamble one unit on the first toss and on each toss after a $T$. After one head, we gamble three. This guarantees that if we get a $T$ next then we go to $-n$. After two heads we are therefore up 4, and so we gamble 7 to get us to $-n$ again. our gambling winnings is a martingale since we are making finite trades in a martingale (any bounded trading strategy in a martingale is a martingale). After three heads our position is $11 - (n-3)=14-n$. the time taken to get three heads is a stopping time with finite expectation so if we stop at it we still have a martingale (Optional sampling theorem) thus $\mathbb E (14 -n) = 0$ and we are done.

I realise there are a few answers to this already, however i am not sure the explanation above, which uses martingale theory, is entirely clear.

The author states that any bounded trading strategy in a martingale is a martingale but what is the underlying martingale here ?

Also I don't understand the underlying motivation for gambling the way described, please could someone put it in more mathematical terms so i can understand the reason for the sizes of the bets ?

• Is it clear to you that the betting strategy achieves what the author claims? That is, that if our gambler throws a T on the $n^{th}$ turn (prior to a win) that the net position is $-n$?
– lulu
Nov 13 '15 at 1:28
• Sorry no it is not :( Nov 13 '15 at 1:29
• Ok. Write out several cases (avoiding the string $HHH$). Confirm that it works. Then proceed by induction. The strategy really is the whole point. The bets are specifically structured to ensure that payout.
– lulu
Nov 13 '15 at 1:30
• The logic of the proof is: "we've given the rules for a betting strategy. From general theory, it is not possible that these rules (nor any other set of rules) has anything other that a $0$ expectation. The beauty of this strategy is that we can actually computed the payout after the expected number of turns.
– lulu
Nov 13 '15 at 1:33
• This is a really neat way to solve this problem. Consider a smaller scenario - expected time to get one $H$. Bet on $H$ so that if you get $T$ on your $nth$ throw, your position is $-n$. Stop if you get an $H$. In other words, always bet one. If you get an $H$ on the $nth$ throw, your position will be $1-(n-1)=2-n$ and hence $E(n)=2$.
– A.S.
Nov 13 '15 at 3:52

I believe that the strategy is that:

consider the payoff of the $i_{th}$ toss

(1) If $i == 1$ or $X_{i-1} = Tail$ , you bet 1 unit on Head. Which means that $Payoff_i(X_i=Tail) = -1$ $Payoff_i(X_i=Head) = 1$;

(2) If $X_{i-1} = Head$ , you bet 3 unit on Head. Which means that $Payoff_i(X_i=Tail) = -3$ $Payoff_i(X_i=Head) = 3$;

(3) If $X_{i-2} = Head$ and $X_{i-1} = Head$ , you bet 7 unit on Head. Which means that $Payoff_i(X_i=Tail) = -7$ $Payoff_i(X_i=Head) = 7$;

(4) stop tossing when you get HHH serial.

(1) If you get a Tail at $i_{th}$ toss, your total payoff is $-n$(you could test this conclusion for arbitrage simple series);

(2)For every toss, your expected payoff is zero. Your total payoff is a martingale.

$$\text{ **any bounded trading strategy in a martingale is a martingale** }$$ I think that the first "martingale" in this quote is the total payoff $M_t = \sum_{s=0}^tpayoff_s$. The trading strategy descripted above is also a maringale.

When this strategy stop, denote $n$ as the strategy stopping time. The expected payoff should be zero.which is

$E[-(n-4)+1+3+7]=14-E[n]=0$. $E[n]=14$.

• why have the values 3 and 7 been chosen here? Sep 22 '19 at 10:11

To be honest, I didn't really enjoy the explanations of the author... I understand that he wants to motivate the use of martingale but it over complicates a simple problem.

Let $E$ be the expected #of tosses to achieve 3 heads, if we throw for example $HT$ then we have to start again counting, so in the particular case $E$ will be augmented by 2; enumerates all cases (HHH, HHT, HT, T) and weight by their probability $$E=\frac{1}{8}3+\frac{1}{8}(3+E)+\frac{1}{4}(2+E)+\frac{1}{2}(1+E)$$ Solve for E.

I understand there is no martingale argument in that reasoning, but I also see little value in forcing concepts where there aren't needed.

I believe the author is using a great deal of words to define the wealth process : $$M_n = M_0 + \sum_{1}^{3} 2^{i}X_{i}\text{ with }M_0=1\text{ and } X_i \text{ iid as }\{1,-1\}\text{ with p=}\frac{1}{2}$$

$\mathbb E(M_n|M_{n-1}) = \mathbb E(M_{n-1}+2^nX_n|M_{n-1})=M_{n-1}+2^n\mathbb E(X_{n-1})=M_{n-1}$ so $M_n$ is a martingale

then for the stopping time $\tau = \tau_{HHH}+1$ since we want the number of throws rather than the number of $M_i$s

$$\mathbb E (M_{\tau}) = 1 + 2^1 + 2^2 + 2^3 = \mathbb E(M_0)\mathbb E(\tau)=\mathbb E_{\tau}=1+E(\tau_{HHH})\text{ so } \mathbb E(\tau_{HHH})=14$$

• This doesn't seem like the process the author defined. What are the bounds of summation in definition of $M_n$? How is $E(M_\tau)=E(M_0)E(\tau)$?
– A.S.
Nov 15 '15 at 9:13
• you are right the Wald identity does not apply. I will amend or delete if I cannot find anything elegant. I would like to avoid this 'team of gamblers' method one usually sees in this context. Nov 15 '15 at 12:56
• He starts with $M_0=0$, sets $M_n=M_{n-1}+X_n(n+M_{n-1})$ - a martingale.
– A.S.
Nov 15 '15 at 22:07