Hi,(adsbygoogle = window.adsbygoogle || []).push({});

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

QUESTION:

Consider the stochastic process [itex]\{X_t,\,t=0,1,2,\ldots\}[/itex] described by,

\begin{align}

X_{t+1} = f_t(X_t,W_t),\,t=0,1,2,\ldots

\end{align}

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.

SOLUTION:

We prove the result by induction. Consider the base case, with [itex]t=2[/itex],

\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 [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,}

\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*}

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Markov Process Proof

**Physics Forums | Science Articles, Homework Help, Discussion**