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

Answer:

False. See te explanation an counter example below.

Step-by-step 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') =\frac{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}\neq 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') \neq 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.