# A question about Markov Chains and transition matrix

Let $$X_{0}$$ a random variable that takes values in the space $$E$$, where $$E$$ is countable and let $$\{Y_{n}\}_{n}$$ a succession of random variables independent and identically distributed $$Unif(0,1)$$. Suppose that there is a function $$G:W \times [0,1] \rightarrow E$$ and define $$X_{n+1}=G(X_{n},Y_{n+1})$$, proof that $$\{X_{n}\}$$ it's a Markov Chain and represent the transition matrix $$P$$ in terms of the function $$G$$. I've been trying to do this exercise for a while, now I know that since $$X_{n+1}=G(X_{n},Y_{n+1})$$ where $$Y_{n+1}$$ is independent, we have:\begin{align}P(X_{n+1}|\{X_n\}_{n})&=P(G(X_n,Y_{n+1})|\{X_n\}_{n})\\&=P(G(X_n,Y_{n+1})|X_n)\\&=P(X_{n+1}|X_n)\end{align} which tell us that $$\{X_{n}\}$$ is a Markov Chain, but I don´t know what to do in order to have that transition matrix $$P$$, thanks for your help.

Let $$i$$ and $$j$$ be elements of $$E$$. Because $$Y_{n+1}$$ is independent of $$X_n$$, \begin{align*} P(X_{n+1} = j \, | \, X_n = i) &= P(G(X_n, Y_{n+1}) = j \, | \, X_n = i) \\ &= P(G(i,Y_{n+1}) = j \, | \, X_n = i) \\ &= P(G(i,Y_{n+1}) = j) . \end{align*} All the random variables $$Y_{n+1}$$ have the same distribution, so this last probability does not depend on $$n$$. Then $$P$$ is the matrix whose entry $$(i,j)$$ is the probability above.