# Proving that an inductively defined function is a Markov chain

Let $X_0$ be a random variable with values in a countable set $I$. Let $Y_1,Y_2,\ldots$ be a sequence of independent random variables, uniformly distributed on $[0,1]$. Suppose we are given a function

$$G\colon I\times [0,1]\rightarrow I$$

and define inductively $$X_{n+1}=G(X_n,Y_{n+1})$$.

I want to show that $(X_n)_{n\ge 0}$ is a Markov Chain. In other words I want to show that $\mathbb{P}(X_{n+1}=i_{n+1}\,|\,X_0=i_0,\ldots,X_n=i_n)=\mathbb{P}(X_{n+1}=i_{n+1}\,|\,X_n=i_n)$ and that $\mathbb{P}(X_0=i_0)=\lambda_i$ for some $\lambda_i\in \lambda$ (distribution).

we see that

\begin{align} \mathbb{P}(X_{n+1}=i_{n+1}\,|\,X_0=i_0,\ldots,X_n=i_n)&=\mathbb{P}(G(X_n,Y_{n+1})=i_{n+1}\,|\,X_0=i_0,\ldots,X_n=i_n)\\ &=\mathbb{P}(G(X_n,Y_{n+1})=i_{n+1}\,|\,X_n=i_n)\\ &=\mathbb{P}(X_{n+1}=i_{n+1}\,|\,X_n=i_n). \qquad\qquad\qquad\text{(1)} \end{align} I think that the equality above is true because $X_n$ is given and $Y_j$ for all $j$ is independent. And because $X_0(\omega)\in I$ we can say that $\mathbb{P}(X_0=i_0)=\lambda_i$ with $\lambda_i\in\lambda$ (distribution i.e. $\sum_{\lambda_i\in\lambda,i\in I}{\lambda_i=1}$). So we can conclude that $(X_n)$ is Markov.

Since $(X_n)_{n\ge 0}$ is a Markov chain we can express its transition matrix in terms of $G$.

The transition matrix $P$ is defined as $P:=(p_{i,j}\colon i,j\in I)$ where $p_{i,j}=\mathbb{P}(X_{n+1}=i\,|\,X_n=j)=\mathbb{P}(G(X_n,Y_{n+1})=i\,|\,X_n=i_n)$. Therefore $P=(\mathbb{P}(G(X_n,Y_{n+1})=i\,|\,X_n=j)\colon i,j\in I).\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad \text{(2)}$

So my questions are as follows:

• Is the equality at (1) true?

• Is (2) the only method to express the transition matrix of $(X_n)_{n\ge 0}$ in terms of $G$?

• Can all Markov chains be realized in this way?