The Ergodic Theorem and Bernoulli r.v. Let $X_1, X_2, X_3, X_4$ be i.i.d. Bernoulli (1/5) random variables. When $i\ge 5$, we produce $X_i$ based on $X_1,...,X_{i-1}$ as follows: If $X_{i-1}=X_{i-2}=X_{i-3}=X_{i-4}=0$, then we set $X_i=1$; and in all the other cases we set $X_i$ to be a Bernoulli (1/5) random variable, independent of $X_1,...,X_{i-1}$. Prove that $\frac{1}{n}\sum_{i=1}^{n}X_i$ converges almost surely when $n\to \infty$ and find the distribution of the limit random variable.
Trying something:
According to the Ergodic Theorem, we know that $X_n=\frac{1}{n}\sum_{i=1}^{n}X_i$ converges almost surely to μ. If $X_{i-1}=X_{i-2}=X_{i-3}=X_{i-4}=0$, then we set $X_i=1$. This corresponds to a Markov chain with memory (4th order) as following:
$$P(X_i=1\mid X_{i-1}=0,X_{i-2}=0,X_{i-3}=0,X_{i-4}=0)=?$$
This case applies if, for example $i=10$, then $\left[ X_1, X_2,X_3,X_4,X_5,0,0,0,0,1\right]$. Otherwise, the outputs should be like this: $\left[ X_1, X_2,X_3,X_4,X_5,X_6,X_7,X_8,X_9,X_{10}\right]$.
The transition matrix should be something like:
$$T=\left[
         \begin{array}{ccc}
         \dfrac{4}{5} & \dfrac{1}{5}   \\
         \dfrac{4}{5} & \dfrac{1}{5}   \\
        \end{array}
    \right]$$
However, it may be affected by the condition above. Any hint?
Thanks for your help!
 A: In this kind of puzzle usually the answer is easy to guess and proving it is hard, but in this instance it's the other way around.
Consider the 1st order Markov chain $M$ whose state space is all 16 bitstrings of length 4, with the transition rule that $0000$ transitions to $0001$ with probability $1$, and all other bitstrings $xyzw$ transition to $yzw0$ with probability $4/5$ and to $yzw1$ with probability $1/5$.  The stated behavior of the $X_n$ sequence is such that the 4-tuples $T_n=(X_n,X_{n+1},X_{n+2},X_{n+3})$  in fact are a realization of $M$. Equivalently, the $X_n$ sequence is an order 4 Markov chain, that is, a chain with memory 4.   It is easy to check that $M$ is aperiodic and transitive, hence ergodic, hence the fraction of times such that $T_n\in S$ converges almost surely to $\pi(S)$, where $\pi$ is the unique stationary distribution for $M$, for all subsets $S$ of 4-long bitstrings.  Your problem is solved by the particular $S$ consisting of eight bitstrings of form $xyz1$.
The job of finding $\pi$ is more intricate than I expected.  For bitstring $s$, it seems (and I don't have a succinct explanation why) that $\pi(s)$ depends only on the number of $1$s in $s$,
and that $\pi(0000)=256/2101$, $\pi(0001)=320/2101$, $\pi(0011)=80/2101$, $\pi(0111)=20/2101$, and $\pi(1111)=5/2101$.
Added, 26,27 Dec:  A 5 state Markov chain $Y_n$ can be used to give this result, at well.  Here $Y_n=\min\{i\ge0: X_{n-i}=1\}$ encodes the idea that  "at time $n$, the most recent $1$ was seen $Y_n$ turns ago, that is, at time $n-Y_n$".  Its transition matrix is
$$\pmatrix{1/5&4/5&0&0&0\\1/5&0&4/5&0&0\\1/5&0&0&4/5&0\\1/5&0&0&0&4/5\\1&0&0&0&0}$$
and its stationary distribution is easy to work out:
$$\pi=(\pi_0,\ldots,\pi_4)=\left(\frac{625}{2101},\frac{500}{2101},\frac{400}{2101},\frac{320}{2101},\frac{256}{2101}\right).$$  Your answer is the limiting fraction of time that $Y_n=0$, namely $\pi_0=625/2101=1/\sum_{i=0}^4(4/5)^i$. The expected return time to $Y_n=0$ is $1/\pi_0=2101/625$.
