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

Markov Process Proof

  1. Jan 19, 2012 #1

    I proved the following statement by induction. Does anyone see any oversights or glaring errors? It is for a class where the homework is assigned but not collected, and I just want to know if I did it right. Thanks

    Consider the stochastic process [itex]\{X_t,\,t=0,1,2,\ldots\}[/itex] described by,
    X_{t+1} = f_t(X_t,W_t),\,t=0,1,2,\ldots
    where [itex]f_0,f_1,f_2,\ldots[/itex] are given functions, [itex]X_0[/itex] is a random variable with given cumulative distribution function, and [itex]W_0,W_1,W_2,\ldots[/itex] are mutually independent rv's that are independent of [itex]X_0[/itex], and have given CDFs. Prove that [itex]\{X_t,\,t=0,1,2,\ldots\}[/itex] is a Markov process.

    We prove the result by induction. Consider the base case, with [itex]t=2[/itex],
    P(X_2 = x_2|X_1=x_1,X_0=x_0)
    & = & P(f_1(X_1,W_1)=x_2|f_0(X_0,W_0)=x_1,X_0=x_0)\\
    & = & P(f_1(X_1,W_1)=x_2|f_0(X_0,W_0)=x_1)\qquad\text{(since }X_0\text{ is independent of }W_1)
    Now, the induction hypothesis is, assume,
    P(X_n = x_n|X_{n-1}=x_{n-1},\ldots,X_0=x_0) = P(X_n = x_n|X_{n-1}=x_{n-1})
    We wish to prove the following (induction step),
    & & P(X_{n+1} = x_{n+1}|X_n=x_n,X_{n-1}=x_{n-1},\ldots X_0=x_0) \\
    & = & P(X_{n+1} = x_{n+1}|X_n=x_n)\\
    & = & P(f_n(X_n,W_n)=x_{n+1}|f_{n-1}(X_{n-1},W_{n-1})=x_n,f_{n-2}(X_{n-2},W_{n-2})=x_{n-1},\ldots,X_0=x_0)
    But from the induction hypothesis, we know that given the present, denoted [itex]X_{n-1}[/itex], the future, [itex]X_n[/itex], and past, [itex]X_{n-1},\ldots,X_0[/itex] are conditionally independent. Also functions of conditionally independent random variables are also conditionally independent. Also using the fact that [itex]W_0,W_1,W_2,\ldots[/itex] are mutually independent rv's that are independent of [itex]X_0[/itex], we obtain,}
    P(X_{n+1} = x_{n+1}|X_n=x_n,\ldots X_0=x_0) & = & P(f_n(X_n,W_n)=x_{n+1}|f_{n-1}(X_{n-1},W_{n-1})=x_n,\ldots,X_0=x_0)\\
    & = & P(f_n(X_n,W_n)=x_{n+1}|f_{n-1}(X_{n-1},W_{n-1})=x_n)\\
    & = & P(X_{n+1}=x_{n+1}|X_n = x_n)
    Last edited by a moderator: Jan 19, 2012
  2. jcsd
  3. Jan 19, 2012 #2


    User Avatar
    Science Advisor

    Hey hadron23 and welcome to the forums.

    I think the proof is ok, but I'm wondering about the other properties of the Markov process.

    One of the other properties of the Markov process is that the state space is 'closed' (I can't think of the proper term). By that I mean that the potential state-space of the chain is the same for every n.

    This seems to be an implicit property, but maybe you have to show a one or two line proof that this holds. I'm only saying this because when I did this course I had to do this, but it might not apply for you.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook