Generating Markov Chains recursively $X_0:\Omega\rightarrow I$ is a random variable where $I$ is countable. Also $Y_1,Y_2,\dots$ are i.i.d. $\text{Unif}[0,1]$ random variables. 
Define a sequence $(X_n)$ inductively as $X_{n+1}=G(X_n,Y_{n+1})$, where $G:I\times[0,1] \rightarrow I$. Show that $(X_n)$ is a Markov chain and determine the transition matrix in terms of G? 
 A: Since $X_{n+1}=G(X_n,Y_{n+1})$ where $Y_{n+1}$ is independent with $X_i$ for all $i$, of course we have
$$\begin{align}P(X_{n+1}|X_n,...,X_0)&=P(G(X_n,Y_{n+1})|X_n,...,X_0)\\&=P(G(X_n,Y_{n+1})|X_n)\\&=P(X_{n+1}|X_n)\end{align}$$
which indicates $\{X_n\}$ is a Markov chain.
A: The question is a particular case of a more general theorem:

Let $S$ be a numerable set and let $X_0:\Omega \to S$ be a random variable on $(\Omega, \mathcal{F}, P)$. Let $\{Y_n\}$, $Y_n:\Omega \to \mathbb{R}^N$ be a sequence of i.i.d. random variables on $(\Omega, \mathcal{F}, P)$ that are also independent of $X_0$, and let $f:S\times \mathbb{R}^N\to S$ be a Borel function. Then the sequence $\{X_n\}$, $X_n:\Omega \to S$ defined by
  $$
X_{n+1}(x) := f(X_n(x), Y_n(x)), \quad \forall\, n \geq 0
$$
  is a homogeneous Markov chain with state space $S$ and transition matrix
  $$
\mathbf{P}_{ij} = P\left(f(i,Y_k)=j\right) \qquad \forall\, i,j\in S
$$

Proof. It follows, from the definition, that for any integer $k$, the random variable $X_k$ is a function of $X_0$ and $Y_1,\dots, Y_{k-1}$. Consequently, for any integer $n$, the random variable $Y_n$, which is by definition independent of $(X_0,Y_1, \dots, Y_{n-1})$, is also independent of $(X_0, \dots, X_n)$. Therefore,
\begin{align*}
& \ P\left(X_{n+1} = j \big\lvert X_0=i_0, \dots, X_n=i \right) \\
&= P\left(f(i,Y_n)=j \big\lvert X_0=i_0, \dots, X_n=i\right) \\
&= P(f(i,Y_n)=j) \\
&= P\left(f(i,Y_n)=j \big\lvert X_n=i\right)
\end{align*} 
the second equality holds since the random variable $(X_0, \dots, X_n)$ is independent of $Y_n$, hence of $f(i,Y_n)$. This shows that $\{X_n\}$ is a Markov chain and the transition matrix is $$\mathbf{P}=(\mathbf{P})_{ij} = P(f(i,Y_n)=j)$$ but this last expression is independent of $n$ since the random variables are i.i.d.
$$\tag*{$\Box$}$$
