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

• January 26th 2013, 03:09 AM
fex
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 $\{Z_n\}_{n \ge 1}$ be a sequence of i.i.d. random variables with values in a denumerable space $E$.
Let $\{X_{n+1} = f(X_n,Z_{n+1})\}_{n \ge 0}$ a new sequence of random variable with values in a denumerable space $F$, with $f:F \times E \rightarrow E$ a generic function ( $X_0$ a random variable on a denumerable set $F$).

If for all $k,k_1,\dots,k_n \in E ,i,i_0,\dots i_{n-1} \in F$:
$P(Z_{n+1} = K | X_n = i, X_{n-1} = i_{n-1},\dots , Z_n = k_n , \dots , Z_1 = k_1)$ $=$ $P(Z_{n+1} = k | X_n = i)$

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

In other words, the previous hypothesis implies that: $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?

• January 26th 2013, 06:28 PM
chiro
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).
• January 27th 2013, 02:20 AM
fex
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 $\{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 $\{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 $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 $P(Z_{n+1}=j | Z_{n}=i_n, \dots , Z_{0}) = P(Z_{n+1} = j)$ ?

fex