1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$ Commented Feb 23, 2023 at 23:14
  • $\begingroup$ It counts as two occurrences. $\endgroup$ Commented Feb 23, 2023 at 23:21
  • $\begingroup$ 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 $\endgroup$ Commented Feb 23, 2023 at 23:51
  • $\begingroup$ Intuitively, this makes sense, since, as $~n~$ increases, the initial toss, which does not by itself afford an opportunity, becomes less and less important. $\endgroup$ Commented Feb 23, 2023 at 23:55

1 Answer 1

1
$\begingroup$

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}$.

$\endgroup$
2
  • $\begingroup$ Could you elaborate how can you use limit arithmetics on sequences of RVs? Also, in order to use SLLN, we need to divide by the number of elements in the sum, no? $\endgroup$ Commented Feb 24, 2023 at 5:14
  • $\begingroup$ 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$. $\endgroup$ Commented Feb 24, 2023 at 12:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .