Proving (or disproving) that a set of random variables is a Markov chain  A fair coin is tossed repeatedly with results $Y_0, Y_1, Y_2, ...$ that are 0 or 1 with probability $1/2$ each. For $n \geq 1$ let $X_n  = Y_n + Y_{n-1}$ be the number of 1's in the $(n-1)$th and $n$th tosses. Is $X_n$ a Markov chain? 
I've just gotten into Stochastic Processes and Markov chains and thus am a little unfamiliar - I know that, by definition, a Markov chain must be such that the probability of an event happening depends only on the previous state, and thus can be written in a probability matrix of the form $P(i, j)$.
Here, however, it doesn't seem that the probability of the event in state $n$ depends not only on state $n-1$, but also on state $n$ itself - does this mean that this is not a Markov chain? If it is, I'm not sure how the probability matrix would look.
 A: $X_n$ is not Markov. Consider for illustration $P(X_3=2 \mid X_2=1,X_1=0)$ vs. $P(X_3=2 \mid X_2=1,X_1=2)$. In the first case, you know from $X_1=0$ that $Y_1=0$. So since $X_2=1$, $Y_2=1$. So the desired probability is $P(Y_3=1)=1/2$. 
In the second case, you know from $X_1=2$ that $Y_1=1$. So since $X_2=1$, $Y_2=0$. Thus this probability is zero. 
Intuitively, the issue here is that the information "$X_{n-1}=1$" does not give you complete information about what $Y_{n-1}$ was, whereas additional information about older values of $X_n$ can do that. If instead you are given $X_{n-1}=0$ or $X_{n-1}=2$ then you get what $Y_{n-1}$ was, which is enough to pin everything down.
A: In a first order Markov chain, $X_{n-1}$ and $X_{n+1}$ are conditionally independent given $X_n$. That is, the function $p(x,y,z)=P((X_{n-1},X_n,X_{n+1}) = (x,y,z)$ factors into a product of form $A(y)B(x,y)C(y,z)$.  (This is equivalent to the condition stated in the Wikipedia article which implies a factorization of form $p(x,y,z)=a(x)b(x,y)c(y,z)$; these are the same on setting $A(y)B(x,y)=a(x)b(x,y)$.) But a tabulation of all 16 possible $(Y_{n-2},Y_{n-1},Y_n,Y_{n+1})$ values yields the following values for $p(x,1,z))$, namely:
$$(p(x,1,z)=\begin{pmatrix}0&1/8&1/8\\1/8&2/8&1/8\\1/8&1/8&0\end{pmatrix}.$$ The factorization property would say that $p(x,1,z)=A(1)B(x,1)C(1,z)$, which is to say the above matrix has rank 1. But it obviously has rank 2.  That is, conditional on $X_n=1$, the immediate past and future $X_{n-1}$ and $X_{n+1}$ are not independent.  The $X_n$ chain is not first order Markov.  
This is intuitively obvious: the sequences 010 and 212 cannot appear in the $X_n$ stream, even though all the 2-long subsequences 01, 10, 12, and 21 can.  A first order Markov chain is not smart enough to make this happen.
