Prove Markov Process Using Induction

[hadron23]

Hi,

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. ThanksQUESTION:
Consider the stochastic process \{X_t,\,t=0,1,2,\ldots\} described by,
\begin{align}
X_{t+1} = f_t(X_t,W_t),\,t=0,1,2,\ldots
\end{align}
where f_0,f_1,f_2,\ldots are given functions, X_0 is a random variable with given cumulative distribution function, and W_0,W_1,W_2,\ldots are mutually independent rv's that are independent of X_0, and have given CDFs. Prove that \{X_t,\,t=0,1,2,\ldots\} is a Markov process.SOLUTION:
We prove the result by induction. Consider the base case, with t=2,
\begin{eqnarray*}
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)
\end{eqnarray*}
Now, the induction hypothesis is, assume,
\begin{align}
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})
\end{align}
We wish to prove the following (induction step),
\begin{eqnarray*}
& & 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)
\end{eqnarray*}
But from the induction hypothesis, we know that given the present, denoted X_{n-1}, the future, X_n, and past, X_{n-1},\ldots,X_0 are conditionally independent. Also functions of conditionally independent random variables are also conditionally independent. Also using the fact that W_0,W_1,W_2,\ldots are mutually independent rv's that are independent of X_0, we obtain,}
\begin{eqnarray*}
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)
\end{eqnarray*}

 

[chiro]

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.