# Markov chain

#### Moo

MHF Hall of Honor
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

#### Focus

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.

- 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.

• Moo

#### Laurent

MHF Hall of Honor
I too think you're trying too hard Here are my suggestions...

- 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)(= (z_n,z_{n+1}))$$ using the fact that the random variable in the probability is independent of those in the condition.

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

• Moo

#### Moo

MHF Hall of Honor
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...

$$\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 !