Lesson 6

This conditional probability is equal to one! Indeed, if we got \(00\), then after this, some number of additional \(0\)s (possibly zero) will appear, after which finally a \(1\) will appear—and we will encounter \(001\).

Now we are ready to conduct a formal analysis. Let \(A\) denote the event “\(001\) appeared before \(011\)”. And let \(p=\Pr[A]\).

If the first flip is \(1\), we make no progress towards reaching \(001\) or \(011\), and we can simply ignore this flip. Thus, \[p=\Pr[A]=\Pr[A \mid 1].\] By the same reasoning, \[p=\Pr[A]=\Pr[A \mid 1]=\Pr[A \mid 11]=\Pr[A \mid 111]=\dotsb.\]

Now, we expand the probability of event \(A\) using the law of total probability: \[\Pr[A]=\frac{1}{2}\Pr[A \mid 0]+\frac{1}{2}\Pr[A \mid 1].\] Since \(\Pr[A]=\Pr[A \mid 1]\), we conclude that \(\Pr[A \mid 0]=p\). Intuitively, this makes sense: the “game” begins when the first \(0\) appears, and the entire prefix of \(1\)s can simply be skipped.

Now, let's expand \(\Pr[A \mid 0]\): \[p=\Pr[A \mid 0]=\frac{1}{2}\Pr[A \mid 00]+\frac{1}{2}\Pr[A \mid 01].\] As we discussed earlier, \(\Pr[A \mid 00]=1\): after obtaining \(00\), the combination \(001\) is guaranteed to win. Finally, let's expand \(\Pr[A \mid 01]\): \[\Pr[A \mid 01]=\frac{1}{2}\Pr[A \mid 010]+\frac{1}{2}\Pr[A \mid 011].\] It is easy to see that \(\Pr[A \mid 010]=\Pr[A \mid 0]\): the initial \(01\) does not help either of our two combinations. Meanwhile, \(\Pr[A \mid 011]=0\). Thus, \[\begin{align*}p=\Pr[A \mid 0]&=\frac{1}{2}\Pr[A \mid 00]+\frac{1}{2}\Pr[A \mid 01]=\\&=\frac{1}{2}+\frac{1}{2}\left(\frac{1}{2}\Pr[A \mid 010]+\frac{1}{2}\Pr[A \mid 011]\right)\\&=\frac{1}{2}+\frac{p}{4}.\end{align*}\] Thus, \(p=\frac{2}{3}\).