# Markov chain

• May 23rd 2010, 05:33 AM
Moo
Markov chain
Hi guys !

I'm pretty desperate : it's a simple question, but I don't manage to write the solution properly...

We have (a Galton-Watson process) $\displaystyle Z_0=a$ and $\displaystyle Z_n=\sum_{i=1}^{Z_{n-1}} X_{i,n}$, where the sequence $\displaystyle (X_{i,n})_{i,n}$ is an iid sequence.

How can I show that $\displaystyle Z_n$ is a homogeneous Markov Chain ? I know all the basic methods :
- prove that P(Z(n+1)=z(n+1)|Z0=a,Z1=z1,...,Zn=zn)=P(Z(n+1)=z(n +1)|Zn=zn) <--- I've tried it, but it wasn't rigourous enough to me
- prove that the process can be expressed as a function of Zn and an random variable U(n+1) independent with Zn <--- the problem here is that either Zn is in the index of the independent rv, either I have an infinite number of random variables. So I don't really know how to extend it...

Thanks
• May 23rd 2010, 06:13 PM
Focus
Quote:

Originally Posted by Moo
Hi guys !

I'm pretty desperate : it's a simple question, but I don't manage to write the solution properly...

We have (a Galton-Watson process) $\displaystyle Z_0=a$ and $\displaystyle Z_n=\sum_{i=1}^{Z_{n-1}} X_{i,n}$, where the sequence $\displaystyle (X_{i,n})_{i,n}$ is an iid sequence.

How can I show that $\displaystyle Z_n$ is a homogeneous Markov Chain ? I know all the basic methods :
- prove that P(Z(n+1)=z(n+1)|Z0=a,Z1=z1,...,Zn=zn)=P(Z(n+1)=z(n +1)|Zn=zn) <--- I've tried it, but it wasn't rigourous enough to me

I think you are trying too hard. On the event {Z_{n-1}=N} the sum is from 1 to N. On the event {Z_1=C_1,...,Z_{n-1}=N}, the sum is again from one to N.

Quote:

- prove that the process can be expressed as a function of Zn and an random variable U(n+1) independent with Zn <--- the problem here is that either Zn is in the index of the independent rv, either I have an infinite number of random variables. So I don't really know how to extend it...
It might help to prove this using the c.f. :

$\displaystyle \mathbb{E}[e^{i \theta Z_n}|Z_{n-1}=N]=\prod_{i=1}^N \mathbb{E}[e^{i \theta X_{i,n}}]=\mathbb{E}[e^{i \theta X_{1,n}}]^N=:\phi(\theta)^N$
By the tower law,
$\displaystyle \mathbb{E}[e^{i \theta Z_n}]=\mathbb{E}[\phi(\theta)^{Z_{n-1}}]$

Characteristic functions uniquely determine distributions and the above is a function of phi and Z_n.
• May 24th 2010, 02:12 AM
Laurent
I too think you're trying too hard :) Here are my suggestions...

Quote:

Originally Posted by Moo
- prove that P(Z(n+1)=z(n+1)|Z0=a,Z1=z1,...,Zn=zn)=P(Z(n+1)=z(n +1)|Zn=zn) <--- I've tried it, but it wasn't rigourous enough to me

We have $\displaystyle P(Z_{n+1}=z_{n+1}|Z_0,\ldots,Z_n=z_n)=P\left(\sum_ {i=1}^{z_n}X_{i,n+1}=z_{n+1}\middle|Z_0,\ldots,Z_n =z_n\right)$ $\displaystyle =P\left(\sum_{i=1}^{z_n}X_{i,n+1}=z_{n+1}\right)(= :p(z_n,z_{n+1}))$ using the fact that the random variable in the probability is independent of those in the condition.

Quote:

- prove that the process can be expressed as a function of Zn and an random variable U(n+1) independent with Zn <--- the problem here is that either Zn is in the index of the independent rv, either I have an infinite number of random variables. So I don't really know how to extend it...
Why not say that $\displaystyle Z_{n+1}$ is a (time-independent) function of $\displaystyle Z_n$ and $\displaystyle U_{n+1}=(X_{i,n+1})_{i\geq 1}$, which is independent of $\displaystyle \mathcal{F}_n$ (the past before time $\displaystyle n$) and whose law $\displaystyle \mu$ does not depend on $\displaystyle n$? Then $\displaystyle U_{n+1}$ is not real, but this doesn't matter in order to deduce that $\displaystyle (Z_n)_n$ is an homogeneous Markov chain:

$\displaystyle E[\varphi(Z_{n+1})|\mathcal{F}_n]=E[\varphi(f(Z_n,U_{n+1}))|\mathcal{F}_n]$ $\displaystyle =\int \varphi(f(Z_n,u)) d\mu(u)$ is a time-independent function of $\displaystyle Z_n$ (choose $\displaystyle \varphi(z)={\bf 1}_{(z=z_{n+1})}$ and take expectation to get the above definition).
• May 24th 2010, 09:45 AM
Moo
One thing I didn't need much time to figure out is that I agree that I was overcomplicating it :( But I really worry for the way I write it...

I sort of combined your replies (though I didn't see Laurent's yet), or so I think...

Quote:

$\displaystyle (a_n)_{n\in N}$ a sequence of integers.
$\displaystyle P(Z_{n+1}=a_{n+1}\mid Z_0=a_0,\dots,Z_n=a_n)$$\displaystyle =P\big(\sum_{i=1}^{a_n} X_{i,n+1}=a_{n+1}\mid Z_0=a_0,\dots,Z_n=a_n\big)$

Whatever values $\displaystyle a_0,\dots,a_{n-1}$ take, the probability won't be changed as none of them intervene in $\displaystyle \sum_{i=1}^{a_n} X_{i,n+1}$.

So $\displaystyle P(Z_{n+1}=a_{n+1}\mid Z_0,\dots,Z_n)=P(Z_{n+1}=a_{n+1}\mid Z_n)$

Hence (Zn) is a Markov chain.
As to show that it's homogeneous, that's no big deal.

I like the way of the characteristic functions, but I already show something similar later on and can't be removed, sorry (Worried)

As for defining $\displaystyle U_{n+1}$, I'm happy, so the formula can be generalized if it's defined this way... I wasn't sure at all about that.

If the above text is not correct, I'll go to this stuff with $\displaystyle U_{n+1}$ (Happy) But I'd be happy if one could point out what's wrong in it :)

Thanks guys !