# Equivalent Conditions for Irreducibility of Discrete Time Markov Chains

Cuong Le Van, John Stachurski

<figure><img src="image_1.png" /></figure>

## To cite this version:

Cuong Le Van, John Stachurski. Equivalent Conditions for Irreducibility of Discrete Time Markov Chains. 2004. halshs-03331248

HAL Id: halshs-03331248

https://shs.hal.science/halshs-03331248

Submitted on 1 Sep 2021

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_3.png" /></figure>

UNIVERSITÉ PARIS 1
-PANTHÉON - SORBONNE -

CERMSEM

UMR CNRS 8095

Cahiers
de la
MSE

Equivalent Conditions for Irreducibility
of Discrete Time Markov Chains

Cuong LE VAN

John STACHURSKI

2004.61

<figure><img src="image_4.png" /></figure>

CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE

Maison des Sciences Économiques, 106-112 boulevard de L'Hôpital, 75647 Paris Cedex 13

ISSN : 1624-0340
EQUIVALENT CONDITIONS FOR IRREDUCIBILITY
OF DISCRETE TIME MARKOV CHAINS

CUONG LE VAN AND JOHN STACHURSKI

ABSTRACT. We consider discrete time Markov chains on general state space. It is shown that a certain property referred to here as nondecomposability is equivalent to irreducibility, and that a Markov chain with invariant distribution is irreducible if and only if the invariant distribution is unique and assigns positive probability to all absorbing sets.

# 1. INTRODUCTION

Let $(S, \mathcal{S})$ be any measurable space, let $\mathcal{M}$ be the finite signed measures on same, and let $\mathcal{P}$ be all $\mu \in \mathcal{M}$ with $\mu \ge 0$ and $\mu(S) = 1$. Let $P: S \times \mathcal{S} \to [0, 1]$ be a Markov kernel on $(S, \mathcal{S})$. In other words, $x \mapsto P(x, B)$ is $\mathcal{S}$-measurable for all $B \in \mathcal{S}$, and $B \mapsto P(x, B)$ is an element of $\mathcal{P}$ for all $x \in S$. For $\mu \in \mathcal{M}$ define $P\mu$ by $P\mu(B) := \int P(x, B)\mu(dx)$. Also $P^{n+1}(x, B) := \int P(x, dy)P^n(y, B)$, with $P^1 := P$.

A $\pi \in \mathcal{M}$ satisfying $P\pi = \pi$ is called $P$-invariant. A set $B \in \mathcal{S}$ is called $P$-absorbing if it is nonempty and $P(x, B) = 1$ for all $x \in B$. Let $\psi \in \mathcal{P}$. We call $P$-nondecomposable when every $P$-absorbing set satisfies $\psi(B) = 1$. As usual, $P$ is called $\psi$-irreducible if for every $x \in S$ and $B \in \mathcal{S}$ with $\psi(B) > 0$ we have $\sum_{n=1}^{\infty} P^n(x, B) > 0$. Finally, let us agree to call $P$ irreducible if it is $\psi$-irreducible for some $\psi \in \mathcal{P}$.

The notion of irreducibility is fundamental to the modern theory of Markov chains (cf., e.g., Meyn and Tweedie, 1993). In this paper we show that $\psi$-nondecomposability is equivalent to $\psi$-irreducibility. In addition, we show that when a $P$-invariant distribution $\pi$ exists, $P$ is
irreducible if and only if $\pi$ is the only invariant distribution in $\mathcal{P}$ and
$\pi(B) = 1$ for every $P$-absorbing $B \in \mathcal{S}$.

## 2. RESULTS

The first result from which many of our conclusions follow is

**Theorem 2.1.** Let $\psi \in \mathcal{P}$. The Markov kernel $P$ is $\psi$-nondecomposable if and only if it is $\psi$-irreducible.

In Theorem 2.1 necessity is well known and rather obvious, but suffi-
ciency is not. The proof is given in the next section.

**Theorem 2.2.** Let a $P$-invariant $\pi \in \mathcal{P}$ exist. The following statements are all equivalent.

(i) $P$ is irreducible.

(ii) $P$ is $\psi$-nondecomposable for some $\psi \in \mathcal{P}$.

(iii) $P$ is $\pi$-nondecomposable.

(iv) $\pi$ is unique, and $P$ is $\pi$-nondecomposable.

(v) $\pi$ is unique, and every $P$-absorbing set has positive $\pi$-measure.<fnref n="1" />

*Proof*. From Theorem 2.1 (i) and (ii) are equivalent. Evidently (iv) implies (iii) implies (ii). Now suppose that (i) holds for $\psi \in \mathcal{P}$. We show that (iv) holds. By Meyn and Tweedie (1993, Theorem 10.4.9) $\pi$ is unique, and also absolutely continuous with respect to $\psi$. From the latter it follows that $P$ is also $\pi$-irreducible, and hence $\pi$-nondecomposable. Thus (iv) is established. Finally, (iv) implies (v) is clear, and it remains only to show that (v) implies (iv). This is established by the following lemma. $\square$

**Lemma 2.1.** If $\pi$ is the only $P$-invariant distribution in $\mathcal{P}$ and $B$ is $P$-absorbing, then $\pi(B) > 0$ implies $\pi(B) = 1$.

<footnote n="1">¹In (iv) and (v), uniqueness means of course that there is no other $P$-invariant measure in $\mathcal{P}$.</footnote>
For completeness we give a direct proof of Theorem 2.2 in the appendix.
Some of the necessary lemmas are of independent interest.

### 3. PROOFS

To begin we state and prove the following simple lemma.

**Lemma 3.1.** Let $B \in \mathcal{S}$ and define $(B_n)_{n=1}^\infty$ by $B_1 := B$ and

$$B_{n+1} := \{x \in B_n : P(x, B_n) = 1\}.$$

If $B_\infty := \bigcap_{n=1}^\infty B_n$ is nonempty, then it is P-absorbing.

*Proof.* Let $x \in B_\infty$ and suppose that $P(x, B_\infty) < 1$. Then $P(x, B_k) < 1$ for some $k$, and hence $x \notin B_{k+1}$. This contradicts $x \in B_\infty$. □

*Proof of Theorem 2.1.* It is easy to check that $\psi$-irreducibility implies $\psi$-nondecomposability (Meyn and Tweedie, 1993, Proposition 4.2.3). Regarding the converse, suppose instead that there is an $x_0 \in S$ and $A \in \mathcal{S}$ with $\psi(A) > 0$ and $P^n(x_0, A) = 0$ for all $n \in \mathbb{N}$. Let

$$B_1 := S \setminus A, \quad B_{n+1} := \{x \in B_n : P(x, B_n) = 1\}.$$

As $B_n \subset S \setminus A$ it can never be P-absorbing, for this would contradict $\psi$-nondecomposability. Therefore $B_n \setminus B_{n+1}$ is never empty.

Observe also that if $x \in B_n \setminus B_{n+1}$, then by definition $P(x, B_n) < 1$ and $P(x, B_{n-1}) = 1$. Hence $P(x, B_{n-1} \setminus B_n) > 0$. Similarly, if $x \in B_1 \setminus B_2$, then $P(x, A) > 0$.

We claim that $P(x_0, B_n) = 1$ for all $n \in \mathbb{N}$. Clearly this is true for $n = 1$. Now let it hold for $B_n$. If $P(x_0, B_{n+1}) < 1$, then $P(x_0, B_n \setminus B_{n+1}) > 0$, in which case it can be deduced that

$$(1) \quad \int_{B_n \setminus B_{n+1}} P(x_0, dx_1) \int_{B_{n-1} \setminus B_n} P(x_1, dx_2) \int_{B_{n-2} \setminus B_{n-1}} P(x_2, dx_3) \quad \dots \quad \int_{B_2 \setminus B_3} P(x_{n-2}, dx_{n-1}) \int_{B_1 \setminus B_2} P(x_{n-1}, dx_n)P(x_n, A)$$
must be strictly positive. But $P^{n+1}(x_0, A)$ is not less than the term in (1), leading to a contradiction. Hence $P(x_0, B_{n+1}) = 1$ as claimed.

Now $B_\infty := \cap_{n=1}^\infty B_n$ must be nonempty, because $P(x_0, B_\infty) = 1$ clearly holds. Hence $B_\infty$ is $P$-absorbing (Lemma 3.1), which contradicts $\psi$-nondecomposability. $\square$

*Proof of Lemma 2.1.* Suppose instead that $\pi(S\setminus B) > 0$. Define $\mu \in \mathcal{P}$ by $\mu(A) = \pi(A \cap B)/\pi(B)$. Since $\mu(B) = 1$ we have

$$P\mu(A) = \int_B P(x, A)\mu(dx).$$

Since $B$ is $P$-absorbing,

$$\int_B P(x, A)\mu(dx) = \int_B P(x, A \cap B)\mu(dx).$$

$$\therefore P\mu(A) = \int_B P(x, A \cap B)\mu(dx) = \frac{1}{\pi(B)} \int_B P(x, A \cap B)\pi(dx).$$

But in fact

$$\int_B P(x, A \cap B)\pi(dx) = \int_S P(x, A \cap B)\pi(dx),$$

because

$$\begin{align*}
\pi(B) &= \int_B P(x, B)\pi(dx) + \int_{S\setminus B} P(x, B)\pi(dx) \\
&= \pi(B) + \int_{S\setminus B} P(x, B)\pi(dx).
\end{align*}$$

$$\therefore P\mu(A) = \frac{\pi(A \cap B)}{\pi(B)} = \mu(A).$$

But then $\mu = \pi$, because $\pi$ is the only invariant distribution, and hence $0 = \mu(S \setminus B) = \pi(S \setminus B) > 0$. Contradiction. $\square$

# APPENDIX A

In the appendix we establish Theorem 2.2 directly. Some lemmas are of independent interest.

**Lemma A.1.** If $P$ is $\psi$-nondecomposable for some $\psi \in \mathcal{P}$, then $P$ has at most one invariant distribution.
**Proof.** Suppose instead that $\pi$ and $\pi'$ are invariant distributions. We can take decompositions $\pi = \varrho + \alpha$ and $\pi' = \varrho + \alpha'$, where $\alpha$ and $\alpha'$ are nontrivial, mutually singular and nonnegative (c.f., e.g., Stokey et al., 1989, p. 195). Note that

$$ (2) \qquad \alpha - \alpha' = P(\alpha - \alpha'). $$

Let $B$ and $C$ be disjoint sets in $\mathcal{S}$ satisfy $\alpha(B) = \alpha(S) > 0$ and $\alpha'(C) = \alpha'(S) > 0$, where existence is by the Hahn decomposition.

**Claim A.1.** If $A \subset B$ and $\alpha(A) = \alpha(B)$, then $\alpha(A) = \int_A P(x, A)\alpha(dx)$.

By (2), $\alpha(A) = P\alpha(A) - P\alpha'(A)$. Since $P\alpha(A) \le \alpha(A)$, it follows that $0 \le P\alpha'(A) = P\alpha(A) - \alpha(A) = 0$. Therefore $P\alpha'(A) = 0$, and hence

$$ (3) \qquad \alpha(A) = P\alpha(A) = \int P(x, A)\alpha(dx) = \int_A P(x, A)\alpha(dx). $$

Now let $B_1 := B$ and $B_{n+1} := \{x \in B_n : P(x, B_n) = 1\}$.

**Claim A.2.** This construction yields a decreasing sequence $(B_n)_{n=1}^{\infty}$ such that (a) $\alpha(B_n) = \alpha(B)$; (b) $\alpha'(B_n) = 0$; and (c) $\alpha(B_n) = \int_{B_n} P(x, B_n)\alpha(dx)$.

That (a)—(c) hold for $n = 1$ is trivial. Suppose now that they hold for fixed $n \in \mathbb{N}$, and consider $n + 1$. Clearly (b) must always hold, and (a) implies (c) by Claim A.1. Regarding (a), we have $\alpha(B_n) = \int_{B_n} P(x, B_n)\alpha(dx)$ by (a) of the induction hypothesis and Claim A.1. This implies (a) for $B_{n+1}$, since $P(x, B_n) \le 1$ and $P(x, B_n) < 1$ on $B_n \setminus B_{n+1}$, in which case $B_n \setminus B_{n+1}$ must be $\alpha$-null.

If we define $B_{\infty} := \bigcap_{n=1}^{\infty} B_n$, then $B_{\infty}$ is nonempty, because $\alpha(B_{\infty}) = \alpha(B) > 0$. Hence $B_{\infty}$ is $P$-absorbing by Lemma 3.1. Also, $\alpha'(B_{\infty}) = \lim_n \alpha'(B_n) = 0$.

After a similar construction using $\alpha'$, we find a $C_{\infty}$ which is absorbing and a subset of $C$. Since $B_{\infty}$ and $C_{\infty}$ are disjoint and absorbing no $\psi$ as in the statement of the lemma can exist. $\square$
**Lemma A.2.** Let $\pi$ be P-invariant. If $\pi(B) = 0$ for some P-absorbing set $B$, then $P$ is not $\psi$-nondecomposable for any $\psi \in \mathcal{P}$.

*Proof.* If $B \in \mathcal{S}$ and $\pi(B) = 0$, then

$$ (4) \quad \int_{S \setminus B} P(x, S \setminus B)\pi(dx) = \int P(x, S \setminus B)\pi(dx) = \pi(S \setminus B) = 1. $$

Now let $D_1 := S \setminus B$ and $D_{n+1} := \{x \in D_n : P(x, D_n) = 1\}$. We claim that $\pi(D_n) = 1$ for all $n$. This is clear for $D_1$. Suppose it is true for $D_n$. If $\pi(D_n \setminus D_{n+1}) > 0$, then

$$ \pi(D_n) = \int_{D_{n+1}} P(x, D_n)\pi(dx) + \int_{D_n \setminus D_{n+1}} P(x, D_n)\pi(dx) \\ < \pi(D_{n+1}) + \pi(D_n \setminus D_{n+1}) = \pi(D_n). $$

Therefore $\pi(D_{n+1}) = 1$, and $\pi(D_n) = 1$ for all $n$ as claimed.

Now let $D_\infty := \bigcap_{n=1}^\infty D_n$. Evidently $D_\infty$ is nonempty, and hence (by Lemma 3.1) P-absorbing. Since $B$ and $D_\infty$ are disjoint the statement of the lemma immediately follows. $\square$

We can now complete the proof of Theorem 2.2. In light of Theorem 2.1 and Lemma 2.1, the nontrivial component which remains to be proved is that either of (i) or (ii) implies (iv). We show (ii) implies (iv). By Lemma A.1, $\pi$ is unique. Now let $B$ be P-absorbing. By Lemma A.2, $\pi(B) > 0$, whence, by Lemma 2.1, $\pi(B) = 1$. This proves (iv).

## REFERENCES

[1] Meyn, S. P. and Tweedie, R. L. (1993): *Markov Chains and Stochastic Stability*, Springer-Verlag: London.

[2] Stokey, N. L., R. E. Lucas and E. C. Prescott (1989): "Recursive Methods in Economic Dynamics (Harvard University Press, Massachusetts).

CENTER FOR OPERATIONS RESEARCH AND ECONOMETRICS, UNIVERSITÉ CATHOLIQUE DE LOUVAIN, 34 VOIE DU ROMAN PAYS, B-1348 LOUVAIN-LA-NEUVE, BELGIUM