Tossing a coin with at least $k$ consecutive heads

The $A_k$ are independent because for any $i \neq j$, the sets of tosses $2^i, \ldots, 2^{i+1}-1$ and $2^j, \ldots, 2^{j+1}-1$ are disjoint. Hence, $A_i$ tells you no information about $A_j$.

Let's find upper and lower bounds for $P(A_k)$.

Amongst the tosses numbered $2^k, \ldots, 2^{k+1}-1$, there are $2^k$ tosses, and so, there are $2^k-k+1$ blocks of $k$ consecutive tosses. For each block of $k$ consecutive tosses, the probability of all $k$ tosses being all heads is $p^k$. Hence, the expected number of blocks of $k$ consecutive tosses is $(2^k-k+1)p^k$. Therefore, $P(A_k) \le (2^k-k+1)p^k$.

Amongst the tosses numbered $2^k, \ldots, 2^{k+1}-1$, there are $2^k$ tosses, and so, there are $\left\lfloor\tfrac{2^k}{k}\right\rfloor$ disjoint blocks of $k$ consecutive tosses. For each disjoint block of $k$ consecutive tosses, the probability of all $k$ tosses being all heads is $p^k$. Hence, the probability of any one of these blocks of $k$ tosses being all heads is $1-(1-p^k)^{\left\lfloor\tfrac{2^k}{k}\right\rfloor}$. Therefore, $P(A_k) \ge 1-(1-p^k)^{\left\lfloor\tfrac{2^k}{k}\right\rfloor}$.

• If $p < \dfrac{1}{2}$, then $P(A_k) \le (2^k-k+1)p^k < (2p)^k$, and so, $\displaystyle\sum_{k = 1}^{\infty}P(A_k) \le \sum_{k = 1}^{\infty}(2p)^k = \dfrac{2p}{1-2p} < \infty$.

  Therefore, $P(A_k \ i.o.) = 0$.

• If $p > \dfrac{1}{2}$, then $\ln(1-P(A_k)) \le \left\lfloor\tfrac{2^k}{k}\right\rfloor\ln(1-p^k) \le -\dfrac{2^k}{k}p^k = -\dfrac{(2p)^k}{k} \to -\infty$ as $k \to \infty$.

  So, $1-P(A_k) \to 0$ i.e., $P(A_k) \to 1$ as $k \to \infty$. Hence, $\displaystyle\sum_{k = 1}^{\infty}P(A_k) = \infty$.

  Therefore, $P(A_k \ i.o.) = 1$.

• If $p = \dfrac{1}{2}$, then $\ln(1-P(A_k)) \le -\dfrac{1}{k}$, and so, $P(A_k) \ge 1-e^{-\tfrac{1}{k}} \sim \dfrac{1}{k}$.

  Hence, $\displaystyle\sum_{k = 1}^{\infty}P(A_k) = \infty$ by limit comparison with $\displaystyle\sum_{k = 1}^{\infty}\dfrac{1}{k}$.

  Therefore, $P(A_k \ i.o.) = 1$.