# Markov Chain and deterministic function

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?

• Hint: first consider the joint chain $(X_n,Y_n)$. Commented Dec 18, 2023 at 6:10

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)?
• Hey Sir Ben, well i found that $Y_{n+1}$ is independent of $X_i, \forall i \leq n$, thats how i would get rid of the past events and keep only $X_n = x_n$ Commented Dec 17, 2023 at 23:20
• I found out somehow, $X_k$ is just a recursif call of $\phi$ over the $Y_i$ is that not valid? Commented Dec 17, 2023 at 23:33
• Well, you assert that $Y_{n+1}$ is independent of $X_1,...,X_n$, so I would just want to know how you got to that. Is it an assumption of the problem, or did it come from some other reasoning?
• well since $X_k = f(Y_0,..,Y_k)$ i got this explicit form from the fact that $X_k$ is just a recursif call of $\phi$ over $Y_i, f$ is a deterministic function , then $X_k$ is independent of $Y_{k+1}$ Commented Dec 19, 2023 at 18:16