Markov Chain Homework: Expressing Transition Matrix P in Terms of G

[hsong9]

Please Help! Markov Chain

Homework Statement

Let X₀ be a random variable with values in a countable set I. Let Y₁, Y₂, ... be a
sequence of independent random variables, uniformly distributed on [0, 1].
Suppose we are given a function G : I x [0, 1] -> I
and define inductively for n >= 0, X_n+1 = G(X_n, Y_n+1).
Show that (Xn)_n>=0 is a Markov chain and
express its transition matrix P in terms of G.

Homework Equations

The Attempt at a Solution

I know that I need to show that X_n+1 depends on X_n by checking the condition in the definition of Markov chain, and then
try to find some formula for P(X_n+1 = j | X_n=i) in terms of G.

Actually, my background for Markov chain lacks a little, so I have no how I find some formula for P in terms of G.. How do I handle terms of G?
Anybody give me some hints or answer?

 

[fi1]

I guess you should only need to show P[X_n+1 = x_n+1 | X₁ = x₁, X₂ = x₂, ..., X_n = x_n] = P[X_n+1 = x_n+1 | X_n = x_n]. (Markov property).

In your case it holds, since G is only a function of X_n; and Y_i are independent random variables. P[X_n+1 = x_n+1 | X_n = x_n] = P[G(x_n, y)=x_n+1] where y is the uniformly distributed random variable.