Markov Chain and deterministic function

Question

Here is a problem I am trying to solve:

Consider a sequence of IID random variables $Y_1,Y_2,Y_3,...$ with values in $E$ and let the function $\varphi: E^2 \rightarrow E$ define the corresponding sequence $X_1,X_2,X_3,...$ given by:

$$X_{n+1} = \varphi(Y_{n+1}, X_n) \quad \quad \quad \text{for } n = 0,1,2,3,...$$

Prove that $\{ X_n | n \in \mathbb{N} \}$ is a markov chain.

My solution:

$$\begin{align} \text{Transition Prob} &= P(X_{n+1} = x_{n+1} | X_n = x_n , ..., X_0 = x_0) \\[6pt] &= P(X_{n+1} = \phi(Y_{n+1}, X_n) = x_{n+1} | X_n = x_n , ..., X_0 = x_0) \\[6pt] &= P(x_{n+1} = \phi(Y_{n+1}, x_n)| X_n = x_n , ..., X_0 = x_0) \\[6pt] &= P(x_{n+1} = \phi(Y_{n+1}, x_n) | X_n = x_n) \\[6pt] \end{align}$$

Thus:

$$\begin{align} P(X_{n+1} = \phi(Y_{n+1}, X_n) = x_{n+1} | X_n = x_n) = P(X_{n+1} = x_{n+1} | X_n = x_n , ..., X_0 = x_0) \end{align}$$

Conclusion $\{ X_n | n \in \mathbb{N} \}$ is a markov chain, is this valid?

Answer 1

Your third step is invalid --- you cannot just replace the random variable $X_{n+1}$ with a constant $x_{n+1}$ in this probability statement. Instead, keep the argument as a statement involving $X_{n+1}$ and then ask yourself about the behaviour of $\varphi(Y_{n+1}, x_n)$ conditional on the $X_i$ values in the conditioning statement. Is there any further step you could take that would remove any of the conditioning variables to get to the Markov property? If so, how might such a step be justified (i.e., by what assumption)?