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

1. ## 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?

2. ## 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).

3. ## 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 ). 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