Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Is X(n) a markov sequence?

  1. Nov 10, 2012 #1
    Hi, this was a midterm problem in a probability class.

    1. The problem statement, all variables and given/known data
    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?

    2. Relevant equations

    3. 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...
  2. jcsd
  3. Nov 10, 2012 #2

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    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).

  4. Nov 10, 2012 #3
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook