exercise01.09.tex

\paragraph{Exercise 1.9} Suppose that a fair coin is flipped $n$ times. Let $i, k \in
\mathbb{N}^+, 1 \leq i \leq n - \left(\log_2(n) + k \right) + 1$ and let $E_i$ be the
event that there is a sequence of $\log_2(n) + k$ consecutive heads, starting with
the $i$th flip. \\
We are interested in an upper bound on $\pr\left(\bigcup_i E_i\right)$. Let's first
determine the probability $\pr(E_i)$ that a coin comes up heads $\log_2(n) + k$
times in succession. Since the coin is fair, one has
\[ \pr(E_i)
  = \left(\frac{1}{2}\right)^{\log_2(n) + k}
  = \frac{1}{2^{\log_2(n)}} \cdot \frac{1}{2^k}
  = \frac{1}{n} \cdot \frac{1}{2^k}
  = \frac{1}{2^k n}.
\]
Note that the events $E_1,...,E_{n - \left(\log_2(n) + k \right) + 1}$ are not
mutually disjoint. Therefore $\pr\left(\bigcup_i E_i\right) = \sum_i \pr(E_i)$
doesn't apply. However, since we are only interested in an upper bound on
$\pr\left(\bigcup_i E_i\right)$ we can apply the union bound (Lemma 1.2),
\[ \pr\left(\bigcup_i E_i\right) \leq \sum_i \pr(E_i). \]
Therefore
\[ \pr\left(\bigcup_i E_i\right)
  \leq \left(n - \left(\log_2(n) + k \right) + 1\right) \cdot \frac{1}{2^k n}
  = \frac{1}{2^k} - \frac{\log_2(n) + k - 1}{2^k n}
  \leq \frac{1}{2^k}.
\]
Hence $\frac{1}{2^k}$ is an upper bound on the probability that there is a
sequence of $\log_2(n) + k$ consecutive heads, with $k \in \mathbb{N}^+$.