Discrete-Time Markov Chains (DTMC)

Published

18 October 2026

Draft

This lecture note is still being edited: the text may contain typos, inaccuracies, and locally unpolished spots. If you find something, please let the author know (contact details on the course page).

The simple random walk and the Galton-Watson branching process had the following property: conditionally on the value at step \(n\), their future values did not depend on the previous values. This property turned out to be very useful in their analysis, and we now turn to the general theory of processes with this property.

1 The Markov property

Let \((X_n \; : \; n \in \mathbb {Z}_+) = (X_0, X_1, \ldots )\) be a random process with values in some space \(\mathcal{X}\), where \(\mathcal{X}\) is a finite or countable set, called the state space or phase space. The process \((X_n)\) (with discrete time) is called a discrete-time Markov chain, abbreviated DTMC, if it has the Markov property: for a fixed present at an arbitrary point in time \(n\), the future of the process (an arbitrary number of steps \(m\) ahead) does not depend on the past (fixed at points \(n_{0} < n_{1} < \ldots < n_{k} < n\)). Formally:

\[ \mathbb {P}\left(X_{n+1} = i_{n+1} \quad \left| \quad \begin{array}{rl} X_{n} & = i_{n} \\ X_{n-1} & = i_{n-1} \\ \cdots & \cdots \\ X_{0} & = i_{0} \\ \end{array}\right.\right) \; = \; \mathbb {P}\left(X_{n+1} = i_{n+1} \mid X_{n} = i_{n}\right) \]

for all \(n\) and all states \(i_{0}, \ldots , i_{n+1} \in \mathcal{X}\) such that the expressions on the left and right make sense (the conditioning events have nonzero probability).

In other words, for a fixed present state \(X_{n} = i_{n}\), the future of the process \(1\) step ahead, \(X_{n+1} = i_{n+1}\), does not depend on the past \(X_{n-1} = i_{n-1}, \ldots , X_{0} = i_{0}\).

Additional material

What if we look at the future of the process not \(1\) step ahead but \(m\) steps ahead? Or look at the present and the past selectively, not at every point from \(0\) to \(n-1\)? It turns out that in all these more general cases, for a Markov process the future still does not depend on the past.

Lemma 1 Let \((X_n)\) be a random process with values in a discrete space \(\mathcal{X}\). The following conditions are equivalent:

\((X_n)\) has the Markov property:

holds for all \(n \in \mathbb {N}\) and all states \(i_{0}, \ldots , i_{n}, i_{n+1} \in \mathcal{X}\) such that the expressions on the left and right make sense.

\[ \mathbb {P}\left(X_{n+m} = i_{n+m} \quad \left| \quad \begin{array}{rl} X_{n} & = i_{n} \\ X_{n-1} & = i_{n-1} \\ \cdots & \cdots \\ X_{0} & = i_{0} \\ \end{array}\right.\right) \; = \; \mathbb {P}\left(X_{n+m} = i_{n+m} \mid X_{n} = i_{n}\right) \]

holds for all \(n, m \in \mathbb {N}\) and all states \(i_{0}, \ldots , i_{n}, i_{n+m} \in \mathcal{X}\) such that the expressions on the left and right make sense.

\[ \mathbb {P}\left(X_{n_{k+1}} = i_{n_{k+1}} \quad \left| \quad \begin{array}{rl} X_{n_k} & = i_{n_k} \\ X_{n_{k-1}} & = i_{n_{k-1}} \\ \cdots & \cdots \\ X_{n_0} & = i_{n_0} \\ \end{array}\right.\right) \; = \; \mathbb {P}\left(X_{n_{k+1}} = i_{n_{k+1}} \mid X_{n_k} = i_{n_k}\right) \]

holds for all nonnegative integers \(n_0 < n_1 < \ldots < n_k < n_{k+1}\) and all states \(i_{n_0}, \ldots , i_{n_k}, i_{n_{k+1}} \in \mathcal{X}\) such that the expressions on the left and right make sense.

2 Distribution of the chain, transition probabilities

\(\mathcal{X}\) is finite or countable. If \(\mathcal{X}\) is finite, it can be identified with \(\left\{ 1, 2, \ldots , \left|\mathcal{X}\right|\right\}\). If \(\mathcal{X}\) is countable, it can be identified with \(\mathbb {N}\).

It is easy to show that the distribution of a DTMC is completely determined by

the initial distribution, i.e. the distribution of \(X_0\). It is usually denoted by the row vector \(\Pi^{(0)}\):

\[ \Pi ^{(0)} = \left(\mathbb {P}\left(X_0 = i\right)\right)_{i \in \mathcal{X}} = \left(\mathbb {P}\left(X_0 = 1\right), \mathbb {P}\left(X_0 = 2\right), \ldots \right) \]
the one-step transition probabilities, i.e. the probabilities \(\mathbb {P}\left(X_{n+1} = i \mid X_{n} = j\right)\). These can be combined into (possibly infinite) matrices \(\mathbf{P}_{0}\), \(\mathbf{P}_{1}\), \(\mathbf{P}_{2}\), \(\ldots\):

\[ \mathbf{P}_n = \bigg(\mathbb {P}\left(X_{n+1} = j \mid X_{n} = i\right)\bigg)_{i,j \in \mathcal{X}} \]

Namely, the distribution of the chain at time \(k\), denoted \(\Pi^{(k)} = \left(\mathbb {P}\left(X_k = i\right)\right)_{i \in \mathcal{X}}\), can be found as follows:

\[ \mathbb {P}\left(X_k = i\right) = \sum _{j\in \mathcal{X}} \mathbb {P}\left(X_{k-1} = j\right) \cdot \mathbb {P}\left(X_{k}= i \mid X_{k-1} = j\right) \]

that is,

\[ \Pi ^{(k)} = \Pi ^{(k-1)} \cdot \mathbf{P}_{k-1} \]

Continuing this process, we get the formula

\[ \Pi ^{(k)} = \Pi ^{(0)} \cdot \mathbf{P}_0 \cdot \mathbf{P}_1 \cdot \cdots \cdot \mathbf{P}_{k-1} \]

A discrete-time Markov chain is called homogeneous if all the transition matrices coincide: \(\mathbf{P} := \mathbf{P}_{0} = \mathbf{P}_{1} = \ldots\). For a homogeneous Markov chain finding the distribution becomes simpler:

\[ \Pi ^{(k)} = \Pi ^{(0)} \cdot \mathbf{P}^k \]

Example 1

Let a homogeneous Markov chain consist of \(4\) states (\(1,2,3,4\)), and suppose the initial distribution is known: \[ \Pi ^{(0)} = \left(0.1, 0.3, 0.4, 0.2\right) \] Suppose the one-step transition matrix is known: \[ \mathbf{P} = \begin{pmatrix} 0.5 & 0.5 & 0 & 0 \\ 0.3 & 0.3 & 0.3 & 0.1 \\ 0 & 0 & 1 & 0 \\ 0.4 & 0.4 & 0 & 0.2 \end{pmatrix} \] Find the distribution of \(X_3\), i.e. the distribution of the chain after \(3\) steps.

Solution

We need to find the row \[ \Pi ^{(3)} = \left(\mathbb {P}\left(X_3 = 1\right), \mathbb {P}\left(X_3 = 2\right), \mathbb {P}\left(X_3 = 3\right), \mathbb {P}\left(X_3 = 4\right)\right) \] By the formula: \[ \begin{align} \Pi ^{(3)} & = \Pi ^{(0)} \cdot \mathbf{P}^3 = \left(0.1, 0.3, 0.4, 0.2\right) \cdot \begin{pmatrix} 0.34 & 0.34 & 0.27 & 0.05 \\ 0.244 & 0.244 & 0.474 & 0.038 \\ 0 & 0 & 1 & 0 \\ 0.352 & 0.352 & 0.24 & 0.056 \\ \end{pmatrix} = \\ & = \left(0.1776, 0.1776, 0.6172, 0.0276\right) \end{align} \]

So far we have not used the Markov property. It is needed when trying to compute finite-dimensional distributions for a DTMC. Namely,

\[ \begin{align} \mathbb {P}\left(\left. \begin{array}{rl} X_{n} & = i_{n} \\ X_{n-1} & = i_{n-1} \\ X_{n-2} & = i_{n-2} \\ \cdots & \cdots \\ X_{0} & = i_{0} \\ \end{array}\right.\right) & = \underbrace{\mathbb {P}\left(X_{n} = i_{n} \quad \left| \quad \begin{array}{rl} X_{n-1} & = i_{n-1} \\ X_{n-2} & = i_{n-2} \\ \cdots & \cdots \\ X_{0} & = i_{0} \\ \end{array}\right.\right)}_{\substack {=\mathbb {P}\left(X_{n}= i_n \mid X_{n-1} = i_{n-1}\right) = \left(\mathbf{P}_{n-1}\right)_{i_{n-1},i_n},\\ \text{Markov property}}} \quad \cdot \quad \mathbb {P}\left(\left. \quad \begin{array}{rl} X_{n-1} & = i_{n-1} \\ X_{n-2} & = i_{n-2} \\ \cdots & \cdots \\ X_{0} & = i_{0} \\ \end{array}\right.\right) = \\ & = \left(\mathbf{P}_{n-1}\right)_{i_{n-1},i_n} \quad \cdot \quad \mathbb {P}\left(\left. \quad \begin{array}{rl} X_{n-1} & = i_{n-1} \\ X_{n-2} & = i_{n-2} \\ \cdots & \cdots \\ X_{0} & = i_{0} \\ \end{array}\right.\right) \end{align} \]

Continuing likewise

\[ \mathbb {P}\left(\left. \begin{array}{rl} X_{n-1} & = i_{n-1} \\ X_{n-2} & = i_{n-2} \\ \cdots & \cdots \\ X_{0} & = i_{0} \\ \end{array}\right.\right) = \left(\mathbf{P}_{n-2}\right)_{i_{n-2},i_{n-1}} \quad \cdot \quad \mathbb {P}\left(\left. \quad \begin{array}{rl} X_{n-2} & = i_{n-2} \\ \cdots & \cdots \\ X_{0} & = i_{0} \\ \end{array}\right.\right) \]

At the end we get \(\mathbb {P}\left(X_0 = i_0\right) = \Pi^{(0)}_{i_0}\). In the end we obtain the formula

\[ \mathbb {P}\left(\left. \begin{array}{rl} X_{n} & = i_{n} \\ X_{n-1} & = i_{n-1} \\ X_{n-2} & = i_{n-2} \\ \cdots & \cdots \\ X_{0} & = i_{0} \\ \end{array}\right.\right) = \begin{array}{cc}& \left(\mathbf{P}_{n-1}\right)_{i_{n-1},i_n} \times \\ \times & \left(\mathbf{P}_{n-2}\right)_{i_{n-2},i_{n-1}} \times \\ & \vdots \\ \times & \left(\mathbf{P}_{0}\right)_{i_{0},i_{1}} \times \\ \times & \Pi ^{(0)}_{i_0} \\ \end{array} \]

For a homogeneous DTMC the formula simplifies:

\[ \mathbb {P}\left(\left. \begin{array}{rl} X_{n} & = i_{n} \\ X_{n-1} & = i_{n-1} \\ X_{n-2} & = i_{n-2} \\ \cdots & \cdots \\ X_{0} & = i_{0} \\ \end{array}\right.\right) = (\mathbf{P})_{i_{n-1}, i_{n}} \cdot \ldots \cdot (\mathbf{P})_{i_{0}, i_{1}} \cdot \Pi ^{(0)}_{i_0} \]

Example 2

Under the assumptions of the previous example, compute \[ \mathbb {P}\left(\begin{array}{rl} X_{4} & = 3 \\ X_{3} & = 2 \\ X_{2} & = 4 \\ X_{1} & = 2 \\ X_{0} & = 1 \\ \end{array}\right) \]

Solution

We have \[ \begin{align} \mathbb {P}\left(\begin{array}{rl} X_{4} & = 3 \\ X_{3} & = 2 \\ X_{2} & = 4 \\ X_{1} & = 2 \\ X_{0} & = 1 \\ \end{array}\right) & = \begin{array}{r} \mathbb {P}\left(X_4 = 3 \mid X_3 = 2\right) \cdot \\ \cdot \mathbb {P}\left(X_3 = 2 \mid X_2 = 4\right) \cdot \\ \cdot \mathbb {P}\left(X_2 = 4 \mid X_1 = 2\right) \cdot \\ \cdot \mathbb {P}\left(X_1 = 2 \mid X_0 = 1\right) \cdot \\ \cdot \mathbb {P}\left(X_{0} = 1\right) \\ \end{array} = \\ & = 0.3 \cdot 0.4 \cdot 0.1 \cdot 0.5 \cdot 0.1 = 0.06 \% \end{align} \]

Additional material

Let us introduce additional notation for the (matrix of) transition probabilities from step \(k\) to step \(l\):

\[ \mathbf{P}_{k \to l} := \left(\mathbb {P}\left(X_l = j \mid X_{k} = i\right)\right)_{i,j \in \mathcal{X}} \]

In the old notation: \(\mathbf{P}_{k} = \mathbf{P}_{k \to k+1}\). Let us list the properties of transition probabilities.

Lemma 2 Let \(\mathbf{P}_{k \to l}\), \(0 \leq k \leq l\), be the transition probability matrices of some DTMC. Then

Each of the matrices is stochastic: all its entries are nonnegative and the entries in each row sum to \(1\).
\(\mathbf{P}_{k \to k} = E\) for any \(k \in \mathbb {Z}_+\). Namely, \(\left(\mathbf{P}_{k \to k}\right)_{i,j}= \delta_{i}^{j}\).
the Chapman-Kolmogorov equations hold: for any \(k<l<n, i, j \in \mathcal{X}\)

\[ \mathbf{P}_{k \to n} = \mathbf{P}_{k \to l} \cdot \mathbf{P}_{l \to n} \]

By this equality we mean the following

\[ \begin{align} \left(\mathbf{P}_{k \to n}\right)_{i,j} & = \sum _{i' \in \mathcal{X}} \left(\mathbf{P}_{k \to l}\right)_{i,i'} \\ & \quad \cdot \left(\mathbf{P}_{l \to n}\right)_{i',j} \end{align} \]

These properties are not only necessary but also sufficient for the existence, given functions with such properties, of a Markov chain with transition probabilities equal to these functions. This is the content of the existence theorem for Markov chains.

Theorem 1 Let \(\mathcal{X}\) be an at most countable set, let \(\Pi\) be a probability distribution on \(\mathcal{X}\), and let the matrices \(\mathbf{P}_{k \to l}\) satisfy the properties from lemma Lemma 2. Then there exists a DTMC with phase space \(\mathcal{X}\), initial distribution \(\Pi\), and transition probabilities \(\mathbf{P}_{k \to l}\).

For a homogeneous DTMC everything becomes simpler.

Theorem 2 Let \(\mathcal{X}\) be an at most countable set, let \(\Pi\) be a probability distribution on \(\mathcal{X}\), and let \(\mathbf{P}\) be some stochastic matrix of dimension \(\left|\mathcal{X}\right| \times \left|\mathcal{X}\right|\) (possibly infinite). Then there exists a homogeneous DTMC with phase space \(\mathcal{X}\), initial distribution \(\Pi\), and one-step transition probabilities \(\mathbf{P}\).

These theorems are a direct consequence of Kolmogorov’s extension theorem for constructing the distribution of a process. Recall that Kolmogorov’s theorem on the path space \(\mathcal{X}^{T}\) (in our case \(T = \mathbb {Z}_+\)) constructs a distribution \(\mathbb {P}\) with given finite-dimensional distributions, and the process itself can then be defined via projections: \(X_n := \pi_n\), \(\pi_n(f) := f(n)\), \(f \in \mathcal{X}^{\mathbb {Z}_+}\). This is called the canonical model.

In the theory of Markov chains one often needs, for a fixed one-step transition matrix \(\mathbf{P}\), to look at the chain under different initial distributions \(\Pi^{(0)}\). In the canonical model this can be realized as follows: for a given (single) matrix \(\mathbf{P}\) on the space \(\mathcal{X}^{\mathbb {Z}_+}\) (with the corresponding cylindrical sigma-algebra) construct at once a whole family of distributions \(\mathbb {P}_{\Pi }\), depending on the initial distribution \(\Pi = \Pi^{(0)}\), and then study the process built from the projections under different \(\Pi\). That is, the expression

\[ \mathbb {P}_{\Pi }\left(X_3 = 4\right) \]

denotes the probability that a Markov chain with initial distribution \(\Pi\) and transition matrix \(\mathbf{P}\) equals \(3\) at time \(3\). In particular, if the initial distribution is concentrated at a single state \(i\) (i.e. \(\Pi_j = \delta_i^j\), \(\Pi = (\ldots , 0,0,1,0,0,\ldots )\)), we use the notation

\[ \mathbb {P}_{i}\left(X_3 = 4\right) \]

This is consistent with the notation we used when studying the random walk.

From now on, unless stated otherwise, we consider only homogeneous chains.

States and the transition probabilities between them are conveniently depicted as a directed graph with weighted edges.

Example 3

Show that the various kinds of random walk given below are homogeneous Markov chains. Draw the states and transition probabilities.

The ordinary simple random walk;
With an absorbing barrier at \(1\);
With a reflecting barrier at \(1\);
With absorbing barriers at \(0\) and at \(5\).

Solution

A brief justification for why each is a Markov chain: each of the random walks given is defined by the formula

\[ S_{n+1} = S_{n} + \xi _n \]

where \(\xi_n\) either does not depend on \(S_1, S_2, \ldots , S_n\) at all (in part 1), or depends, but only on \(S_{n}\).

The simple random walk: the graph of states and transition probabilities, and the (infinite) transition probability matrix, \(q := 1-p\).

State graph of the simple random walk: to the right with probability p, to the left with probability 1−p.

\[ \mathbf{P} = \begin{pmatrix} & \cdots & -3 & -2 & -1 & 0 & 1 & 2 & 3 & \cdots \\ \vdots & \ddots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & ⋰ \\ -3 & \cdots & 0 & p & 0 & 0 & 0 & 0 & 0 & \cdots \\ -2 & \cdots & q & 0 & p & 0 & 0 & 0 & 0 & \cdots \\ -1 & \cdots & 0 & q & 0 & p & 0 & 0 & 0 & \cdots \\ 0 & \cdots & 0 & 0 & q & 0 & p & 0 & 0 & \cdots \\ 1 & \cdots & 0 & 0 & 0 & q & 0 & p & 0 & \cdots \\ 2 & \cdots & 0 & 0 & 0 & 0 & q & 0 & p & \cdots \\ 3 & \cdots & 0 & 0 & 0 & 0 & 0 & q & 0 & \cdots \\ \vdots & ⋰ & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{pmatrix} \]

The (infinite) transition probability matrix of the simple random walk, \(q := 1-p\).

The simple random walk with an absorbing barrier at \(1\). The player plays until their capital reaches \(1\).

The simple random walk with an absorbing barrier at state 1: once the chain reaches 1, it stays there forever.

The simple random walk with a reflecting barrier at \(1\).

The simple random walk with a sticky (holding) barrier at state 1: from 1 the chain stays put with probability p and moves down with probability 1−p.

The simple random walk with absorbing barriers at \(0\) and at \(5\). The player plays until their capital hits zero or reaches \(5\).

The simple random walk with absorbing barriers at 0 and at 5 (the gambler plays until the fortune hits 0 or reaches 5).

The transition probability matrix for this walk (with p = 0.6, q = 1-p = 0.4 – specific values chosen for illustration).

Example 4

Show that the Galton-Watson process is a homogeneous Markov chain. Draw the states and transition probabilities for the Galton-Watson branching process with offspring law

\(\operatorname {Bin}(1, 0.7) = \operatorname {Ber}(0.7)\);
\(\operatorname {Bin}(2, 0.7)\);
\(\operatorname {Pois}(\lambda )\). In which case is the number of states finite?

Solution

(1)

\(\operatorname {Bin}(1, 0.7) = \operatorname {Ber}(0.7)\): the number of states is finite.

A simple two-state chain: 1 is transient, 0 is absorbing.

(2)

\(\operatorname {Bin}(2, 0.7)\): the number of states is countable.

Transition probability graph of a Galton–Watson branching process with offspring law Bin(2, 0.7): state 0 is absorbing (extinction), and from state n the states 0,…,2n are reachable.

(3)

\(\operatorname {Pois}(\lambda )\): the number of states is countable.

The same transition probability graph for the offspring law Pois(λ): only some of the probabilities are shown – from state n any state ≥ 0 is reachable.

Problem 1

Let \(\left\{ X_{n}, n \in \mathbb {Z}_{+}\right\}\) be a Markov chain with phase space \(\mathcal{X}= \left\{ 1,2,3\right\}\), initial state \(X_{0}=1\) a.s., and transition probability matrix

Transition probability graph of a three-state chain: all 9 transition probabilities are shown (including the three self-loop probabilities).

Write down the transition probability matrix \(\mathbf{P}\).
Suppose the initial distribution is:

\[ \mathbb {P}\left(X_0 = k\right) = \begin{cases} 0.5, & k = 1\\ 0.3 & k = 2 \\ 0.2 & k = 3 \end{cases} \]

Find the probability \(\mathbb {P}\left(X_{4} = 2\right)\).

Compute \(\mathbf{P}^{10}\). What do its rows look like?
Let

\[ Y_{n} = \begin{cases} 1, & X_n = 1 \\ 2, & X_n \in \left\{ 2,3\right\} \end{cases} \]

Prove that \(Y_{n}\) is also a Markov chain, and find its transition matrix.

Use a computer to raise the matrix to a power.

Example 5

Let \((X_n)\) be a Markov chain, let \(f: \mathcal{X} \to \mathcal{Y}\) be some function on the phase space, and let \(Y_n = f(X_n)\), \(n \geq 0\).

Show that if \(f\) is injective (does not glue points together), then \(Y_n\) is also a Markov chain.
Give an example of a DTMC \(X_n\) and a function \(f\) (respectively, non-injective) such that \(Y_n = f(X_n)\) is not a Markov chain.

Solution

(1)

If \(f\) is injective, the values of \(X_n\) can be uniquely recovered from the values of \(Y_n\). Namely, without loss of generality we can set \(\mathcal{Y} := \operatorname {Im}f\). Then \(f\) becomes bijective and \(X_{n} = f^{-1}(Y_n)\). We have

\[ \begin{align} \mathbb {P}\left(Y_{n+1} = r_{n+1} \quad \left| \quad \begin{array}{rl} Y_{n} & = r_{n} \\ Y_{n-1} & = r_{n-1} \\ \cdots & \cdots \\ Y_{0} & = r_{0} \\ \end{array}\right.\right) & = \mathbb {P}\left(X_{n+1} = f^{-1}(r_{n+1}) \quad \left| \quad \begin{array}{rl} X_{n} & = f^{-1}(r_{n}) \\ X_{n-1} & = f^{-1}(r_{n-1}) \\ \cdots & \cdots \\ X_{0} & = f^{-1}(r_{0}) \\ \end{array}\right.\right) = \\ & =\mathbb {P}\left(X_{n+1} = f^{-1}(r_{n+1}) \mid X_{n} = f^{-1}(r_{n})\right) = \\ & = \mathbb {P}\left(Y_{n+1} = r_{n+1} \mid Y_{n} = r_{n}\right) \end{align} \]

(2)

Consider a DTMC with the following transition probabilities:

EVOLUTION OF THE DISTRIBUTION π_t t = 0

INITIAL DISTRIBUTION π₀ Σ = 1.000

−1

speed

show the stationary distribution π*

π* =−1 · 16.7%0 · 33.3%1 · 33.3%2 · 16.7%

the chain has period 2, so π_t does not converge to π*; its Cesàro average converges to it instead (dashed line on the plot)

Interactive: evolution of the distribution of a discrete-time Markov chain on the states −1, 0, 1, 2. Set the initial distribution π₀ with the slider bars or as numbers (values are normalized automatically when you press “Play”/“Step”/“Reset”) or choose a preset: node size and fill show the current π_t = π₀Pᵗ, and the plot below shows the trajectories of π_t(s) over time. The checkbox shows the stationary distribution π: the chain has period 2, so π_t oscillates and only its Cesàro average converges to π (dashed lines).

Let \(f(x) = x^2\). Then the event \(Y_{2} = 0\) conditioned on \(Y_{1} = 1\), \(Y_{0} = 4\) is uniquely recovered:

\[ \begin{align} \left\{ Y_1 = 1, Y_0 = 4\right\} & = \left\{ X_{1} = 1, X_{0} = 2\right\} \\ \mathbb {P}\left(Y_{2} = 0 \mid Y_1 = 1, Y_0 = 4\right) & = \mathbb {P}\left(Y_2 = 0 \mid X_{1} = 1, X_{0} = 2\right) = \\ & = \mathbb {P}\left(X_{2} = 0 \mid X_{1} = 1, X_{0} = 2\right) = \frac{1}{2} \end{align} \]

On the other hand, the event \(Y_{2} = 0\) conditioned on \(Y_{1} = 1\), \(Y_{0} = 0\) is not uniquely recovered:

\[ \left\{ Y_1 = 1, Y_0 = 0\right\} = \left\{ X_{1} = 1, X_{0} = 0\right\} \sqcup \left\{ X_{1} = -1 , X_{0} = 0\right\} \]

The probability:

\[ \begin{align} \mathbb {P}\left(Y_{2} = 0 \mid Y_1 = 1, Y_0 = 0\right) & = \begin{array}{l} \mathbb {P}\left(X_{2} = 0 \mid X_1 = 1\right) \cdot \\ \cdot \mathbb {P}\left(X_{1} = 1 \mid X_{0} = 0\right) \end{array} + \begin{array}{l} \mathbb {P}\left(X_{2} = 0 \mid X_1 = -1\right) \cdot \\ \cdot \mathbb {P}\left(X_{1} = -1 \mid X_{0} = 0\right) \end{array} = \\ & = \frac{1}{2} \cdot \frac{1}{2} + 1 \cdot \frac{1}{2} = \frac{3}{4} \end{align} \]

In the end we get

\[ \mathbb {P}\left(Y_{2} = 0 \mid Y_1 = 1, Y_0 = 4\right) \neq \mathbb {P}\left(Y_{2} = 0 \mid Y_1 = 1, Y_0 = 0\right), \]

a violation of the Markov property.

Problem 2

Let \(\left\{ \xi_{n}, n \in \mathbb {N}\right\}\) be i.i.d. random variables with values in \(\mathbb {Z}\), with probability mass function \(p(x) := \mathbb {P}\left(\xi_i = x\right)\), positive for all \(x \in \mathbb {Z}\). Determine whether the following random sequences are Markov chains:

\(\xi =\left(\xi_{n}, \; n \in \mathbb {N}\right)\);
\(S_{n}=\xi_{1}+\ldots +\xi_{n}, \; n \in \mathbb {Z}_{+}\), where \(S_{0}=0\);
\(S^{+}_{n} := S_{n} \cdot \; \mathbb {1}_{S_{n} \geq 0}, \; n \in \mathbb {Z}_{+}\);
\(M_{n} := \max \left\{ S_{0}, \ldots , S_{n}\right\} , \; n \in \mathbb {Z}_{+}\). For those that turn out to be Markov chains, give the one-step transition probabilities.

3 Finite number of states

Throughout this section the phase space is assumed to be finite.

3.1 Communicating states

In the theory of Markov chains, states \(i,j \in \mathcal{X}\) are called communicating if they are strongly connected in the transition graph: it is possible with positive probability (in some finite number of steps) to go from \(i\) to \(j\) and from \(j\) to \(i\). The strongly connected components are called communicating classes.

A state is called transient if it is possible to leave this state and, with some positive probability, never return to it. Otherwise, i.e. when starting from the state one returns to it eventually with probability \(1\), the state is called recurrent.

Lemma 3

Within the same class all states are either simultaneously recurrent or simultaneously transient. In other words, each communicating class is either entirely recurrent or entirely transient.
Determining the type of a class (recurrent/transient) is simple: if the class is closed, i.e. there are no transitions out of it, then it is recurrent. Otherwise it is transient. ¹

Example 6

The (one-step) transition probabilities of some Markov chain are given as a graph.

Transition probability graph of a Markov chain (the vertices are deliberately left unlabeled — the task is to determine the communicating classes and their type on your own).

Determine the communicating classes of states.
For each class, determine whether it is recurrent or not.
Number the classes so that the transient ones come first, followed by the recurrent ones. Moreover, number the transient ones so that transitions are only possible from a smaller to a larger number.
Number the vertices. Write down the transition matrix of this chain.

Solution

The same graph with numbered states and highlighted communicating classes: I, II are transient, III, IV, V are recurrent.

The transient classes (I, II) are shaded in yellow-orange tones, and the recurrent classes (III, IV, V) in blue tones; the border color of each vertex reflects this same division.

The full transition matrix P in the canonical numbering of the states from the example above. Color highlights only the diagonal blocks corresponding to communicating classes: yellow and orange are the transient classes {1,2,3} and {4,5}; blue, teal, and purple are the recurrent (closed) classes {6,7,8}, {9}, and {10,11,12,13}. Hover over a cell to see the transition probability.

Why the \(2 \times 2\) blocks in the lower-right submatrix (shown in teal, corresponding to class V) are highlighted will become clear a bit later.

The numbering of states obtained in the example above is called canonical. This is a numbering under which the transition matrix has the block form \[ \mathbf{P} = \left( \begin{array}{c|c} \mathbf{T}_{11} & \mathbf{T}_{12} \\ \hline \mathbf{0} & \mathbf{T}_{22} \end{array} \right) \]

Block form of the transition matrix under the canonical numbering of states: \(\mathbf{T}_{11}\) is the transitions within and between transient classes, \(\mathbf{T}_{12}\) is the transitions from transient classes into recurrent ones, \(\mathbf{T}_{22}\) is the transitions within recurrent classes, and \(\mathbf{0}\) is the block accounting for the (impossible) transitions from recurrent classes into transient ones. The block sizes depend on the specific chain, so the matrix is shown schematically.

\(\mathbf{T}_{11}\) is responsible for transitions within transient classes and between transient classes. Let \(r\) be the number of transient classes. Then \(\mathbf{T}_{11}\) is a square matrix with block structure

\[ \mathbf{T}_{11} = \begin{pmatrix} \mathbf{P}_{11} & \mathbf{P}_{12} & \cdots & \mathbf{P}_{1r} \\ \mathbf{0} & \mathbf{P}_{22} & \cdots & \mathbf{P}_{2r} \\ \vdots & \ddots & \ddots & \vdots \\ \mathbf{0} & \cdots & \mathbf{0} & \mathbf{P}_{rr} \\ \end{pmatrix} \]

The matrix is upper triangular (viewed block-wise). Under the canonical numbering, transitions are only possible from a transient class of smaller number to one of larger number.
\(\mathbf{T}_{12}\) is responsible for transitions from transient classes to recurrent ones. Let \(m\) be the total number of classes. Then \(\mathbf{T}_{12}\) has the form

\[ \mathbf{T}_{12} = \begin{pmatrix} \mathbf{P}_{1,r+1} & \cdots & \mathbf{P}_{1m} \\ \vdots & \cdots & \vdots \\ \mathbf{P}_{r,r+1} & \cdots & \mathbf{P}_{rm} \\ \end{pmatrix} \]
\(\mathbf{T}_{22}\) is responsible for transitions within recurrent classes (transitions between recurrent classes are impossible by definition). It has block form

\[ \mathbf{T}_{22} = \begin{pmatrix} \mathbf{P}_{r+1,r+1} & \mathbf{0} & \mathbf{0} & \cdots & \mathbf{0} \\ \mathbf{0} & \mathbf{P}_{r+1,r+1} & \mathbf{0} & \cdots & \mathbf{0} \\ \vdots & \cdots & \cdots & \cdots & \vdots \\ \mathbf{0} & \mathbf{0} & \cdots & \mathbf{P}_{m-1,m-1} & \mathbf{0} \\ \mathbf{0} & \mathbf{0} & \cdots & \mathbf{0} & \mathbf{P}_{mm} \\ \end{pmatrix} \]

Any DTMC with a finite number of states can be brought to this form.

3.2 Limiting behavior

We are interested in the behavior of the chain as \(n\) grows. As we have already established, the distribution at step \(n\) is given by \(\Pi^{(n)} = \Pi^{(0)} \cdot \mathbf{P}^n\). Let us examine the behavior of the matrices \(\mathbf{P}^n\) as \(n\) grows, as well as the sequence of arithmetic means

\[ \frac{1}{n}\left(\mathbf{P}^0 + \mathbf{P}^1 + \ldots + \mathbf{P}^{n-1}\right) \]

(\(\mathbf{P}^0 = E\)).

We say the sequence of matrices \(\mathbf{P}^0, \mathbf{P}^1, \mathbf{P}^2, \ldots\) converges if each of its entries converges. We say the same sequence is Cesàro summable (Cesàro convergent) if the sequence of arithmetic means \(\frac{1}{n}\left(\mathbf{P}^0 + \mathbf{P}^1 + \ldots + \mathbf{P}^{n-1}\right)\) has an entrywise limit.

Recall that if a numerical sequence converges (in the ordinary sense), it also converges in the Cesàro sense, with the same limit. However, Cesàro convergence is a more general notion. For example, the sequence \(1,0,1,0,1,0, \ldots\) does not converge, yet the sequence of arithmetic means

\[ \frac{1}{1}, \frac{1}{2}, \frac{2}{3}, \frac{2}{4}, \frac{3}{5}, \frac{3}{6}, \ldots , \frac{n}{2n}, \frac{n+1}{2n+1}, \ldots \]

converges to \(\frac{1}{2}\). That is, the sequence is Cesàro summable. It is therefore convenient to first study the Cesàro limit, and then the ordinary limit.

Let us look at heat maps of the sequences \(\mathbf{P}^n\) and \(\frac{1}{n}(\mathbf{P}^0 + \ldots + \mathbf{P}^{n-1})\) for the example above.

Animation of the evolution of Pⁿ for n = 0,1,2,…,40 (the same matrix as in the example above). Use the slider or the Play button to track how the matrix entries change as n grows.

The limit lim Pⁿ (to 2 decimal places, where it exists). The diagonal blocks of the transient classes {1,2,3}, {4,5} tend to zero (the chain leaves the transient states almost surely). The block of the recurrent class {6,7,8} and the absorbing state {9} converge to their stationary values. But for the periodic (period 2) class {10,11,12,13}, as well as for all transitions from transient states into this class, the limit of Pⁿ does not exist – the matrix merely oscillates between two limit points as n grows (see also the animation above and the Cesàro limit below, which always exists).

Animation of the evolution of the Cesàro averages Cₙ = (1/n)(P⁰+P¹+…+Pⁿ⁻¹) for the same transition matrix P. Unlike Pⁿ (see the animation above), this sequence converges entrywise as n → ∞ for all blocks of the matrix, including the periodic recurrent class {10,11,12,13}.

The Cesàro limit lim(1/n)·(P⁰+P¹+…+Pⁿ⁻¹) for the transition matrix P from the example above. Unlike the ordinary limit of Pⁿ, the Cesàro limit exists for all blocks – including the periodic recurrent class {10,11,12,13}. The values are computed exactly: for each recurrent class, the row of the limit coincides with its stationary distribution, and for transient states it is the absorption probability into the class multiplied by the stationary distribution within it.

As can be seen from the heat-map animations, some of the entries of the sequence \((\mathbf{P}^n, \; n \in \mathbb {Z}_+)\) converge, while others do not. At the same time \((\mathbf{P}^n, \; n \in \mathbb {Z}_+)\) is Cesàro summable. In fact, \(\mathbf{P}^n\) will always be Cesàro summable. See below.

What is the probabilistic meaning of the Cesàro limit? Let us examine \(\frac{1}{n}\sum_{k=0}^{n-1}\mathbf{P}^{k}\). Its \(i,j\) entry equals

\[ \begin{align} \left(\frac{1}{n}\sum _{k=0}^{n-1}\mathbf{P}^{k}\right)_{ij} & = \frac{1}{n}\bigg(\mathbb {P}_{i}\left(X_{0} = j\right) + \mathbb {P}_{i}\left(X_{1} = j\right) + \ldots + \mathbb {P}_{i}\left(X_{n-1} = j\right)\bigg) = \\ & = \frac{1}{n} \bigg( \mathbb {E}_{i}\left[\; \mathbb {1}_{X_{0} = j}\right] + \mathbb {E}_{i}\left[\; \mathbb {1}_{X_{1} = j}\right] + \ldots + \mathbb {E}_{i}\left[\; \mathbb {1}_{X_{n-1} = j}\right] \bigg) = \\ & = \mathbb {E}_{i}\left[\frac{\; \mathbb {1}_{X_0 = j} + \; \mathbb {1}_{X_1 = j} + \ldots + \; \mathbb {1}_{X_{n-1} = j}}{n}\right] = \\ & = \mathbb {E}_{i}\left[\frac{1}{n} \sum _{k=0}^{n-1} \; \mathbb {1}_{X_k = j}\right] \end{align} \]

Let us introduce the notation:

\[ V^{(n)}_{j} := \left|\left\{ 0 \leq k \leq n \; : \; X_{k} = j\right\} \right| = \sum _{k=0}^{n} \; \mathbb {1}_{X_k = j} \]

The sum of indicators \(V^{(n-1)}_j = \sum_{k=0}^{n-1} \; \mathbb {1}_{X_k = j}\) is the number of visits (hence the letter \(V\)) to state \(j\) at times \(0, 1, \ldots , n-1\). Dividing by \(n\), i.e. by the total time, gives the visit frequency of state \(j\). Hence the \(i,j\) entry of the matrix \(\frac{1}{n}\sum_{k=0}^{n-1}\mathbf{P}^{k}\) is the expected visit frequency of state \(j\) over \(n\) steps, given that the chain started at state \(i\).

Note that (for fixed \(j\)) the process \(V^{(n)}_{j}, n \geq 0\) is almost a renewal process. Namely, let \(\tau^{(k)}_j\) be the time of the \(k\)-th visit to state \(j\). These can be defined inductively:

\[ \begin{align} \tau _{j}^{(1)} & := \min \left\{ n \geq 0 \; : \; X_n = j\right\} \\ \tau _{j}^{(k)} & := \min \left\{ n > \tau _{j}^{(k-1)} \; : \; X_n = j\right\} , \; k \geq 2 \end{align} \]

Additional material

Relation to the old notation from the random walk: \(\tau_j = \tau^{(1)}_j\) is the time of the first visit to \(j\), \[ T_j = \min \left\{ n \geq 1 \; : \; X_n = j\right\} = \begin{cases} \tau ^{(1)}_j, & X_0 \neq j \\ \tau ^{(2)}_j, & X_0 = j \end{cases} \] is the time of the first visit to \(j\) after step \(1\). Along the way, note that by definition state \(j\) is called recurrent if \[ \mathbb {P}_{j}\left(\tau ^{(2)}_j < \infty \right) = 1 \quad \text{or, equivalently, } \quad \mathbb {P}_{j}\left(T_j < \infty \right) = 1 \]

In this case \(V^{(n)}_j\) is a visit counter built from

\[ \begin{align} \xi ^{(1)}_j & := \tau _{j}^{(1)}, \\ & \quad \xi ^{(2)}_j := \tau _{j}^{(2)} - \tau _{j}^{(1)}, \\ & \quad \xi ^{(3)}_j := \tau _{j}^{(3)} - \tau _{j}^{(2)}, \ldots \end{align} \]

We have already studied such processes in detail, renewal processes in particular. Let’s try to apply what we know!

Recall that in the definition of a renewal process we required \(\xi_1, \xi_2, \ldots\) to be nonnegative i.i.d. random variables with a nondegenerate distribution. We need to understand how \(\xi^{(1)}_j, \xi^{(2)}_j, \xi^{(3)}_j, \ldots\) are distributed. Are they i.i.d.?

What follows is a slightly informal argument, since writing it out formally would be long and tedious, and after all these are seminar notes rather than lecture notes. The Markov property: the process, upon entering state \(j\), forgets its previous behavior. Hence, for any initial distribution \(\Pi\) (i.e. under any \(\mathbb {P}_{\Pi }\)) these random variables are independent. Moreover, again due to the Markov property, \(\xi^{(2)}_j, \xi^{(3)}_j, \ldots\) will be identically distributed (and this distribution also does not depend on \(\Pi\), since it is characterized only by the fact that the process has entered state \(j\) at some fixed step, and hence it no longer matters how it got there). The distribution of \(\xi^{(1)}_j = \tau^{(1)}_j\), however, may differ from the rest. For example, if the process a.s. starts at \(j\), i.e. \(\Pi_i = \delta_i^j\), then \(\xi^{(1)}_j \equiv 0\),

\[ \mathbb {P}_{j}\left(\tau ^{(1)}_j = 0\right) = 1, \]

while \(\xi^{(2)}_j, \xi^{(3)}_j, \ldots\) will still have some nontrivial distribution.

So, \(\xi^{(1)}_j, \xi^{(2)}_j, \xi^{(3)}_j, \ldots\) are independent random variables, all identically distributed except for the first time. Recall that \(\tau^{(m)}_j = \xi^{(1)}_j + \ldots + \xi^{(m)}_j\). The process

\[ V^{(n-1)}_j = \max \left\{ m \geq 1 \; : \; \tau ^{(m)}_j \leq n-1\right\} = \sum _{k=0}^{n-1} \; \mathbb {1}_{X_k = j} , \qquad n \geq 1 \]

(the maximum over the empty set is taken to be \(0\)) is called a delayed renewal process.

What are the limiting properties of a delayed renewal process? It turns out that the elementary renewal theorem remains valid in many cases.

Theorem 3 (Elementary renewal theorem for a delayed process) Let \(\xi_1, \xi_2, \xi_3, \ldots\) be independent random variables with values in \([0, +\infty ]\), where \(\xi_2, \xi_3, \ldots\) are identically distributed and \(\mathbb {E}\left[\xi_2\right] > 0\). Then, if \(\mathbb {P}\left(\xi_1 < \infty \right) = 1\), the delayed renewal process built from them, \(N_t = \max \left\{ n \; : \; \xi_1 + \ldots + \xi_n \leq t\right\}\), satisfies the elementary renewal theorem for the ordinary renewal process built from \(\xi_2, \xi_3, \ldots\): \[ \frac{\mathbb {E}\left[N_t\right]}{t} \xrightarrow [t \to +\infty ]{} \frac{1}{\mathbb {E}\left[\xi _2\right]} \]

See the proof in (Grimmett and Stirzaker 2020, Theorem 10.4.15).

Let us first consider some special cases.

3.3 Irreducible chains

A Markov chain is called irreducible if all its states form a single communicating class (which in this case must be closed). Studying a chain with more than one communicating class essentially reduces to studying its “restrictions” to the various classes.

One can show that if a chain is irreducible and has a finite number of states, then

\[ \mathbb {P}_{i}\left(\tau _j < \infty \right) = \mathbb {P}_{j}\left(T_j < \infty \right) = 1, \qquad \forall i,j \in \mathcal{X} \]

That is, from any state, any other state is reached in an a.s. finite time, and all states are recurrent. Such a chain is not transient².

Returning to the delayed renewal process, in this case we have

\[ \mathbb {P}_{i}\left(\xi ^{(1)}_j < \infty \right) = 1 \]

(recall that \(\xi^{(1)}_j = \tau^{(1)}_j = \tau_j\)). That is, starting at state \(i\), the process reaches state \(j\) a.s. in finite time. The counter overcomes the first barrier \(\xi^{(1)}_j\) a.s. in finite time. In this case, \(\xi^{(2)}_j, \xi^{(3)}_j, \ldots\) then come into play, which are i.i.d., so the limiting properties of the process are the same as for the ordinary renewal process built from \(\xi^{(2)}_j, \xi^{(3)}_j, \ldots\). In particular, the elementary renewal theorem holds:

\[ \begin{align} \left(\frac{1}{n}\sum _{k=0}^{n-1}\mathbf{P}^{k}\right)_{ij} & = \frac{1}{n} \cdot \mathbb {E}_{i}\left[ V^{(n-1)}_j\right] \quad \xrightarrow [n \to \infty ]{} \\ & \quad \frac{1}{\mathbb {E}_{i}\left[\xi ^{(2)}_j\right]} \end{align} \]

Note that \(\xi^{(2)}_j = \tau^{(2)}_j - \tau^{(1)}_j\) is the time between the first and second visit to \(j\). Since the process has already visited \(j\), by the Markov property its distribution, in particular the distribution of \(\xi^{(2)}_j\), does not depend on the initial distribution. In other words,

\[ \mathbb {E}_{i'}\left[\xi ^{(2)}_j\right] = \mathbb {E}_{i''}\left[\xi ^{(2)}_j\right] = \mathbb {E}_{j}\left[\xi ^{(2)}_j\right] \]

for all \(i', i'' \in \mathcal{X}\). And if the chain started at \(j\), then \(\tau^{(1)}_j \equiv 0\) and

\[ \xi ^{(2)}_j = \tau ^{(2)}_j - \tau ^{(1)}_j = \tau ^{(2)}_j = T_j \]

is the return time to state \(j\). This brings us to the theorem.

Theorem 4 Let \((X_n)\) be an irreducible DTMC with a finite number of states and transition matrix \(\mathbf{P}\). Then the matrices \(\mathbf{P}^0, \mathbf{P}^{1}, \ldots\) have a Cesàro limit: \[ \frac{1}{n}\sum _{k=0}^{n-1}\mathbf{P}^{k}\qquad \xrightarrow [n \to \infty ]{} \qquad \begin{pmatrix} \left(\mathbb {E}_{1}\left[T_1\right]\right)^{-1} & \left(\mathbb {E}_{2}\left[T_2\right]\right)^{-1} & \cdots & \left(\mathbb {E}_{\left|\mathcal{X}\right|}\left[T_{\left|\mathcal{X}\right|}\right]\right)^{-1} \\ \left(\mathbb {E}_{1}\left[T_1\right]\right)^{-1} & \left(\mathbb {E}_{2}\left[T_2\right]\right)^{-1} & \cdots & \left(\mathbb {E}_{\left|\mathcal{X}\right|}\left[T_{\left|\mathcal{X}\right|}\right]\right)^{-1} \\ \vdots & \vdots & \vdots & \vdots \\ \left(\mathbb {E}_{1}\left[T_1\right]\right)^{-1} & \left(\mathbb {E}_{2}\left[T_2\right]\right)^{-1} & \cdots & \left(\mathbb {E}_{\left|\mathcal{X}\right|}\left[T_{\left|\mathcal{X}\right|}\right]\right)^{-1} \end{pmatrix} \] That is, the limit does not depend on the row index \(i\), but only on the column index \(j\), and equals the reciprocal of the mean return time to state \(j\).

3.4 Stationary distribution

For a homogeneous DTMC, an (initial) distribution \(\Pi\) is called stationary if it does not change with time, i.e.

\[ \Pi = \Pi \cdot \mathbf{P} \]

In essence this is a left eigenvector (i.e. a row vector) for the matrix \(\mathbf{P}\). Or, \(\Pi^T\) is a right eigenvector (column vector) for the matrix \(\mathbf{P}^T\). Note that the sum of all columns of the matrix \(\mathbf{P}\) itself equals the column of ones. That is, \((1,1,\ldots ,1)^T\) is a right eigenvector for the matrix \(\mathbf{P}\) with eigenvalue \(1\). The eigenvalues of \(\mathbf{P}\) and \(\mathbf{P}^T\) coincide, so for this eigenvalue there is also a left eigenvector. Moreover it can always be normalized, i.e. turned into a distribution. This brings us to the theorem.

Theorem 5 A DTMC with a finite number of states always has a stationary distribution.

How is the stationary distribution related to the Cesàro limit? Note that

\[ \begin{align} \Pi \cdot \left(\frac{1}{n}\sum _{k=0}^{n-1}\mathbf{P}^{k}\right) & = \frac{1}{n}\sum _{k=0}^{n-1}\Pi \cdot \mathbf{P}^{k} \\ & = \frac{1}{n}\sum _{k=0}^{n-1}\Pi = \Pi \end{align} \]

Suppose we have an irreducible chain, as in the previous section. Let us pass to the limit as \(n \to \infty\). We get

\[ \Pi \cdot \begin{pmatrix} \left(\mathbb {E}_{1}\left[T_1\right]\right)^{-1} & \left(\mathbb {E}_{2}\left[T_2\right]\right)^{-1} & \cdots & \left(\mathbb {E}_{\left|\mathcal{X}\right|}\left[T_{\left|\mathcal{X}\right|}\right]\right)^{-1} \\ \left(\mathbb {E}_{1}\left[T_1\right]\right)^{-1} & \left(\mathbb {E}_{2}\left[T_2\right]\right)^{-1} & \cdots & \left(\mathbb {E}_{\left|\mathcal{X}\right|}\left[T_{\left|\mathcal{X}\right|}\right]\right)^{-1} \\ \vdots & \vdots & \vdots & \vdots \\ \left(\mathbb {E}_{1}\left[T_1\right]\right)^{-1} & \left(\mathbb {E}_{2}\left[T_2\right]\right)^{-1} & \cdots & \left(\mathbb {E}_{\left|\mathcal{X}\right|}\left[T_{\left|\mathcal{X}\right|}\right]\right)^{-1} \end{pmatrix} = \Pi \]

Let us expand the left-hand side:

\[ \begin{pmatrix} \sum _{i=1}^{\left|\mathcal{X}\right|} \Pi _i \cdot \left(\mathbb {E}_{1}\left[T_1\right]\right)^{-1}, & \sum _{i=1}^{\left|\mathcal{X}\right|} \Pi _i \cdot \left(\mathbb {E}_{2}\left[T_2\right]\right)^{-1}, & \cdots , & \sum _{i=1}^{\left|\mathcal{X}\right|} \Pi _i \cdot \left(\mathbb {E}_{\left|\mathcal{X}\right|}\left[T_{\left|\mathcal{X}\right|}\right]\right)^{-1} \end{pmatrix} \]

But \(\sum_{i=1}^{\left|\mathcal{X}\right|} \Pi_i = 1\). In the end we obtain

\[ \begin{pmatrix} \left(\mathbb {E}_{1}\left[T_1\right]\right)^{-1} & \left(\mathbb {E}_{2}\left[T_2\right]\right)^{-1} & \cdots & \left(\mathbb {E}_{\left|\mathcal{X}\right|}\left[T_{\left|\mathcal{X}\right|}\right]\right)^{-1} \end{pmatrix} = \Pi \]

In other words, the Cesàro limit consists row by row precisely of stationary distributions! From this, incidentally, one can conclude that for an irreducible chain the stationary distribution can only be unique, since the limit is unique. In other words, the geometric multiplicity of the eigenvalue \(1\) for the matrix \(\mathbf{P}\) equals \(1\). Let us state the theorem.

Theorem 6 Let \((X_n)\) be an irreducible DTMC with a finite number of states and transition matrix \(\mathbf{P}\). Then its stationary distribution is unique and equals any row of the Cesàro limit of the matrices \(\mathbf{P}^0, \mathbf{P}^{1}, \ldots\).

3.5 Period of a state, ergodic chain

We have worked out in detail the Cesàro limit of the transition matrices \(\mathbf{P}^0, \mathbf{P}^1, \ldots\) for an irreducible DTMC with finitely many states. But what about the ordinary limit? It turns out this does not always exist.

Example 7

Consider class \(V\) from the example above as a separate chain:

Transition graph of an auxiliary 4-state chain with period 4: the class {1,3} and the class {2,4} alternate at every step, so the sequence P⁰, P¹, … has no ordinary (entrywise) limit, although the Cesàro limit exists.

Show that the sequence \(\mathbf{P}^0, \mathbf{P}^{1}, \mathbf{P}^{2}, \ldots\) has no limit.

Solution

We have \[ \mathbf{P} = \begin{pmatrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 0.6 & 0.3 \\ 0 & 1 & 0 & 0 \\ 0.3 & 0.7 & 0 & 0 \end{pmatrix} \] This matrix is block-structured: \[ \mathbf{P} = \begin{pmatrix} \mathbf{0} & \mathbf{A} \\ \mathbf{B} & \mathbf{0} \end{pmatrix} \] That is, \[ \mathbf{P}^2 = \begin{pmatrix} \mathbf{A}\mathbf{B} & \mathbf{0} \\ \mathbf{0} & \mathbf{B}\mathbf{A} \end{pmatrix}, \quad \mathbf{P}^{3} = \begin{pmatrix} \mathbf{0} & \mathbf{A}\mathbf{B}\mathbf{A} \\ \mathbf{B}\mathbf{A}\mathbf{B} & \mathbf{0} \end{pmatrix}, \quad \mathbf{P}^4 = \begin{pmatrix} (\mathbf{A}\mathbf{B})^2 & \mathbf{0} \\ \mathbf{0} & (\mathbf{B}\mathbf{A})^2 \end{pmatrix}, \quad \ldots \] There is no limit, since the zeros keep hopping around.

What is the issue with the chain above? It has periodic behavior: starting from any state, one can return to it only after an even number of steps. An even simpler example of such a chain is:

The simplest periodic chain with 2 states: deterministic transitions 1→2→1→…, with period 2.

Its transition matrix:

\[ \mathbf{P} = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \]

In this case

\[ \mathbf{P}^{2k} = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}, \qquad \mathbf{P}^{2k + 1} = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \]

It has no entrywise limit. However, it does have a Cesàro limit:

\[ \frac{1}{n}\sum _{k=0}^{n-1}\mathbf{P}^k \quad \xrightarrow [n \to \infty ]{} \quad \begin{pmatrix} 1/2 & 1/2 \\ 1/2 & 1/2 \end{pmatrix} \]

The period of state \(j\) (notation: \(d(j)\)) is the gcd of all step counts at which one can, with positive probability, return to \(j\) after leaving \(j\). In other words,

\[ d(j) := \operatorname {gcd} \left\{ k \geq 1 \; : \; \mathbb {P}_{j}\left(T_j = k\right) > 0\right\} \]

A state is called aperiodic if \(d(j) = 1\).

Lemma 4 The period, like recurrence, is a characteristic of the entire communicating class. That is, if \(i,j\) are communicating states, then \(d(i) = d(j)\).

In particular, all states of an irreducible chain have the same period. That is, one can speak of the period of the entire (irreducible) chain. For the chains above the period equals \(2\).

For an irreducible chain, periodicity arises, as we saw, when there is some nontrivial period (i.e. greater than \(1\)). It turns out that if an irreducible chain is aperiodic, then \(\mathbf{P}^{n}\) converges. An irreducible, aperiodic chain is called an ergodic chain.

Let us state the theorem.

Theorem 7 (The ergodic theorem) Let \((X_n)\) be an ergodic DTMC with a finite number of states. Then

its stationary distribution \(\Pi\) exists, is unique, and equals the reciprocals of the return times to the states:

\[ \Pi = \left(\frac{1}{\mathbb {E}_{1}\left[T_1\right]}, \quad \frac{1}{\mathbb {E}_{2}\left[T_2\right]}, \quad \cdots , \quad \frac{1}{\mathbb {E}_{|\mathcal{X}|}\left[T_{\left|\mathcal{X}\right|}\right]}\right) \]
The matrices \(\mathbf{P}^{n}\) converge, both in the ordinary sense and in the Cesàro sense, to the matrix whose rows all equal \(\Pi\):

\[ \lim _{n \to \infty }\mathbf{P}^n \quad = \quad \lim _{n \to \infty }\frac{1}{n}\sum _{k=0}^{n-1}\mathbf{P}^k \quad = \quad \begin{pmatrix} \Pi \\ \Pi \\ \vdots \\ \Pi \end{pmatrix} \]

The distribution \(\Pi\) from the ergodic theorem is itself called ergodic. Note that if \(\Pi^{(0)}\) is some other initial distribution, then

\[ \Pi ^{(0)} \cdot \mathbf{P}^{n} \quad \xrightarrow [n \to \infty ]{} \Pi ^{(0)} \cdot \begin{pmatrix} \Pi \\ \Pi \\ \vdots \\ \Pi \end{pmatrix} = \Pi \]

Corollary 1 (Sometimes this is also called the ergodic theorem) The limiting distribution of an ergodic chain always exists (i.e. \(X_n\) always converges in distribution), and it equals the ergodic distribution. In particular, the limiting distribution does not depend on the initial distribution of the chain \(\Pi^{(0)}\), but only on the transition matrix \(\mathbf{P}\), and equals its normalized left eigenvector corresponding to the eigenvalue \(1\).

An ergodic chain, as time goes on, effectively forgets where it started, stabilizing at the stationary distribution.

Example 8

Consider the DTMC \((X_n)\) from problem Problem 1.

Find all stationary distributions of the chain.
Is this chain irreducible? Is it ergodic? If so, find the ergodic distribution.
Find the limit of the sequence \(\mathbf{P}^0, \mathbf{P}^{1}, \mathbf{P}^{2}, \ldots\) in the ordinary sense and in the Cesàro sense (if they exist, of course).
Find the limit in distribution of \(X_n\), depending on the initial distribution \(\Pi^{0}\).
Find the mean return time \(\mathbb {E}_{i}\left[T_i\right]\) for each of the states \(i \in \mathcal{X}\).

Solution

(i)

Let us find all left eigenvectors for the matrix \(\mathbf{P}\) (for eigenvalue \(1\)):

\[ \Pi \cdot \begin{pmatrix} 3/7 & 3/7 & 1/7 \\ 1/11 & 2/11 & 8/11\\ 1/11 & 4/11 & 6/11 \end{pmatrix} = \Pi \]

We solve the homogeneous linear system

\[ \Pi \cdot \begin{pmatrix} -4/7 & 3/7 & 1/7 \\ 1/11 & -9/11 & 8/11\\ 1/11 & 4/11 & -5/11 \end{pmatrix} = \begin{pmatrix} 0 & 0 & 0 \end{pmatrix} \]

… The solution:

\[ \Pi = \alpha \begin{pmatrix} 91 & 209 & 363 \end{pmatrix}, \quad \alpha \in \mathbb {R} \]

We normalize to obtain a distribution:

\[ \Pi = \begin{pmatrix} \frac{91}{663} & \frac{209}{663} & \frac{363}{663} \end{pmatrix} \approx \begin{pmatrix} 13.73\% & 31.52\% & 54.75\% \end{pmatrix} \]

(ii)

All states communicate, so the chain is irreducible. Moreover, for instance, from state \(1\) one can return to itself in \(1\) step. Hence the gcd of the step counts at which one can return to \(1\) equals \(1\). So \(1\) is an aperiodic state. All states of the chain form a single communicating class, so the chain is aperiodic. It follows that it is ergodic (being irreducible and aperiodic). The ergodic distribution coincides with the stationary one, found in the previous part.

(iii)

By the ergodic theorem,

\[ \lim _{n \to \infty } \mathbf{P}^{n} = \lim _{n \to \infty } \frac{1}{n}\sum _{k=0}^{n-1}\mathbf{P}^k = \begin{pmatrix} \Pi \\ \Pi \\ \Pi \end{pmatrix} = \begin{pmatrix} \frac{91}{663} & \frac{209}{663} & \frac{363}{663} \\ \frac{91}{663} & \frac{209}{663} & \frac{363}{663}\\ \frac{91}{663} & \frac{209}{663} & \frac{363}{663} \end{pmatrix} \approx \begin{pmatrix} 13.73\% & 31.52\% & 54.75\% \\ 13.73\% & 31.52\% & 54.75\% \\ 13.73\% & 31.52\% & 54.75\% \end{pmatrix} \]

(iv)

By the ergodic theorem,

\[ X_n \xrightarrow [n \to +\infty ]{d} \Pi \]

The limiting distribution does not depend on the initial distribution.

(v)

By the ergodic theorem,

\[ \begin{cases} \mathbb {E}_{1}\left[T_1\right] = \frac{663}{91} \approx 7.3 \\ \mathbb {E}_{2}\left[T_2\right] = \frac{663}{209} \approx 3.2 \\ \mathbb {E}_{3}\left[T_3\right] = \frac{663}{363} \approx 1.8 \\ \end{cases} \]

Problem 3

Consider the DTMC \((Y_n)\) from problem Problem 1.

Find all stationary distributions of the chain.
Is this chain irreducible? Is it ergodic? If so, find the ergodic distribution.
Find the limit of the sequence \(\mathbf{P}^0, \mathbf{P}^{1}, \mathbf{P}^{2}, \ldots\) in the ordinary sense and in the Cesàro sense (if they exist, of course).
Find the limit in distribution of \(X_n\), depending on the initial distribution \(\Pi^{0}\).
Find the mean return time \(\mathbb {E}_{i}\left[T_i\right]\) for each of the states \(i \in \mathcal{X}\).

Hint

The transition matrix of \(Y_n\): \[ \mathbf{P} = \begin{pmatrix} 3/7 & 4/7\\ 1/11 & 10/11 \end{pmatrix} \]

Problem 4

Consider the DTMC \((X_n)\) from example Example 1. Recall its transition matrix: \[ \mathbf{P} = \begin{pmatrix} 0.5 & 0.5 & 0 & 0 \\ 0.3 & 0.3 & 0.3 & 0.1 \\ 0 & 0 & 1 & 0 \\ 0.4 & 0.4 & 0 & 0.2 \end{pmatrix} \]

Find all stationary distributions of the chain.
Is this chain irreducible? Is it ergodic? If so, find the ergodic distribution.
Find the limit of the sequence \(\mathbf{P}^0, \mathbf{P}^{1}, \mathbf{P}^{2}, \ldots\) in the ordinary sense and in the Cesàro sense (if they exist, of course).
Find the limit in distribution of \(X_n\), depending on the initial distribution \(\Pi^{(0)}\).
Find the mean return time \(\mathbb {E}_{i}\left[T_i\right]\) for each of the states \(i \in \mathcal{X}\).

Hint

You may renumber the states for clarity.

For an irreducible chain (with a finite number of states) there is a useful criterion for ergodicity (i.e. aperiodicity).

Lemma 5 (Frobenius’s aperiodicity criterion) Let \((X_n)_{n \geq 0}\) be an irreducible DTMC with a finite number of states. It is ergodic if and only if there exists \(m \in \mathbb {Z}\) such that in this many steps one can go from any state to any other with positive probability: \[ \mathbb {P}\left(X_{m} = j \mid X_{0} = i\right) > 0, \qquad \forall i,j \in \mathcal{X} \] In matrix terms: \[ \mathbf{P}^{m} > \mathbf{0} \quad \text{(entrywise comparison)} \]

See the proof in (Meyer 2001, 678).

Problem 5

An auto insurance company assigns each of its clients to one of three categories. The higher the category number \(i \in \{ 1,2,3\}\), the higher the price of the insurance \(c_{i}\). Let \(X_{n} \in \{ 1,2,3\}\) be the category number to which the client belongs at time \(n, n=0,1,2, \ldots\), and let \(Y_{n}\) be the number of accidents the client had in year \(n\). The value \(X_{n}, n \geq 1\), is determined based on \(X_{n-1}\) and \(Y_{n-1}\) using the table:

	0 accidents	1 accident	\(\geq 2\) accidents
category 1	1	2	3
category 2	1	3	3
category 3	2	3	3

Assume that the probabilities of having 0, 1, and \(\geq 2\) accidents in a year are \(p_{0}, p_{1}, p_{2}>0\), regardless of the past and of the year number \(n\). For simplicity let \(X_{0}=1\).

Let \(p_0 = \frac{1}{2}\), \(p_{1} = \frac{1}{3}\), \(p_2 = \frac{1}{6}\). Find the expected price of the insurance at time \(n\).
Does the limit of \(X_{n}\) as \(n \rightarrow \infty\) exist in the sense of convergence in distribution?
Does the limit of the expected insurance price exist? If so, find it.

Problem 6

Let \(\left(\xi_{n}, n \in \mathbb {Z}_{+}\right)\) be i.i.d. random variables with values in \(\left\{ 0,1,2,3\right\}\) and the following distribution: \[ \begin{align} \mathbb {P}\left(\xi _{n}=0\right) & = \frac{1}{7}, & \quad \mathbb {P}\left(\xi _{n}=1\right) & = \frac{2}{7}, \\ \mathbb {P}\left(\xi _{n}=2\right) & = \frac{3}{7}, & \quad \mathbb {P}\left(\xi _{n}=3\right) & = \frac{1}{7} \end{align} \] Consider the processes \[ \begin{align} X_{0} = 0, X_{n} & = \xi _{1} + \ldots + \xi _{n} \; \pmod{4}, n \geq 1 \\ Y_{0} = 1, Y_{n} & = \xi _{1} \cdot \ldots \cdot \xi _{n} \; \pmod{4}, n \geq 1 \end{align} \] \(n \in \mathbb {N}\). Prove that \(\left(X_{n}, \; n \in \mathbb {N}\right)\) and \(\left(Y_{n}, \; n \in \mathbb {N} \right)\) are homogeneous Markov chains, and find their limiting distributions, depending on the initial one.

3.6 Limiting and stationary distributions: the general case

Let us now consider chains consisting of several communicating classes.

Problem 7

Consider the large DTMC \((X_n)\) from example Example 6.

Find all stationary distributions of the chain.
Is this chain irreducible? Is it ergodic? If so, find the ergodic distribution.
Find the limit of the sequence \(\mathbf{P}^0, \mathbf{P}^{1}, \mathbf{P}^{2}, \ldots\) in the ordinary sense and in the Cesàro sense (if they exist, of course).
Find the limit in distribution of \(X_n\), depending on the initial distribution \(\Pi^{0}\).
Find the mean return time \(\mathbb {E}_{i}\left[T_i\right]\) for each of the states \(i \in \mathcal{X}\).

To find the limits of \(\mathbf{P}^{0}, \mathbf{P}^{1}, \ldots\), you may use the results obtained above.

Problem 8

Prove that for any DTMC (even an infinite one, looking ahead) the sequence \(\mathbf{P}^{0}, \mathbf{P}^1, \ldots\) converges in the Cesàro sense. What is the probabilistic meaning of the limit \[ \lim _{n \to \infty } \left(\frac{1}{n} \sum _{k=0}^{n-1} \mathbf{P}^k\right)_{ij} \] for arbitrary states \(i,j \in \mathcal{X}\)? Namely, write down a formula for this limit in terms of probabilities and expectations. In particular, what is the probabilistic meaning of the numbers in the upper-right corner of the Cesàro limit for the large Markov chain (with 13 states) from the example above?

What do you think is the equivalent condition on the chain for the sequence \(\mathbf{P}^{0}, \mathbf{P}^1, \ldots\) to have an ordinary limit? Under what condition does the chain converge in probability?

Hint

Apply the elementary renewal theorem for delayed renewal processes (theorem Theorem 3).

4 Countably many states

The definitions for a DTMC with finitely many states carry over to a DTMC with countably many states: communicating states, classes of states, irreducible chains, recurrent/transient states, the period of a state, etc. Moreover, as in the finite case, recurrence and period are properties that are preserved within a given communicating class.

Example 9

For the various kinds of simple random walk on a countable number of states from example Example 3 (parts 1, 2, 3), determine the communicating classes, their recurrence, and their period.

Solution

(1)

The ordinary simple random walk with step probability \(+1\) equal to \(p \in [0,1]\):

The ordinary simple random walk with step +1 probability equal to p ∈ [0,1] (and step −1 probability 1−p).

If \(p = 1\), then no state communicates with any other; each state forms its own class, and all states are transient. The same holds when \(p = 0\).

If \(p \in (0,1)\), then all states communicate, the chain is irreducible (consists of a single class), and the period equals \(2\). Moreover, if \(p = \frac{1}{2}\), then (as we proved earlier for random walks) \(\mathbb {P}_{0}\left(T_0 < \infty \right) = 1\), i.e. the chain is recurrent. Note, however, that \(\mathbb {E}_{0}\left[T_0\right]\) is still \(+\infty\), as for a transient state.

If \(p \in (0,1)\), \(p \neq \frac{1}{2}\), then the chain is transient.

(2)

Absorbing barrier at \(1\):

The simple random walk with an absorbing barrier at state 1: from state 0 the transition to 1 occurs with probability p, after which the chain stays at 1 forever.

The case \(p = 1\) or \(0\) is not very interesting.

Let \(p \in (0,1)\). Then the chain splits into \(2\) classes: \(\left\{ 1\right\}\) and \(\left\{ 0, -1,-2,\ldots \right\}\). The first class is, of course, recurrent, consisting of a single (absorbing) state. The second class is transient, since state \(0\) is transient: with probability \(p\) one can move to \(1\) and never return from there.

Period of class \(\left\{ 1\right\}\): \(1\). Period of class \(\left\{ 0,-1,\ldots \right\}\): \(2\).

(3)

Reflecting barrier at \(1\):

The simple random walk with a sticky (holding) barrier at state 1: from state 1 the chain stays put with probability p and moves down with probability 1−p.

This chain is very similar to the previous one. Again, we will not consider \(p=0,1\); you can work this out yourself. If \(p \in (0,1)\), then the chain consists of a single class, i.e. it is irreducible. Let us determine recurrence.

\[ \begin{align} \mathbb {P}_{1}\left(T_1 < \infty \right) & = \underbrace{\mathbb {P}_{1}\left(T_1 < \infty \mid S_{1} = 1\right)}_{=1} \cdot \mathbb {P}\left(S_{1} = 1\right) \\ & \quad + \underbrace{\mathbb {P}_{1}\left(T_1 < \infty \mid S_{1} = 0\right)}_{=\mathbb {P}_{0}\left(T_1 < \infty \right), \text{ Markov prop.}} \cdot \; \mathbb {P}\left(S_{1} = 0\right) = \\ & = p + \mathbb {P}_{0}\left(T_{1} < \infty \right) \cdot (1-p)\\ \mathbb {E}_{1}\left[T_1\right] & = \underbrace{\mathbb {E}_{1}\left[T_1 \mid S_{1} = 1\right]}_{=1} \cdot \mathbb {P}\left(S_{1} = 1\right) \\ & \quad + \underbrace{\mathbb {E}_{1}\left[T_1 \mid S_{1} = 0\right]}_{=1 + \mathbb {E}_{0}\left[T_1\right], \text{ Markov prop.}} \cdot \; \mathbb {P}\left(S_{1} = 0\right) = \\ & = p + \left(1 + \mathbb {E}_{0}\left[T_{1}\right]\right) \cdot (1-p) = 1 + (1-p)\mathbb {E}_{0}\left[T_1\right] \end{align} \]

The distribution of the random variable \(T_1\) (under the measure \(\mathbb {P}_0\)) is the same as for the ordinary random walk. We have computed it:

if \(p > \frac{1}{2}\), then \(\mathbb {P}_{0}\left(T_1 < \infty \right) = 1\) and \(\mathbb {E}_{0}\left[T_1\right] < \infty\). Hence \(\mathbb {P}_{1}\left(T_1 < \infty \right) = 1\) and \(\mathbb {E}_{1}\left[T_1\right] < \infty\), the chain is recurrent (even positive recurrent, see the definition below);
if \(p = \frac{1}{2}\), then \(\mathbb {P}_{0}\left(T_1 < \infty \right) = 1\), but \(\mathbb {E}_{0}\left[T_1\right] = \infty\). Hence \(\mathbb {P}_{1}\left(T_1 < \infty \right) = 1\), but \(\mathbb {E}_{1}\left[T_1\right] = \infty\). The chain is recurrent, though the mean return time is infinite;
if \(p < \frac{1}{2}\), then \(\mathbb {P}_{0}\left(T_1 < \infty \right) < 1\) and \(\mathbb {E}_{0}\left[T_1\right] = \infty\). Hence \(\mathbb {P}_{1}\left(T_1 < \infty \right) < 1\) and \(\mathbb {E}_{1}\left[T_1\right] = \infty\). The chain is transient.

In this example we can see differences between a DTMC with countably many states and the finite case:

The chain may have no closed class at all (the simple random walk with \(p = 1\)).
An infinite class (and hence the chain itself) can be transient and closed at the same time (the simple random walk with \(p \in (0,1)\), \(p \neq \frac{1}{2}\)).

This means that determining the recurrence of a class of states is now more complicated: if it is not closed, then, as before, it is transient; but if the class is closed, it can be either recurrent or transient (in the finite case it would necessarily be recurrent).
Moreover, even if a class is transient and not closed, the chain need not leave this class with probability \(1\) when starting from it (the random walk with an absorbing barrier at \(1\)). Recall that in the finite case, a chain starting from a transient (and not closed, respectively) class would leave it with probability \(1\) (at some finite time).
Even if a state is recurrent, the mean return time can be infinite, even though it is a.s. finite by the very definition of recurrence (the simple random walk with \(p = \frac{1}{2}\), the walk with a reflecting barrier at \(1\) and \(p = \frac{1}{2}\)). In the finite case the mean return time for a recurrent state was always finite.

In connection with the last point, a new definition is introduced: a recurrent state \(i\) (i.e. one such that \(\mathbb {P}_{i}\left(T_{i} < +\infty \right) = 1\)) is called

positive recurrent if \(\mathbb {E}_{i}\left[T_{i}\right] < +\infty\);
null recurrent if \(\mathbb {E}_{i}\left[T_{i}\right] = +\infty\).

Lemma 6 These characteristics (positive/null recurrence) are also preserved within a single communicating class.

Let us give a useful table, valid both in the finite and in the infinite case. See the proofs in (Grimmett and Stirzaker 2020, chap. 6).

	State \(j\) transient	State \(j\) recurrent
		Positive recurrent	Null recurrent
Equivalent condition via the return time \(T_j\)	\(\displaystyle \mathbb{P}_j\!\left(T_j = +\infty\right) > 0\)	\(\displaystyle \mathbb{P}_j\!\left(T_j = +\infty\right) = 0\)
		\(\displaystyle \mathbb{E}_j\!\left[T_j\right] < +\infty\)	\(\displaystyle \mathbb{E}_j\!\left[T_j\right] = +\infty\)
Equivalent condition via the transition matrix \(\mathbf{P}\). \(V_j = \left\|\{n \geq 0 : X_n = j\}\right\|\) is the total number of visits paid by the chain to state \(j\)	\(\displaystyle \underbrace{\sum_{n=0}^{+\infty} \left(\mathbf{P}^n\right)_{jj}}_{=\, \mathbb{E}_j[V_j]} < +\infty\)	\(\displaystyle \sum_{n=0}^{+\infty} \left(\mathbf{P}^n\right)_{jj} = +\infty\)
		\(\displaystyle \left(\mathbf{P}^n\right)_{jj} \not\to 0\)	\(\displaystyle \left(\mathbf{P}^n\right)_{jj} \xrightarrow[n \to \infty]{} 0\)
Equivalent condition via the number of returns	\(\displaystyle \mathbb{P}_j\!\left(X_n = j \text{ i.o.}\right) = 0\)	\(\displaystyle \mathbb{P}_j\!\left(X_n = j \text{ i.o.}\right) = 1\)
Equivalent condition via communicating classes (for a finite number of states)	\(j\) lies in a non-closed class (i.e. is inessential)	\(j\) lies in a closed class
For a chain with a finite number of states		At least one such state must exist	Does not exist
Some properties. Notation: \(f_{ij} = \mathbb{P}_i\!\left(T_j < \infty\right)\) is the probability of reaching \(j\) from \(i\) in finite time	\(\displaystyle \underbrace{\sum_{n=0}^{+\infty} \left(\mathbf{P}^n\right)_{ij}}_{\mathbb{E}_i[V_j]} < +\infty\) for all \(i\)	\(\displaystyle \sum_{n=0}^{+\infty} \left(\mathbf{P}^n\right)_{ij} = +\infty\) for all \(i\) such that \(f_{ij} > 0\)

Table 1: Summary of equivalent conditions for recurrence/transience and positive/null recurrence of a state (j) of a discrete-time Markov chain.

4.1 Irreducible chains

For a DTMC with transition matrix \(\mathbf{P}\), a stationary measure \(\Psi\) is a measure on \(\mathcal{X}\) (i.e. a row of nonnegative numbers indexed by \(\mathcal{X}\)) such that

\[ \Psi \cdot \mathbf{P} = \Psi \]

Theorem 8

An irreducible DTMC has a stationary distribution \(\Pi\) \(\iff\) it is positive recurrent. In this case the stationary distribution is unique and equals the reciprocal return times:

\[ \Pi _{i} = \frac{1}{\mathbb {E}_{i}\left[T_i\right]}, \qquad \forall i \in \mathcal{X} \]
If an irreducible chain is recurrent (either null recurrent or positive recurrent), then there exists a measure \(\Psi\) on \(\mathcal{X}\), unique up to multiplication by a constant, consisting entirely of positive values (\(\Psi_i > 0\) for all \(i \in \mathcal{X}\)). Moreover the chain is
- positive recurrent if \(\sum_{i \in \mathcal{X}}\Psi_{i} < +\infty\);
- null recurrent if \(\sum_{i \in \mathcal{X}}\Psi_{i} = +\infty\);
For an irreducible, aperiodic DTMC,

\[ \left(\mathbf{P}^{n}\right)_{ij} \xrightarrow [n \to \infty ]{} \frac{1}{\mathbb {E}_{j}\left[T_j\right]}, \qquad \forall i,j \in \mathcal{X} \]

That is, whatever the initial distribution \(\Pi^{(0)}\),

\[ \left(\Pi ^{(0)} \cdot \mathbf{P}^{n}\right)_j = \mathbb {P}_{\Pi ^{(0)}}\left(X_{n} = j\right) \xrightarrow [n \to \infty ]{} \frac{1}{\mathbb {E}_{j}\left[T_j\right]} \]

See the proof in (Grimmett and Stirzaker 2020, sec. 6.4).

Problem 9

Let \(\frac{1}{2} < p \leq 1\), \(q = 1 - p\). Consider the chain

An infinite chain ‘condensing’ toward zero: from state 0 there is a transition to ±1 with probability q and a self-transition with probability 1−2q; from any other state there is a transition toward zero with probability p and away from zero with probability q (here 1/2 < p ⩽ 1, q = 1−p).

Find \(\mathbb {E}_{i}\left[T_i\right]\) for each of the states \(i \in \mathcal{X}\) and all stationary distributions of the chain.
Is this chain irreducible? Ergodic? Positive recurrent?
Find the (entrywise) limit of the sequence \(\mathbf{P}^0, \mathbf{P}^{1}, \mathbf{P}^{2}, \ldots\) in the ordinary sense and in the Cesàro sense (if they exist, of course).
Find the limit in distribution of \(X_n\), depending on the initial distribution \(\Pi^{0}\).

Hint

From the theory of the random walk we know that in this case \(\mathbb {E}_{-1}\left[T_0\right] = \frac{1}{p-q}\).

Problem 10

In this problem all chains are assumed to be irreducible. Can there exist

a stationary distribution for a transient chain?
a stationary measure for a transient chain?
a stationary distribution for a null recurrent chain?
a stationary measure for a null recurrent chain?

4.2 Limiting properties in the general case

Let us assemble the overall picture of limiting behavior for an arbitrary (possibly countable, consisting of several classes) DTMC. The key is still the representation \(\left(\frac{1}{n}\sum_{k=0}^{n-1}\mathbf{P}^k\right)_{ij} = \frac{1}{n}\mathbb {E}_{i}\left[V^{(n-1)}_j\right]\) in terms of mean visit frequencies, and the elementary renewal theorem for delayed processes (theorem Theorem 3), applied carefully: now the first interval \(\xi^{(1)}_j = \tau_j\) can be infinite with positive probability.

Theorem 9 For any DTMC the Cesàro limit exists and equals \[ \lim _{n \to \infty } \left(\frac{1}{n} \sum _{k=0}^{n-1} \mathbf{P}^k\right)_{ij} = \frac{\mathbb {P}_{i}\left(\tau _j < \infty \right)}{\mathbb {E}_{j}\left[T_j\right]}, \qquad \forall i, j \in \mathcal{X} \] (with the convention \(\frac{1}{+\infty } = 0\)). In particular, the columns corresponding to transient and null recurrent states \(j\) are zero in the limit.

The idea: on the event \(\left\{ \tau_j = \infty \right\}\) there are no visits to \(j\) at all and the frequency is \(0\); on the event \(\left\{ \tau_j < \infty \right\}\) the argument for the delayed renewal process applies, giving frequency \(\frac{1}{\mathbb {E}_{j}\left[T_j\right]}\). The formula combines both cases. It also explains the upper-right corner of the Cesàro limit for the large chain from example Example 6: this is the probability of ever reaching the (recurrent) state \(j\) from the transient state \(i\), multiplied by the fraction of time \(\pi_j\) that the chain spends at \(j\) within its own class.

The ordinary (non-Cesàro) limit of \(\mathbf{P}^n\) exists if and only if every positive recurrent class is aperiodic: within a periodic class the diagonal entries \(\left(\mathbf{P}^n\right)_{jj}\) oscillate (vanishing for \(n\) not a multiple of the period), as we saw in the examples above. See the details in (Grimmett and Stirzaker 2020, chap. 6).

5 Proofs

5.1 Proof of lemma Lemma 1 (equivalence of forms of the Markov property)

Proof

(i)⟹(ii), induction on \(m\). Base case \(m=1\) is (i). Suppose (ii) holds for \(m-1\) for any \(n\). By the law of total probability:

\[ \begin{align} \mathbb {P}\left(X_{n+m}=i_{n+m}\mid X_n=i_n,\ldots ,X_0=i_0\right) & = \sum _{i_{n+1}} \\ & \quad \mathbb {P}\left(X_{n+m}=i_{n+m}\mid X_{n+1}=i_{n+1},X_n=i_n,\ldots ,X_0=i_0\right)\cdot \\ & \quad \cdot \mathbb {P}\left(X_{n+1}=i_{n+1}\mid X_n=i_n,\ldots ,X_0=i_0\right) \end{align} \]

The second factor, by (i), equals \(\mathbb {P}\left(X_{n+1}=i_{n+1}\mid X_n=i_n\right)\). The first is (ii) at level \(m-1\) with the “present” at \(n+1\), equal to \(\mathbb {P}\left(X_{n+m}=i_{n+m}\mid X_{n+1}=i_{n+1}\right)\). Altogether the sum \(=\sum_{i_{n+1}}\mathbb {P}\left(X_{n+m}=i_{n+m}\mid X_{n+1}=i_{n+1}\right)\mathbb {P}\left(X_{n+1}=i_{n+1}\mid X_n=i_n\right)\). The same computation (total probability + (i) + induction hypothesis), applied directly to \(\mathbb {P}\left(X_{n+m}=i_{n+m}\mid X_n=i_n\right)\), gives the very same sum. Hence the two expressions are equal — this is (ii) for \(m\).

(ii)⟹(i): the special case \(m=1\).

(ii)⟹(iii): it suffices to learn how to remove the earliest thinned-out point \(n_0\) from the condition (further points are removed one at a time by induction). By the law of total probability, inserting between \(n_0\) and \(n_1\) the full (non-thinned) path \(\mathbf c=(c_{n_0+1},\ldots ,c_{n_1-1})\):

\[ \mathbb {P}\left(X_{n_{k+1}}=i_{k+1}, X_{n_1}=i_1,X_{n_0}=i_0,\ldots \right) = \sum _{\mathbf c}\mathbb {P}\left(X_{n_{k+1}}=i_{k+1}, X_{n_1}=i_1, X_{n_1-1}=c_{n_1-1},\ldots ,X_{n_0+1}=c_{n_0+1}, X_{n_0}=i_0,\ldots \right) \]

For each term, the condition already contains the full history up to \(n_1\) — we apply (ii): the tail depends only on \(X_{n_1}=i_1\), the factor is taken out of the sum over \(\mathbf c\), and the remaining sum over \(\mathbf c\) is exactly \(\mathbb {P}\left(X_{n_1}=i_1,X_{n_0}=i_0,\ldots \right)\). After dividing, the dependence on \(i_0\) (and earlier points) cancels.

(iii)⟹(ii): the special case \(n_r=r\).

5.2 Proof of lemma Lemma 2 (properties of \(\mathbf{P}_{k\to l}\))

Proof

(1) Stochasticity. \(\left(\mathbf{P}_{k\to l}\right)_{ij}=\mathbb {P}\left(X_l=j\mid X_k=i\right)\ge 0\) is obvious; \(\sum_j\mathbb {P}\left(X_l=j\mid X_k=i\right)=\mathbb {P}\left(X_l\in \mathcal{X}\mid X_k=i\right)=1\).

(2) \(\left(\mathbf{P}_{k\to k}\right)_{ij}=\mathbb {P}\left(X_k=j\mid X_k=i\right)\): when \(i=j\) the probability is \(1\), when \(i\ne j\) the events are incompatible, giving probability \(0\). That is, \(=\delta_i^j\).

(3) Chapman-Kolmogorov. For \(k<l<n\), by the law of total probability and the Markov property (form (iii) of lemma Lemma 1):

\[ \begin{align} \left(\mathbf{P}_{k\to n}\right)_{ij}=\mathbb {P}\left(X_n=j\mid X_k=i\right) & = \sum _{i'}\mathbb {P}\left(X_n=j,X_l=i'\mid X_k=i\right) \\ & = \sum _{i'}\mathbb {P}\left(X_n=j\mid X_l=i',X_k=i\right)\cdot \mathbb {P}\left(X_l=i'\mid X_k=i\right) \\ & \overset {\text{Markov property}}{=} \sum _{i'}\mathbb {P}\left(X_n=j\mid X_l=i'\right)\cdot \mathbb {P}\left(X_l=i'\mid X_k=i\right) \\ & = \sum _{i'}\left(\mathbf{P}_{k\to l}\right)_{ii'}\left(\mathbf{P}_{l\to n}\right)_{i'j} \end{align} \]

5.3 Proof of theorems Theorem 1 and Theorem 2 (existence of a DTMC)

Proof

We construct, via Kolmogorov’s extension theorem (theorem Kolmogorov’s extension theorem), a distribution \(\mathbb {P}\) on \(\mathcal{X}^{\mathbb {Z}_+}\) (with the cylindrical \(\sigma\)-algebra), by setting the finite-dimensional distributions via the formula from lemma Lemma 2: \[ \mathbf{P}_{i_0,\ldots ,i_n}\left(\right) := \Pi _{i_0}\cdot \left(\mathbf{P}_{0\to 1}\right)_{i_0i_1}\cdots \left(\mathbf{P}_{n-1\to n}\right)_{i_{n-1}i_n} \] Verification of consistency. By the stochasticity of \(\mathbf{P}_{n-1\to n}\) (lemma Lemma 2, property 1): \[ \sum _{i_n}\mathbf{P}_{i_0,\ldots ,i_n}\left(\right) = \Pi _{i_0}\cdots \left(\mathbf{P}_{n-2\to n-1}\right)_{i_{n-2}i_{n-1}}\cdot \underbrace{\sum _{i_n}\left(\mathbf{P}_{n-1\to n}\right)_{i_{n-1}i_n}}_{=1} = \mathbf{P}_{i_0,\ldots ,i_{n-1}}\left(\right) \] — the consistency condition holds. Kolmogorov’s theorem gives \(\mathbb {P}\) on \(\mathcal{X}^{\mathbb {Z}_+}\) with these finite-dimensional distributions; set \(X_n:=\pi_n\) (the projection). The resulting process has exactly the required initial distribution (\(\mathbf{P}_{i_0}\left(\right)=\Pi_{i_0}\) at \(n=0\)) and transition probabilities (recovered from the joint distributions via lemma Lemma 2). The homogeneous case (theorem Theorem 2) is the special case \(\mathbf{P}_{k\to k+1}\equiv \mathbf{P}\).

5.4 Proof of theorem Theorem 3 (elementary renewal theorem for the delayed process)

Proof

Let \(N'_t\) be the ordinary (non-delayed) renewal process built from \(\xi_2,\xi_3,\ldots\), and \(m(t):=\mathbb {E}\left[N'_t\right]\) its renewal function; by the ordinary elementary renewal theorem \(m(t)/t\to 1/\mathbb {E}\left[\xi_2\right]\).

Relation between \(N_t\) and \(N'_t\). If \(\xi_1\le t\): after the first jump at time \(\xi_1\), the subsequent jumps are exactly the process \(N'\), shifted by \(\xi_1\), i.e. \(N_t=1+N'_{t-\xi_1}\). If \(\xi_1>t\): \(N_t=0\). So \(N_t=\; \mathbb {1}_{\xi_1\le t}\left(1+N'_{t-\xi_1}\right)\), and, using the independence of \(\xi_1\) from \((\xi_2,\xi_3,\ldots )\):

\[ \mathbb {E}\left[N_t\right] = \mathbb {E}\left[\; \mathbb {1}_{\xi _1\le t}\left(1+m(t-\xi _1)\right)\right] \]

Passing to the limit. Since \(\mathbb {P}\left(\xi_1<\infty \right)=1\), for a.e. \(\omega\) as \(t\to \infty\) we have \(\xi_1(\omega )\le t\) and

\[ \frac{\; \mathbb {1}_{\xi _1\le t}\left(1+m(t-\xi _1)\right)}{t} = \frac{1+m(t-\xi _1)}{t-\xi _1}\cdot \frac{t-\xi _1}{t} \xrightarrow [t\to \infty ]{} \frac{1}{\mathbb {E}\left[\xi _2\right]}\cdot 1 \]

A standard linear bound on the renewal function \(m(s)\le c(1+s)\) gives uniform integrability and allows passing to the limit under the \(\mathbb {E}\left[\right]\) sign (the dominated convergence theorem), whence \(\mathbb {E}\left[N_t\right]/t\to 1/\mathbb {E}\left[\xi_2\right]\).

5.5 Proof of theorem Theorem 4 (Cesàro limit for an irreducible finite chain)

Proof

As already noted in the main text: for an irreducible finite chain \(\mathbb {P}_{i}\left(\xi^{(1)}_j<\infty \right)=1\) (by lemma Lemma 3), and \(\xi^{(2)}_j,\xi^{(3)}_j,\ldots\) are i.i.d. with \(\mathbb {E}_{j}\left[\xi^{(2)}_j\right]=\mathbb {E}_{j}\left[T_j\right]\). Applying theorem Theorem 3 to \(\xi_1:=\xi^{(1)}_j\), \(\xi_2,\xi_3,\ldots :=\xi^{(2)}_j,\xi^{(3)}_j,\ldots\): \[ \frac{\mathbb {E}_{i}\left[V^{(n-1)}_j\right]}{n}\xrightarrow [n\to \infty ]{}\frac{1}{\mathbb {E}_{j}\left[T_j\right]} \] It remains to note (already shown in the main text) that \(\left(\frac1n\sum_{k=0}^{n-1}\mathbf{P}^k\right)_{ij}=\frac1n\mathbb {E}_{i}\left[V^{(n-1)}_j\right]\) is exactly the left-hand side.

5.6 Proof of theorem Theorem 5 (existence of a stationary distribution)

Proof

Consider the simplex \(\Delta =\left\{ \Pi \in \mathbb {R}^{\left|\mathcal{X}\right|}: \Pi_i\ge 0,\sum_i\Pi_i=1\right\}\) — a compact convex set. The map \(f(\Pi ):=\Pi \cdot \mathbf{P}\) is continuous (linear) and maps \(\Delta\) into itself: for \(\Pi \in \Delta\), \((\Pi \mathbf{P})_j=\sum_i\Pi_i\mathbf{P}_{ij}\ge 0\) and \(\sum_j(\Pi \mathbf{P})_j=\sum_i\Pi_i\underbrace{\sum_j\mathbf{P}_{ij}}_{=1}=1\). By Brouwer’s fixed point theorem there exists \(\Pi^*\in \Delta\) with \(\Pi^*\mathbf{P}=\Pi^*\).

5.7 Proof of theorem Theorem 6 (uniqueness = a row of the Cesàro limit)

Proof

Let \(\Pi\) be any stationary distribution, and let \(\Pi^{\text{Ces}}\) be the matrix from theorem Theorem 4 (all rows coincide). Then \(\Pi \cdot \frac1n\sum_{k=0}^{n-1}\mathbf{P}^k = \frac1n\sum_{k=0}^{n-1}\Pi \mathbf{P}^k=\frac1n\sum_{k=0}^{n-1}\Pi =\Pi\). Passing to the limit \(n\to \infty\): \(\Pi \cdot \Pi^{\text{Ces}}=\Pi\). Expanding coordinatewise and using \(\sum_i\Pi_i=1\) together with the fact that the rows of \(\Pi^{\text{Ces}}\) coincide, the left-hand side equals this common row. Hence \(\Pi =\) (the row of \(\Pi^{\text{Ces}}\)) — the only possible value.

5.8 Proof of lemma Lemma 3 (recurrence is a class property; a closed finite class is recurrent)

Proof

Recurrence criterion: \(i\) is recurrent \(\iff \sum_{n=1}^\infty p_{ii}^{(n)}=\infty\). Let \(f_i:=\mathbb {P}_{i}\left(T_i<\infty \right)\), \(V_i:=\sum_{n=0}^\infty \; \mathbb {1}_{X_n=i}\). By the strong Markov property and the fact that \(\xi_j^{(k)}\), \(k\ge 2\), are i.i.d., \(\mathbb {P}_{i}\left(V_i\ge k+1\right)=f_i^k\). Hence \(\mathbb {E}_{i}\left[V_i\right]=\sum_{k\ge 0}f_i^k\), which equals \(\frac{1}{1-f_i}<\infty\) when \(f_i<1\) and \(+\infty\) when \(f_i=1\). On the other hand, \(\mathbb {E}_{i}\left[V_i\right]=\sum_n\mathbb {P}_{i}\left(X_n=i\right)=\sum_n p_{ii}^{(n)}\). Hence \(\sum_n p_{ii}^{(n)}=\infty \iff f_i=1 \iff i\) is recurrent.

Recurrence is a class property. Let \(i\leftrightarrow j\): there exist \(n,m\) with \(\alpha := p_{ij}^{(n)}>0\), \(\beta := p_{ji}^{(m)}>0\). For any \(r\ge 0\) (the path \(j\to i\to (\text{stay }r)\to i\to j\)): \(p_{jj}^{(m+r+n)}\ge \beta \cdot p_{ii}^{(r)}\cdot \alpha\). Summing over \(r\ge 0\): \(\sum_k p_{jj}^{(k)}\ge \alpha \beta \sum_r p_{ii}^{(r)}\). Hence \(\sum p_{ii}=\infty \Rightarrow \sum p_{jj}=\infty\); the converse holds symmetrically.

A closed finite class \(C\) is recurrent. Fix \(i\in C\). Since \(C\) is closed, \(\sum_{k\in C}V_k=\sum_n\; \mathbb {1}_{X_n\in C}=+\infty\) identically. If every \(V_k\) (\(k\in C\)) were a.s. finite, then a finite sum of a.s.-finite quantities would be a.s. finite — a contradiction. Hence there exists \(k_0\in C\) with \(\mathbb {P}_{i}\left(V_{k_0}=\infty \right)>0\), i.e. \(k_0\) is recurrent. By the class property, \(i\) is recurrent too.

A non-closed class \(C\) is transient. There exist \(i\in C, j\notin C\) with \(p_{ij}>0\). If there were a return from \(j\) to \(i\), then \(i,j\) would communicate, i.e. \(j\in C\) — a contradiction. Hence \(1-f_i\ge \mathbb {P}_{i}\left(X_1=j\right)=p_{ij}>0\), i.e. \(f_i<1\).

Corollary 2 (To lemma Lemma 3, proving the claim from the example on the irreducible finite chain; see the text before theorem Theorem 4) For an irreducible finite DTMC, \(\mathbb {P}_{i}\left(\tau_j<\infty \right)=1\) for any \(i,j\in \mathcal{X}\).

Proof

The entire \(\mathcal{X}\) is a single class, trivially closed. By lemma Lemma 3 all states are recurrent: \(\mathbb {P}_{j}\left(T_j<\infty \right)=1\). Let \(u_i:=\mathbb {P}_{i}\left(\tau_j<\infty \right)\); by the law of total probability (first step) \(u_j=1\), \(u_i=\sum_k\mathbf{P}_{ik}u_k\) for \(i\ne j\). Let \(i^*=\arg \min_i u_i\). If \(u_{i^*}<1\), then, since \(u_{i^*}\) is a weighted average of the values \(u_k\ge u_{i^*}\), equality is possible only if \(u_k=u_{i^*}\) for all \(k\) with \(\mathbf{P}_{i^*k}>0\). By irreducibility one can go from \(i^*\) to \(j\) along a chain of positive transitions — along it \(u\equiv u_{i^*}\), in particular \(u_j=u_{i^*}<1\) — a contradiction. Hence \(u_{i^*}=1\), i.e. \(u_i\equiv 1\).

5.9 Proof of lemma Lemma 4 (the period is a class property)

Proof

Let \(i\leftrightarrow j\), \(\alpha =p_{ij}^{(n)}>0\), \(\beta =p_{ji}^{(m)}>0\). For any \(r\ge 1\) with \(p_{jj}^{(r)}>0\) (the path \(i\to j\to j\to i\)): \(p_{ii}^{(n+r+m)}\ge \alpha \cdot p_{jj}^{(r)}\cdot \beta >0 \Rightarrow d(i)\mid (n+r+m)\). Also \(p_{ii}^{(n+m)}\ge \alpha \beta >0\Rightarrow d(i)\mid (n+m)\). Subtracting: \(d(i)\mid r\) for each \(r\) in the set defining \(d(j)\) — hence \(d(i)\mid d(j)\). Symmetrically \(d(j)\mid d(i)\). Hence \(d(i)=d(j)\).

5.10 Proof of theorem Theorem 7 (the ergodic theorem) and corollary Corollary 1

Proof

Part (i) is a special case of theorems Theorem 5 and Theorem 6 (which do not require aperiodicity).

Part (ii), coupling method. Let \((Y_n)\) be an independent copy of the chain with \(Y_0\sim \Pi\) (so \(Y_n\sim \Pi \; \forall n\)). \(Z_n=(X_n,Y_n)\) is a DTMC on \(\mathcal{X}\times \mathcal{X}\) with transitions \(\mathbf{P}_{xx'}\mathbf{P}_{yy'}\).

Irreducibility of \(Z\). By lemma Lemma 5, for an ergodic \(\mathbf{P}\) there exists \(m\) such that \(\mathbf{P}^m>0\) everywhere. Then \(\mathbf{P}^m_{xx'}\mathbf{P}^m_{yy'}>0\) for any \((x,y),(x',y')\) — so \(Z\) is irreducible (and finite).

By lemma Lemma 3, a finite irreducible (closed) \(Z\) is recurrent: the diagonal \(\Delta =\left\{ (a,a)\right\}\) is reached a.s. Let \(\tau =\min \left\{ n:X_n=Y_n\right\} <\infty\) a.s.

Define \(\tilde Y_n:= Y_n\) for \(n<\tau\), \(\tilde Y_n:= X_n\) for \(n\ge \tau\). By the strong Markov property, replacing the tail does not change the distribution: \(\tilde Y_n\sim \Pi \; \forall n\). Since \(\left\{ X_n=j\right\}\) and \(\left\{ \tilde Y_n=j\right\}\) differ only on \(\left\{ \tau >n\right\}\):

\[ \left|\mathbb {P}_{i}\left(X_n=j\right)-\Pi _j\right|=\left|\mathbb {P}\left(X_n=j\right)-\mathbb {P}\left(\tilde Y_n=j\right)\right|\le \mathbb {P}\left(\tau >n\right)\xrightarrow [n\to \infty ]{}0 \]

that is, \(\mathbf{P}^n_{ij}\to \Pi_j\) for all \(i,j\).

Corollary Corollary 1. \(\Pi^{(0)}\mathbf{P}^n=\sum_i\Pi^{(0)}_i\left(\mathbf{P}^n\right)_{i\cdot }\to \sum_i\Pi^{(0)}_i\Pi =\Pi \cdot \underbrace{\sum_i\Pi^{(0)}_i}_{=1}=\Pi\).

5.11 Proof of lemma Lemma 5 (Frobenius’s aperiodicity criterion)

Proof

Let \(R_i:=\left\{ n\ge 1: p_{ii}^{(n)}>0\right\}\). \(R_i\) is closed under addition (\(a,b\in R_i\Rightarrow p_{ii}^{(a+b)}\ge p_{ii}^{(a)}p_{ii}^{(b)}>0\)), and \(d(i)=\gcd (R_i)\).

Aperiodicity \(\iff\) \(\exists m_0: p_{ii}^{(m)}>0\; \forall m\ge m_0\). This is a numerical fact (the Chicken McNugget / Frobenius coin problem): a set of integers closed under addition with \(\gcd =1\) contains all sufficiently large natural numbers; conversely, if \(\gcd (R_i)=d>1\), then \(R_i\subset d\mathbb {N}\) never contains all large numbers.

\(\mathbf{P}^m>0\) everywhere \(\Rightarrow\) aperiodicity. Suppose \(\mathbf{P}^m>0\). Then \(d(i)\mid m\; \forall i\). Suppose \(d:= d(i)>1\) for some (and, by lemma Lemma 4, for all, the chain being irreducible) \(i\). The classes \(C_r:=\left\{ k: \exists n\equiv r\! \! \pmod d,\, p_{i_0 k}^{(n)}>0\right\}\), \(r=0,\ldots ,d-1\) (for a fixed \(i_0\)), partition \(\mathcal{X}\), and in one step the chain moves from \(C_r\) to \(C_{r+1\bmod d}\) (verified via the Chapman-Kolmogorov equations and the definition of \(d\) as a gcd). Then from \(C_0\), after exactly \(m\) steps, one can only reach \(C_{m\bmod d}\) — contradicting \(\mathbf{P}^m>0\) everywhere when \(d>1\).

Aperiodicity \(\Rightarrow\) \(\exists m: \mathbf{P}^m>0\) everywhere. By irreducibility, for each pair \((i,j)\) there exists \(n_{ij}\) with \(p_{ij}^{(n_{ij})}>0\); since \(\mathcal{X}\) is finite, \(N:=\max_{ij}n_{ij}<\infty\). By aperiodicity there exists \(m_0(i)\) such that \(p_{ii}^{(r)}>0\; \forall r\ge m_0(i)\); let \(M=\max_i m_0(i)\). For \(m\ge M+N\): \(p_{ij}^{(m)}\ge p_{ii}^{(m-n_{ij})}\cdot p_{ij}^{(n_{ij})}>0\).

5.12 Proof of lemma Lemma 6 (positive/null recurrence is a class property)

Proof

Let \(i\leftrightarrow j\), both recurrent (by lemma Lemma 3 this is already a single class-wide property). Let \(\gamma_i:=\mathbb {E}_{j}\left[\sum_{n=0}^{T_j-1}\; \mathbb {1}_{X_n=i}\right]\) be the mean number of visits to \(i\) during one excursion from \(j\) to \(j\). By the strong law of large numbers applied to the delayed renewal process built from the cycles \(j\to j\) (the visits to \(i\) within each cycle being i.i.d. terms): \[ \frac{1}{N}\sum _{n=0}^{N-1}\; \mathbb {1}_{X_n=i} \xrightarrow [N\to \infty ]{\text{a.s.}} \frac{\gamma _i}{\mathbb {E}_{j}\left[T_j\right]} \] On the other hand, the same frequency, computed relative to state \(i\) itself (cycles \(i\to i\)), gives the limit \(1/\mathbb {E}_{i}\left[T_i\right]\). Equating: \[ \frac{1}{\mathbb {E}_{i}\left[T_i\right]} = \frac{\gamma _i}{\mathbb {E}_{j}\left[T_j\right]} \quad \Longrightarrow \quad \mathbb {E}_{i}\left[T_i\right] = \frac{\mathbb {E}_{j}\left[T_j\right]}{\gamma _i} \] Since \(i,j\) communicate, \(0<\gamma_i<\infty\). Hence \(\mathbb {E}_{i}\left[T_i\right]<\infty \iff \mathbb {E}_{j}\left[T_j\right]<\infty\).

5.13 Proof of theorem Theorem 8 (general theorem for a countable number of states)

Proof

Part 1: positive recurrent \(\Rightarrow\) \(\exists\) a stationary distribution \(\Pi_i=1/\mathbb {E}_{i}\left[T_i\right]\). Fix \(j\in \mathcal{X}\), \(\gamma_i:=\mathbb {E}_{j}\left[\sum_{n=0}^{T_j-1}\; \mathbb {1}_{X_n=i}\right]\) (mean number of visits to \(i\) during an excursion \(j\to j\)).

\(\gamma \mathbf{P}=\gamma\). Each visit to state \(k\) within an excursion generates exactly one next step; moving from \(k\) to \(i\) with probability \(\mathbf{P}_{ki}\) and summing over all visits to \(k\) and over \(k\), we get the mean number of “arrivals” at \(i\): \(\sum_k\gamma_k\mathbf{P}_{ki}\). This is the same as the mean number of visits to \(i\) within the excursion (each visit to \(i\), except possibly the start, is an arrival from the previous step). The balance of arrivals/departures over the closed excursion: \(\gamma_i=\sum_k\gamma_k\mathbf{P}_{ki}\).

Sum. \(\sum_i\gamma_i=\mathbb {E}_{j}\left[T_j\right]\) (each of the \(T_j\) steps of the excursion is counted exactly once).

When \(\mathbb {E}_{j}\left[T_j\right]<\infty\) we normalize: \(\Pi_i:=\gamma_i/\mathbb {E}_{j}\left[T_j\right]\) is a stationary distribution, \(\Pi_j=1/\mathbb {E}_{j}\left[T_j\right]\). By lemma Lemma 6, \(j\) was arbitrary, so \(\Pi_i=1/\mathbb {E}_{i}\left[T_i\right]\) for every \(i\).

Conversely. Let \(\Pi\) be stationary. By irreducibility \(\Pi_i>0\; \forall i\) (if \(\Pi_k>0\) and \(p_{ki}^{(n)}>0\), then \(\Pi_i\ge \Pi_k p_{ki}^{(n)}>0\)). The strong law of large numbers for the delayed renewal process started from \(\Pi\) gives the visit frequency to \(i\), equal simultaneously to \(1/\mathbb {E}_{i}\left[T_i\right]\) (by construction) and to \(\Pi_i\) (by the Birkhoff-Khinchin ergodic theorem for a stationary chain). Hence \(\mathbb {E}_{i}\left[T_i\right]=1/\Pi_i<\infty\).

Part 2: stationary measure under recurrence, unique up to scale. Existence uses the same construction of \(\gamma\) (only recurrence of \(j\) is needed; \(\sum \gamma_i=\mathbb {E}_{j}\left[T_j\right]\) can be \(+\infty\)). Strict positivity \(\gamma_i>0\): by irreducibility \(i\) is reachable from \(j\) with positive probability in finitely many steps, hence it is visited during an excursion with positive probability. Uniqueness up to scale: if \(\Psi\) is another stationary measure, then \(\Psi =\Psi_j\cdot \gamma\) (via a construction expressing \(\Psi_i\) as a sum over paths arriving at \(i\); not given in full — the most technical part, see (Grimmett and Stirzaker 2020, chap. 6)).

Classification via \(\sum \Psi_i\). Under positive recurrence \(\gamma_i=\mathbb {E}_{j}\left[T_j\right]\cdot \Pi_i\) (Part 1 + uniqueness up to scale), \(\sum \gamma_i=\mathbb {E}_{j}\left[T_j\right]<\infty\). Under null recurrence \(\mathbb {E}_{j}\left[T_j\right]=+\infty =\sum_i\gamma_i\).

Part 3: \(\mathbf{P}^n_{ij}\to 1/\mathbb {E}_{j}\left[T_j\right]\). The same coupling argument as in the proof of theorem Theorem 7 also works for countable \(\mathcal{X}\); the only difference is that recurrence of the product \(Z=(X,Y)\) on \(\mathcal{X}\times \mathcal{X}\) does not follow automatically here from lemma Lemma 3 (which requires finiteness), but needs a separate argument about the recurrence of the product of two independent copies of the same recurrent aperiodic chain. See the details in (Grimmett and Stirzaker 2020, sec. 6.4).

References

Grimmett, Geoffrey, and David Stirzaker. 2020. Probability and Random Processes. 4th ed. OUP Oxford.

Meyer, Carl D. 2001. Matrix Analysis and Applied Linear Algebra. SIAM.

Footnotes

This is true only when the chain has a finite number of states. If the chain has infinitely many states, it may contain a closed class of states that is transient. See the details below.↩︎
Again, this is true only when the number of states is finite. As paradoxical as it may seem, a chain with infinitely many states can consist of a single class that is transient. An example is the simple random walk with \(p\neq \frac{1}{2}\). See more below.↩︎