$(S_0+\ldots + S_n)_{n\geq 0}$ not a Markov chain

Question

Assume that $Y_0,\ldots , Y_n$ are independent random variables with the following identical distribution: $Y_i=1$ with propability $p$ and $Y_i=0$ with propability $1-p$. Also set $S_0=0$ and $S_n=Y_0+\ldots + Y_n$.

It's quite trivial that $(Y_n)_{n\geq 0}$ is a Markov chain, and I managed to show that $(X_n)=(S_n)_{n\geq 0}$ is also a Markov chain, by showing that

$\mathbb{P}(X_{n+1}=i_{n+1}\,|\,X_0=i_0,\ldots,X_n=i_n)=\mathbb{P}(X_{n+1}-X_n=i_{n+1}-X_n\,|\,X_0=i_0,\ldots,X_n=i_n)=\mathbb{P}(Y_{n+1}=i_{n+1}-X_n\,|\,X_0=i_0,\ldots,X_n=i_n)=\mathbb{P}(Y_{n+1}=i_{n+1}-i_n)=\mathbb{P}(Y_{n+1}+i_n=i_{n+1})=\mathbb{P}(X_{n+1}=i_{n+1}\,|\,X_n=i_n)$

However I am now running into the problem that I have to find whether or not $(X_n)=(S_0+\ldots + S_n)_{n\geq 0}$ is a Markov chain. I suspect that it isn't, but i'm having trouble finding a counterexample. I also need to find if $(X_n)=(S_n, S_0+\ldots+S_n)$ is a Markov chain, but I think this actually might be one, since $X_n$ gives "more information" (so to speak) to $X_(n+1)$. Again, having trouble actually proving that.

I appreciate any help, tips etc you can give me.

Answer 1

For the counterexample, consider $$P(X_5 = 4 | X_4 = 3, X_3 = 2, X_2 = 1, X_1 = 0, X_0 = 0)$$ and $$P(X_5 = 4 | X_4 = 3, X_3 = 1, X_2 = 0, X_1 = 0, X_0 = 0).$$ How do these two probabilities differ based on different $X_3, X_2, X_1$? (Unravel the definitions and figure out what each $Y_i$ has to be.) Hopefully by doing this, you'll have some more intuition for the latter problem. Hope this is helpful!

Answer 2

Let $X_n =(S_0+\ldots + S_n)$. Then, $\{X_n\}_{n\geq 0}$ is not a Markov chain because the distribution of $X_{n+1}$ given $X_n$ is not known. However, $X_{n+1}|X_n, X_{n-1} \overset{D}{=} X_{n} + X_{n} - X_{n-1} + Y_{n+1}$. Thus, the chain $\{Z_n\}_{n\geq 1}$, where $Z_n = (X_n, X_{n-1})$, is a Markov chain.