Irreducibility and recurrence in the discrete-space case

The chain is called irreducible when

\[ \forall x, y\in\mathcal{X}, \;\exists n=n(x, y)\in\mathbb{N}, \; K_n(x, y) > 0.\]

It is called strongly irreducible when $n(x, y) = 1$ for all $x, y\in\mathcal{X}.$

We say that $x$ is connected to $y$ when there exists $n=n(x, y)\in\mathbb{N}$ such that $K_n(x, y) > 0.$ Thus, the chain is recurrent if, and only if, every point is connected to every other point in space.

When $x$ is connected to $y$, we write $x \rightarrow y.$ When $x$ is connected to $y$ and $y$ is connected to $x,$ we write $x \leftrightarrow y.$

Given a point $x\in\mathcal{X},$ we define the return time to $x$ by

\[ \tau_x = \inf\left\{n\in\mathbb{N}\cup\{+\infty\}; \; n = \infty \textrm{ or } X_n = x\right\}.\]

A point $x$ is connected to $y$ if, and only if, there is a positive probability of reaching $y$ from $x$ in a finite number of steps, which can be written as

\[ x \rightarrow y \quad \Longleftrightarrow \quad \mathbb{P}(\tau_y < \infty | X_0 = x) > 0.\]

\[ (X_n)_n \textrm{ is irreducible } \quad \Longleftrightarrow \quad \mathbb{P}(\tau_y < \infty | X_0 = x) > 0, \quad \forall x, y\in\mathcal{X}.\]

The number of passages through a given state $x\in\mathcal{X}$ is defined by

\[ \eta_x = \sum_{n=1}^\infty \mathbb{1}_{\{X_n = x\}}.\]

\[ x \rightarrow y \quad \Longleftrightarrow \quad \mathbb{P}(\eta_y \geq 1 | X_0 = x) > 0,\]

and

\[ (X_n)_n \textrm{ is recurrent } \quad \Longleftrightarrow \quad \mathbb{P}(\eta_y \geq 1 | X_0 = x) > 0, \quad \forall x, y\in\mathcal{X}.\]

Consider a state $x\in\mathcal{X}.$ Then either

\[ \mathbb{P}(X_n = x \textrm{ infinitely often} | X_0 = x) = 1\]

or

\[ \mathbb{P}(X_n = x \textrm{ infinitely often} | X_0 = x) = 0\]

Let

\[ q = \mathbb{P}(\tau_x < \infty | X_0 = x).\]

The idea is to show, using the Markovian property, that the probability of having two consecutive visits to $x$ is always $q.$ Then, the probability of having $m$ visits is $q^m.$ Finally, the probability of having infinitely many visits is $\lim_{m\rightarrow \infty} q^m.$ Thus, either $0 \leq q < 1$ and then $\lim_{m\rightarrow \infty} q^m = 0$ or $q = 1$ and $\lim_{m\rightarrow \infty} q^m = 1.$

A state $x$ is called recurrent when

\[ \mathbb{P}(X_n = x \textrm{ infinitely often} | X_0 = x) = 1.\]

Otherwise, the state $x$ is called transient, i.e. if

\[ \mathbb{P}(X_n = x \textrm{ infinitely often} | X_0 = x) < 1.\]

For any state $x\in\mathcal{X},$ we have

\[ x \textrm{ is recurrent } \quad \Longleftrightarrow \quad \mathbb{P}(\tau_x < \infty | X_0 = x) = 1 \quad \Longleftrightarrow \quad \mathbb{E}[\eta_x | X_0 = x] = \infty,\]

and

\[ x \textrm{ is transient } \quad \Longleftrightarrow \quad \mathbb{P}(\tau_x < \infty | X_0 = x) < 1 \quad \Longleftrightarrow \quad \mathbb{E}[\eta_x | X_0 = x] < \infty.\]

Moreover, we have the relation

\[ \mathbb{E}[\eta_x | X_0 = x] = \frac{\mathbb{P}(\tau_x < \infty | X_0 = x)}{\left( 1 - \mathbb{P}(\tau_x < \infty | X_0 = x) \right)^2},\]

with the understanding that the left hand side is infinite wen the probability in the right hand side is 1.

We have that $\tau_x = \infty$ iff $X_n$ never returns to $x.$ If $\tau_x < \infty,$ then it returns to $x$ in finite time at least once. If $\tau_x < \infty$ with probability one, then, with probability one, it will return again and again to $x,$ still with probability one, since the countable intersection of sets of full measure still has full measure. Thus,

\[ \mathbb{P}(X_n = x \textrm{ infinitely often} | X_0 = x) = 1 \quad \Longleftrightarrow \quad \mathbb{P}(\tau_x < \infty | X_0 = x) = 1.\]

This proves that $x$ is recurrent if, and only if, $\mathbb{P}(\tau_x < \infty | X_0 = x) = 1,$ which is the first part of the equivalence in the recurrence case. The complement of that is precisely that $x$ is transient if, and only if, $\mathbb{P}(\tau_x < \infty | X_0 = x) < 1.$

For the remaining equivalences, let us suppose, first, that $x$ is transient. Then, as we have seen,

\[ q = \mathbb{P}(\tau_x < \infty | X_0 = x) < 1.\]

We compute the expectation of the number of passages by

\[ \begin{align*} \mathbb{E}[\eta_x | X_0 = x] & = \mathbb{E}\left[ \sum_{n=1}^\infty \mathbb{1}_{X_n = x} \bigg| X_0 = x\right] = \sum_{n=1}^\infty \mathbb{E}\left[\mathbb{1}_{X_n = x} \bigg| X_0 = x\right] \\ & = \sum_{n=1}^\infty \mathbb{P}(X_n = x | X_0 = x) = \sum_{n=1}^\infty p_n(x, x). \end{align*}\]

We can also compute this in a different way. Since $\eta_x$ is always an integer, its expectation is given by

\[ \mathbb{E}[\eta_x | X_0 = x] = \sum_{m=1}^\infty m \mathbb{P}(\eta_x = m | X_0 = x).\]

We need a way to calculate $\mathbb{P}(\eta_x = m | X_0 = x),$ for each integer $m\in\mathbb{N}.$ When $\eta_x = m,$ it means it returns to $x$ $m$ times and then it does not return anymore. This means that $\mathbb{P}(\eta_x = m | X_0 = x) = q^m.$ Thus,

\[ \mathbb{E}[\eta_x | X_0 = x] = \sum_{m=1}^\infty m q^m.\]

Let $S = \sum_{m=1}^\infty m q^m,$ so that $qS = \sum_{m=1}^\infty m q^{m+1} = \sum_{m=2}^\infty (m-1)q^m,$ and hence

\[ (1 - q)S = S - qS = q + \sum_{m=1}^\infty q^m = \sum_{m=1}^\infty q^m = \frac{q}{1 - q}.\]

Thus, $S = q / (1 - q)^2,$ which means

\[ \mathbb{E}[\eta_x | X_0 = x] = \frac{\mathbb{P}(\tau_x < \infty | X_0 = x)}{\left(1 - \mathbb{P}(\tau_x < \infty | X_0 = x)\right)^2}.\]

(In Lawler(2006), the number of passages includes the initial time $n=1,$ so that the formula obtained is $1/(1-q),$ instead of $q/(1 - q)^2.$)

When

\[ q = \mathbb{P}(\tau_x < \infty | X_0 = x) = 1,\]

then

\[ \mathbb{P}(\tau_x < \infty | X_0 = x) \geq r,\]

for any $0 < r < 1,$ and we get, similarly, that

\[ \mathbb{E}[\eta_x | X_0 = x] \geq \sum_{m=1}^\infty m r^m = \frac{r}{(1 - r)} \rightarrow \infty,\]

as $r \rightarrow 1,$ so that $\mathbb{E}[\eta_x | X_0 = x] = \infty.$

This proves the identity between the expectation and the probability. In particular, the expectation is finite if, and only if, the probability is strictly less than one, which proves the remaining equivalences.

If $x$ is a transient state, then, in fact,

\[ \mathbb{P}(X_n = x \textrm{ infinitely often} | X_0 = x) = 0.\]

A state $x$ is recurrent if, and only if,

\[ \mathbb{E}\left[\eta_x\right | X_0 = x] = \infty.\]

The Markov chain is called recurrent when every state is recurrent, i.e.

\[ \mathbb{P}(X_n = x \textrm{ infinitely often} | X_0 = x) = 1, \quad \forall x\in\mathcal{X}.\]

Suppose that, for some $x\in\mathcal{X},$

\[ \mathbb{E}[\tau_{x} | X_0 = x] < \infty.\]

Then

\[ P_x(z) = \frac{1}{\mathbb{E}[\tau_{x} | X_0 = x]} \sum_{n=1}^\infty \mathbb{P}(X_n = z, \tau_{x} \geq n | X_0 = x)\]

defines an invariant probability distribution for the Markov chain.

For the proof, we consider, for the sake of simplicity, the unnormalized measure

\[ {\tilde P}_x(z) = \sum_{n=1}^\infty \mathbb{P}(X_n = z, \tau_{x} \geq n | X_0 = x).\]

We show that it defines a positive and finite invariant measure, with ${\tilde P}_x(\mathcal{X}) = \mathbb{E}[\tau_{x} | X_0 = x].$ After that, we obtain the desired result by normalizing ${\tilde P}_x$ by the expectation $\mathbb{E}[\tau_{x} | X_0 = x].$

First of all, since the space is discrete and each ${\tilde P}_x(z) \geq 0,$ for $z\in\mathcal{X},$ it follows that ${\tilde P}_x$ defines indeed a measure on $\mathcal{X}.$ Let us check that ${\tilde P}_x$ is in fact a nontrivial and finite measure. We have

\[ \begin{align*} {\tilde P}_x(\mathcal{X}) & = \sum_{z\in\mathcal{X}} P_x(z) \\ & = \sum_{z\in\mathcal{X}}\sum_{n=1}^\infty \mathbb{P}(X_n = z, \tau_{x} \geq n | X_0 = x) \\ & = \sum_{n=1}^\infty \sum_{z\in\mathcal{X}} \mathbb{P}(X_n = z, \tau_{x} \geq n | X_0 = x) \\ & = \sum_{n=1}^\infty \mathbb{P}( \tau_{x} \geq n | X_0 = x) \\ & = \sum_{n=1}^\infty \sum_{m=n}^\infty \mathbb{P}(\tau_{x} = m | X_0 = x) \\ & = \sum_{m=1}^\infty \sum_{n=1}^{m} \mathbb{P}(\tau_{x} = m | X_0 = x) \\ & = \sum_{m=1}^\infty m \mathbb{P}(\tau_{x} = m | X_0 = x) \\ & = \mathbb{E}[\tau_{x} | X_0 = x] \end{align*}\]

Since it is assumed that

\[ \mathbb{E}[\tau_{x} | X_0 = x] < \infty,\]

it follows that the measure ${\tilde P}$ is finite. And since, by definition, $\tau_x$ is an integer with $1 \leq \tau_x \leq +\infty,$ the measure is non-trivial, i.e. it is positive, with

\[ 1 \leq {\tilde P}(\mathcal{X}) < \infty.\]

In particular,

\[ \begin{align*} {\tilde P}(\mathcal{x}) & = \sum_{n=1}^\infty \mathbb{P}(X_n = x, \tau_{x} \geq n | X_0 = x) \\ & = \sum_{n=1}^\infty \mathbb{P}(X_n = x, \tau_{x} = n | X_0 = x) \\ & = \sum_{n=1}^\infty \mathbb{P}(\tau_{x} \geq n | X_0 = x) \\ & = \mathbb{P}(\cup_{n\in\mathbb{N}} \{\tau_{x} = n | X_0 = x\}) \\ & = \mathbb{P}(\tau_{x} < \infty | X_0 = x). \end{align*}\]

The condition

\[ \mathbb{E}[\tau_{x} | X_0 = x] < \infty.\]

implies that $\tau_{x}$ must be finite almost surely, so that

\[ {\tilde P}(\mathcal{x}) = \mathbb{P}(\tau_{x} < \infty | X_0 = x) = 1.\]

Now, let us check that ${\tilde P}_x$ is invariant. We need to show that

\[ \sum_{y\in\mathcal{X}} K(y, z){\tilde P}_x(y) = {\tilde P}_x(z),\]

for every $z\in\mathcal{X}.$ For that, we write

\[ \begin{align*} \sum_{y\in\mathcal{X}} K(y, z){\tilde P}_x(y) & = \sum_{y\in\mathcal{X}} K(y, z)\sum_{n=1}^\infty \mathbb{P}(X_n = y, \tau_{x} \geq n | X_0 = x) \\ & = \sum_{n=1}^\infty \sum_{y\in\mathcal{X}} K(y, z) \mathbb{P}(X_n = y, \tau_{x} \geq n | X_0 = x) \end{align*}\]

We split the sum according to $y=x$ and $y\neq x,$ so that

\[ \begin{align*} \sum_{y\in\mathcal{X}} K(y, z){\tilde P}_x(y) & = \sum_{n=1}^\infty K(x, z) \mathbb{P}(X_n = x, \tau_{x} \geq n | X_0 = x) \\ & \qquad + \sum_{n=1}^\infty \sum_{y\neq x} K(y, z) \mathbb{P}(X_n = y, \tau_{x} \geq n | X_0 = x) \\ & = K(x, z) {\tilde P}(x) + \sum_{n=1}^\infty \sum_{y\neq x} \mathbb{P}(X_{n+1} = z, X_n = y, \tau_{x} \geq n | X_0 = x) \\ \end{align*}\]

For $y\neq z,$ we have

\[ \mathbb{P}(X_{n+1} = z, X_n = y, \tau_{x} \geq n | X_0 = x) = \mathbb{P}(X_{n+1} = z, X_n = y, \tau_{x} \geq n+1 | X_0 = x).\]

Thus,

\[ \begin{align*} \sum_{y\in\mathcal{X}} K(y, z){\tilde P}_x(y) & = K(x, z) {\tilde P}(x) + \sum_{n=1}^\infty \sum_{y\neq x} \mathbb{P}(X_{n+1} = z, X_n = y, \tau_{x} \geq n+1 | X_0 = x) \\ & = K(x, z) {\tilde P}(x) + \sum_{n=1}^\infty \mathbb{P}(X_{n+1} = z, \tau_{x} \geq n+1 | X_0 = x) \\ & = K(x, z) {\tilde P}(x) + \sum_{n=2}^\infty \mathbb{P}(X_{n} = z, \tau_{x} \geq n | X_0 = x), \end{align*}\]

where in the last step we just reindexed the summation. Now we use that ${\tilde P}(x) = 1$ (as proved above) and that

\[ K(x, z) = \mathbb{P}(X_1 = z | X_0 = x) = \mathbb{P}(X_1 = z, \tau_{x} \geq 1 | X_0 = x)\]

(since $\tau_{x} \geq 1$ always), to obtain

\[ \begin{align*} \sum_{y\in\mathcal{X}} K(y, z){\tilde P}_x(y) & = \mathbb{P}(X_1 = z, \tau_{x} \geq 1 | X_0 = x) + \sum_{n=2}^\infty \mathbb{P}(X_{n} = z, \tau_{x} \geq n | X_0 = x) \\ & = \sum_{n=1}^\infty \mathbb{P}(X_{n} = z, \tau_{x} \geq n | X_0 = x) \\ & = {\tilde P}(z), \end{align*}\]

proving the invariance.

Now, as mentioned above, since ${\tilde P}(\mathcal{X}) = \mathbb{E}[\tau_{x} | X_0 = x]$ is finite and positive, we can normalize ${\tilde P}$ by this expectation to obtain the invariant probability distribution

\[ P(z) = \frac{1}{\mathbb{E}[\tau_{x} | X_0 = x]} \sum_{n=1}^\infty \mathbb{P}(X_{n} = z, \tau_{x} \geq n | X_0 = x).\]