Markov chains as function of a sequence of i.i.d. random variables

Hi!

I'm a new user and first of all congratulations, this forum is very useful, I'm finding out a lot of interesting answers, I hope I can contribute soon.

I've got a question about Markov chains.

Studying a manual I've found out the following theorem, related to one of the canonical representations of Markov chains:

Let $\displaystyle $\{Z_n\}_{n \ge 1} $$ be a sequence of i.i.d. random variables with values in a denumerable space $\displaystyle $E$$.

Let $\displaystyle $\{X_{n+1} = f(X_n,Z_{n+1})\}_{n \ge 0}$$ a new sequence of random variable with values in a denumerable space $\displaystyle $F$$, with $\displaystyle $f:F \times E \rightarrow E$$ a generic function ($\displaystyle $X_0$$ a random variable on a denumerable set$\displaystyle $F$$).

If for all $\displaystyle $k,k_1,\dots,k_n \in E ,i,i_0,\dots i_{n-1} \in F $$:

$\displaystyle $P(Z_{n+1} = K | X_n = i, X_{n-1} = i_{n-1},\dots , Z_n = k_n , \dots , Z_1 = k_1)$ $ $\displaystyle $=$$ $\displaystyle P(Z_{n+1} = k | X_n = i)$$

then $\displaystyle $\{X_n\}_{n \ge 0}$$ is a Markov chain.

In other words, the previous hypothesis implies that: $\displaystyle $P(X_{n+1} = j | X_n = i, X_{n-1} = i_{n-1}, \dots , X_0 = i_0) = P(X_{n+1} = j | X_{n} = i)$$

The manual doesn't show the proof and I tried to prove it but I didn't succeed.

Could anybody help me obtaing the proof or links to other lecture notes with the solution?

Thanks in advance!

Re: Markov chains as function of a sequence of i.i.d. random variables

Hey fex.

Since we know Z_n is I.I.D then this implies P(Z_n+1|Z_n,Z_n-1,...) = P(Z_n+1|anything) = P(Z_n+1) (complete independence).

So now we have a distribution involving X_n and Z_n but since Z_n is I.I.D then the probability for f(Xn.Zn) will be P(Xn)*P(Zn).

With this factorization you should be able to do some re-arranging to get P(Xn+1|Xn,Xn-1,Xn-2,...) = P(Xn+1|Xn).

Re: Markov chains as function of a sequence of i.i.d. random variables

Hi chiro,

thanks for your reply. I'm so sorry, there was an error in my previous post, the random variables $\displaystyle $\{Z_n\}$$ are not i.i.d. (the way the theorem is proposed by the author fooled me (Worried)).

You're right, when the random variables $\displaystyle \{$Z_n\}$$ are i.i.d., following you're line of reasoning we can find out a way to prove it (indeed we don't need even the statement "for all $\displaystyle $k, k_1, \dots ,k_n \in E, i, i_0, \dots , i_{n-1} \in F $$ ...").

The point is, what happens if I can't state $\displaystyle $P(Z_{n+1}=j | Z_{n}=i_n, \dots , Z_{0}) = P(Z_{n+1} = j)$$ ?

fex