- #1

hadron23

- 28

- 1

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

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

Last edited by a moderator: