Estimating the probability of having at least $\log_2 k$ highest streaks of heads before $k$ streaks of tail

Question

In a coin tossing game, a fair coin is tossed over and over until there are $k$ consecutive tails where the game ends. I want to show that the probability of having at least $\log_2k$ consecutive heads before the game ends is greater than $1-\frac{1}{e}$.

I'm not sure how should I think about this problem. I've tried considering a smaller problem where there are $N$ trials before $k$ consecutive tails and estimate the probability of having at least $\log_2k$ consecutive head within $N$ trials. We have

1. The streak starts at the first trial: $\leq2^{N-\lceil\log_2k\rceil}$ possible outcomes.
2. The streak starts at elsewhere: $\leq (N-\lceil\log_2k\rceil)\cdot 2^{N-\lceil\log_2k\rceil-1}$ outcomes.

The inequalities are there since it is also possible that $N-\lceil\log_2k\rceil>\lceil\log_2k\rceil$ in which we might count the case where the streak occurs later. But this further complicates the problem and it seems not the right approach to me. Not to mention that I also have to consider the possibility of having $N+k$ trials before the game ends. Can you give me some hints or suggestions?

Answer 1

I finally found a solution after seeing this:

If $k=1$ then $\log_2k=0$ and the possibility is $1>1-e^{-1}$.

For $k\geq 2$, notice that the game is nothing but a finite sequence of geometric random variables of the form of either $(H_1,T_1,\ldots,H_n,T_n)$ or $(T_1,H_1,\ldots,T_n,H_n,T_{n+1})$. Here, $H_i$ counts the total number of heads before the next tail, and $T_i$ counts the total number of tails before the next head or until the $k$ tails. Let $$ p_H:=P(H_i\geq\log_2k) = \left(\frac{1}{2}\right)^{\lceil\log_2k\rceil-1}, \quad q_T:=P(T_i<k) = 1-\left(\frac{1}{2}\right)^{k-1} $$ and $q_H:=P(H_i<\log_2k)=1-p_H$.

Let $\mathbb{H}$ and $\mathbb{T}$ denote the collection of events starting with $H$ and $T$ respectively, and $E$ denote the desired outcome. We have $$ P(E|\mathbb{H}) = p_H+(q_Hq_T)p_H+(q_Hq_T)^2p_H+\ldots = \frac{p_H}{1-q_Hq_T} $$ and $$ P(E|\mathbb{T}) = q_Tp_H + (q_Tq_H)q_Tp_H + (q_Tq_H)^2q_Tp_H + \ldots = \frac{q_Tp_H}{1-q_Hq_T}. $$

Therefore, $$ \begin{align*} P(E) &= P(E|\mathbb{H})P(\mathbb{H})+P{(E|\mathbb{T})}P(\mathbb{T}) \\ &= \frac{1}{2}\left(\frac{p_H}{1-q_Tq_H}\right)\left(1+q_T\right) \\ &=\frac{2^k-1}{2^{\lceil\log_2k\rceil}+2^k-2}\\ &\geq\frac{2^k-1}{2^k}\\ &=1-\frac{1}{2^k}>1-\frac{1}{e} \end{align*} $$ for all $k\geq 2$.