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

  • $\begingroup$ 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$? $\endgroup$
    – lulu
    Nov 13 '15 at 1:28
  • $\begingroup$ Sorry no it is not :( $\endgroup$ Nov 13 '15 at 1:29
  • $\begingroup$ 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. $\endgroup$
    – lulu
    Nov 13 '15 at 1:30
  • $\begingroup$ 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. $\endgroup$
    – lulu
    Nov 13 '15 at 1:33
  • $\begingroup$ 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$. $\endgroup$
    – 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.

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

  • $\begingroup$ why have the values 3 and 7 been chosen here? $\endgroup$
    – Trajan
    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$$

  • $\begingroup$ 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)$? $\endgroup$
    – A.S.
    Nov 15 '15 at 9:13
  • $\begingroup$ 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. $\endgroup$ Nov 15 '15 at 12:56
  • $\begingroup$ He starts with $M_0=0$, sets $M_n=M_{n-1}+X_n(n+M_{n-1})$ - a martingale. $\endgroup$
    – A.S.
    Nov 15 '15 at 22:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.