# Convergence in probability and almost surely of number of occurences of yielding H twice in a row.

A fair coin is tossed independently and infinitely many times. Let $$Y_n$$ be the number of occurences of yielding H (heads) twice in a row during the first $$n$$ tosses.

1. Does $$\frac{Y_n}{n}$$ converge in probability?
2. Does $$\frac{Y_n}{n}$$ converge almost-surely?

I've managed to find the expected value and variance of $$Y_n$$ by constructing $$Y_i=X_iX_{i+1}$$ for all $$1 \le i \le n-1$$, with $$X_i$$ is $$Ber(\frac{1}{2})$$ (so $$Y_n = \sum^{n-1}_{i=1}Y_i)$$. I've come up with:

$$\mathbb E\left[Y_n\right] = \frac{n-1}{4}$$ $$Var(Y_n) = \frac{5n-7}{16}$$

But I'm at really not sure how to approach this. I think I'm supposed to use one of the known upper bounds (we've seen Markov's, Chebyshev's, Chernoff's and Hoeffding's inequalities) but I'm not sure how. Any help would be appreciated.

• If $n=3$, and you get the sequence HHH does this count as one occurrence of two consecutive Heads, or two occurrences of two consecutive Heads? Commented Feb 23, 2023 at 23:14
• It counts as two occurrences. Commented Feb 23, 2023 at 23:21
• Linearity of Expectation provides a shortcut to the expected number of occurrences, since each of the $(n-1)$ opportunities has a $(1/4)$ probability of occurring. See Linearity of Expectation, which includes a proof that the formula applies even when the events are not independent of each other. Also, as $n \to \infty,$ the fraction $\dfrac{n-1}{n} \to 1.$ Therefore, $\dfrac{Y_n}{n} \to \dfrac{1}{4}.$ ...see next comment Commented Feb 23, 2023 at 23:51
• Intuitively, this makes sense, since, as $~n~$ increases, the initial toss, which does not by itself afford an opportunity, becomes less and less important. Commented Feb 23, 2023 at 23:55

It would be tempting to use SLLN, but unfortunately, we cannot since the random variables $$X_i X_{i+1}$$ are not independent. However, with a small trick, we can make this approach work. Let $$U_i = X_{2i-1} X_{2i}$$ and $$V_i = X_{2i} X_{2i+1}$$ for $$i\in \mathbb{N}$$. Now notice that we can write $$Y_n = \sum_{i=1}^{\left\lceil (n-1)/2\right\rceil}U_i + \sum_{i=1}^{\lfloor (n-1)/2 \rfloor} V_i$$
Denote $$S_n = \sum_{i=1}^n U_i$$ and $$T_n = \sum_{i=1}^n V_i$$. From SLLN both $$\frac{S_n}{n} \to \frac{1}{4}$$ and $$\frac{T_n}{n} \to \frac{1}{4}$$ a.s. because the families $$\{U_n\}$$ and $$\{V_n\}$$ are i.i.d. Finally, write $$\frac{Y_n}{n} = \frac{\lceil (n-1)/2 \rceil}{n}\cdot \frac{S_{\lceil (n-1)/2 \rceil}}{\lceil (n-1)/2 \rceil} + \frac{\lfloor (n-1)/2 \rfloor}{n}\cdot \frac{T_{\lfloor (n-1)/2 \rfloor}}{\lfloor (n-1)/2 \rfloor}$$ and take the limit as $$n\to \infty$$ to get $$\lim_{n\to \infty} \frac{Y_n}{n}=\frac{1}{2}\cdot \frac{1}{4} + \frac{1}{2}\cdot \frac{1}{4} = \frac{1}{4} \;\; \text{a.s.}$$ Because almost sure convergence implies convergence in probability we also have $$\frac{Y_n}{n} \xrightarrow{p}\frac{1}{4}$$.
• We treat the limits that contain only $n$'s as usual limits and the limits that contain RVs as a.s. limits, getting an a.s. limit as a result. The SLLN asserts that $S_n/n$ converges almost surely but using basic limit properties we can replace $n$ by any subsequence $n_k \to \infty$. Commented Feb 24, 2023 at 12:12