Toss a coin repeatedly and independently. Show that heads eventually appears. Show that any fixed finite sequence such as HTHHHT eventually appears?

Question

I'm not getting the answer for the second part where I have to prove about the fixed finite such as HTHHHT will eventually appears. Please help me with this part.

Answer 1

Do you know the Borel-Cantelli lemmas? In particular, the second one?

It says that if $E_1,\ldots,E_n$ are independent events, and $$ P(E_1)+P(E_2)+\cdots=\infty, $$ then with probability 1 infinitely many of the events $(E_n)_{n=1}^{\infty}$ occur.

What if $E_n$ is "elements $6n+1,\ldots,6n+6$ are HTHHHT"?

You could, of course, come up with a proof that doesn't use Borel-Cantelli. For any $n$, $P(E_n)=\frac{1}{2^6}$, and these events are independent. Using this, what's the probability that at least one event $E_1,\ldots,E_n$ occurs? What does this probability do as $n\to\infty$?

Answer 2

Let $X_n$ denote the event that the particular $6$-long pattern occurs starting at position $n$, so $P(X_n)=1/2^6$.

Let $Y_n$ be the event that none of the events $X_1,\ldots,X_n$ occur. It is tempting to claim that $P(Y_n)=(1-1/2^6)^n$, but this is false! $X_i$ and $X_j$ are dependent if $|i-j|<6$, since the two windows overlap.

However, if $|i-j|\ge6$ then $X_i$ and $X_j$ are independent, as they depend on distinct dice throws. So we have $$P(Y_n)\le P(\neg X_n) P(\neg X_{n-6}) P(\neg X_{n-12})\cdots = (1-1/2^6)^{\lfloor n/6\rfloor}\to 0$$ as $n\to \infty$. Thus the pattern will eventually appear "almost surely" (i.e. with probability one.)