Irreducibility and aperiodicity of a Markov chain

258 Views Asked by At

Theorem: If $P$ is the transition matrix on $\chi$ of a null recurrent irreducible chain, then

$$\lim_{t\to \infty} P^t(x,y) = 0 \text{ for all $x,y\in \chi$}$$

There is a part of the proof that shows the above is true if the chain is aperiodic which I understand. I have a question when the chain is periodic whose explanation is as follows:

If the chain is periodic, fix $x,y\in \chi$ and let

$$l:=\gcd\{t:P^t(x,x)>0\}$$

There exist $q,r$ s.t. $P^{ql+r}(x,y)>0$. The definition of $l$ implies that $P^s(y,x)>0$ only if $s=-r\mod l$. Therefore, $P^t(x,y)>0$ only if $t=r\mod l$. Let

$$\chi_r = \{z\in \chi: P^{sl+r}(x,z)>0 \text{ for some }s\geq 0\}$$

By an analogous argument to the one above, $P^l$ is irreducible. Clearly $P^l$ is null recurrent which means for every $z\in \chi_r$, $P^{kl}(z,y)\to 0$.

I don't understand why $P^l$ is irreducible and aperiodic on $\chi_r$?

1

There are 1 best solutions below

0
On BEST ANSWER

Basically the idea is to use your recurrent, irreducible, periodic chain to define an equivalence relation: $x$ is related to $y$ if $y$ can be reached from $x$ in a number of steps which is a multiple of the period of the chain. The fact that this relation is reflexive is obvious; the fact that it is transitive is also obvious. The fact that this relation is symmetric follows from the fact that the chain is recurrent: if you could get from $x$ to $y$ in a multiple of $l$ steps and then couldn't get back to $x$ in a multiple of $l$ steps, then by the definition of $l$ you wouldn't be able to return to $x$ at all, so $x$ would be transient, which it isn't by assumption.

This tells you that the chain with matrix $P^l$ is irreducible on each equivalence class of this equivalence relation. The fact that it is aperiodic on each equivalence class more or less follows from the fact that the period is a communicating class invariant, so if $P^l$ were periodic on some equivalence class then the period of the chain would have to be greater than $l$.

The last thing is to say that the $\chi_r$ for, say, $r=0,1,\dots,l-1$, actually are the equivalence classes, in other words that the dynamics started from any particular point will necessarily shuffle you between all the equivalence classes. I'm less clear on how to show that: intuitively, I think that if you could visit the same equivalence class twice in the same segment of $l$ consecutive time steps, then the period of the chain would have to be less than $l$, but I am not totally sure that's right.