Problem
A biased coin that lands heads with probability 3/8 is repeatedly flipped. Compute the expected number of of flips until the first HH string appears.
Solution
This is a classic interview questions whose variants come up frequently.
The key to the problem is to setup a Markov Chain with the right state space. Once you do this - it'll be easy to compute the desired probability. We'll see how this generalizes to other questions at the end.
If you're new to Markov Chains - read up here and come back, or book a session now and we're happy to teach them to you !
To set-up the state space, think about the event you're after: obtaining a HH. There are 3 possibilities:
S: No heads have been flipped yet, or the last one was a T
H: Exactly one head has been flipped (the last flip was a H)
HH: Two heads have been flipped in a row
We can setup a diagram to illustrate the state-space and the probabilities as follows:
Computation of the Expected Absorption Time
To compute the expected hitting time, note there's two transient states (S and H) and one absorbing state (HH). That means we should expect two equations with two unknowns (E[HH]=0).
Taking expected values E[S] and E[H] and conditioning on the terminal state, we get:
E[S] = 1 + 3/8 E[H] + 5/8 E[S]
E[H] = 1 + 3/8 E[HH] + 5/8 E[S]
E[HH] = 0 (we've already reached our goal)
Solving for E[S] we get, E[S]=88/9.
Notice if we set p=3/8, we obtain a general formula,
Lost? Book a session now and master stochastic processes !
Expected time to HHH
Same idea here: setup the Markov Chain with the below diagram:
This time you'll have 3 equations and 3 unknowns:
E[S] = 1 + 3/8 E[H] + 5/8 E[S]
E[H] = 1 + 3/8 E[HH] + 5/8 E[S]
E[HH]= 1 + 3/8 E[HHH] + 5/8 E[S]
E[HHH]=0
Solving for E[S], you'll get E[S] = 776/27.
Expected time to THH
Same idea: setup the Markov Chain:
You'll again have 3 equations and 3 unknowns:
E[S] = 1 + 3/8 E[S] + 5/8 E[T]
E[T] = 1 + 3/8 E[TH] + 5/8 E[T]
E[TH]= 1 + 3/8 E[THH] + 5/8 E[T]
E[THH]=0
Solving for E[S], you'll get E[S] = 11.38.
Probability of THH before HHH
This one is a bit more subtle. We're going to combine the previous two Markov Chains to introduce 2 absorbing states: THH and HHH, below.
Now we have to compute the probability starting from S we get absorbed to THH.
We do this by setting by defining the probability of starting at i and being absorbed at THH, a_i. Doing so, we get,
and,
This is a 5 x 5 linear system:
a_S = 5/8 a_T + 3/8 a_H
a_T = 5/8 a_T + 3/8 a_{TH}
a_H = 5/8 a_T + 3/8 a_{HH}
a_{TH} = 3/8 a_{THH} + 5/8 a_T
a_{HH} = 5/8 a_T + 3/8 a_{HHH}
a_{HHH}=0
a_{THH}=1
Solving for a_S yields a_S = 485/512.
Book your first session now to master Markov Chains and ace Quant Finance Interviews !
Want more?
Learn how Roth IRAs and Mega Backdoor Roth IRAs could generate millions tax-free in your post-tax retirement strategies !
Estimate how much you could have in retirement using Pre-Tax Strategies that could reduce your taxes now and nab you millions at retirement.
Subscribe to our Substack page to read and keep up-to-date on upcoming strategies.
コメント