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