A theorem states the following:


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

Additional information on the notation:

$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:


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!

  • 1
    $\begingroup$ 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. $\endgroup$
    – cardinal
    Jan 28, 2013 at 1:57

1 Answer 1


Begin by truncating the sum

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.