# Proof of theorem on recurrent states and its equivalence class

A theorem states the following:

## Theorem

if $i \in S$ is a state which is recurrent, then every state in the equivalence class of $i$ $(\ K(i) \ )$ is recurrent.

$S$ is the space of the states of a markov chain $X_n$ with stochastic matrix (transition matrix) $P=(p_{ij})$. For $i,j \in S$ let $i \sim j$ be defined as $(i \leftrightarrow j)$ V $(i=j)$, where $(i \leftrightarrow j)$ means that $i$ communicates with $j$, so in other words $p_{ij}^{(n)},p_{ji}^{(n)}>0$. Thus, we define $K(i):=\{j \in S | i \sim j\}$.

The proof works like this:

## Proof

Let $i$ be recurrent and $j \in K(i),j \neq i$, so that there are $n,m \in \mathbb{N}$ with $p_{ij}^{(m)}\cdot p_{ji}^{(n)}>0$

$\sum\limits_{k=0}^\infty p_{jj}^{(k)} \geq \sum\limits_{k=0}^\infty p_{jj}^{(m+n+k)} \geq \sum\limits_{k=0}^\infty p_{ji}^{(n)}p_{ii}^{(k)}p_{ij}^{(m)}$

$\color{green}{Can \ someone \ explain \ to \ me \ why \ the \ first \ and \ second \ inequality \ sign \ holds? }$

Thank you!

• Hi, Chris. Though I and most others can guess at the meaning, it would be very helpful for you to set out clearly your notation. – cardinal Jan 28 '13 at 1:57

$$\sum_{k=0}^\infty p_{jj}^{\left(k\right)} \ge \sum_{k=n+m}^\infty p_{jj}^{\left(k\right)}\\ = \sum_{k=0}^\infty p_{jj}^{\left(n+m+k\right)}$$
For the second inequality, we can without loss of generality, by the definition of a Markov process, consider the elements $A,B,C$ of the $\sigma$-algebra restricted to $X\left(\omega\right)_0=j$
$$A=\left\lbrace \omega : X\left(\omega\right)_{0}=j,X\left(\omega\right)_{n}=i,X\left(\omega\right)_{n+k}=i,X\left(\omega\right)_{n+m+k}=j\right\rbrace\\ B=\left\lbrace \omega : X\left(\omega\right)_{0}=j,X\left(\omega\right)_{n+m+k}=j \right\rbrace\\ C=\left\lbrace \omega : X\left(\omega\right)_0 = j \right\rbrace$$
Clearly $A \subseteq B \subseteq C$. But by the definition of the probabilities, and in particular the sub-additivity of probability measures,
$$p_{jj}^{\left(n+m+k\right)}=\mathbb{P}\left[\left.B \right| C\right] \ge \mathbb{P}\left[\left. A \right| C\right]=p_{ij}^{\left(n\right)}p_{ii}^{\left(k\right)}p_{ji}^{\left(m\right)}$$ The rest follows...