Prove Convergence in Probability of $\frac{x_n}{n}$ where $x_n$ = {# of times in Bernoulli RV that success is followed by failure} We have IID Bernoulli trials with $p=1/3$. Let $x_n = ${number of times in the first n trials that a success is followed by a failure}. Prove that $\frac{x_n}{n}$ converges in probability to $\frac{2}{9}$.
This is the first probability convergence problem I have come across and I am struggling with where to begin. My first that was to use the weak law of large numbers. But I am not sure how to apply it here because technically the sequence of interest is not Bernoulli.
Can you get me started?
 A: Here is an approach you can follow (there are still computations to do):
Expectations:
You can compute $E[\frac{X_n}{n}]$ very easily via the indicator function approach that you mentioned.
Since $0 \leq \frac{X_n}{n} \leq 1$ for all $n$, if $\frac{X_n}{n}$ converges to some constant $c$ with probability 1 (or even in the weaker sense "in probability") then $E[\frac{X_n}{n}]$ must also converge to $c$.  You can justify this, for example, by the Lebesgue dominated convergence theorem and/or the "bounded convergence theorem."
DTMC
If we define a Discrete Time Markov Chain (DTMC) with state space $\{SS, SF, FS, FF\}$, where the state represents the history of the past two trials, then $\lim_{n\rightarrow\infty} \frac{X_n}{n}$ is the same as the fraction of time we are in state $SF$. We know by steady state theory that this fraction of time converges to some steady state value $\pi(SF)$ with probability 1 (regardless of the initial state).
So you can either compute the steady state of this 4-state DTMC directly, or you can use the fact that steady state exists, and so $\frac{X_n}{n}\rightarrow c$ with probability 1 for some constant $c$, then compute $c$ by $c=\lim_{n\rightarrow\infty} E[\frac{X_n}{n}]$.
