Coin Series #3

Question

You are bored and you keep on tossing a fair coin. What is the probability that you have a sequence of HHH (heads heads heads) before THH (tails heads heads)?

Prove the outcome by using Markov chains. The solution without using a Markov Chain is easy to find (as already suggested in the discussion section of this problem). However, sometimes you can be asked to solve a problem using a particular method, or, it can simply be good to exercise a problem using different methods in order to polish your skills for each approach. For this question, try to solve it using Markov Chains.

Accepted Answer

The easy way to solve this problem is to realize that HHH can only occur if you throw HHH in the first three throws. As soon as you throw a tails, it's over. So, there is a $(\frac{1}{2})^3 = \frac{1}{8}$ probability that this happens in the first three throws.

If you want to challenge yourself and solve it through a Markov chain approach, have a look at the following explanation.

The transition graph for this problem is given in Figure 1.

[caption id="attachment_96479" align="aligncenter" width="656"] Figure 1 - Transition graph for this problem.[/caption]

$s_s$ is the starting state and $s_{HHH}$ is the absorption state. Take a look at Figure 1. We can conclude that $s_{THH} = 0$, $s_{TH} = 0$, $s_{T} = 0$  and $s_{HHH} = 1$. $s_{HHH} = 1$ because it is the absorption state, but $s_{THH} = 0$, $s_{TH} = 0$ and $s_{T} = 0$ because it is not possible to reach the absorption state once these individual states are reached. We are looking for the expected number of tosses to get the sequence THH. Applying the equations that are elaborated on in the lesson about Markov Chain Probability, we get the following set of equations: \begin{equation}
s_s = \frac{1}{2} s_T + \frac{1}{2} s_H
\end{equation} \begin{equation}
s_T = \frac{1}{2} s_T + \frac{1}{2} s_{TH}
\end{equation} \begin{equation}
s_{TH} = \frac{1}{2} s_T + \frac{1}{2} s_{THH}
\end{equation} \begin{equation}
s_H = \frac{1}{2} s_T + \frac{1}{2} s_{HH}
\end{equation} \begin{equation}
s_{HH} = \frac{1}{2} s_T + \frac{1}{2} s_{HHH}
\end{equation} Solving this set of equations gives us $s_s=\frac{1}{8}$. Therefore, the probability that we end up with the HHH pattern before the THH pattern is $s_s=\frac{1}{8}$.

Proof
Since we know that $s_{THH} = 0$, $s_{TH} = 0$, $s_{T} = 0$ and $s_{HHH} = 1$, we can simplify some of the equations. Equation 2 and Equation 3 simply become equal to zero. Next, we need to use $s_{HHH} = 1$ in Equation 5 as follows:  \begin{equation}
s_{HH} = \frac{1}{2} * 0 + \frac{1}{2} * 1 = \frac{1}{2}
\end{equation} Next, we substitute $s_{HH}$ in Equation 4. \begin{equation}
s_H = \frac{1}{2} * 0 + \frac{1}{2} *  \frac{1}{2} =  \frac{1}{4}
\end{equation} Finally, we have that \begin{equation}
s_s = \frac{1}{2} * 0 + \frac{1}{2} * \frac{1}{4} = \frac{1}{8}
\end{equation}

Title	Category	Subcategory	Difficulty	Status
Animal Migrations	Probability and Statistics	Markov Chain Probability	Easy	Unlock
Bankrupt	Probability and Statistics	Markov Chain Probability	Easy	Example
Bold Betting Strategy	Probability and Statistics	Markov Chain Probability	Medium	Unlock
Coin Series #1	Probability and Statistics	Markov Chain Probability	Easy	Unlock
Coin Series #2	Probability and Statistics	Markov Chain Probability	Medium	Unlock
Dominant Game	Probability and Statistics	Markov Chain Probability	Hard	Unlock
Jumping Toad	Probability and Statistics	Markov Chain Probability	Medium	Unlock
Parking Meter	Probability and Statistics	Markov Chain Probability	Easy	Unlock
Picking Tiles	Probability and Statistics	Markov Chain Probability	Easy	Unlock
Random Ant	Probability and Statistics	Markov Chain Probability	Medium	Example
Region Spinner	Probability and Statistics	Markov Chain Probability	Easy	Unlock
The Drunkard's Walk	Probability and Statistics	Markov Chain Probability	Hard	Unlock
Top 2000 Songs	Probability and Statistics	Markov Chain Probability	Medium	Unlock

The Interview Guide for Quants and Traders

Coin Series #3

Coin Series #3

Related Lectures

Trading Interview

Quick Links

What do you think of this page?

Coin Series #3

Related Lectures

Careers

What do you think of this page?