Is X(n) a Markov Sequence Given Its Dependency on Previous Coin Tosses?

[alidemedi]

Hi, this was a midterm problem in a probability class.

Homework Statement

A fair coin is tossed repeatedly with results Y(0), Y(1)... that are 1 or 0 for heads or tails. For n>0, define a new sequence X(n) = Y(n)+Y(n-1), i.e. the number of 1's in the last two tosses.
Is Xn a markov sequence?

Homework Equations

The Attempt at a Solution

I thought, when X(n) = 1, we cannot determine P( X(n+1) | X(n) ), due to the fact that the values X(n+1) can take depends on whether the last two flips were 0 and 1 or 1 and 0. In the former case we can have X(n+1)= 0 or 1, whereas in the latter we can have X(n+1)=1 or 2. The probabilities of all these are 1/2, but the values are different. So i said X(n) is not markov.

In the posted solutions, X(n) is given as markov. Probabilities in the above case are calculated as

P(X(n+1)=0 | X(n) = 1) = P(X(n+1) =0 | Y(n)=0, Y(n-1)=1)*P(Y(n)=0, Y(n-1)=1) + P(X(n+1) =0 | Y(n)=1, Y(n-1)=0)*P(Y(n)=1, Y(n-1)=0)
= 1/2*1/2 + 0*1/2 = 1/4.

Similarly, P(1|1) is found to be 1/2 and P(2|1) is 1/4.

What is confusing is that, I thought, when X(n) is given, there must be a certain realization for Y(n) and Y(n-1), so we couldn't do the above...

 

[Ray Vickson]

Hi, this was a midterm problem in a probability class.

Homework Statement

A fair coin is tossed repeatedly with results Y(0), Y(1)... that are 1 or 0 for heads or tails. For n>0, define a new sequence X(n) = Y(n)+Y(n-1), i.e. the number of 1's in the last two tosses.
Is Xn a markov sequence?

Homework Equations

The Attempt at a Solution

I thought, when X(n) = 1, we cannot determine P( X(n+1) | X(n) ), due to the fact that the values X(n+1) can take depends on whether the last two flips were 0 and 1 or 1 and 0. In the former case we can have X(n+1)= 0 or 1, whereas in the latter we can have X(n+1)=1 or 2. The probabilities of all these are 1/2, but the values are different. So i said X(n) is not markov.

In the posted solutions, X(n) is given as markov. Probabilities in the above case are calculated as

P(X(n+1)=0 | X(n) = 1) = P(X(n+1) =0 | Y(n)=0, Y(n-1)=1)*P(Y(n)=0, Y(n-1)=1) + P(X(n+1) =0 | Y(n)=1, Y(n-1)=0)*P(Y(n)=1, Y(n-1)=0)
= 1/2*1/2 + 0*1/2 = 1/4.

Similarly, P(1|1) is found to be 1/2 and P(2|1) is 1/4.

What is confusing is that, I thought, when X(n) is given, there must be a certain realization for Y(n) and Y(n-1), so we couldn't do the above...

I am not convinced by the above posted solution. We need to worry about whether
P{X(n+1) = j | X(n) = i, X(n-1) = i1} = P{X(n+1) = j|X(n) = i}; that is, we need to know that giving X(n-1) or earlier X(t) will not affect the probability of X(n+1).

RGV

 

[alidemedi]

I am not convinced by the above posted solution. We need to worry about whether
P{X(n+1) = j | X(n) = i, X(n-1) = i1} = P{X(n+1) = j|X(n) = i}; that is, we need to know that giving X(n-1) or earlier X(t) will not affect the probability of X(n+1).

RGV

Oh that is right! For example, P{X(n+1) = 0 | X(n) = 1, X(n-1) = 0} = 0, which would not be equal to P{X(n+1) = 0 | X(n) = 1} = 1/4 given above!

So, was her solution incorrect then? It seems so.