Whether the followings are Markov Chain

Question

Suppose that $\{X_n\}$ are i.i.d. random variables with $\mathbb{P}(X_n=0)=\mathbb{P}(X_n=1)=1/2$. Let $Y_n=X_n+X_{n-1}$ and $Z_n=2X_n+X_{n-1}$. Why $\{Z_n\}$ is Markov chain but $\{Y_n\}$ is not?

Answer 1

I will assume that $X_0 = 0$.

Why $Y_n$ is not Markov: Suppose $X_1 = 1, X_2 = 0$. Note that $Y_2 = 1$. Since $Y_3 = 0 + X_3$, we see that $Y_3$ will be $0$ or $1$ with equal probability. Now, suppose on the other hand that $X_1 = 0, X_2 = 1$. Again, $Y_2 = 1$ -- but this time, $Y_3 = 1 + X_3$, so it is either $1$ or $2$ with equal probability.

In short: $Y_n$ is not Markov because $\mathbb P(Y_3 = 2 \mid Y_2 = 1, Y_1 = 1) = 0$ but $\mathbb P(Y_3 = 2 \mid Y_2 = 1, Y_1 = 0) = 1/2$.

Why $Z_n$ is Markov: knowing the value of $Z_n$ completely determines both $X_n$ and $X_{n-1}$. (The four possible values of $Z_n$ are $0, 1, 2, 3$.) Thus, if you know $Z_n$, you can completely determine the distribution of $Z_{n+1}$ without ever explicitly needing to know $Z_{n-1}$. For instance: if $Z_2 = 2$, this requires that $X_1 = 0$ and $X_2 = 1$. Thus, $Z_3$ will be $2 X_3 + 1$, which has a well-defined probability distribution and does not require us to know the explicit value of $Z_1$. That's the essential distinction from the $Y_n$ process.