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

Question

(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 ?

Answer 1

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.

Answer 2

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$$

Answer 3

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.

Conclusions about this strategy:

(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$.