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}$$


$$\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?

  • $\begingroup$ Hint: first consider the joint chain $(X_n,Y_n)$. $\endgroup$
    – Xi'an
    Dec 18, 2023 at 6:10

1 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)?

  • $\begingroup$ 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$ $\endgroup$
    – HellBoy
    Dec 17, 2023 at 23:20
  • $\begingroup$ Okay, but how did you "find" that exactly? Is it an assumption of the problem or something you inferred from something else? $\endgroup$
    – Ben
    Dec 17, 2023 at 23:27
  • $\begingroup$ I found out somehow, $X_k$ is just a recursif call of $\phi$ over the $Y_i$ is that not valid? $\endgroup$
    – HellBoy
    Dec 17, 2023 at 23:33
  • 1
    $\begingroup$ 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? $\endgroup$
    – Ben
    Dec 17, 2023 at 23:47
  • $\begingroup$ 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}$ $\endgroup$
    – HellBoy
    Dec 19, 2023 at 18:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.