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!


1 Answer 1


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

  • $\begingroup$ Thank you! I think that the transition matrix should be $\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}$. Right? $\endgroup$
    – user866530
    Dec 26, 2020 at 20:37
  • $\begingroup$ You are correct, & thanks for spotting the mistake and pointing it out. I've fixed my answer. $\endgroup$ Dec 26, 2020 at 20:40
  • $\begingroup$ Did you use recursion to compute $\pi(s)$? $\endgroup$
    – user866530
    Dec 26, 2020 at 23:33
  • 1
    $\begingroup$ First I used Monte Carlo on the 16 state model. Then I used iteration to get $\pi$. Then I asked the computer to print out the ratios of components and noticed that they seemed to be rational multiples of each other. Then I solved for $\pi$ with pencil-and-paper algebra. Then I thought of the 5 state MC, and found its $\pi$ with pencil-and-paper algebra. $\endgroup$ Dec 26, 2020 at 23:56
  • $\begingroup$ Shouldn't be $E[Y]=\sum_{i=0}^4(4/5)^i$ $\endgroup$
    – user866530
    Dec 27, 2020 at 5:35

You must log in to answer this question.