11affiliationtext: Institut für Neuroinformatik, Ruhr-Universität Bochum

# A Tutorial on the Spectral Theory of Markov Chains

Eddie Seabrook Email<EMAIL_ADDRESS>ORCID-ID: 0000-0002-8985-1893
Laurenz Wiskott Email<EMAIL_ADDRESS>ORCID-ID:
0000-0001-6237-740X

###### Abstract

Markov chains are a class of probabilistic models that have achieved
widespread application in the quantitative sciences. This is in part due to
their versatility, but is compounded by the ease with which they can be probed
analytically. This tutorial provides an in-depth introduction to Markov
chains, and explores their connection to graphs and random walks. We utilize
tools from linear algebra and graph theory to describe the transition matrices
of different types of Markov chains, with a particular focus on exploring
properties of the eigenvalues and eigenvectors corresponding to these
matrices. The results presented are relevant to a number of methods in machine
learning and data mining, which we describe at various stages. Rather than
being a novel academic study in its own right, this text presents a collection
of known results, together with some new concepts. Moreover, the tutorial
focuses on offering intuition to readers rather than formal understanding, and
only assumes basic exposure to concepts from linear algebra and probability
theory. It is therefore accessible to students and researchers from a wide
variety of disciplines.

Keywords: Markov chains, graph theory, Random walks, linear algebra,
eigendecomposition

###### Contents

  1. 1 Introduction
  2. 2 Markov Chains
    1. 2.1 Definition
    2. 2.2 Evolution via matrix-vector multiplication
    3. 2.3 Eigenvalues and eigenvectors
    4. 2.4 Classification of states
      1. 2.4.1 Communicating classes
      2. 2.4.2 Recurrence and transience
      3. 2.4.3 Periodicity
    5. 2.5 Ergodic chains
    6. 2.6 Reversible chains
    7. 2.7 Absorbing chains
    8. 2.8 Summary
  3. 3 Graphs
    1. 3.1 Definition
    2. 3.2 Matrix representation
    3. 3.3 Vertex degrees
    4. 3.4 Self-loops
    5. 3.5 Eigenspaces of transition matrices
      1. 3.5.1 Irreducible chains
      2. 3.5.2 Reducible chains
  4. 4 Random walks
    1. 4.1 Definition
    2. 4.2 Random walks on undirected graphs
      1. 4.2.1 Relationship to symmetric matrices
      2. 4.2.2 Normalized Graph Laplacian
    3. 4.3 Random walks on directed graphs
      1. 4.3.1 Key difficulties
      2. 4.3.2 Alternative methods
      3. 4.3.3 Directed Normalized Graph Laplacian
      4. 4.3.4 Random surfer model
    4. 4.4 Summary
  5. 5 Conclusion
  6. 6 Acknowledgements
  7. A Proofs
    1. A.1 2.6.2
    2. A.2 2.6.3
    3. A.3 Theorem 4.1.2
    4. A.4 Theorem 4.1.3
    5. A.5 4.1.4
    6. A.6 Theorem 4.2.4
    7. A.7 Theorem 4.2.5
    8. A.8 Theorem 4.2.6
    9. A.9 4.2.7
    10. A.10 Theorem 4.2.10

##  1 Introduction

Markov chains are a versatile tool for modelling stochastic processes, and
have been applied in a wide variety of scientific disciplines, such as
biology, computer science, and finance [1]. This is unsurprising considering
the number of practical advantages they offer: (i) they are easy to describe
analytically, (ii) in many domains they make complex computations tractable,
and (iii) they are a well understood model type, meaning that they offer some
level of interpretability when used as a component of an algorithm.
Furthermore, as we show in this tutorial, Markov chains are temporal processes
that take place on graphs. This makes them particularly suitable for modeling
data generating processes that underlie time series and graph data sets, both
of which have received much attention in the fields of machine learning and
data mining [2].

The application of Markov chains requires the assumption that at least some
aspect of the process being modelled has no memory. An important consequence
of this assumption is that the process can be described in detail using a
transition matrix. Furthermore, there exists a rich framework for describing
distinct features of such processes based on the eigenvalues and eigenvectors
of this matrix. This tutorial provides an in-depth exploration of this
framework, making use of tools from probability theory, linear algebra and
graph theory. Since the work is intended for readers from diverse academic
backgrounds, we concentrate on providing intuition for the tools used rather
than strict mathematical formalism.

The material presented underlies multiple methods from different areas of
machine learning, and instead of exploring these methods individually we focus
on the general properties that make Markov chains useful across these domains.
Nonetheless, so that readers can appreciate the scope of the tutorial, we now
briefly summarize the methods that it is relevant to. In graph-based
unsupervised learning, it is related to non-linear dimensionality reduction
techniques such as Laplacian eigenmaps [3, 4] and spectral clustering [5, 6,
7]. These two closely related methods both aim to represent data sets in a way
that preserves local geometry, and are traditionally formulated using graph
Laplacians. However, one line of work on spectral clustering instead uses
Markov chains [8, 9, 10, 11, 12, 13, 14]. Furthermore, the method of diffusion
maps [15, 16] is a generalization of Laplacian eigenmaps that is based on
Markov chains, and can be tuned to different length scales in a graph, thereby
allowing a multiscale geometric analysis of data sets. An in-depth survey of
Laplacian eigenmaps, spectral clustering, diffusion maps, as well as other
related methods can be found in [17]. In the domain of time series analysis,
the tutorial is relevant to slow feature analysis (SFA) [18], a dimensionality
reduction technique that is based on the notion of temporal coherence and is
conceptually related to Laplacian eigenmaps [19]. The ideas underlying
Laplacian eigenmaps and spectral clustering have also been extended to
classification problems, both for labelled [20], and partially labelled data
sets [21, 22, 23]. Lastly, the material presented in this tutorial also forms
the basis of various approaches to value function approximation in
reinforcement learning, such as Mahadevan’s proto-value functions [24, 25,
26], Stachenfeld’s work on the successor representation [27, 28], and other
closely related methods [29, 30]. Something common to many of the applications
mentioned thus far is that they assume all underlying graphs to be undirected,
or equivalently that the corresponding Markov chain is reversible. This
provides a number of guarantees that are crucial for these methods to work,
and we explore these guarantees in-depth in this tutorial. In most cases, the
extension to the directed/non-reversible setting faces a number of challenges
and is still actively researched. We discuss these challenges and present
various solutions that have been suggested in the literature.

The rest of the text is organized as follows. In Section 2, we give a general
introduction to discrete-time, stationary Markov chains on finite state spaces
and explore some specific types of chains in detail. Section 3 then gives a
formal introduction to graphs in order to provide a more detailed description
of Markov chains. In Section 4, random walks are presented as a canonical
transformation that turns any graph into a Markov chain, and the
undirected/directed cases are considered separately to better understand the
types of Markov chains that they typically give rise to.

##  2 Markov Chains

###  2.1 Definition

Markov processes are an elementary family of stochastic models describing the
temporal evolution of an infinite sequence of random variables
$\mathcal{X}=\\{X_{t}:t\in T\\}$, defined on a state space $\mathcal{S}$ and
indexed by a time set $T$. Such processes respect the Markov property, in
which the future evolution is conditionally independent of the past, given the
present state of the chain. In this tutorial, we focus on models for which
time is discretized, i.e. $T=\mathbb{N}_{0}$, known as Markov chains.
Furthermore, we restrict our consideration to Markov chains defined on finite
state spaces with $|\mathcal{S}|=N$ states. In such settings, the Markov
property can be formalized in terms of transition probabilities:

$\text{Pr}(X_{t+1}=x|X_{1}=x_{1},X_{2}=x_{2},X_{3}=x_{3},...,X_{t}=x_{t})=\text{Pr}(X_{t+1}=x|X_{t}=x_{t})$
(1)

If these probabilities are themselves independent of time, the Markov chain is
said to be homogeneous, and its evolution can be fully described by one-step
transition probabilities between pairs of states in $\mathcal{S}$:
$\text{Pr}(X_{t+1}=s_{j}|X_{t}=s_{i})=P_{ij}$. Collectively, these
probabilities can be represented as an $N\times N$ right-stochastic matrix:

$\bm{P}=\left(\begin{array}[]{cccc}P_{11}&P_{12}&\cdots&P_{1N}\\\
P_{21}&P_{22}&\cdots&P_{2N}\\\ \vdots&\vdots&\ddots&\vdots\\\
P_{N1}&P_{N2}&\cdots&P_{NN}\\\ \end{array}\right)$ (2)

which is called the transition matrix of the Markov chain and has the property
that the rows sum to one, i.e. $\sum_{j=1}^{N}P_{ij}=1$ $\forall i$.

Figure 1: The transition graph of a Markov chain describing the activities of
a PhD student.

Markov chains can also be depicted visually in the form of a graph, with the
state space $\mathcal{S}$ drawn as a collection of circles and labelled arrows
between these circles representing the non-zero transition probabilities
$P_{ij}$. We call this diagram the transition graph of a Markov chain. A
formal introduction to the mathematics of graphs is given in Section 3, but
until then transition graphs are simply used as an illustrative tool.

As an example, imagine you are a PhD student who wants to evaluate how
efficiently you work. In order to simplify your analysis, you posit that at
any time of a working day you are doing one of four activities: (i) studying,
(ii) speaking to your professor, (iii) eating food, and (iv) drinking coffee,
which you denote as a set of states $s_{1}=S$, $s_{2}=P$, $s_{3}=F$ and
$s_{4}=C$, respectively. As a further simplification, you assume that
transitions between these activities are Markovian. After monitoring your
activities for a few days, you come up with a set of empirical transition
probabilities which you use to construct a transition graph, shown in Figure
1, and the following transition matrix:

$\bm{P}=\bordermatrix{&S&P&F&C\cr S&0.5&0.1&0.2&0.2\cr P&1&0&0&0\cr
F&0&0&0.5&0.5\cr C&1&0&0&0}$ (3)

With either of these two representations, it is straightforward to generate a
realization of this Markov chain. To do this, we first need to pick a starting
activity. Suppose that you are studying at time $t=0$, then all activities are
possible at $t=1$. In order to choose from these possibilities, one must
sample from a probability vector equal to the first row of $\bm{P}$, i.e.
$\text{Pr}(X_{1}|X_{0}=S)=(0.5,0.1,0.2,0.2)$. If our sample yields $X_{1}=C$,
then this becomes the current state and we repeat the process. Doing this
iteratively can generate sequences of arbitrary length, for example:

$S-C-S-F-F-C-S-P-S-F-...$

which we refer to as a trajectory in the state space $\mathcal{S}$. As is
often the case when studying a stochastic process, generating single
trajectories is rather uninformative since it provides no collective
description of how the process tends to evolve. Naively, one way we could try
to achieve such a description would be to perform a type of Monte Carlo
sampling by generating several trajectories from the same starting state and
summarizing the frequency with which future activities occur.

(a) $n=10,t=0$

(b) $n=10,t=1$

(c) $n=10,t=2$

(d) $n=10,t=3$

(e) $n=100,t=0$

(f) $n=100,t=1$

(g) $n=100,t=2$

(h) $n=100,t=3$

(i) $n=1000,t=0$

(j) $n=1000,t=1$

(k) $n=1000,t=2$

(l) $n=1000,t=3$

Figure 2: Simulations of the chain in Figure 1, each of length $4$ and with
starting state $s_{1}=S$. (a-d) shows $n=10$ simulations of the chain, with
colors indicating each trajectory, (e-h) shows $n=100$ simulations, this time
all depicted in black, and (i-l) shows the outcome of $n=1000$ simulations via
gray scale shadings. In (e-h) and (i-l) percentage values indicate the
relative population of each state at each time point.

In Figure 2(a-d), we do this for $n=10$ trajectories of length $4$, each
starting with $X_{0}=S$. Each trajectory is depicted in a specific color, and
consists of points in a transition graph plotted across $4$ time points, so
that the position of each point indicates a state that one of the trajectories
is in at time $t$. Other than a slight bias towards studying ($S$) at each
time point, it is hard to pick out any clear patterns using only these $10$
trajectories. Figure 2(e-h) shows similar plots for $n=100$, but with all
points colored black and the relative occupation of each state for $t>0$
indicated by a percentage. Finally, we increase the number of trajectories to
$n=1000$ in Figure 2(i-l). Percentages are again used to indicate the relative
state occupations, but instead of representing the trajectories with dots we
color each state in gray-scale based on the percentage values. Comparing all
the plots in this figure, one can note that in the first row it is possible to
track each of the individual trajectories, whereas in the second and third
rows the focus is instead on approximating the relative probability of doing
each activity at each time.

The plots of Figure 2 represent collections of random experiments, and
therefore running them again would not yield exactly the same outcomes.
However, taking a frequentist interpretation of probability, we can ask: In
the limit $n\to\infty$, how often is each activity done at time $t$? The
answer to this question for $t=1$ is given by the vector
$\text{Pr}(X_{1}|X_{0}=S)=(0.5,0.1,0.2,0.2)$, from which we sample at each
time point in a trajectory. For $t=2$, a distribution vector can be calculated
by evaluating all the possible trajectories that lead up to each state after
two steps. For example, first consider the probability with which we are
drinking coffee at $t=2$. Clearly, there are two ways this can happen: (i)
$S-S-C$ (i.e. $s_{1}-s_{1}-s_{4}$), (ii) $S-F-C$ (i.e. $s_{1}-s_{3}-s_{4}$).
By combining the corresponding probabilities, we get:

$\displaystyle\text{Pr}(X_{2}=s_{4}|X_{0}=s_{1})$
$\displaystyle=\sum_{j=1}^{4}\text{Pr}(X_{1}=s_{j}|X_{0}=s_{1})\text{Pr}(X_{2}=s_{4}|X_{1}=s_{j})$
(4) $\displaystyle=\sum_{j=1}^{4}P_{1j}P_{j4}$ (5)
$\displaystyle=P_{11}P_{14}+P_{12}P_{24}+P_{13}P_{34}+P_{14}P_{44}$ (6)
$\displaystyle=0.1+0+0.1+0$ (7) $\displaystyle=0.2$ (8)

By performing a similar calculation for the other activities at $t=2$, we get
the following probability vector:
$\text{Pr}(X_{1}|X_{0}=S)=(0.55,0.05,0.2,0.2)$. A number of comments can be
made at this stage. Firstly, while we can extend this type of calculation to
$t>2$, this quickly becomes unfeasible to do by hand as the number of steps
increases. It turns out that there is a simple mathematical formalism which
makes these computations both more efficient and more interpretable. We
introduce this formalism in the following section. Secondly, we can also apply
the distribution picture at $t=0$. In the example we gave, we always started
in the same state, but we can easily generalize this to the case where $X_{0}$
is not fully determined. For example, $\text{Pr}(X_{0})=(0.5,0,0,0.5)$
indicates that studying and drinking coffee both occur at $t=0$ with
probability $0.5$. Lastly, while the trajectories of a Markov chain were
random, the two distributions we obtained for $t=1$ and $t=2$ were fully
determined by our initial condition of $X_{0}=s_{1}=S$. Thus, moving from the
trajectory perspective to the distribution perspective rather interestingly
makes the evolution of our Markov chain look deterministic.

###  2.2 Evolution via matrix-vector multiplication

The structure and action of $\bm{P}$, just like any other matrix, can be
evaluated using tools from linear algebra. In particular, $\bm{P}$ can either
multiply column vectors from the left, or row vectors from the right. While
typical conventions formulate matrix multiplication in the former way, the
latter is more common for right stochastic matrices due to its semantic
interpretation. Nonetheless, as both operations offer their own insight into
the descriptive capacity of Markov chains, we outline both in this section.

For any vector $\bm{x}\in\mathbb{R}^{N}$, we see that by multiplying it in row
form with $\bm{P}$ from the right gives a new vector
$\bm{z}\in\mathbb{R}^{N}$:

$\bm{z}^{T}=\bm{x}^{T}\bm{P}$ (9)

where $z_{j}=\sum_{i=1}^{N}x_{i}P_{ij}$. By summing over the elements of
$\bm{z}$, we see that:

$\sum_{j=1}^{N}z_{j}=\sum_{j=1}^{N}\sum_{i=1}^{N}x_{i}P_{ij}=\sum_{i=1}^{N}x_{i}\underbrace{\sum_{j=1}^{N}P_{ij}}_{=1}=\sum_{i=1}^{N}x_{i}$
(10)

meaning that multiplying with $\bm{P}$ from the right preserves the sum over
vector entries. Furthermore, note that since all entries of $\bm{P}$ are non-
negative, if $\bm{x}$ is non-negative then so too is $\bm{z}$. These two
properties are particularly useful when dealing with probability vectors,
which by definition both sum to $1$ and have non-negative entries, since it
means that a probability vector $\bm{x}$ is mapped into another probability
vector when multiplied from the right by $\bm{P}$.

As we have seen, probability vectors are a suitable representation for
tracking the evolution of a Markov chain, and as a shorthand we describe the
distribution of a chain at time $t$ by
$\bm{\mu}(t)=(\mu_{1}(t),\mu_{2}(t),...,\mu_{N}(t))^{T}$. Such a distribution
can easily be evolved into another distribution describing the chain at time
$t+1$. To see this, consider the probability of being in some state $s_{j}$ at
time $t+1$, i.e. $\mu_{j}(t+1)$. This depends both on the probability of being
in each state $s_{i}$ at time $t$, i.e. $\mu_{i}(t)$, as well the probability
of making a transition from each state $s_{i}$ to $s_{j}$, i.e. $P_{ij}$. By
summing over all possible states $s_{i}$, we therefore see that:

$\mu_{j}(t+1)=\sum_{i=1}^{N}\mu_{i}(t)P_{ij}$ (11)

Using these probabilities, we can now form the probability vector
$\bm{\mu}(t+1)=(\mu_{1}(t+1),\mu_{2}(t+1),...,\mu_{N}(t+1))^{T}$, which is
described by the vector-matrix analogue of Equation 11:

$\bm{\mu}(t+1)^{T}=\bm{\mu}(t)^{T}\bm{P}$ (12)

Thus, multiplying probability vectors with $\bm{P}$ from the right represents
the one-step evolution of a Markov chain. Furthermore, this operation can be
extended to multiple steps of evolution by raising the power of $\bm{P}$:

$\displaystyle\bm{\mu}(t+k)^{T}$ $\displaystyle=\bm{\mu}(t+k-1)^{T}\bm{P}$
(13) $\displaystyle=\bm{\mu}(t+k-2)^{T}\bm{P}\bm{P}$ (14)
$\displaystyle\;\;\vdots$ (15)
$\displaystyle=\bm{\mu}(t)^{T}\underbrace{\bm{P}\cdots\bm{P}}_{k\;\text{times}}$
(16) $\displaystyle=\bm{\mu}(t)^{T}\bm{P}^{k}$ (17)

where it is straightforward to establish that $\bm{P}^{k}$ is itself
stochastic. The fact that the $k$-step evolution of a chain is represented
simply by $\bm{P}^{k}$ is a result known as the Chapman-Kolmogorov equation
[31], and it tells us that the transition matrix is the only thing needed to
evolve a starting distribution of a Markov chain arbitrarily far into the
future.

A particularly special type of distribution for a Markov chain is one which is
invariant under its evolution:

######  Definition 2.2.1 (Stationary distribution).

A distribution $\bm{\pi}$ that is invariant when multiplied by $\bm{P}$ from
the right, i.e.

$\bm{\pi}^{T}=\bm{\pi}^{T}\bm{P}$ (18)

is said to be a stationary distribution of the Markov chain, and for finite
state spaces it is guaranteed that at least one such distribution exists.

The set of $N$ equations implied by Equation 18 are often referred to as the
equations of global balance. To understand why, consider the $j$-th equation
in this set:

$\pi_{j}=\sum_{i=1}^{N}\pi_{i}P_{ij}$ (19)

The right-hand term in Equation 19 represents the total flow of probability
mass into state $s_{j}$ from all other states (including $s_{j}$ itself when
$P_{jj}\neq 0$). Since $\pi_{j}$ remains invariant under this flow, then an
equal amount of probability mass must be flowing from $s_{j}$ to all other
states in $\mathcal{S}$, hence the name global balance. An important
implication of Equation 18 and Equation 19 is that when a chain is in a
stationary distribution at time $t$, it remains there for all future time
steps. We can therefore interpret such distributions as a type of steady state
of the underlying process.

We can also ask how much probability mass moves from one state to another in a
given stationary distribution $\bm{\pi}$. This is described by the following
matrix:

######  Definition 2.2.2 (Flow matrix).

Given that a Markov chain is in one of its stationary distributions
$\bm{\pi}$, the corresponding flow matrix is defined as:

$\bm{F}^{\bm{\pi}}:=\bm{\Pi}\bm{P}$ (20)

where $\bm{\Pi}:=\text{diag}(\bm{\pi})$ is a diagonal matrix consisting of the
entries of $\bm{\pi}$, and $(\bm{F}^{\bm{\pi}})_{ij}=\pi_{i}P_{ij}$ is the
stationary flow of probability mass from one state $s_{i}$ to another state
$s_{j}$.

So far we have only considered row vectors, and their interpretation as
probability vectors was fitting due to the way they transform when multiplied
by $\bm{P}$. For reasons that we outline below, this interpretation does not
apply in the case of column vectors, which are multiplied by $\bm{P}$ from the
left. To show this, we first assume that $\bm{x}=(x_{1},x_{2},...,x_{N})^{T}$
is any vector in $\mathbb{R}^{N}$. Since this vector assigns a value to each
state, we can interpret it as a function on $\mathcal{S}$. If the chain is
described at time $t$ by $\bm{\mu}(t)$, we can use this distribution to
calculate the expected value of $\bm{x}$:

$\displaystyle\mathbb{E}_{\mu(t)}(\bm{x})$
$\displaystyle=\sum_{i}\mu_{i}(t)x_{i}$ (21)
$\displaystyle=\bm{\mu}(t)^{T}\bm{x}$ (22)

If we want to look $k$ time steps into the future, then expected values are
calculated in the same way but with the additional evolution of $\bm{\mu}(t)$
in accordance with Equation 17:

$\displaystyle\mathbb{E}_{\mu(t)}^{k}(\bm{x})$
$\displaystyle=\mathbb{E}_{\mu(t+k)}(\bm{x})$ (23)
$\displaystyle=\bm{\mu}(t+k)^{T}\bm{x}$ (24)
$\displaystyle=\bm{\mu}(t)^{T}\bm{P}^{k}\bm{x}$ (25)
$\displaystyle=\mathbb{E}_{\mu(t)}(\bm{P}^{k}\bm{x})$ (26)

Hence, given any starting distribution $\bm{\mu}(t)$, the transition matrix
can produce expected values of any function on the state space arbitrarily far
into the future.

Often, the initial condition of a Markov chain has zero uncertainty, with all
probability occupying a single state $s_{i}$. In such settings, the starting
distribution is a row vector with one component equal to $1$ and all others
zero - known as a one-hot vector, and denoted by $\bm{e}_{i}$. If we evaluate
the $k$-step expectation in Equation 25 with $\bm{e}_{i}$ as a starting
distribution, we get:

$\displaystyle\mathbb{E}_{e_{i}}^{k}(\bm{x})$
$\displaystyle=\bm{e}_{i}^{T}\bm{P}^{k}\bm{x}$ (27)
$\displaystyle=\sum_{j}(\bm{P}^{k})_{ij}x_{j}$ (28)
$\displaystyle=(\bm{P}^{k}\bm{x})_{i}$ (29)

This tells us how a vector $\bm{x}$ is transformed when multiplied by
$\bm{P}^{k}$ from the left - it produces a new vector
$\bm{x}^{\prime}=\bm{P}^{k}\bm{x}$, whose $i$-th element is the expected value
of $\bm{x}$ after $k$ steps, conditioned on the starting state being $s_{i}$.
Formally, this is a conditional expectation:

$(\bm{P}^{k}\bm{x})_{i}=\mathbb{E}^{k}(\bm{x}\;|\;X_{t}=s_{i})$ (30)

which is the main operation underlying value functions in reinforcement
learning [32].

Summing over the elements of $\bm{x}^{\prime}$ gives:

$\sum_{i=1}^{N}x^{\prime}_{i}=\sum_{i=1}^{N}\sum_{j=1}^{N}(\bm{P}^{k})_{ij}x_{j}=\sum_{j=1}^{N}x_{j}\underbrace{\sum_{i=1}^{N}(\bm{P}^{k})_{ij}}_{\neq
1}\neq\sum_{j=1}^{N}x_{j}$ (31)

since the columns of $\bm{P}^{k}$, unlike its rows, do not sum to one. Hence,
multiplying column vectors with $\bm{P}^{k}$ does not preserve the vector sum,
which is why they are best interpreted as functions rather than distributions.

###  2.3 Eigenvalues and eigenvectors

Every real matrix $\bm{A}\in\mathbb{R}^{N\times N}$ can be interpreted as a
linear transformation. A central task of linear algebra is to shed light on
the relationship between the numerical properties of a matrix and various
aspects of the transformation that it represents. Often, a single matrix
represents a combination of several distinct transformations - e.g. an object
in two or more dimensions can simultaneously be rotated and stretched. Finding
the eigenvalues and eigenvectors of a matrix is one way to partition a linear
transformation into its component parts and to reveal their relative
magnitudes. In this section, we give a brief and informal summary of how this
works, and apply this to transition matrices.

An eigenvector of a matrix $\bm{A}$ is a vector which is only multiplied by
some number $\lambda$ when multiplied by $\bm{A}$. Like all vectors, they can
either be rows, i.e. $\bm{l}^{T}\bm{A}=\lambda\bm{l}^{T}$, or columns, i.e.
$\bm{A}\bm{r}=\lambda\bm{r}$, which are known as left eigenvectors and right
eigenvectors, respectively. In both cases, the number $\lambda$ is called the
eigenvalue of the respective eigenvector. Lastly, it is worth noting that real
matrices, including transition matrices, can have complex eigenvalues, i.e.
$\lambda\in\mathbb{C}$, in which case the corresponding eigenvector is also
complex, i.e. $\bm{v}\in\mathbb{C}^{N}$. However, such solutions can only
occur in complex conjugate pairs, meaning that $\lambda^{*}$ and $\bm{v}^{*}$
are also guaranteed to be an eigenvalue-eigenvector pair, where ∗ denotes the
complex conjugate.

A quick inspection of Equation 18 reveals that we have already encountered an
example of an eigenvector in the case of a transition matrix: a stationary
distribution $\bm{\pi}$ is a left eigenvector of $\bm{P}$ with eigenvalue
$\lambda=1$, normalized such that it sums to $1$. Similarly, it is
straightforward to see that $\bm{\eta}=(1,1,...,1)^{T}$ is a right eigenvector
with eigenvalue $\lambda=1$:

$(\bm{P}\bm{\eta})_{i}=\sum_{j=1}^{N}P_{ij}\eta_{j}=\sum_{j=1}^{N}P_{ij}=1$
(32)

so that $\bm{P}\bm{\eta}=\bm{\eta}$.

We can similarly describe the action of a matrix $\bm{A}$ on a set of $k$
eigenvectors. Let $\bm{Y}_{R}\in\mathbb{R}^{n\times k}$ be a matrix whose
columns are equal to $k$ right eigenvectors $\bm{A}$:

$\bm{Y}_{R}=\begin{pmatrix}\bm{r}_{1}&\bm{r}_{2}&\cdots&\bm{r}_{k}\end{pmatrix}$
(33)

Then the action of $\bm{A}$ on this matrix is simply:

$\displaystyle\bm{AY}_{R}$
$\displaystyle=\begin{pmatrix}\bm{A}\bm{r}_{1}&\bm{A}\bm{r}_{2}&\cdots&\bm{A}\bm{r}_{k}\end{pmatrix}$
(34)
$\displaystyle=\begin{pmatrix}\lambda_{1}\bm{r}_{1}&\lambda_{2}\bm{r}_{2}&\cdots&\lambda_{k}\bm{r}_{k}\end{pmatrix}$
(35)
$\displaystyle=\begin{pmatrix}\bm{r}_{1}&\bm{r}_{2}&\cdots&\bm{r}_{k}\end{pmatrix}\begin{pmatrix}\lambda_{1}&0&\cdots&0\\\
0&\lambda_{2}&\cdots&0\\\ \vdots&\vdots&\ddots&0\\\
0&0&0&\lambda_{N}\end{pmatrix}$ (36) $\displaystyle=\bm{Y}_{R}\bm{\Delta}$
(37)

If we had alternatively used a matrix $\bm{Y}_{L}$ with rows equal to left
eigenvectors of $\bm{A}$, then an equivalent argument can show that
$\bm{Y}_{L}\bm{A}=\bm{\Delta}\bm{Y}_{L}$.

In linear algebra, one is often interested in finding linearly independent
sets of eigenvectors. Without this condition, a set of eigenvectors can
contain a lot of redundancy. For example, if $\bm{r}$ is an eigenvector of
$\bm{A}$ with eigenvalue $\lambda$, then so too is the vector $c\bm{r}$ for
any $c\in\mathbb{C}$. Therefore, it is possible to construct an arbitrarily
large set of eigenvectors using $\bm{r}$ alone, and the set of all possible
vectors that can be formed in this way is known as the eigenspace of $\bm{A}$
corresponding to $\lambda$. If we instead look for a set of linearly
independent eigenvectors of $\bm{A}$, there can be at most $N$. When a set of
$N$ linearly independent eigenvectors exists, they form a basis for
$\mathbb{R}^{N}$ (i.e. the domain on which $\bm{A}$ acts). In this case, the
set of eigenvectors is called an eigenbasis, and the matrix $\bm{A}$ is said
to be diagonalizable. To justify the use of this latter term, imagine that the
matrix $\bm{Y}_{R}$ contains $N$ linearly independent right eigenvectors.
Then, by definition it is full rank, meaning that its inverse
$\bm{Y}_{R}^{-1}$ exists. If we then multiply both sides of Equation 37 by
this inverse from the left, we get:

$\bm{Y}_{R}^{-1}\bm{A}\bm{Y}_{R}=\bm{\Delta}$ (38)

Before interpreting this expression, it is worth reflecting on its general
form. If two matrices $\bm{B}$ and $\bm{C}$ can be related via
$\bm{U}^{-1}\bm{B}\bm{U}=\bm{C}$ for some invertible matrix $\bm{U}$, then
they are said to be similar. Alternatively, $\bm{C}$ is said to be a
similarity transformation on $\bm{B}$, and since we could instead write
$\bm{B}=\bm{U}\bm{C}\bm{U}^{-1}$ the converse also holds. In words, similar
matrices represent the same linear transformation, but expressed in two
different bases, where the matrix $\bm{U}$ is known as the change-of-basis
matrix. In the case of Equation 38, this means that $\bm{A}$ behaves like a
diagonal matrix when acting on vectors that are expressed in its eigenbasis
$\bm{Y}_{R}$, hence the term diagonalizable.

Equation 38 can easily be rearranged to get the following expression for
$\bm{A}$:

$\bm{A}=\bm{Y}_{R}\bm{\Delta}\bm{Y}_{R}^{-1}$ (39)

and since this only involves the eigenvalue and eigenvector matrices
$\bm{\Delta}$ and $\bm{Y}_{R}$, it is known as the eigendecomposition of
$\bm{A}$. Furthermore, multiplying Equation 39 from the left with
$\bm{Y}_{R}^{-1}$ yields $\bm{Y}_{R}^{-1}\bm{A}=\bm{\Delta Y}_{R}^{-1}$,
meaning that the rows of $\bm{Y}_{R}^{-1}$ are a set of $N$ linearly
independent left eigenvectors of $\bm{A}$. Therefore:

$\displaystyle\bm{A}$
$\displaystyle=\begin{pmatrix}\bm{r}_{1}&\bm{r}_{2}&\cdots&\bm{r}_{N}\end{pmatrix}\begin{pmatrix}\lambda_{1}&0&\cdots&0\\\
0&\lambda_{2}&\cdots&0\\\ \vdots&\vdots&\ddots&0\\\
0&0&0&\lambda_{N}\end{pmatrix}\begin{pmatrix}\bm{l}_{1}^{T}\\\
\bm{l}_{2}^{T}\\\ \vdots\\\ \bm{l}_{N}^{T}\end{pmatrix}$ (40)
$\displaystyle=\begin{pmatrix}\lambda_{1}\bm{r}_{1}&\lambda_{2}\bm{r}_{2}&\cdots&\lambda_{N}\bm{r}_{N}\end{pmatrix}\begin{pmatrix}\bm{l}_{1}^{T}\\\
\bm{l}_{2}^{T}\\\ \vdots\\\ \bm{l}_{N}^{T}\end{pmatrix}$ (41)
$\displaystyle=\sum_{\omega=1}^{N}\lambda_{\omega}\bm{r}_{\omega}\bm{l}_{\omega}^{T}$
(42)

where each term $\bm{r}_{\omega}\bm{l}_{\omega}^{T}$ in Equation 42 is a
matrix of rank $1$ and is known as the outer product between $\bm{r}_{\omega}$
and $\bm{l}_{\omega}$.111In component notation, the outer product between two
vectors $\bm{x}=(x_{1},x_{2},\cdots,x_{N})^{T}$ and
$\bm{y}=(y_{1},y_{2},\cdots,y_{N})^{T}$ is:
$\bm{x}\bm{y}^{T}:=\begin{pmatrix}x_{1}\\\ x_{2}\\\ \vdots\\\
x_{N}\end{pmatrix}\begin{pmatrix}y_{1}&y_{2}&\cdots&y_{N}\end{pmatrix}=\begin{pmatrix}x_{1}y_{1}&x_{1}y_{2}&\cdots&x_{1}y_{N}\\\
x_{2}y_{1}&x_{2}y_{2}&\cdots&x_{2}y_{N}\\\ \vdots&\vdots&\ddots&\vdots\\\
x_{N}y_{1}&x_{N}y_{2}&\cdots&x_{N}y_{N}\end{pmatrix}$ Writing the matrix
$\bm{A}$ in this way therefore gives a good insight into how a diagonalizable
matrix can be partitioned into distinct modes.

Lastly, if $\bm{l}_{\omega}$ and $\bm{r}_{\gamma}$ are left and right
eigenvectors of $\bm{A}$ with distinct eigenvalues, i.e.
$\lambda_{\omega}\neq\lambda_{\gamma}$, then:

$\displaystyle\bm{l}_{\omega}^{T}\bm{A}\bm{r}_{\gamma}-\bm{l}_{\omega}^{T}\bm{A}\bm{r}_{\gamma}$
$\displaystyle=0$ (43)
$\displaystyle\lambda_{\omega}\bm{l}_{\omega}^{T}\bm{r}_{\gamma}-\lambda_{\gamma}\bm{l}_{\omega}^{T}\bm{A}\bm{r}_{\gamma}$
$\displaystyle=0$ (44)
$\displaystyle(\lambda_{\omega}-\lambda_{\gamma})\bm{l}_{\omega}^{T}\bm{r}_{\gamma}$
$\displaystyle=0$ (45)

Since $(\lambda_{\omega}-\lambda_{\gamma})=0$ by assumption, this means that
$\bm{l}_{\omega}$ and $\bm{r}_{\gamma}$ must be orthogonal. Thus, when all
eigenvalues are distinct and the corresponding eigenvectors are normalized to
have unit euclidean norm, the following relation between the columns of
$\bm{Y}_{R}$ and the rows of $\bm{Y}_{R}^{-1}$ holds:

$\bm{l}_{\omega}^{T}\bm{r}_{\gamma}=\delta_{\omega\gamma}=\left\\{\begin{array}[]{ll}1&\mbox{if
}\omega=\gamma\\\ 0&\mbox{otherwise}\end{array}\right.$ (46)

Because of this, $\bm{Y}_{R}^{-1}$ is sometimes called the dual basis of
$\bm{Y}_{R}$ and the two sets of vectors are collectively referred to as a
biorthogonal system. It is worth noting that when a diagonalizable matrix has
repeated eigenvalues, there is extra freedom in the choice of left and right
eigenvectors. Consequently, for such matrices Equation 46 is not guaranteed to
hold, however there exist certain choices of bases for which it does [33].

In the case of a Markov chain, these concepts can be applied when the
transition matrix $\bm{P}$ is diagonalizable. In this case, any probability
distribution $\bm{\mu}(t)$ can be expressed in terms of the eigenbasis of
$\bm{P}$. Since we are treating distributions as row vectors, we do this using
the left eigenvectors of $\bm{P}$:

$\bm{\mu}(t)^{T}=\sum_{\omega=1}^{N}c_{\omega}\bm{l}_{\omega}^{T}$ (47)

where the components $c_{\omega}$ are the coordinates of $\bm{\mu}(t)$ in this
basis. We can then use this to re-express the one-step evolution of the chain
as:

$\displaystyle\bm{\mu}(t+1)^{T}$ $\displaystyle{=}\bm{\mu}(t)^{T}\bm{P}$ (48)
$\displaystyle{=}\bigg{(}\sum_{\omega=1}^{N}c_{\omega}\bm{l}_{\omega}^{T}\bigg{)}\bm{P}$
(49) $\displaystyle=\sum_{\omega=1}^{N}c_{\omega}\bm{l}_{\omega}^{T}\bm{P}$
(50)
$\displaystyle=\sum_{\omega=1}^{N}c_{\omega}\lambda_{\omega}\bm{l}_{\omega}^{T}$
(51)

which can easily be extended to multiple steps of evolution:

$\displaystyle\bm{\mu}(t+k)^{T}$ $\displaystyle{=}\bm{\mu}(t)^{T}\bm{P}^{k}$
(52)
$\displaystyle=\sum_{\omega=1}^{N}c_{\omega}\lambda_{\omega}^{k}\bm{l}_{\omega}^{T}$
(53)

Comparing Equations 17 and 53, one can see that by working in the eigenbasis
of $\bm{P}$ we have transformed the evolution of the Markov chain from a
matrix multiplication to a scalar multiplication along each basis vector
$\bm{l}_{\omega}$ by $\lambda_{\omega}^{k}$. We have therefore improved our
computational complexity from $\mathcal{O}(N^{2})$ to $\mathcal{O}(N)$.

This type of manipulation can be done for any diagonalizable matrix, and does
not depend on $\bm{P}$ being stochastic. However, one important result we
present in Section 3.5 is that all eigenvalues of a transition matrix have
absolute value less than or equal to $1$. Using this fact, we can order the
eigenvalues of $\bm{P}$ by their absolute value and separate the terms in
Equation 53 corresponding to eigenvalues with $|\lambda_{\omega}|=1$, and
those corresponding to $|\lambda_{\omega}|<1$:

$\bm{\mu}(t+k)^{T}=\underbrace{\sum_{\omega=1}^{m}c_{\omega}\lambda_{\omega}^{k}\bm{l}_{\omega}^{T}}_{\text{persistent}}+\underbrace{\sum_{\omega^{\prime}=m+1}^{N}c_{\omega^{\prime}}\lambda_{\omega^{\prime}}^{k}\bm{l}_{\omega^{\prime}}^{T}}_{\text{transient}}$
(54)

where $m$ is the number of eigenvalues of $\bm{P}$ with
$|\lambda_{\omega}|=1$. In the long time limit ($k\to\infty$) the terms with
$|\lambda_{\omega}|=1$ survive whereas those with $|\lambda_{\omega}|<1$ die
off, with $|\lambda|$ measuring the rate of decay in the latter case. This
allows us to interpret the first and second sums in Equation 54 to represent
the persistent and transient behavior of the Markov chain, respectively.

In the persistent case, we can partition the terms into three types based on
the eigenvalues: (i) $\lambda=1$, (ii) $\lambda=-1$, and (iii)
$\lambda\in\mathbb{C}$, $|\lambda|=1$. We have already seen that a stationary
distribution $\bm{\pi}$ and the vector $\bm{\eta}$ are left and right
eigenvectors of type (i), and in both cases these eigenvectors represent fixed
structures on the state space that persist when acted on by $\bm{P}$. To
capture this property, we call such eigenvectors persistent structures. In
case (ii), eigenvectors flip their sign when acted on by the transition
matrix, i.e. $\bm{y}^{T}\bm{P}=-\bm{y}^{T}$, and return after two steps, i.e.
$\bm{y}^{T}\bm{P}^{2}=\bm{y}^{T}$. Eigenvectors of this type therefore
correspond to permanent oscillations of probability mass between states in
$\mathcal{S}$, and we therefore refer to them as persistent oscillations.
Eigenvalues of type (iii) are explored in more depth in Section 3.5, where we
show that they are always complex roots of unity, i.e. $\lambda^{k}=1$ for
some $k>2$. Therefore, when their corresponding eigenvectors are acted on
repeatedly by $\bm{P}$ they are returned to after $k$ steps, i.e.
$\bm{y}^{T}\bm{P}^{k}=\bm{y}^{T}$. Thus, in analogy to (ii) they describe
permanent cycles of probability mass through the state space $\mathcal{S}$,
and we therefore call such eigenvectors persistent cycles.

| Persistent | Transient
---|---|---
Structure | $\lambda=1$ | $\lambda\in(0,1)$
Oscillation | $\lambda=-1$ | $\lambda\in(-1,0)$
Cycle | $\lambda\in\mathbb{C}$, $|\lambda|=1$ | $\lambda\in\mathbb{C}$, $|\lambda|<1$
Table 1: Eigenvalues of type (i-iii) and (i’-iii’) organized and colored based
on whether they are persistent or transient, and whether they are structures,
oscillations or cycles.

In the transient case, an analogous categorization based on the eigenvalues
can be applied, consisting of the following three types: (i’)
$\lambda\in[0,1)$, (ii’) $\lambda\in(-1,0)$, and (iii’)
$\lambda\in\mathbb{C}$, $|\lambda|<1$. For type (i’), the corresponding
eigenvectors represent perturbations to the persistent behavior that decay
over time, i.e. $\bm{y}^{T}\bm{P}=\lambda\bm{y}^{T}$ where
$|\lambda\bm{y}|=|\lambda||\bm{y}|<|\bm{y}|$. We therefore call such
eigenvectors transient structures. When $|\lambda_{j}|\approx 1$ these
structures describe sets of states that, on average, a chain spends a long
time in before converging, which are known as metastable sets [34].
Furthermore, $\lambda=0$ can be thought of as a limiting case of type (i’) in
the sense that any corresponding eigenvector decays infinitely quickly, i.e.
$\bm{P}\bm{y}=0$, and does not exhibit oscillatory or cyclic behavior.
Eigenvalues of type (ii’) also decay over time, but like case (ii) their
negative sign means that the corresponding eigenvectors exhibit oscillatory
behavior when acted on by $\bm{P}$, i.e. $\bm{y}^{T}\bm{P}=-\lambda\bm{y}^{T}$
where $|\lambda\bm{y}|=|\lambda||\bm{y}|<|\bm{y}|$. We refer to eigenvectors
of this type as transient oscillations. Eigenvalues of type (iii’) generalize
those of type (iii) to the transient case, i.e.
$\bm{y}^{T}\bm{P}^{k}=\lambda^{k}\bm{y}^{T}$ for some $k>2$ where
$|\lambda^{k}\bm{y}|=|\lambda^{k}||\bm{y}|<|\bm{y}|$, and we therefore call
them transient cycles. When $|\lambda|\approx 1$, these cycles can persist for
a long time, and have been referred to as dominant cycles [34].

Figure 3: Eigenvalues of type (i-iii) and (i’-iii’) plotted based on where
they lie on the unit circle, with the same color coding as in Table 1.

The above categorizations are summarized in Table 1, where structures,
oscillations and cycles are colored in green, blue and red, respectively, and
the persistent and transient cases are shaded bright and pale, respectively.
In Figure 3, we visualize the six different types of eigenvalue using this
color scheme by shading the respective regions of the unit circle in which
they can occur.

Before moving on, a couple of details are worth pointing out. Firstly, the
above analysis is possible only if the transition matrix $\bm{P}$ is
diagonalizable. One case in which this is guaranteed to hold is for symmetric
matrices. However, given that transition probabilities are rarely pairwise
symmetric (i.e. $P_{ij}=P_{ji}$), this restriction is clearly too strong.
Thus, a more detailed investigation is needed in order to identify the
conditions under which the above decomposition can be made, which we do in
Section 3 and Section 4. For a more in-depth account of the theory of
diagonalizable matrices, we recommend [35]. Secondly, a quick check reveals
that all terms in Equation 54 are dependent on the components $w_{j}$ that
describe the starting distribution (Equation 47). Because of this, in the most
general case both the persistent and transient behavior of a Markov chain can
be sensitive to initial conditions. In a later section, we consider a
particular type of Markov chain for which this is not the case, and provide a
simplified analysis of their evolution over time.

###  2.4 Classification of states

In the following sections, we explore three types of Markov chains. In order
to describe each type in detail, we first need to define various properties
that apply to individual states, or sets thereof, in a state space
$\mathcal{S}$. This is the focus of the current section.

####  2.4.1 Communicating classes

We start by making the following definitions related to how states in
$\mathcal{S}$ are connected:

######  Definition 2.4.1 (Accessibility).

For two states $s_{i}$, $s_{j}\in\mathcal{S}$, we say that $s_{j}$ is
accessible from $s_{i}$, denoted $s_{i}\to s_{j}$, when it is possible to
reach $s_{j}$ from $s_{i}$ in $k\geq 0$ steps, i.e.
$\exists\;k\;:(\bm{P}^{k})_{ij}>0$.

######  Definition 2.4.2 (Communication).

Two states $s_{i}$, $s_{j}\in\mathcal{S}$, are said to communicate if
$s_{i}\to s_{j}$ and $s_{j}\to s_{i}$, which is denoted $s_{i}\leftrightarrow
s_{j}$.

Communication is a useful property for describing states in a Markov chain, as
exemplified by the following result:

######  Proposition 2.4.3 (Communicating class).

Communication is an equivalence relation, meaning that:

  * •

$\forall s_{i}\in\mathcal{S}$, $s_{i}\leftrightarrow s_{i}$, since by
definition each state can reach itself in $0$ steps, i.e.
$(\bm{P}^{0})_{ii}=(\bm{\mathbbm{1}})_{ii}=1>0$.

  * •

if $s_{i}\leftrightarrow s_{j}$, then $s_{j}\leftrightarrow s_{i}$.

  * •

if $s_{i}\leftrightarrow s_{j}$ and $s_{j}\leftrightarrow s_{k}$, then
$s_{i}\leftrightarrow s_{k}$.

and the state space $\mathcal{S}$ can be partitioned into communicating
classes, each containing states that all communicate with one another.

Furthermore, we can make a useful categorization of Markov chains based on the
number of communicating classes they have:

######  Definition 2.4.4 (Number of communicating classes).

Let $n$ be the number of communicating classes of a Markov chain. When $n=1$,
the chain is said to be irreducible, otherwise it is reducible.

In words, an irreducible Markov chain is one in which for any pair of states
there exists a connecting path in both directions. In Figure 4, three example
Markov chains are shown, with the communicating classes indicated by the
dashed boxes. Take a moment to double-check why each state belongs to its
communicating class, and verify that the examples in Figure 4(a,b) are
reducible, whereas the one in Figure 4(c) is irreducible. Finally, observe
from Figure 4(b) that it is possible for states in one communicating class to
be accessible from states in another class (e.g. $s_{3}\to s_{4}$).

(a) Reducible, recurrent

(b) Reducible, not recurrent

(c) Irreducible

Figure 4: Three Markov chains with differing connectivity, each with $N=6$
states.

Irreducible Markov chains feature in a number of subsequent sections of this
tutorial, due to the following result:

######  Theorem 2.4.5.

A Markov chain is irreducible if and only if it has a unique stationary
distribution $\bm{\pi}$. Furthermore, this distribution has strictly positive
elements, i.e. $\pi_{i}>0\;\forall s_{i}\in\mathcal{S}$.

This result can be applied to the example of Figure 4(c) by using the
observation of the previous section that stationary distributions of a given
Markov chain are eigenvectors of the associated transition matrix with
eigenvalue $1$. If we were to find the transition matrix of the chain in
Figure 4(c) and compute its eigenvectors, we would indeed find a single left
eigenspace of $\bm{P}$ corresponding to eigenvalue $1$, with strictly positive
elements. When normalized such that the row sum is $1$, the resulting vector
is
$\bm{\pi}=(\pi_{1},\pi_{2},\pi_{3},\pi_{4},\pi_{5},\pi_{6})^{T}=(0.09,0.09,0.07,0.31,0.18,0.26)^{T}$,
which we encourage readers to check themselves. For reducible Markov chains,
the guarantees of uniqueness and positivity of the stationary probabilities no
longer hold. In order to describe the stationary distributions of such chains,
we first introduce some new concepts for describing states.

####  2.4.2 Recurrence and transience

Each state $s_{i}\in\mathcal{S}$ can be categorized based on how likely it is
to be revisited, given that it is currently occupied. This is formalized by
the following definition:

######  Definition 2.4.6 (Recurrence/transience).

Given that the system is in state $s_{i}$ initially, the probability of
returning to $s_{i}$ is defined as:

$f_{i}:=\textup{Pr}(X_{k}=s_{i}\text{ for some }k\geq 1|X_{0}=s_{i})$ (55)

States for which $f_{i}=1$ are called recurrent, and those for which $f_{i}<1$
are called transient.

This is a useful way to characterize states in $\mathcal{S}$, since it
generalizes to all states within a communicating class, i.e. for any
communicating class $C\subseteq\mathcal{S}$, either all states in $C$ are
recurrent or all states in $C$ are transient. Transience/recurrence are
therefore examples of class properties, and we henceforth use the terms
recurrent class and transient class for communicating classes that contain
recurrent and transient states, respectively. Furthermore, for finite state
spaces a Markov chain is guaranteed to have at least one recurrent class.
Building upon this, we can then apply the notion of recurrence to a Markov
chain as a whole:

######  Definition 2.4.7 (Recurrent chains).

A Markov chain that contains only recurrent classes is called a recurrent
Markov chain.

As an illustration, we apply these concepts to the reducible chains depicted
in Figure 4. In Figure 4(a), there are two communicating classes and in each
one there is no possibility to exit. This means that if a state in one of
these classes is occupied, it is guaranteed to be revisited at some future
time step, i.e. $f_{i}=1$ for all states in each class. Therefore, both
classes are recurrent and the chain as a whole is recurrent. In Figure 4(b),
the main difference is that there is now the possibility to exit the blue
class without returning. For example, assuming $s_{1}$ is occupied, although
there is a possibility that $s_{1}$ can be visited again later (e.g. $s_{1}\to
s_{2}\to s_{1}$), as soon as a transition $s_{1}\to s_{4}$ takes place this
will no longer be possible. This is why $f_{i}<1$ for states in the blue
class. Hence, while the red class is recurrent, the blue class is transient,
and because of this the chain as a whole is not recurrent.

For an irreducible Markov chain, such as the example shown in Figure 4(c),
every state is guaranteed to be recurrent, leading to the following
proposition:

######  Proposition 2.4.8 (Recurrence of irreducible Markov chains).

All irreducible Markov chains are recurrent.

However, from the example in Figure 4(a) it is clear that the converse does
not hold, since it is also possible for a reducible chain to be recurrent. In
fact, whether a reducible chain is recurrent or not determines certain
features of the stationary distributions belonging to the chain. This is
outlined by the following proposition:

######  Proposition 2.4.9 (Stationary distributions of Reducible chains).

For a reducible Markov chain with $r$ recurrent classes and $t$ transient
classes:

  * •

Any stationary distribution has probability zero for states belonging to a
transient class.

  * •

For the $k$-th recurrent class, there exists a unique stationary distribution
$\bm{\pi}_{k}$ with non-zero probabilities only for states in that class.

  * •

When the number of recurrent classes $r$ is bigger than $1$, stationary
distributions can be formed via convex combinations of each distribution
$\bm{\pi}_{k}$, i.e.

$\bm{\pi}_{\textup{combo}}=\sum_{k=1}^{r}\alpha_{k}\bm{\pi}_{k}\quad,\quad\textup{with}\quad\alpha_{k}\geq
0\quad\textup{and}\quad\sum_{k=1}^{r}\alpha_{k}=1$ (56)

meaning that there are an infinite number of stationary distributions.

  * •

Furthermore, when the number of transient classes $t$ is zero, or in other
words when the chain is recurrent, performing the procedure above with nonzero
coefficients always yields distributions that are strictly positive.

We can apply these results to the two reducible chains in Figure 4. In the
example of Figure 4(a), the stationary distribution associated to the blue
class is $\bm{\pi}_{\text{1}}=(0.35,0.36,0.29,0,0,0)^{T}$ and the one
associated to the red class is
$\bm{\pi}_{\text{2}}=(0,0,0,0.39,0.26,0.35)^{T}$. We can then generate an
arbitrary number of extra stationary distributions by taking convex
combinations of $\bm{\pi}_{\text{1}}$ and $\bm{\pi}_{\text{2}}$ with
coefficients $\alpha_{1}$ and $\alpha_{2}$. For example, with
$\alpha_{1}=0.25$ and $\alpha_{2}=0.75$ we get
$\bm{\pi}=(0.09,0.09,0.07,0.29,0.2,0.26)^{T}$. Furthermore, the last bullet
point in 2.4.9 tells us that since this chain is recurrent we can be sure that
any convex combination with positive coefficients yields a distribution with
strictly positive entries. This property of recurrent chains is particularly
relevant to our treatment of both reversible chains in Section 2.6 and random
walks in Section 4, and we henceforth use $\bm{\pi}>0$ to denote a stationary
distribution with this property. In the example of Figure 4(b), the red class
is the only recurrent class, meaning that the stationary distribution
associated to this class is the only stationary distribution of the chain.
Since the transition probabilities for states in this class are the same as in
the example of Figure 4(a), this stationary distribution is
$\bm{\pi}=\bm{\pi}_{2}$. Furthermore, in agreement with 2.4.9, we see that the
transient states in this chain have a stationary probability of $0$.

####  2.4.3 Periodicity

The notion that states can be revisited is also meaningful in another sense.
We define the following quantity, which describes how frequently such revisits
can take place.

######  Definition 2.4.10 (Periodic chains).

For each state $s_{i}\in\mathcal{S}$, the period is defined as:

$d_{i}:=gcd\\{k\geq 1\;:\;(\bm{P}^{k})_{ii}>0\\}$ (57)

where gcd indicates the greatest common divisor. Then, Equation 57 says that
when starting in state $s_{i}$ it is only possible to return to $s_{i}$ in
multiples of the period $d_{i}$. States for which $d_{i}>1$ are called
periodic and those for which $d_{i}=1$ are aperiodic.

Like transience/recurrence, period is also a class property, and we use $d$ to
refer to the period of a whole class. This in turn allows us to define the
period of a Markov chain:

######  Definition 2.4.11 (Periodicity).

When all communicating classes in $\mathcal{S}$ have period $d>1$, the Markov
chain is said to be periodic, with period $d$.

######  Definition 2.4.12 (Aperiodicity).

When all communicating classes in $\mathcal{S}$ are aperiodic, the Markov
chain is said to be aperiodic.

######  Definition 2.4.13 (Mixed Periodicity).

If $\mathcal{S}$ contains communicating classes with different periods, the
Markov chain is said to have mixed periodicity.

Consider the example shown in Figure 5(a). This chain has two communicating
classes, the red one being a transient class with $d=2$ and the blue one being
a recurrent class with $d=1$, meaning that this chain has mixed periodicity.
In Figure 5(b-d), we show three irreducible Markov chains, with (b) and (c)
having period $3$ and $2$, respectively, and (d) being aperiodic.

(a) $d=1$, $d=2$

(b) $d=3$

(c) $d=2$

(d) $d=1$

Figure 5: Four Markov chains with differing periodicity, each with $N=3$
states.

Markov processes are a broad class of models, and even under the restricted
settings considered in this tutorial (discrete time, homogeneous and finite
state spaces), there are many distinct types of chains. In the following
sections, we concentrate on three particular types that are relevant in
applied domains.

###  2.5 Ergodic chains

When modeling a system that evolves over time, it is important to ask what can
be said, if anything, about its long term behavior. For a Markov chain, this
question can be phrased in two ways. On one hand, we can sample a single
trajectory starting from some initial state and ask what the average behavior
is over time, i.e. how often is it found in each state $s_{i}\in\mathcal{S}$
for a trajectory of length $t$? On the other hand, we can describe our
starting conditions as a distribution $\bm{\mu}(0)$ and ask what this evolves
to in the future, i.e. what is the probability of being in each state $s_{i}$
at a later time $t$? We refer to these two notions of long term behavior as
the trajectory and distribution perspectives, respectively. While the analyses
given so far predominantly use the latter perspective, we remind readers that
in Section 2.1 we have introduced the idea of a distribution over
$\mathcal{S}$ by taking the limit of an infinitely large ensemble of
trajectories, meaning that the two concepts are closely related.

This two-way view originates from the field of statistical physics, where
physical processes can either be analyzed with temporal averages (i.e. the
trajectory perspective) or ensemble averages (i.e. the distribution
perspective). One class of systems that has received a lot of study in this
field are those for which these two types of averaging yield the same result
as $t\to\infty$. Such systems are known as ergodic systems, and this
equivalence means that a statistical description of their long term behavior
can be described simply by a single, sufficiently long sample. One implication
of this is that initial conditions are forgotten over time, which makes
ergodic systems particularly attractive from a simulation or modeling
perspective. Finally, with this in mind we can define an ergodic Markov chain
as follows:

######  Definition 2.5.1 (Ergodic Markov chain).

An ergodic Markov chain is one that is guaranteed to converge to a unique
stationary distribution.

Clearly, in order for a chain to be ergodic it must have a unique stationary
distribution. Therefore, by virtue of Theorem 2.4.5, a necessary condition for
a chain to be ergodic is that it is irreducible. However, there is no
guarantee that an irreducible chain converges, which is the second condition
of 2.5.1. The convergence of a Markov chain is related to its periodicity, as
explained by the following result:

######  Theorem 2.5.2 (Convergence of a Markov chain).

The evolution of a Markov chain with period $d$ can lead to a permanent,
repeating sequence of $d$ distributions, i.e.

$\bm{\mu}(k)\to\bm{\mu}(k+1)\to...\to\bm{\mu}(k+d-1)\to\bm{\mu}(k)$ (58)

which for $d=2$ and $d>2$ correspond to persistent oscillations and persistent
cycles, respectively. In the case of an aperiodic Markov chain ($d=1$), only
sequences of length $1$ are allowed, which means that one of the stationary
distributions is guaranteed to be reached.

We can apply this result to the irreducible Markov chain in Figure 5(c). This
chain has a unique stationary distribution $\bm{\pi}=(0.35,0.15,0.5)^{T}$ and
a period of $d=2$. Therefore, there is no guarantee that the chain converges
to $\bm{\pi}$ since it can get trapped in persistent oscillations. To observe
this, we can try out different initial conditions and iteratively applying the
update rule in Equation 12. For example, starting with the distribution
$\bm{\mu}(0)=(0.25,0.5,0.25)^{T}$ we get a persistent oscillation between the
following two distributions: $\bm{\mu}(k)=(0.175,0.075,0.75)^{T}$ and
$\bm{\mu}(k+1)=(0.525,0.225,0.25)^{T}$. However, this is not the only
persistent oscillation possible for this chain, which can be observed by
trying out different initial conditions. Lastly, in Section 3.5 we gain more
insight on Theorem 2.5.2 by using tools from graph theory to describe the
eigenvectors of $\bm{P}$ with $|\lambda|=1$.

A key insight from Theorem 2.5.2 is that a Markov chain is guaranteed to
converge only if it is aperiodic. Together with irreducibility, this therefore
provides the conditions under which a chain is ergodic:

######  Theorem 2.5.3 (Conditions for Ergodicity).

A Markov chain is ergodic if and only if it is both irreducible and aperiodic,
which respectively ensure that (i) there is a unique distribution $\bm{\pi}$,
and (ii) the chain always converges to this distribution. Furthermore, the
distribution $\bm{\pi}$ is said to be the limiting distribution of the chain.

Ergodic Markov chains have a number of beneficial properties. Firstly, as with
any ergodic system, the initial conditions are eventually forgotten, which
means that when studying the statistical behavior of an ergodic chain it is
not necessary to explore different starting states. This advantageous property
underlies a number of methods in machine learning and beyond, with Markov
chain Monte Carlo methods being a particularly well known example [36].
Secondly, the equivalence between the trajectory and distribution perspectives
allows us to interpret the limiting probabilities $\pi_{i}$ as the long run
fraction of steps that the chain spends in each state $s_{i}$ [37]. Lastly,
analyzing the evolution of a Markov chain in terms of the eigenvectors of its
transition matrix becomes somewhat simpler in the case of an ergodic chain. We
have already seen that when the transition matrix of a Markov chain is
diagonalizable, we can vastly simplify the computation of the $k$-step
evolution of the Markov chain (Equation 54). When the Markov chain is also
ergodic, we know that its persistent behavior is fully described by
$\bm{l}_{1}=\bm{\pi}$, meaning that this expression simplifies to:

$\bm{\mu}(t+k)^{T}=\bm{\pi}^{T}+\sum_{\omega=2}^{N}c_{\omega}\lambda_{\omega}^{k}\bm{l}_{\omega}^{T}$
(59)

###  2.6 Reversible chains

One of the defining characteristics of Markov chains is that the future ($X$)
is conditionally independent of the past ($Z$), given the present ($Y$). A
simple calculation demonstrates that the relationship of conditional
independence is symmetric. Assuming that $\text{Pr}(X|Y,Z)=\text{Pr}(X|Y)$, we
find that:

$\displaystyle\text{Pr}(Z|Y,X)$
$\displaystyle=\frac{\text{Pr}(X,Y,Z)}{\text{Pr}(Y,X)}$ (60)
$\displaystyle=\frac{\text{Pr}(X|Y,Z)\text{Pr}(Y,Z)}{\text{Pr}(X|Y)\text{Pr}(Y)}$
(61)
$\displaystyle=\frac{\text{Pr}(X|Y)\text{Pr}(Y,Z)}{\text{Pr}(X|Y)\text{Pr}(Y)}\quad\text{(by
assumption)}$ (62) $\displaystyle=\frac{\text{Pr}(Y,Z)}{\text{Pr}(Y)}$ (63)
$\displaystyle=\text{Pr}(Z|Y)$ (64)

Assuming that we have an initial Markov chain $\mathcal{X}$ described by a
transition matrix $\bm{P}$, this symmetry tells us that reversing the
direction of time produces a new process which itself satisfies the Markov
property. Hence, we can define this new Markov chain as the time-reversal of
$\mathcal{X}$, which we denote as $\mathcal{\tilde{X}}$. A natural question we
can ask is how the transition matrix of $\mathcal{\tilde{X}}$ is related to
$\bm{P}$. In order to answer this, we make the assumption that at time $t$ the
chain is described by one of its stationary distributions $\bm{\pi}$.
Therefore:

$\text{Pr}(X_{t}=s_{i})=\pi_{i}\;\forall
s_{i}\in\mathcal{S}\;\text{and}\;t\geq 0$ (65)

We can make use of this, together with Bayes’ theorem, to work out the
transition probabilities $(\bm{P}_{\text{rev}})_{ij}$ of $\mathcal{\tilde{X}}$
[38]:

$(\bm{P}_{\text{rev}})_{ij}=\text{Pr}(X_{t}=s_{j}|X_{t+1}=s_{i})=\frac{\text{Pr}(X_{t+1}=s_{i}|X_{t}=s_{j})\text{Pr}(X_{t}=s_{j})}{\text{Pr}(X_{t+1}=s_{i})}=\frac{P_{ji}\;\pi_{j}}{\pi_{i}}$
(66)

A couple of reflections can be made about the result above. Firstly, since we
initialized $\mathcal{X}$ to one of its stationary distributions, the time
reversal relationship between $\mathcal{X}$ and $\mathcal{\tilde{X}}$ only
holds once they have converged. Secondly, since we have $\pi_{i}$ in the
denominator of Equation 66, the time reversal of a Markov chain is only valid
for a starting distribution with $\pi_{i}>0\;\forall s_{i}\in\mathcal{S}$. In
Section 2.4.1, we have established that only recurrent chains have stationary
distributions of this type, meaning that the time reversal of a Markov chain
is only well-defined if the chain is recurrent. Lastly, using Equation 66 it
is possible to define $\bm{P}_{\text{rev}}$ in matrix notation as follows:

######  Definition 2.6.1 (Time reversal).

Let $\mathcal{X}$ be a recurrent Markov chain with transition matrix $\bm{P}$
and $\bm{\pi}>0$ one of its stationary distributions. Then, the transition
matrix of its time reversal $\mathcal{\tilde{X}}$ is given by:

$\bm{P}_{\textup{rev}}:=\bm{\Pi}^{-1}\bm{P^{T}}\bm{\Pi}$ (67)

It is worth emphasizing that since no assumption is made in 2.6.1 about the
number communicating classes, it also applies in the case of reducible
recurrent chains where there are an infinite number of distributions
$\bm{\pi}>0$ to choose from. However, in such cases the choice of $\bm{\pi}$
makes no difference:

######  Proposition 2.6.2 (Time reversal of reducible chains).

For a reducible recurrent Markov chain $\mathcal{X}$, the time reversal
$\mathcal{\tilde{X}}$ is uniquely defined, with $\bm{P}_{\textup{rev}}$ being
independent of which stationary distribution $\bm{\pi}>0$ is used (proof: see
Appendix A).

Moreover, the set of stationary distributions $\bm{\pi}>0$ belonging to a
recurrent Markov chain is the same as the set belonging to the corresponding
time reversal:

######  Proposition 2.6.3 (Stationary distributions of time reversal).

Let $\mathcal{X}$ be a recurrent Markov chain. Then $\bm{\pi}>0$ is a
stationary distribution of $\mathcal{\tilde{X}}$ if and only if it is a
stationary distribution of $\mathcal{X}$.222For continuous time Markov chains,
this result is known as Kelly’s lemma.

We now consider the special case where a Markov chain $\mathcal{X}$ is
indistinguishable from its time reversal $\mathcal{\tilde{X}}$. Such processes
are known as reversible Markov chains, since in any stationary distribution
the forward and backwards dynamics of the chain are statistically equivalent,
i.e. any trajectory $X_{1}$, $X_{2}$, …, $X_{k-1}$, $X_{k}$ occurs with equal
probability as the corresponding reversed trajectory $X_{k}$, $X_{k-1}$, …,
$X_{2}$, $X_{1}$. The stationary dynamics of such chains therefore has no
inherent arrow of time. Furthermore, since $\mathcal{X}$ and
$\mathcal{\tilde{X}}$ are indistinguishable, they have the same transition
matrix, i.e. $\bm{P}=\bm{P}_{\text{rev}}$, and for any stationary distribution
$\bm{\pi}>0$ the forward and backwards flow matrices are the same. Therefore:

$\displaystyle\bm{F}^{\bm{\pi}}$
$\displaystyle=\bm{F}^{\bm{\pi}}_{\text{rev}}$ (68)
$\displaystyle\bm{\Pi}\bm{P}$ $\displaystyle=\bm{\Pi}\bm{P}_{\text{rev}}$ (69)
$\displaystyle\bm{\Pi}\bm{P}$ $\displaystyle{=}\bm{P^{T}}\bm{\Pi}$ (70)

By expressing Equation 70 in component form, we arrive at the following
theorem which is used throughout the rest of the tutorial:

######  Theorem 2.6.4 (Detailed balance).

A recurrent Markov chain is reversible if and only if it for any stationary
distribution $\bm{\pi}>0$:

$\pi_{i}P_{ij}=\pi_{j}P_{ji}\quad\forall s_{i},s_{j}\in\mathcal{S}$ (71)

which are known as the equations of detailed balance.

A number of observations can be made about this definition. Firstly, the left
(right) terms represent the flow of probability from $s_{i}$ to $s_{j}$
($s_{j}$ to $s_{i}$), given that the chain is described by distribution
$\bm{\pi}$. Thus, for a reversible Markov chain in one of its stationary
distributions, the flow from one state to another is completely balanced by
the flow in the reverse direction, meaning that the flow matrix
$\bm{F}^{\bm{\pi}}$ is always symmetric for such chains. By comparison with
Equation 19, we see that detailed balance is a stronger condition than global
balance, since in the latter case there is only an equivalence between the
total flow in and out of each state. Secondly, since $\pi_{i}$ and $\pi_{j}$
are non-zero, it follows that $P_{ij}\neq 0$ if and only if $P_{ji}\neq 0$.
Thus, the transition structure of a reversible Markov chain always permits the
return to the previous state, and because of this the period of a reversible
Markov chain can be at most $2$. Thirdly, while some sources assume
irreducibility as a precondition of reversibility, we instead base our
definition on the weaker condition of recurrence [37]. This is due to the fact
that we only need recurrence in order to define the time reversal of a Markov
chain. Furthermore, with this convention Theorem 2.6.4 applies more broadly to
reducible Markov chains, which lets us make a closer comparison between
reversible Markov chains and undirected graphs in Section 4. Lastly, Theorem
2.6.4 implies that there are two distinct ways in which Markov chains can be
non-reversible: (i) they can be recurrent without satisfying detailed balance,
or (ii) they can be non-recurrent. In the case of (i), $\bm{\Pi
P}\neq\bm{P^{T}}\bm{\Pi}$ for any distribution $\bm{\pi}>0$, meaning that the
flow matrix $\bm{F}^{\bm{\pi}}$ is asymmetric, and in the case of (ii) no
positive stationary distribution exists. Lastly, note that for a non-recurrent
chain, there exists the possibility that $\bm{F}^{\bm{\pi}}$ is symmetric for
all stationary distributions despite none of those distributions being
strictly positive. For such chains, removing all transient states from
$\mathcal{S}$ produces a reversible chain. We therefore refer to such chains
as semi-reversible.

(a)

$\bm{P}_{\text{1}}=\left(\begin{array}[]{cccc}0&0.3&{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0.1}&{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0.6}\\\
0.75&0&0&0.25\\\ 0.5&0&0&0.5\\\ 0.75&0.125&0.125&0\end{array}\right)$

$\bm{\pi}_{\text{1}}=(0.417,0.167,0.083,0.333)^{T}$

$\bm{F}_{\text{1}}^{\bm{\pi}}=\left(\begin{array}[]{cccc}0&0.125&0.042&0.25\\\
0.125&0&0&0.042\\\ 0.042&0&0&0.042\\\ 0.25&0.042&0.042&0\end{array}\right)$

(b)

(c)

(d)

$\bm{P}_{\text{2}}=\left(\begin{array}[]{cccc}0&0.3&{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0.3}&{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0.4}\\\
0.75&0&0&0.25\\\ 0.5&0&0&0.5\\\ 0.75&0.125&0.125&0\end{array}\right)$

$\bm{\pi}_{\text{2}}=(0.406,0.157,0.157,0.280)^{T}$

$\bm{F}_{\text{2}}^{\bm{\pi}}=\left(\begin{array}[]{cccc}0&0.122&0.122&0.165\\\
0.118&0&0&0.039\\\ 0.078&0&0&0.078\\\ 0.210&0.035&0.035&0\\\
\end{array}\right)$

(e)

(f)

(g)

$\bm{P}_{\text{3}}=\left(\begin{array}[]{cccc}0&0.75&0&0.25\\\
0.25&0&0&0.75\\\ 0.6&0&0&0.4\\\
{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0.1}&{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0.9}&0&0\\\
\end{array}\right)$

$\bm{\pi}_{\text{3}}=(0.154,0.462,0,0.385)$

$\bm{F}_{\text{3}}^{\bm{\pi}}=\left(\begin{array}[]{cccc}0&0.115&0&0.038\\\
0.115&0&0&0.346\\\ 0&0&0&0\\\ 0.038&0.346&0&0\\\ \end{array}\right)$

(h)

(i)

(j)

$\bm{P}_{\text{4}}=\left(\begin{array}[]{cccc}0&0.75&0&0.25\\\
0.25&0&0&0.75\\\ 0.6&0&0&0.4\\\
{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0.5}&{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0.5}&0&0\\\
\end{array}\right)$

$\bm{\pi}_{\text{4}}=(0.270,0.378,0,0.352)^{T}$

$\bm{F}_{\text{4}}^{\bm{\pi}}=\left(\begin{array}[]{cccc}0&0.203&0&0.068\\\
0.095&0&0&0.284\\\ 0&0&0&0\\\ 0.176&0.176&0&0\\\ \end{array}\right)$

(k)

(l)

Figure 6: Three example Markov chains: (a) reversible, (d) recurrent and non-
reversible, (g) semi-reversible, (j) non-recurrent and non-reversible. In (b,
e, h, k), the transition matrices, stationary distributions and flow matrices
of each example are shown, with numerical values rounded to 3 decimal places.
In (c, f, i, l), the stationary distributions are visualized by a bar plot,
with states represented along the $x$-axis. The right (left) portion of each
bar represents the outgoing (incoming) flow of probability mass to (from) all
other states. The color of each segment indicates which state the probability
mass is flowing to or from, with $s_{1}$, $s_{2}$, $s_{3}$ and $s_{4}$
depicted in blue, orange, green and red, respectively.

To illustrate some of these points, we consider three Markov chains in Figure
6, with (a, d, g, j) showing the transition graphs of each example, and (b, e,
h, k) showing the respective transition matrix, stationary distribution and
flow matrix (for simplicity, each example has a single recurrent class, so
that both the stationary distribution and the associated flow matrix are
unique). As a visual illustration of the pairwise stationary flow between
states in each example, in (c, f, i, l) the stationary distribution is
represented as a bar plot, with the portions of probability mass flowing in
(left) and out (right) of each state shown as portions of each bar. The
example in (a) is reversible, as can be seen by the symmetry of
$\bm{F}_{\text{1}}^{\bm{\pi}}$ in (b), or equivalently by the matching between
left and right portions of all bars in (c). The example in (d) is almost
equivalent to the one in (a), except that the outgoing transition
probabilities from $s_{1}$ have been slightly modified (indicated by the
colored arrows in (a, d) and the colored entries of $\bm{P}_{\text{1}}$ and
$\bm{P}_{\text{2}}$ in (b, e)). This modification is enough to violate
detailed balance, as can be seen by the asymmetry of
$\bm{F}_{\text{2}}^{\bm{\pi}}$ or the bar plot in (f). Lastly, the chains
depicted in (g, j) are non-recurrent since in both cases state $s_{3}$ has
only outgoing transitions. Therefore, $\pi_{3}=0$ and both examples are non-
reversible. However, a quick check of $\bm{F}_{\text{3}}^{\bm{\pi}}$ or the
bar plot in (i) reveals that the example in (g) is semi-reversible.
Conversely, the example in (h) is identical to the one in (g) except for the
outgoing transitions from $s_{4}$ (again indicated by the colored arrows in
(g, j) and the colored entries of $\bm{P}_{\text{3}}$ and $\bm{P}_{\text{4}}$
in (h,k)), which leads to an asymmetric stationary flow between the recurrent
states.

It is worth pointing out that in our analysis above, reversibility was checked
by inspecting the stationary distributions and the corresponding flow matrices
of each example. However, since reversibility is a property associated to
Markov chains and not to distributions, one might wonder whether there is an
alternative way to formalize it based purely on the transition probabilities
$P_{ij}$. Clearly, Equation 71 prohibits one way transitions (i.e. $P_{ij}>0$
and $P_{ji}=0$), but this is only a necessary condition of reversibility - can
we offer anything more precise? Fortunately, the answer is yes, and it is
given by Kolmogorov’s criterion [39]:

######  Theorem 2.6.5 (Kolmogorov’s criterion).

A recurrent Markov chain is reversible if and only if the product of one-step
transition probabilities along any finite closed path of length more than two
is the same as the product of one-step transition probabilities along the
reversed path. In other words:

$P_{i_{1},i_{2}}P_{i_{2},i_{3}}\cdots
P_{i_{n-1},i_{n}}P_{i_{n},i_{1}}=P_{i_{1},i_{n}}P_{i_{n},i_{n-1}}\cdots
P_{i_{3},i_{2}}P_{i_{2},i_{1}}$ (72)

for any $n\geq 2$ and any sequence of states $s_{i_{1}}$, $s_{i_{2}}$,
$s_{i_{3}}$, …, $s_{i_{n-1}}$, $s_{i_{n}}\in\mathcal{S}$.

One way to understand this theorem is that for reversible Markov chains, the
probability for traversing any closed path in the state space $\mathcal{S}$ is
independent of the direction of traversal. Hence, reversible Markov chains can
be thought of as having zero net circulation. By contrast, recurrent Markov
chains that are non-reversible have at least one path that violates Equation
72, over which there is a higher probability to traverse in one direction than
the other. For the example in Figure 6(a), the relevant closed paths are (up
to a cyclic permutation): (i) $s_{1}\leftrightarrow s_{2}\leftrightarrow
s_{4}\leftrightarrow s_{3}\leftrightarrow s_{1}$, (ii) $s_{1}\leftrightarrow
s_{2}\leftrightarrow s_{4}\leftrightarrow s_{1}$, (iii) $s_{1}\leftrightarrow
s_{4}\leftrightarrow s_{3}\leftrightarrow s_{1}$. In any of these cases, going
around clockwise is equally probable as going around anticlockwise, which is
to be expected since this Markov chain is reversible. The example in Figure
6(d) has the same closed paths available, except that the outgoing transition
probabilities from $s_{1}$ have been changed. This small adjustment is enough
to introduce circulation on all the closed paths: for both (i) and (iii) the
anticlockwise direction is more probable since
$P_{13}P_{34}P_{42}P_{21}>P_{12}P_{24}P_{43}P_{31}$ and
$P_{13}P_{34}P_{41}>P_{14}P_{43}P_{31}$, respectively, and for (ii) the
clockwise direction is more probable since
$P_{12}P_{24}P_{41}>P_{14}P_{42}P_{21}$. Therefore, by virtue of having at
least one path with net circulation, Equation 72 confirms that this chain is
indeed non-reversible.

The foregoing analyses illustrate how Theorem 2.6.4 and Theorem 2.6.5 provide
two alternative but equivalent definitions of reversibility. Something common
to both of these interpretations is that reversible Markov chains satisfy a
type of equilibrium, either between the exchange of probability mass between
pairs of states or the circulation along closed paths, respectively. In fact,
the concept of detailed balance stems from early work in the field of
statistical mechanics aimed at formalizing the notion of thermodynamic
equilibrium on a microscopic level [40]. More recently, Markov chain Monte-
Carlo methods, which are predominantly based on reversible ergodic chains,
have received widespread application in the natural sciences as a way to model
systems that are in thermodynamic equilibrium [36]. Conversely, Markov chains
that violate detailed balance, or equivalently those with net circulation,
have been applied to the less well understood case of systems which are out of
equilibrium [41, 42, 43]. Furthermore, their stationary distributions have
been referred to as non-equilibrium steady states (or NESS) [41, 42, 43, 34,
44], which reflects the fact that such distributions are kept fixed over time
via unequal flows of probability mass between states ($\bm{\pi}_{2}$ is an
example of a NESS, as can be seen in the bar plot in Figure 6(f)).

Reversible Markov chains are significantly easier to treat both analytically
and numerically than non-reversible chains. Because of this, there exist
various procedures for modifying a non-reversible Markov chain so that it
becomes reversible, which is sometimes referred to as reversibilization [45,
38]. For a recurrent chain, this can be done by taking an average of the
forward and backwards transition probabilities, $\bm{P}$ and
$\bm{P}_{\text{rev}}$, that describe the chain and its time reversal,
respectively. This averaging process can be either additive or multiplicative,
leading to the following two definitions:

######  Definition 2.6.6 (Additive Reversibilization).

Let $\mathcal{X}$ be a recurrent non-reversible Markov chain with transition
matrix $\bm{P}$ and a stationary distribution $\bm{\pi}>0$. Then the additive
reversibilization of $\mathcal{X}$ is a chain with the following transition
matrix:

$\displaystyle\bm{P}_{\textup{A}}$
$\displaystyle:=\frac{\bm{P}+\bm{P}_{\textup{rev}}}{2}$ (73)
$\displaystyle\;=\frac{\bm{P}+\bm{\Pi}^{-1}\bm{P^{T}}\bm{\Pi}}{2}$ (74)

and for which $\bm{\pi}$ is also a stationary distribution.

######  Definition 2.6.7 (Multiplicative Reversibilization).

For a non-reversible Markov chain with transition matrix $\bm{P}$ and a
strictly positive stationary distribution $\bm{\pi}$, the multiplicative
reversibilization produces a Markov chain described by the following
transition matrix:

$\displaystyle\bm{P}_{\textup{M}}$
$\displaystyle:=\bm{P}\bm{P}_{\textup{rev}}$ (75)
$\displaystyle\;=\bm{P}\bm{\Pi}^{-1}\bm{P^{T}}\bm{\Pi}$ (76)

and for which $\bm{\pi}$ is also a stationary distribution.

Since both definitions produce chains that have the same set of stationary
distributions as the starting chain, a simple way to verify their
reversibility is to calculate the flow matrix for the distribution $\bm{\pi}$.
For the additive reversibilization this gives:

$\displaystyle\bm{F}_{\text{A}}^{\bm{\pi}}$
$\displaystyle=\bm{\Pi}\bm{P}_{\textup{A}}$ (77)
$\displaystyle=\frac{\bm{\Pi}\bm{P}+\bm{P^{T}}\bm{\Pi}}{2}$ (78)
$\displaystyle=\frac{\bm{\Pi}\bm{P}+(\bm{\Pi}\bm{P})^{T}}{2}$ (79)
$\displaystyle=\frac{\bm{F}^{\bm{\pi}}+(\bm{F}^{\bm{\pi}})^{T}}{2}$ (80)

and for the multiplicative reversibilization:

$\displaystyle\bm{F}_{\text{M}}^{\bm{\pi}}$
$\displaystyle=\bm{\Pi}\bm{P}_{\textup{M}}$ (81)
$\displaystyle=\bm{\Pi}\bm{P}\bm{\Pi}^{-1}\bm{P^{T}}\bm{\Pi}$ (82)
$\displaystyle=(\bm{\Pi}\bm{P}\bm{\Pi}^{-\frac{1}{2}})(\bm{\Pi}^{-\frac{1}{2}}\bm{P}^{T}\bm{\Pi})$
(83)
$\displaystyle=(\bm{\Pi}\bm{P}\bm{\Pi}^{-\frac{1}{2}})(\bm{\Pi}\bm{P}\bm{\Pi}^{-\frac{1}{2}})^{T}$
(84)

both of which are by definition symmetric. While Equation 84 does not admit a
simple interpretation, Equation 80 says that for the additive
reversibilization the flow matrix is symmetric because it corresponds to an
average of the forwards flow, $\bm{F}^{\bm{\pi}}$, and backwards flow,
$(\bm{F}^{\bm{\pi}})^{T}$, of the starting chain $\mathcal{X}$. This
interpretation is used when we consider random walks on directed graphs in
Section 4.3.

###  2.7 Absorbing chains

Finally, one concept in the theory of Markov chains that is particularly
relevant to applied domains is absorption. A state $s_{i}\in\mathcal{S}$ is
called absorbing if it is possible to transition into the state but not out of
it, meaning that $P_{ii}=1$ and the chain stays in $s_{i}$ for all future time
steps. An absorbing Markov chain is one for which from every state
$s_{i}\in\mathcal{S}$ there exists some path to an absorbing state. Since it
is possible to start in a non-absorbing state and never return, all non-
absorbing states are transient, and the presence of such states means that
absorbing chains can be neither reversible nor ergodic. Absorbing chains often
occur in Markov Decision Processses (MDPs), which are central to the field of
reinforcement learning [32].

The possible transitions in an absorbing chain can be partitioned into three
types: (i) transient $\to$ transient, (ii) transient $\to$ absorbing, and
(iii) absorbing $\to$ absorbing. Although the assignment of indices to states
in $\mathcal{S}$ is arbitrary, an assignment based on this partitioning
simplifies the analysis of absorbing Markov chains.

######  Definition 2.7.1 (Canonical Form).

For an absorbing Markov chain with $r$ absorbing and $t$ transient states, the
transition matrix $\bm{P}$ can be arranged to have the following block
structure, known as the canonical form:

$\bm{P}=\left(\begin{array}[]{c|c}\bm{Q}&\bm{R}\\\
\hline\cr\bm{0}&\bm{\mathbbm{1}}\\\ \end{array}\right)$ (85)

where $\bm{Q}\in\mathbb{R}^{t\times t}$, $\bm{R}\in\mathbb{R}^{t\times r}$ and
$\bm{\mathbbm{1}}\in\mathbb{R}^{r\times r}$ describe transitions of type (i),
(ii), and (iii), respectively, and $\bm{0}\in\mathbb{R}^{r\times t}$ is a
matrix of zeros. Thus, matrix $\bm{Q}$ is what remains of $\bm{P}$ when we
remove any absorbing states from $\mathcal{S}$.

We depict this partitioning of transition probabilities in Figure 7(a). An
absorbing chain with one absorbing state is shown, with the transitions
belonging to $\bm{Q}$, $\bm{R}$ and $\bm{\mathbbm{1}}$ colored black, red and
blue, respectively. Furthermore, in Figure 7(b) we show the matrices $\bm{Q}$
and $\bm{R}$.

(a)

$\bm{Q}=\left(\begin{array}[]{cccc}0.2&0.4&0.4\\\ 0.3&0&0.5\\\
0.3&0.5&0\end{array}\right)$

$\bm{R}=\left(\begin{array}[]{cccc}0\\\ 0.2\\\ 0.2\end{array}\right)$

(b)

Figure 7: (a) The transition graph of an absorbing Markov chain with $4$
states, where $s_{4}$ is an absorbing state, and (b) the matrices $\bm{Q}$ and
$\bm{R}$ associated to this chain.

Since any transient state can reach an absorbing state in a finite number of
steps, the probability that the chain ends up in an absorbing state at some
future time is 1. For this reason, in the infinite time limit we can expect to
see no transitions taking place between transient states, i.e.
$\lim_{n\to\infty}\bm{Q}^{n}=0$. This is an advantageous property, since it
means that if we sum up all powers of $\bm{Q}$, known as the Neumann series of
$\bm{Q}$, then the contributions for larger powers get progressively smaller
and the sum converges to $(\bm{\mathbbm{1}}-\bm{Q})^{-1}$ (see [35] p. 618).
Calculating this sum for $\bm{Q}$ leads to the following useful quantity which
relates transient states in $\mathcal{S}$ [37]:

######  Definition 2.7.2 (Fundamental Matrix).

For any absorbing Markov chain, the Neumann series of matrix $\bm{Q}$ is given
by:

$\displaystyle\bm{N}$ $\displaystyle:=\sum_{k=0}^{\infty}\bm{Q}^{k}$ (86)
$\displaystyle\;=\bm{\mathbbm{1}}+\bm{Q}+\bm{Q}^{2}+\bm{Q}^{3}+...$ (87)
$\displaystyle\;=(\bm{\mathbbm{1}}-\bm{Q})^{-1}$ (88)

and is known as the fundamental matrix of the Markov chain. The elements of
this matrix $N_{ij}$ give the expected number of times the chain visits a
transient state $s_{j}$ before absorption, given that the chain started in a
transient state $s_{i}$.

When analyzing an absorbing chain, it is very handy to have access to the
fundamental matrix. By taking into account all non-negative powers of
$\bm{Q}$, it contains information about all possible paths available between
pairs of transient states. Because of this, it is a useful predictive tool
that allows several properties of the Markov chain to be deduced [37].
Furthermore, in the field of reinforcement learning, it is closely related to
the successor representation [46].

###  2.8 Summary

Figure 8: A Venn diagram composed of the different types of Markov chains
introduced in this section.

This concludes our exploration of different types of Markov chains. In Figure
8, we provide a summary of the material presented in this section in the form
of a Venn diagram. In this diagram, each type of Markov chain is drawn as a
circle or ellipse, with defining properties/results listed in each case. Take
a moment to look at this image and pay attention to the overlapping regions
which indicate how different types of chains are related. Furthermore, for a
more in-depth presentation of the material in this section, we recommend [37]
and [38].

In the next section, we introduce graphs as an alternative way to describe
Markov chains and summarize insights that emerge from this description. Then,
in Section 4 the connection between graphs and Markov chains is explored in
more depth using the notion of random walks, which allows various
relationships to be made between specific types of graphs and some types of
Markov chains introduced in this section.

##  3 Graphs

So far, we have implicitly been interpreting Markov chains as graphs whenever
we draw a transition graph. In the current section, we formally introduce the
concept of graphs, which provides a foundation to the material on random walks
in Section 4. Readers should note that definitions in graph theory often vary
between different sources. Here we use a convention that can encompass a wider
variety of graphs, thereby offering greater generality.

###  3.1 Definition

A graph $G=(V,E)$ is a set of $N$ vertices $V=\\{v_{1},v_{2},\cdots,v_{N}\\}$
together with an edge set $E$ containing pairs of vertices in $V$.
Conceptually, $V$ might represent a collection of objects, and $E$ a
specification of how some pairs in this collection are related to one another.
A natural way to categorize graphs is based on the way in which edges are
defined. For instance, in an undirected graph each edge has no direction and
is typically denoted as $(v_{i},v_{j})\in E$, whereas in a directed graph each
edge has a specified starting and ending vertex and is usually denoted as
$(v_{i}\to v_{j})\in E$. Examples of undirected and directed graphs can be
seen in the first and second rows of Figure 9, respectively. Unless otherwise
stated, we depict undirected edges as straight lines and directed edges as
curved lines with arrowheads indicating the direction. A second distinction we
can make is between unweighted graphs, in which one only cares about whether
two vertices are related or not, and weighted graphs, in which each edge has a
positive weight $w_{ij}$ describing the strength of the relationship.333We
restrict edge weights to be positive in order to maintain this notion of
strength, however it is worth noting that some conventions in graph theory
allow negative weights. In Figure 9, the examples in the first column are
unweighted and all other graphs are weighted, with weights indicated by
numbers next to each edge. The type of edges that a graph has is often chosen
based on the type of relationship that one wants to describe. For example,
assume that we have a graph $G$ where vertices represent PhD students. Then,
if we want to represent the relationship of being in the same research group,
undirected unweighted edges are a natural choice (such as Figure 9(a)).
Conversely, if we want edges to describe whether one student has participated
on a main project of another student, then this clearly requires directed
unweighted edges (such as Figure 9(d)). If we now consider variants of the
first and second examples, instead focusing on how similar the research topics
of two students are, or how much work has one student has contributed to
another student’s project, then we now need undirected weighted and directed
weighted edges, respectively (such as Figure 9(b,c) and Figure 9(e,f)). It is
worth noting that in order to assign weights to edges, one needs to specify a
scale on which to measure the strength of relationships between vertices.

$\bm{A}=\left(\begin{array}[]{cccc}0&1&0&0\\\ 1&0&1&1\\\ 0&1&0&1\\\ 0&1&1&0\\\
\end{array}\right)$

(a)

$\bm{W}=\left(\begin{array}[]{cccc}0&2&0&0\\\ 2&0&0.5&1\\\ 0&0.5&0&0.8\\\
0&1&0.8&0\\\ \end{array}\right)$

(b)

$\bm{W}=\left(\begin{array}[]{cccc}0&3&0&0\\\ 3&0&0&0\\\ 0&0&0&2\\\ 0&0&2&0\\\
\end{array}\right)$

(c)

$\bm{A}=\left(\begin{array}[]{cccc}0&1&0&0\\\ 1&0&0&1\\\ 0&1&0&0\\\ 0&1&1&0\\\
\end{array}\right)$

(d)

$\bm{W}=\left(\begin{array}[]{cccc}0&0.5&0&0\\\ 1&0&0&2\\\ 0&1&0&0\\\
0&1&0.8&0\\\ \end{array}\right)$

(e)

$\bm{W}=\left(\begin{array}[]{cccc}0&0&1&0\\\ 0&0&0&2\\\ 3&0&0&0\\\ 0&1&4&0\\\
\end{array}\right)$

(f)

Figure 9: Six examples of graphs and their corresponding matrices. (a-c) are
undirected whereas (d-f) are directed. Furthermore, (a,d) are unweighted
whereas (b,c,e,f) are weighted.

One can also describe graphs based on their connectivity. In an undirected
graph, if there exists a path between each pair of vertices then the graph is
said to be connected, otherwise it is disconnected. The notion of connectivity
can generalize to disconnected graphs if we instead consider subsets of
vertices in $G$, which are known as subgraphs. Any subgraph that is connected
but is not part of any larger connected subgraph is called a connected
component. Both of the undirected graphs in Figure 9(a, b) are connected,
whereas Figure 9(c) shows an example that is disconnected, with two connected
components. In particular, this latter example even has a vertex that does not
have any edges at all, which is known as an isolated vertex. For a directed
graph, if there are directed paths running from $v_{i}$ to $v_{j}$ and from
$v_{j}$ to $v_{i}$ for all pairs of vertices $v_{i},v_{j}\in V$ then the graph
is said to be strongly connected. Alternatively, a directed graph is weakly
connected if for all pairs of vertices $v_{i},v_{j}\in V$ it is possible to
get from $v_{i}$ to $v_{j}$ and from $v_{j}$ to $v_{i}$ by any path,
regardless of the direction of edges. Clearly, a directed graph is weakly
connected if it is strongly connected, but not vice versa. Furthermore,
strongly or weakly connected subgraphs that are not part of any larger such
subgraphs are referred to as strongly or weakly connected components,
respectively. The directed graphs in Figure 9(d,e) are strongly connected,
whereas the one in Figure 9(f) is only weakly connected and has a two strongly
connected components (take a moment to verify this).

###  3.2 Matrix representation

A natural way to numerically represent graphs with $|V|=N$ vertices is with a
$N\times N$ matrix. In the unweighted case, this matrix is a binary matrix
$\bm{A}$, with entries:

$A_{ij}:=\left\\{\begin{array}[]{ll}1&\mbox{if }(v_{i}\sim v_{j})\in E\\\
0&\mbox{otherwise}\end{array}\right.$ (89)

where $(v_{i}\sim v_{j})=(v_{i},v_{j})$ when $G$ is undirected, and
$(v_{i}\sim v_{j})=(v_{i}\to v_{j})$ when it is directed. Furthermore, the
matrix $\bm{A}$ is usually referred to as the adjacency matrix of $G$. This
extends easily to the weighted case, where instead we have a non-negative
matrix $\bm{W}$, with entries:

$W_{ij}:=\left\\{\begin{array}[]{ll}w_{ij}&\mbox{if }(v_{i}\sim v_{j})\in E\\\
0&\mbox{otherwise}\end{array}\right.$ (90)

which is often referred to as the weight matrix of $G$. In Figure 9, the
relevant matrix is shown below each graph, and we encourage readers to verify
that they match in each case. Furthermore, something worth pointing out is
that undirected graphs always have corresponding matrices that are symmetric,
as can be seen in Figure 9(a-c).

$\bm{W}=\left(\begin{array}[]{ccc}0&3&0\\\ 3&0&1\\\ 0&1&0\end{array}\right)$

Figure 10: An undirected graph represented both with undirected edges (top)
and pairs of directed edges (middle), as well as its weight matrix (bottom).

For the remainder of this tutorial, we assume that the graphs we deal with are
both weighted and directed. The reason we choose this convention is that it is
more general. On one hand, any unweighted graph can be considered as a special
case of a weighted graph where the weights are all set to $1$. Thus, we
henceforth only talk about weight matrices as opposed to adjacency matrices
when describing graphs numerically. On the other hand, there is one sense in
which directed graphs can be thought of as a generalization of undirected
graphs. If $v_{i}$ and $v_{j}$ are two distinct vertices that share an edge in
an undirected graph, then the weight of this edge is guaranteed to appear
twice in the weight matrix $\bm{W}$ by virtue of it being symmetric. If
instead these vertices belong to a directed graph and there is an edge
$(v_{i}\to v_{j})$, then this edge appears only once in $\bm{W}$. Therefore,
it is possible to interpret an undirected edge between $v_{i}$ and $v_{j}$ as
being equivalent to a pair of directed edges of the same weight, with one
connecting $v_{i}$ to $v_{j}$ and the other connecting $v_{j}$ to $v_{i}$.
This is the interpretation we use throughout the rest of the tutorial whenever
we refer to undirected graphs. As an example, in Figure 10 we show two
equivalent depictions of an undirected graph, with the top image drawn in the
usual way, and the bottom image drawn using pairs of directed edges. Below
these two drawings, the weight matrix of this graph is shown. One must note
that interpreting undirected graphs in this way is somewhat atypical, however
it allows us a greater level of generality when dealing with different types
of graphs in Section 4. Furthermore, this interpretation only applies to edges
between distinct vertices, and edges that connect vertices to themselves are
discussed in Section 3.4.

###  3.3 Vertex degrees

Once the weight matrix of a graph is known, it is easy to calculate the total
weight coming in and out of each vertex. The total incoming weight of a vertex
$v_{i}$ can be found by summing over the $i$-th column of $\bm{W}$, and is
known as the in-degree of $v_{i}$, i.e. $d_{i}^{-}:=\sum_{j=1}^{N}W_{ji}$.
Conversely, the total outgoing weight of $v_{i}$ is calculated by the sum over
the $i$-th row of $\bm{W}$, i.e. $d_{i}^{+}:=\sum_{j=1}^{N}W_{ij}$, and is
known as the out-degree of $v_{i}$. Since undirected graphs always have
bidirectional edges and symmetric weight matrices, the in- and out-degrees of
such graphs are always equal, and are simply referred to as vertex degrees,
denoted by $d_{i}$.444Since in graph theory unweighted graphs are a more
commonly studied than weighted graphs, the degree quantities we have defined
are sometimes referred to as weighted degrees [47], but for simplicity we just
use the term degree.

$\bm{W}=\left(\begin{array}[]{cccc}0&3&0&0\\\ 1&0&4&0\\\ 0&2&0&2\\\
2&0&0&0\end{array}\right)$

Figure 11: A balanced graph (top) and its weight matrix (bottom).

For example, in the graph of Figure 10 the degrees are $d_{1}=3$, $d_{2}=4$
and $d_{3}=1$. In the more general case of directed graphs, there is no
guarantee that $d_{i}^{+}=d_{i}^{-}$. However, summing over all in- or out-
degrees for any graph always produces the same number, i.e.
$\text{vol}(G)=\sum_{i=1}^{N}d_{i}^{+}=\sum_{i=1}^{N}d_{i}^{-}=\sum_{i=1}^{N}\sum_{j=1}^{N}W_{ij}$,
which is sometimes referred to as the volume of $G$. As an example, consider
the directed graph in Figure 9(e): each vertex has a different in- and out-
degrees, i.e. $d_{1}^{-}=1$, $d_{1}^{+}=0.5$, $d_{2}^{-}=2.5$, $d_{2}^{+}=3$,
$d_{3}^{-}=0.8$, $d_{3}^{+}=1$, $d_{4}^{-}=2$ and $d_{4}^{+}=1.8$, but summing
over either of the degree types yields $\text{vol}(G)=6.3$. Nonetheless, some
directed graphs can have $d_{i}^{+}=d_{i}^{-}$ for each vertex, and such cases
are known as balanced graphs [48, 49]. In keeping with the notation of
undirected graphs, we denote the vertex degrees of a balanced graph as
$d_{i}=d_{i}^{+}=d_{i}^{-}$. An example of a balanced graph along with its
corresponding weight matrix is shown in Figure 11, and a quick check reveals
that summing over the rows or columns of $\bm{W}$ indeed yields the same
values. Just as a balanced graph is a special case of a directed graph, we can
similarly say that an undirected graph is a special case of a balanced graph,
and this interpretation is important in Section 4.

###  3.4 Self-loops

In the examples considered so far, all edges connect pairs of vertices that
are distinct, i.e. $v_{i}\neq v_{j}$. While this is sometimes enforced as a
rule, some conventions also allow edges to connect vertices to themselves,
which are known as self-loops. For undirected graphs, the standard convention
is that a self-loop at vertex $v_{i}$ counts doubly to the vertex degree
$d_{i}$, while other edges only count singly, i.e. $d_{i}=2\times
W_{ii}+\sum_{j\neq i}W_{ij}$. This somewhat counter-intuitive property is
typically demonstrated using the degree sum formula [50]. For undirected
graphs, this states that each edge contributes twice its weight to the volume.
Since self-loops only involve a single vertex, the only way that this rule can
be respected is if they count twice as much to the vertex degrees as other
edges. A property that we require when dealing with undirected graphs in
Section 4 is that the vertex degrees are calculated by the row sums of
$\bm{W}$.

$\bm{W}=\left(\begin{array}[]{cc}4&3\\\ 3&5\\\ \end{array}\right)$

(a)

$\bm{W}=\left(\begin{array}[]{cc}2&5\\\ 3&4\\\ \end{array}\right)$

(b)

Figure 12: (a) An undirected graph containing self-loops, and its weight
matrix (bottom). (b) A directed graph containing self-loops (top), and its
weight matrix (bottom).

Clearly, this property is violated by the factor of $2$ that applies to
undirected self-loops. As a result, in this tutorial we assume that self-loops
are always directed, regardless of whether they occur in undirected or
directed graphs. This is an atypical definition, since undirected graphs
typically are not allowed to have directed edges. However, as can be seen from
the examples in Figure 12, this preserves the fact that undirected graphs have
symmetric weight matrices, whereas directed graphs have non-symmetric weight
matrices, which is sufficient for the scope of this tutorial.

We close this section by noting some similarities between our definitions of
Markov chains and graphs. Firstly, the transition matrices of Markov chains,
like the weight matrices of graphs, are non-negative. Secondly, in a directed
graph any entry $W_{ij}\neq 0$ of the weight matrix describes an outgoing edge
from vertex $v_{i}$ to $v_{j}$, and analogously any entry $P_{ij}\neq 0$ of a
transition matrix describes an outgoing transition probability from $s_{i}$ to
$s_{j}$. Putting these together, we see that in the most general sense any
Markov chain can be thought of as a directed graph, with $\bm{P}$ being the
associated weight matrix. Indeed, this interpretation is precisely what
justifies us in visualizing a Markov chain by its transition graph. In the
next section, we present some useful results that emerge as a result of this
way of thinking about a Markov chain. Lastly, for a comprehensive text on
graph theory that covers much of the material in this section, we recommend
[50].

###  3.5 Eigenspaces of transition matrices

Non-negative matrices have received widespread attention in mathematics, and
in particular their eigenvalues and eigenvectors are the focus of spectral
graph theory [51]. In this section, we apply some results from this field to
transition matrices, considering first irreducible chains and then
subsequently exploring the generalization to reducible chains.

####  3.5.1 Irreducible chains

A fundamental result used in spectral graph theory is the Perron-Frobenius
theorem, and while a full treatment of it is beyond the scope of this
tutorial, we now summarize its key implications for transition matrices of
irreducible Markov chains.

######  Theorem 3.5.1 (Perron Frobenius theorem for irreducible Markov
chains).

If $\bm{P}$ is the transition matrix of an irreducible Markov chain, then:

  * •

$\lambda=1$ is guaranteed to be an eigenvalue.

  * •

$\lambda=1$ is simple eigenvalue, meaning that it occurs only once.

  * •

Upon suitable normalization, the eigenvalue $\lambda=1$ has a left eigenvector
equal to the unique stationary distribution
$\bm{\pi}=(\pi_{1},\pi_{2},...,\pi_{N})^{T}$ and a right eigenvector equal to
$\bm{\eta}=(1,1,...,1)^{T}$.

  * •

All other eigenvalues have $|\lambda|\leq 1$, where $|\cdot|$ is the complex
modulus, meaning that the spectral radius of $\bm{P}$ is $1$.555We remind
readers that the spectral radius of a square matrix $\bm{X}$ is its largest
eigenvalue in absolute value, and is denoted $\rho(\bm{X})$. The name relates
to the fact that all eigenvalues are contained within a disk of radius
$\rho(\bm{X})$ centered at the origin of the complex plane.

To illustrate the above theorem, in Figure 13(a-c) we show the transition
graphs and eigenvalue plots of three irreducible Markov chains. The first
observation to make is that, in agreement with Theorem 3.5.1, $\lambda=1$ is
an eigenvalue in each case and occurs only once. Furthermore, as a quick
exercise we encourage readers to find the eigenvectors of $\lambda=1$ for each
example and normalize them to obtain $\bm{\pi}$ and $\bm{\eta}$. Lastly, the
eigenvalue plots show that in each example all eigenvalues indeed lie either
on the unit circle ($|\lambda|=1$), or within it ($|\lambda|<1$).

(a) irreducible, $d=1$

(b) irreducible, $d=2$

(c) irreducible, $d=3$

(d) reducible, $d=1$

Figure 13: Four Markov chains, together with plots showing the eigenvalues of
their transition matrices.

Other than $\lambda=1$, Theorem 3.5.1 implies that the following two types of
eigenvalues are also possible: (i) those that lie on other points of the unit
circle (i.e. $|\lambda|=1$, persistent), and (ii) those that lie within the
unit circle (i.e. $|\lambda|<1$, transient). In either case, Equation 45 tells
us that if $\bm{l}_{\omega}$ is a corresponding left eigenvector, then it must
be orthogonal to the unique right eigenvector with $\lambda=1$, which is
$\bm{\eta}$. Therefore:

$\bm{l}_{\omega}^{T}\bm{\eta}=\sum_{i=1}^{N}l_{\omega,i}=0$ (91)

where $l_{\omega,i}$ denotes the $i$-th component of $\bm{l}_{\omega}$.
Consequently, left eigenvectors with $\lambda\neq 1$ sum to zero, meaning that
unlike stationary distributions they are not probability vectors.

Using our terminology from Section 2.3, case (i) includes transient
structures, transient oscillations and transient cycles. Of the irreducible
chains in Figure 13, only (a) and (b) have eigenvalues of this type, and in
both cases they are complex conjugate pairs describing transient cycles.
Looking at the transition probabilities in each example, it is clear that
these transient cycles flow clockwise around the state space.

Case (ii) on the other hand includes persistent oscillations and persistent
cycles. Theorem 2.5.2 tells us that these are only possible when a chain is
periodic. The following result sheds light on this by relating the eigenvalues
with $|\lambda|=1$ to the period of a chain [52]:

######  Proposition 3.5.2.

If $\bm{P}$ is the transition matrix of an irreducible Markov chain with
period $d$, then there are $d$ distinct eigenvalues with modulus $1$, given
by:

$\lambda_{1}=1,\lambda_{2}=\phi,\lambda_{3}=\phi^{2},...,\lambda_{d}=\phi^{d-1}$
(92)

where $\phi=e^{\frac{2\pi i}{d}}$.

In simple terms, 3.5.2 says that the eigenvalues of $\bm{P}$ with modulus $1$
are always $d$-th roots of unity. We can verify this by checking the periodic
examples in Figure 13(b,c). In both case the number of eigenvalues on the unit
circle is indeed equal to the period of the chain and they are also equally
spaced. Furthermore, 3.5.2 offers an alternative perspective on how the
periodicity affects the persistent behavior of a Markov chain. For example,
the chain in Figure 13(a) has only a single vector on the unit circle,
corresponding to its unique stationary distribution. It is therefore
guaranteed to end up in this distribution since all other eigenvalues have
$|\lambda|<1$. This is equivalent to the statement that this chain is ergodic,
which a quick check of the transition graph confirms. Conversely, the chain in
Figure 13(b) has an additional eigenvalue $\lambda=e^{\pi i}=-1$ on the unit
circle, by virtue of the fact that it has period $2$. Therefore, its
persistent behavior can only be fully described using both the unique
stationary distribution $\bm{\pi}$ and the eigenvector $\bm{y}$ associated to
$\lambda=-1$. For example, we know from Theorem 2.5.2 that such a chain can
get trapped in a persistent oscillation (i.e.
$\bm{\mu}_{1}\to\bm{\mu}_{2}\to\bm{\mu}_{1}\to\bm{\mu}_{2}\to...$). For any
such oscillation, $\bm{\mu}_{1}$ and $\bm{\mu}_{2}$ can always be expressed as
a linear combination of $\bm{\pi}$ and $\bm{y}$, meaning that this sequence
indeed oscillates between two points in the space spanned by these
eigenvectors. While this example only involves real eigenvalues and therefore
only real eigenvectors, the interpretation extends to $d>2$, for which 3.5.2
tells us that there must be complex eigenvalues with $|\lambda|=1$. For
example, the chain in Figure 13(c) has period $d=3$, and it has the following
$3$ eigenvalues on the unit circle: $\lambda_{1}=1$,
$\lambda_{2}=e^{\frac{2\pi i}{3}}$ and $\lambda_{3}=e^{\frac{4\pi i}{3}}$.
Analogous to the $d=2$ case, any persistent cycle of this chain can be
expressed using the three corresponding eigenvectors, which in the case of
$\lambda_{2}$ and $\lambda_{3}$ must have complex entries. Rather
interestingly, this means that for chains with period $d>2$, persistent cycles
are cycles in a complex space despite being sequences of real valued
distributions.

####  3.5.2 Reducible chains

Applying spectral graph theory to the transition matrices of reducible Markov
chains produces a weaker set of results. For example, the generalization of
Theorem 3.5.1 to the reducible chains is the following:

######  Theorem 3.5.3 (Perron Frobenius theorem for reducible Markov chains).

If $\bm{P}$ is the transition matrix of a reducible Markov chain, then:

  * •

$\lambda=1$ is guaranteed to be an eigenvalue.

  * •

The number of linearly independent eigenvectors with $\lambda=1$ is equal to
the number r of recurrent communicating classes in the Markov chain.

  * •

There are many choices of left and right eigenvectors for $\lambda=1$.
However, a convenient choice which mirrors the irreducible case is to choose
$\bm{\pi}_{k}$ and $\bm{\eta}_{k}$ as a pair of left and right eigenvectors
for each of the recurrent communicating classes, with $\bm{\pi}_{k}$ being the
unique stationary distribution associated to each class and $\bm{\eta}_{k}$
being an indicator vector with entry $1$ for states in this class and zeros
elsewhere.

  * •

All other eigenvalues have $|\lambda|\leq 1$, where $|\cdot|$ is the complex
modulus, meaning that the spectral radius of $\bm{P}$ is $1$.

To understand Theorem 3.5.3 in more depth, consider the example in Figure
13(d). This Markov chain has $2$ recurrent communicating classes, which means
that $\lambda=1$ has a multiplicity of $2$. We indicate this on the eigenvalue
plot by a larger size circle. Furthermore, we color this circle half red and
half blue to reflect the fact that we can choose the eigenvectors for
$\lambda=1$ based on the two recurrent communicating classes, i.e.
$\bm{\pi}_{1}=(0.58,0.42,0,0)^{T}$ and $\bm{\eta}_{1}=(1,1,0,0)^{T}$ as a pair
of left and right eigenvectors for the red class, and
$\bm{\pi}_{2}=(0,0,0.43,0.57)^{T}$ and $\bm{\eta}_{2}=(0,0,1,1)^{T}$ as a pair
of left and right eigenvectors for the blue class. Then, $\bm{\pi}_{1}$ and
$\bm{\pi}_{2}$ together span the left eigenspaces of $\lambda=1$ (including
all possible stationary distributions), whereas $\bm{\eta}_{1}$ and
$\bm{\eta}_{2}$ span the right eigenspaces of $\lambda=1$. It is worth
emphasizing that while there are an infinite number of other ways to choose
the basis vectors for $\lambda=1$, this is a convenient choice since it is the
only one for which all basis vectors have strictly non-negative entries. For
example, consider the choice of
$\tilde{\bm{\pi}}_{1}=\frac{1}{3}\bm{\pi}_{1}+\frac{2}{3}\bm{\pi}_{2}=(0.19,0.14,0.29,0.38)^{T}$
and $\tilde{\bm{\eta}}_{1}=\bm{\eta}=(1,1,1,1)^{T}$ as a first pair of
eigenvectors. If we then choose a second pair $\tilde{\bm{\pi}}_{2}$ and
$\tilde{\bm{\eta}}_{2}$ that satisfy biorthogonality (Equation 46) within this
space, they are guaranteed to contain negative entries, for example
$\tilde{\bm{\pi}}_{2}=\bm{\pi}_{1}-\bm{\pi}_{2}=(0.58,0.42,-0.43,-0.57)^{T}$
and
$\tilde{\bm{\eta}}_{2}=3\bm{\eta}_{1}-\frac{3}{2}\bm{\eta}_{2}=(3,3,-\frac{3}{2},-\frac{3}{2})^{T}$.
Thus, the choice of eigenvectors stated in Theorem 3.5.3 is in some sense
special since it is the only one that preserves our intuition that left
eigenvectors with $\lambda=1$ correspond to distributions over the state space
$\mathcal{S}$. For this reason, we henceforth assume this convention when
referring to eigenvectors with $\lambda=1$.

Unfortunately, there is no general analogue of Equation 91 for reducible
chains. One reason for this is that, like the $\lambda=1$ case, there are many
choices of eigenvectors for $\lambda\neq 1$. However, for a recurrent
reducible chain the transition matrix can be written in block diagonal form
(see proof of 2.6.2), which means we can mirror the $\lambda=1$ case by
choosing eigenvectors with $\lambda\neq 1$ to have non-zero entries only in a
single recurrent class. If the $k$-th recurrent class has $n$ states, then the
corresponding block is a $n\times n$ matrix, meaning that there are a total of
$n$ pairs of left and right eigenvectors with non-zero entries for states in
this class, i.e. one pair with $\lambda=1$ ($\bm{\pi}_{k}$ and
$\bm{\eta}_{k}$), and another $n-1$ pairs with $\lambda\neq 1$. We can
therefore apply an equivalent argument to Equation 91 for the $k$-th class,
but instead using the vector $\bm{\eta}_{k}$. Thus, for each recurrent class,
the left eigenvectors with $\lambda\neq 1$ can also be chosen such that they
all sum to zero. Conversely, non-recurrent chains cannot be written in block
diagonal form, which means that this argument cannot be applied. Therefore,
some eigenvectors will not sum to zero for such chains, although to our
knowledge this case has not received significant attention so far in the
literature.

Looking at the eigenvalue plot of Figure 13(d), we see that there are two
eigenvalues with $|\lambda|<1$, both of which are real and negative. Using the
terminology from Section 2.3, they therefore correspond to transient
oscillations of the chain. Furthermore, since the chain is recurrent we can
apply the procedure described above and choose one eigenvector to have non-
zero entries only in the red class, and the other eigenvector to have non-zero
entries only in the blue class. With this choice, we see that each transient
oscillation takes place on a distinct communicating class, which we indicate
on the plot by coloring the eigenvalues red and blue.

In the case of 3.5.2, the extension to reducible chains is straightforward
since one can simply apply this result individually to each recurrent
communicating class of a reducible chain. Therefore, for each class of period
$d$, there are $d$ eigenvalues of modulus $1$ that satisfy the same properties
as in the irreducible case.

Lastly, a couple of similarities between Theorem 3.5.3 and Theorem 3.5.1 can
be pointed out. Firstly, in both theorems $\lambda=1$ is guaranteed to be an
eigenvalue. Since every eigenvalue has at least one eigenvector, this means
that we can always find a left eigenvector with $\lambda=1$. Provided that we
choose an eigenvector with non-negative entries and normalize it to one, it is
a stationary distribution of the chain. This therefore justifies our claim
from Section 2.2 that every finite Markov chain has at least one stationary
distribution. Secondly, in both theorems the eigenvalues cannot have absolute
value greater than one, which is one of the assumptions we made when studying
the evolution of a chain in terms of its eigenvectors and eigenvalues in
Section 2.3, and which justified our partitioning of Equation 54 into
persistent and transient terms.

The results of this section emerge by treating Markov chains as graphs.
However, in most graphs the outgoing edges from each vertex do not sum up to
$1$, meaning that they cannot be interpreted as transition probabilities.
Because of this, Markov chains can be more precisely interpreted as a type of
normalized graph. This idea is formalized in the next section, where we
introduce a well-known method for transforming any graph $G$ into a Markov
chain.

##  4 Random walks

###  4.1 Definition

Suppose we have a graph $G$ with weight matrix $\bm{W}$ that we want to
normalize such that the outgoing weights from each vertex $v_{i}$ sum up to
$1$.666For this definition to work, we require that all vertices have
$d_{i}^{+}>0$, meaning that isolated vertices or vertices with only incoming
edges are forbidden. The most obvious way to do this is to divide all entries
in the $i$-th row of $\bm{W}$ by $d_{i}^{+}$. By scaling each edge weight
$W_{ij}$ by the out-degree of the starting vertex $v_{i}$, we obtain the
transition probabilities $P_{ij}=\frac{W_{ij}}{d_{i}^{+}}$. In order to write
this in matrix notation, we first define a degree matrix $\bm{D}$ whose
elements are given by:

$D_{ij}:=\left\\{\begin{array}[]{ll}d_{i}^{+}&\mbox{if }i=j\\\
0&\mbox{otherwise}\end{array}\right.$ (93)

Since $d_{i}^{+}>0$, we can invert $\bm{D}$ to produce a diagonal matrix with
the entries $\frac{1}{d_{i}^{+}}$ on the diagonals. Using this inverse,
$\bm{W}$ can be row normalized by multiplying with $\bm{D}^{-1}$ from the
left:

$\bm{P}:=\bm{D}^{-1}\bm{W}$ (94)

The Markov chain represented by Equation 94 is called the random walk on $G$
[53, 54]. This is a fitting name, since if we imagine an agent walking between
vertices in $G$, and randomly choosing where to go at each time step based on
the weights of outgoing edges, then Equation 94 would describe the resulting
Markov chain.

Qualitatively, we can say that the transformation in Equation 94 is useful
when we have a starting graph $G$ that we would like to describe in
probabilistic and/or temporal terms. Conversely, if we have a starting Markov
chain and transition matrix $\bm{P}$, knowing some matrix $\bm{W}$ for which
Equation 94 holds can offer insight into the type of relationships between
states that give rise to the chain. However, the latter of these two
perspectives is partially complicated by the fact that the mapping from
$\bm{P}$ to $\bm{W}$ is one-to-many, and there are in fact an infinite number
of different graphs $G$ which produce the same Markov chain. As an example, in
Figure 14 we show two distinct weight matrices $\bm{W}_{1}$ and $\bm{W}_{2}$
that get transformed to the same transition matrix $\bm{P}$ using Equation 94.
How can we describe the infinite set of graphs corresponding to a single
Markov chain? In principle, it involves undoing the row normalization of
Equation 94. Thus, for a given Markov chain $\mathcal{X}$ with transition
matrix $\bm{P}$, we consider all possible scalings of the rows of $\bm{P}$ by
positive constants. Every such scaling can be described by a diagonal matrix
$\bm{A}\in\mathbb{R}_{>0}^{N\times N}$ that multiplies $\bm{P}$ from the left
to produce a single corresponding weight matrix, i.e. $\bm{W}=\bm{A}\bm{P}$.
As an illustration, in Figure 14(d, e) we show the two scaling matrices that
undo the row normalization of the transition matrix in Figure 14(c) and
transform it back into the weight matrices $\bm{W}_{1}$ and $\bm{W}_{2}$,
respectively. The following definition generalizes this to the set of all such
weight matrices that can be realized in this way:

$\bm{W}_{1}=\left(\begin{array}[]{cccc}0&0&0&1.5\\\ 2&0&6&0\\\ 1&3&0&0\\\
2&0&8&0\\\ \end{array}\right)$

(a)

$\bm{W}_{2}=\left(\begin{array}[]{cccc}0&0&0&6\\\ 20&0&60&0\\\ 3&9&0&0\\\
10&0&40&0\\\ \end{array}\right)$

(b)

$\bm{P}=\left(\begin{array}[]{cccc}0&0&0&1\\\ 0.25&0&0.75&0\\\
0.25&0.75&0&0\\\ 0.2&0&0.8&0\\\ \end{array}\right)$

(c)

$\bm{A}_{1}=\left(\begin{array}[]{cccc}1.5&0&0&0\\\ 0&8&0&0\\\ 0&0&4&0\\\
0&0&0&10\\\ \end{array}\right)$

(d)

$\bm{A}_{2}=\left(\begin{array}[]{cccc}6&0&0&0\\\ 0&80&0&0\\\ 0&0&12&0\\\
0&0&0&50\\\ \end{array}\right)$

(e)

Figure 14: (a, b) The weight matrices of two graphs $G_{1}$ and $G_{2}$ that
have edges connecting the same pairs of states but with different weights, (c)
the transition matrix of the Markov chain produced via a random walk on either
of these graphs, (d, e) the scaling matrices that transform $\bm{P}$ into
$\bm{W}_{1}$ and $\bm{W}_{2}$, respectively.

######  Definition 4.1.1.

For a Markov chain $\mathcal{X}$ defined on a state space with
$|\mathcal{S}|=N$ states and with a transition matrix $\bm{P}$, the following
defines the set of all graphs from which the chain can be generated via a
random walk:

$\mathcal{RW}(\mathcal{X})=\\{G:\bm{W}=\bm{A}\bm{P},\;\textup{where}\;\bm{A}\in\mathbb{R}_{>0}^{N\times
N}\;\textup{is a positive diagonal matrix}\\}$ (95)

which we call the random walk set of $\mathcal{X}$.

A few details are worth noting about 4.1.1. Firstly, since the trivial scaling
$\bm{A}=\mathbbm{1}$ is allowed, $\bm{P}\in\mathcal{RW}(\mathcal{X})$ for any
Markov chain. Secondly, the fact that $\bm{A}\in\mathbb{R}_{>0}^{N\times N}$
means that each of these matrices is invertible, with $\bm{A}^{-1}$ also being
diagonal and having entries equal to the reciprocals of the diagonals of
$\bm{A}$. Consequently, if $\bm{W}_{1}=\bm{A}_{1}\bm{P}$ and
$\bm{W}_{2}=\bm{A}_{2}\bm{P}$ are two weight matrices in the random walk set
of a given Markov chain, we can always write
$\bm{W}_{1}=\bm{A}_{1}\bm{A}_{2}^{-1}\bm{W}_{2}=\bm{A}_{3}\bm{W}_{2}$, meaning
that $\bm{W}_{1}$ and $\bm{W}_{2}$ are also related simply by a row scaling
with positive constants, with $\bm{A}_{3}=\bm{A}_{1}\bm{A}_{2}^{-1}$
describing this scaling. Therefore, the row scaling defined in Equation 95
effectively partitions the set of all non-negative matrices into equivalence
classes. Lastly, since 4.1.1 allows any non-zero scaling of the rows of
$\bm{P}$, the random walk set of any Markov chain predominantly consists of
graphs which are neither undirected nor balanced. In fact, only certain types
of Markov chains have random walk sets that contain undirected or balanced
graphs, as explained by the following two results:

######  Theorem 4.1.2.

A Markov chain $\mathcal{X}$ is recurrent if and only if
$\mathcal{RW}(\mathcal{X})$ contains balanced graphs (proof: see Appendix A).

######  Theorem 4.1.3.

A recurrent Markov chain $\mathcal{X}$ is reversible if and only if the
balanced graphs in $\mathcal{RW}(\mathcal{X})$ are undirected (proof: see
Appendix A).

(a)

(b)

(c)

(d)

(e)

Figure 15: (a-c): The random walk sets of the three Markov chains in Figure
6(a, d, j), including undirected (green), balanced directed (blue), and
unbalanced (red) graphs, as well as the chains themselves (black) which are
reversible (a), recurrent and non-reversible (b), and non-recurrent (c). Venn
diagrams in (d, e) illustrate the relationships between the three types of
graph, and the three types of Markov chain, respectively. In (d) the colors
indicate the type of graph, whereas in (e) they indicate the types of graphs
that exist in the random walk sets of each type of Markov chain. For both Venn
diagrams, the color scheme is in accordance with (a-c).

As an illustration, in Figure 15(a-c) we show the random walk sets for the
three Markov chains that were studied in Figure 6(a, d, j) of Section
2.6.777While the examples here each have a single communicating class, the
analysis would apply equally to chains with multiple classes. In each case,
the Markov chain is located in the center and is colored in black. Other
graphs in the random walk sets are colored based on the graph type
(undirected=green, balanced directed=blue, unbalanced=red), and are depicted
as miniature graphs without edge weights (except for one representative
example of each type). The Markov chains of Figure 15(a, b) are both
recurrent, and we indeed see that their random walk sets contain balanced
graphs (Theorem 4.1.3). In both figures, notice that more unbalanced graphs
are drawn to reflect the fact that they are more numerous than the balanced
cases. Furthermore, the chain in Figure 15(a) is reversible, whereas the chain
in Figure 15(b) is non-reversible, meaning that in the former case all
balanced graphs in $\mathcal{RW}(\mathcal{X})$ are undirected, and in the
latter case they are directed (Theorem 4.1.3). The Markov chain in Figure
15(c) is non-recurrent, and in agreement with Theorem 4.1.2 it contains only
unbalanced graphs. Lastly, note that we do not include a corresponding diagram
for the semi-reversible example in Figure 6(g). However, since such chains can
be made reversible by removing non-recurrent states, a simple extension of
Theorem 4.1.3 ensures that for such chains there exist graphs in
$\mathcal{RW}(\mathcal{X})$ for which the edges between recurrent states are
undirected.

To summarize these observations, in Figure 15(d,e) we show two Venn diagrams
that illustrate the relationships between the different types of Markov chains
and graphs considered. In Figure 15(d), graphs are shown as an outer circle,
with balanced graphs as a particular case, and undirected graphs as a special
type of balanced graph, i.e. graphs $\supset$ balanced graphs $\supset$
undirected graphs (colored red, blue and green, respectively). In Figure
15(e), Markov chains are organized in a similar way, i.e. Markov chains
$\supset$ recurrent chains $\supset$ reversible chains. Moreover, the colors
in the Markov chain diagram are based on the types of graphs allowed in
$\mathcal{RW}(\mathcal{X})$ for each type of chain. For example, reversible
chains are shaded in red and green since they correspond to random walks on
either undirected or unbalanced graphs.

The balanced graphs belonging to a recurrent Markov chain’s random walk set
are in some sense special, since the vertex degrees have a simple relationship
to the stationary probabilities:

######  Proposition 4.1.4.

Let $\mathcal{X}$ be a recurrent Markov chain and $G$ one of the balanced
graphs in $\mathcal{RW}(\mathcal{X})$. Then, the degrees of this graph are
related to one of the stationary distributions $\bm{\pi}>0$ of $\mathcal{X}$,
via:

$\frac{d_{i}}{z}=\pi_{i}$ (96)

where $z=\sum_{i}d_{i}$ is the volume of $G$ (proof: see Appendix A).

For example, evaluating $\frac{d_{i}}{z}$ for $v_{1}$ in the balanced graphs
in Figure 15(a) and Figure 15(b) yields $\frac{20}{48}\approx 0.417$ and
$\frac{290}{714}\approx 0.406$, respectively, which are indeed the stationary
probabilities of state $s_{1}$ for each of the corresponding Markov chains
(see Figure 6(b, e)). This highlights something useful about balanced graphs,
which is that the weight matrix $\bm{W}$ allows direct calculation of one of
the stationary distributions without having to simulate the random walk.
Conversely, for an unbalanced graph there is no universally valid expression
relating stationary probabilities of the random walk to the vertex degrees.

Perhaps the most important conclusion to draw from this section is that one
can always describe a reversible Markov chain as a random walk on some
undirected graph. Since undirected graphs have symmetric weight matrices, and
since matrices of this type have received a large amount of study in
mathematics, this interpretation provides a number of tools for describing
reversible chains in more detail. This is the focus of the next section.
Directed graphs, on the other hand, are as of yet far less understood, meaning
that the same level of description for non-reversible chains is not possible.
However, in Section 4.3 we explore some cases where concepts can be extended
to the directed/non-reversible case. Since balanced directed graphs are less
common objects in graph theory, we do not dedicate a section to them and
instead consider them briefly as a special case in Section 4.3.

###  4.2 Random walks on undirected graphs

####  4.2.1 Relationship to symmetric matrices

In this section, we explore in more depth the connections between real
symmetric matrices and the transition matrices of reversible chains. We start
by providing the following two results for real symmetric matrices:

######  Theorem 4.2.1.

A real matrix $\bm{A}\in\mathbb{R}^{n\times n}$ is symmetric if and only if:

$\langle\bm{A}\bm{x},\bm{x}^{\prime}\rangle=\langle\bm{x},\bm{A}\bm{x}^{\prime}\rangle\quad\forall\bm{x},\bm{x}^{\prime}\in\mathbb{R}^{n}$
(97)

where $\langle\cdot,\cdot\rangle$ denotes the standard Euclidean inner
product.

######  Theorem 4.2.2.

A real matrix $\bm{A}\in\mathbb{R}^{n\times n}$ is symmetric if and only if it
is orthogonally diagonalizable, meaning that there exists a orthogonal matrix
$\bm{Y}$ for which:

$\displaystyle\bm{\Delta}$ $\displaystyle=\bm{Y}^{-1}\bm{A}\bm{Y}$ (98)
$\displaystyle=\bm{Y}^{T}\bm{A}\bm{Y}$ (99)

where $\bm{\Delta}$ is a diagonal matrix.

A couple of details can be pointed out about Theorem 4.2.2. Firstly, by
comparing Equation 98 to our analysis of Section 2.3, we see that the columns
of $\bm{Y}$ are a basis of right eigenvectors of $\bm{A}$ and the rows of
$\bm{Y}^{T}$ are the corresponding dual basis of left eigenvectors. Secondly,
both of these bases are orthonormal since $\bm{Y}$ is orthogonal. Thirdly, the
matrix $\bm{\Delta}$ contains the eigenvalues of $\bm{A}$, which are
guaranteed to be real since all other matrices in Equations 98 and 99 are
real. Lastly, it is worth emphasizing the existential condition of Theorem
4.2.2, since not all choices of eigenvectors of a symmetric matrix obey this
result. On one hand, Equation 98 requires that the sets of left and right
eigenvectors are chosen together to be a biorthogonal system. On the other
hand, even if we assume this property, when a symmetric matrix has repeated
eigenvalues the corresponding eigenvectors can be non-orthogonal. However,
even in this case it is always possible to apply the Gramm-Schmidt procedure
to make them orthonormal, and provided that we find such a basis we can relate
the left and right eigenvectors in the following way:

######  Proposition 4.2.3.

Let $\bm{A}$ be a real symmetric matrix. Then, if $\bm{Y}$ is an orthonormal
basis of right eigenvectors of $\bm{A}$ and $\bm{Y}^{T}$ is the corresponding
dual basis, for each eigenvalue $\lambda_{\omega}$ the left and right
eigenvectors are equal, i.e. $\bm{l}_{\omega}=\bm{r}_{\omega}$.

Clearly, for any Markov chain, reversible or otherwise, the transition matrix
is itself rarely symmetric. Therefore, the results above do not directly apply
to $\bm{P}$. However, reversible Markov chains can be related in a number of
ways to symmetric matrices, and by virtue of these relations they satisfy
variants of the results above [38]. For example, from Section 2.6 we know that
any flow matrix of a reversible Markov is symmetric. This fact allows us to
establish the following analogue of Theorem 4.2.1:

######  Theorem 4.2.4.

Let $\mathcal{X}$ be a Markov chain with transition matrix $\bm{P}$. Then
$\mathcal{X}$ is reversible if and only if there exists a stationary
distribution $\bm{\pi}>0$, such that:

$\langle\bm{x},\bm{P}\bm{x}^{\prime}\rangle_{\bm{\Pi}}=\langle\bm{P}\bm{x},\bm{x}^{\prime}\rangle_{\bm{\Pi}}\quad\forall\bm{x},\bm{x}^{\prime}\in\mathbb{R}^{n}$
(100)

where

$\langle\bm{a},\bm{b}\rangle_{\bm{\Pi}}:=\bm{a}^{T}\bm{\Pi}\bm{b}=\sum_{i}\pi_{i}a_{i}b_{i}$
(101)

defines an inner product normalized by the stationary probabilities $\pi_{i}$
(proof: see Appendix A).

Furthermore, Theorem 4.1.3 tells us that there exist certain row scalings
which transform the transition matrix $\bm{P}$ of a reversible Markov chain
into symmetric matrices. In fact, this is not the only scaling operation that
transforms $\bm{P}$ into a matrix of this type. The next result shows that
such a matrix is also formed when we scale both the rows and columns of
$\bm{P}$ as follows:

######  Theorem 4.2.5.

Let $\mathcal{X}$ be a Markov chain with transition matrix $\bm{P}$. Then
$\mathcal{X}$ is reversible if and only if for any stationary distribution
$\bm{\pi}>0$:

$\bm{K}:=\bm{\Pi}^{\frac{1}{2}}\bm{P\Pi}^{-\frac{1}{2}}$ (102)

is a symmetric matrix. Furthermore, regardless of which stationary
distribution is used, the matrix $\bm{K}$ is unique (proof: see Appendix A).

The first thing to note about Theorem 4.2.5 is that the output of the scaling
operation is somewhat different to that in Theorem 4.1.3, since in the former
case there is only a single symmetric matrix, whereas in the latter there are
an infinite number. Additionally, Equation 102 implies that $\bm{P}$ and
$\bm{K}$ are similar matrices (Section 2.3). Since similar matrices have the
same eigenvalues and related sets of eigenvectors, we can use this to
establish the following generalizations of Theorem 4.2.2 and 4.2.3:

######  Theorem 4.2.6.

Let $\mathcal{X}$ be a reversible Markov chain with transition matrix
$\bm{P}$. Then $\mathcal{X}$ is reversible if and only if it is diagonalizable
with real eigenvalues, and there exists a basis of right eigenvectors that are
orthogonal w.r.t. $\langle\cdot,\cdot\rangle_{\bm{\Pi}}$ and a corresponding
dual basis of left eigenvectors that are orthogonal w.r.t.
$\langle\cdot,\cdot\rangle_{\bm{\Pi}^{-1}}$, where $\bm{\pi}>0$ is a
stationary distribution of the chain (proof: see Appendix A).

######  Proposition 4.2.7.