Question

A fair coin is tossed repeatedly with results Y0, Y1, Y2, . . . that are 0 or 1 with probability 1/2 each. For n ≥ 1 let Xn = Yn + Yn−1 be the number of 1’s in the (n − 1)th and nth tosses. Is Xn a Markov chain?

Answer 1

False. See te explanation an counter example below.

Explanation:

For this case we need to find:

`P(X_(n+1) = | X_n =i, X_(n-1)=i') =P(X_(n+1)=j |X_n =i)` for all
`i,i',j` and for
`X_n` in the Markov Chain assumed. If we proof this then we have a Markov Chain

For example if we assume that
`j=2, i=1, i'=0` then we have this:

`P(X_(n+1) = | X_n =i, X_(n-1)=i') =(1)/(2)`

Because we can only have
`j=2, i=1, i'=0` if we have this:

`Y_(n+1)=1 , Y_n= 1, Y_(n-1)=0, Y_(n-2)=0`, from definition given
`X_n = Y_n + Y_(n-1)`

With
`i=1, i'=0` we have that
`Y_n =1 , Y_(n-1)=0, Y_(n-2)=0`

So based on these conditions
`Y_(n+1)` would be 1 with probability 1/2 from the definition.

If we find a counter example when the probability is not satisfied we can proof that we don't have a Markov Chain.

Let's assume that
`j=2, i=1, i'=2` for this case in order to satisfy the definition then
`Y_n =0, Y_(n-1)=1, Y_(n-2)=1`

But on this case that means
`X_(n+1)\\eq 2` and on this case the probability
`P(X_(n+1)=j| X_n =i, X_(n-1)=i')= 0`, so we have a counter example and we have that:

`P(X_(n+1) =j| X_n =i, X_(n-1)=i') \\eq P(X_(n+1) =j | X_n =i)` for all
`i,i', j` so then we can conclude that we don't have a Markov chain for this case.