hadron23
Jan19-12, 01:10 PM
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. Thanks
QUESTION:
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{(s ince }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*}
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 \{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{(s ince }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*}