4 Markov Chains and Networks

Markov chains evolving on finite sets are a foundational class of stochastic processes. These processes have been employed in quantitative economics to study stochastic systems ranging from labor income to harvest outputs, firm productivity, stock prices, unemployment dynamics, policy regimes, interest rates, and social mobility. Fortunately, we are now well placed to study Markov chains, since such chains are most naturally viewed as a special kind of weighted digraph. Moreover, graph-theoretic properties such as connectedness and periodicity are key determinants of their dynamics. In this chapter we investigate these ideas.

4.1Markov Chains as Digraphs¶

We begin with fundamental definitions and then investigate dynamics.

4.1.1Markov Models¶

A finite Markov model is a weighted directed graph $\mM = (S, E, p)$, where $S$ is the (finite) set of vertices, $E$ is the set of edges and $p$ is the weight function, with the additional restriction that

Figure 1.15 presented an example of such a digraph.

The set of vertices $S$ of a finite Markov model $\mM = (S, E, p)$ is also called the state space of the model, and vertices are called states. The two standard interpretations are

These two perspectives are related in ways that we explore below.

4.1.1.1Transition Matrices¶

If $\mM$ is a finite Markov model, then the restriction (4.1) is equivalent to the statement that the adjacency matrix associated with $\mM$ is stochastic (see Section 1.3.1.3 for the definition). Identifying $S = \{\text{poor}, \text{middle}, \text{rich}\}$ with $\{1, 2, 3\}$, the adjacency matrix for this weighted digraph is

Since $P_a \geq 0$ and rows sum to unity, $P_a$ is stochastic as required. In the context of finite Markov models, the adjacency matrix of $\mM$ is also called the transition matrix.

Regarding notation, when $S$ has typical elements $x, y$, it turns out to be convenient to write elements of the transition matrix $P$ as $P(x, y)$ rather than $P_{ij}$ or similar. We can think of $P$ as extending the weight function $p$ from $E$ to the set of all $(x,y)$ pairs in $S \times S$, assigning zero whenever $(x,y) \notin E$. As such, for every possible choice of $(x,y)$, the value $P(x,y)$ represents the probability of transitioning from $x$ to $y$ in one step.

The requirement that $P$ is stochastic can now be written as $P \geq 0$ and

The restriction in (4.3) just says that the state space is “complete:” after arriving at $x \in S$, the state must now move to some $y \in S$.

Using notation from Section 1.3.1, to say that $P$ is stochastic is the same as requiring that each row of $P$ is in $\dD(S)$.

The transition matrix for the Markov model in Example 4.1.1 is

Note the large values on the principal diagonal of $P_Q$. These indicate strong persistence: the state stays constant from period to period with high probability.

Quah (1993) estimated $P_Q$ by maximum likelihood, pooling transitions over the years 1960–1984. (In this case maximum likelihood estimation amounts to recording the relative frequency of transitions between states.) Figure 4.2 shows how the numbers change if we repeat the exercise using World Bank GDP data from 1985–2019. The numbers are quite stable relative to the earlier estimate. Below we will examine how long run predictions are affected.

As another example, Benhabib et al. (2019) estimate the following transition matrix for intergenerational social mobility:

Here the states are percentiles of the wealth distribution. In particular, with the states represented by $1, 2, \ldots, 8$, the corresponding percentiles are

0–20%, 20–40%, 40–60%, 60–80%, 80–90%, 90–95%, 95–99%, 99–100%

Transition probabilities are estimated from US 2007–2009 Survey of Consumer Finances data. Relative to the highly persistent matrix $P_Q$, less weight on the principle diagonal suggests more mixing—the influence of initial conditions is relatively short-lived.

Additional insight about the dynamics can be obtained from a contour plot of the matrix $P_B$, as in Figure 4.3. Here $P_B$ is plotted as a heat map after rotating it 90 degrees anticlockwise. The rotation is so that the dynamics are comparable to the 45 degree diagrams often used to understand discrete time dynamic systems. A vertical line from state $x$ corresponds to the next period conditional distribution $P(x, \cdot)$.

In this case, we see that, for example, lower states are quite persistent, whereas households in the highest state tend to fall back towards the middle.

4.1.1.2Markov Chains¶

Consider a finite Markov model $\mM$ with state space $S$ and transition matrix $P$. As before, $P(x, y)$ indicates the probability of transitioning from $x$ to $y$ in one step. Another way to say this is that, when in state $x$, we update to a new state by choosing it from $S$ via the distribution $P(x, \cdot)$. The resulting stochastic process is called a Markov chain.

We can state this more formally as follows. Let $(X_t)_{t \in \ZZ_+}$ be a sequence of random variables taking values in $S$. We say that $(X_t)$ is a Markov chain on $S$ if there exists a stochastic matrix $P$ on $S$ such that

To simplify terminology, we also call $(X_t)$ $P$-Markov when it satisfies (4.7) . We call either $X_0$ or its distribution $\psi_0$ the initial condition of $(X_t)$ depending on context.

The definition of a Markov chain says two things:

One way to think about Markov chains is algorithmically: Let $P$ be a stochastic matrix and let $\psi_0$ be an element of $\dD(S)$. Now generate $(X_t)$ via Algorithm 3. The resulting sequence is $P$-Markov with initial condition $\psi_0$.

4.1.1.3Simulation¶

For both simulation and theory, it is useful to be able to translate Algorithm 3 into a stochastic difference equation governing the evolution of $(X_t)_{t \geq 0}$. We now outline the procedure, which uses inverse transform sampling (see Section 1.3.1.2). For simplicity, we assume that $S = \natset{n}$, with typical elements $i,j$. The basic idea is to apply the inverse transform method to each row of $P$ and then sample by drawing a uniform random variable at each update.

To this end, we set

where, for each $i, j \in S$, the value $q(i, j)$ is defined recursively by

Let $U(0, 1)$ represent the uniform distribution on $(0, 1)$ and take

If $X_0$ is an independently drawn random variable with distribution $\psi_0$ on $S$, then $(X_t)$ is $P$-Markov on $S$ with initial condition $\psi_0$, as Exercise 4.1.2 asks you to show.

Each subfigure in Figure 4.4 shows realizations of two Markov chains, both generated using the stochastic difference equation (4.8). The sequences are generated each with its own independent sequence of draws $(U_t)$. The underlying transition matrices are $P_B$ from (4.5) in the top panel and $P_Q$ from (4.4) in the bottom panel. In both panels, one chain starts from the lowest state and the other from the highest. Notice that time series generated by $P_B$ mix faster than those generated by $P_Q$: the difference in initial states is not a strong predictor of outcomes after an initial “burn in” period. We discuss mixing and its connection to stability below.

4.1.1.4Higher Order Transition Matrices¶

Given a finite Markov model $\mM$ with state space $S$ and transition matrix $P$, define $(P^k)_{k \in \NN}$ by $P^{k+1} = P P^k$ for all $k$, with the understanding that $P^0 = I =$ the identity matrix. In other words, for each $k$, the matrix $P^k$ is the $k$-th power of $P$. If we spell out the matrix product $P^{k+1} = P P^k$ element-by-element, we get

In this context, $P^k$ is called the $k$-step transition matrix corresponding to $P$. The $k$-step transition matrix has the following interpretation: If $(X_t)$ is $P$-Markov, then, for any $t, k \in \NN$ and $x, y \in S$,

In other words, $P^k$ provides the $k$-step transition probabilities for the $P$-Markov chain $(X_t)$, as suggested by its name.

This claim can be verified by induction. Fix $t \in \NN$ and $x, y \in S$. The claim is true by definition when $k=1$. Suppose the claim is also true at $k$ and now consider the case $k+1$. By the law of total probability, we have

The induction hypothesis allows us to use (4.10), so the last equation becomes

This completes our proof by induction.

A useful identity for the higher order Markov matrices is

which holds for any $j, k$ in $\NN$. This is called the Chapman–Kolmogorov equation. Note that

• (4.9) is a special case of (4.11) and

• (4.11) is a special case of (1.27), written with different notation.

To provide probabilistic intuition for the validity of the Chapman–Kolmogorov equation, let $X_0 = x$ and let $y \in S$ be given. Using the law of total probability again, we have

By Markov property (4.7), the future and past are independent given the present, so

As a result of this fact and (4.10), the equation before this one can be rewritten as (4.11).

4.1.2Distribution Dynamics¶

Let $\mM$ be a finite Markov model with state space $S$ and transition matrix $P$. Let $(X_t)$ be $P$-Markov and, for each $t \geq 0$, let $\psi_t \in \dD(S)$ be defined by

The vector $\psi_t$ is called the marginal distribution of $X_t$. While $(X_t)$ is random, the sequence $(\psi_t)$ is deterministic. In this section we investigate its dynamics.

4.1.2.1Updating Marginal Distributions¶

The key idea for this section is that there is a simple link between successive marginal distributions: by the law of total probability, we have

which can be rewritten as

This fundamental expression tells how to update marginal distributions given the transition matrix $P$.

When each $\psi_t$ is interpreted as a row vector, we can write (4.12) as

(Henceforth, in expressions involving matrix algebra, distributions are row vectors unless otherwise stated). Some authors refer to (4.13) as the forward equation associated with $P$, while $\psi \mapsto \psi P$ is called the forward operator, by analogy with the Kolmogorov forward equation from continuous time.

Think of (4.13) as a difference equation in distribution space. Iterating backwards,

Given any $\psi_0 \in \dD(S)$ and $t \in \NN$, we have

4.1.2.2Trajectories in the Long Run¶

One of the main sub-fields of Markov chain analysis is asymptotics of distribution sequences. This topic turns out to be important for network theory as well. In Section 4.2.2 we will investigate asymptotics in depth. In this section we build some intuition via simulations.

Figure 4.6 shows the trajectory $(\psi P_a^t)$ when $S = \{1, 2, 3\}$, $\psi = (0, 0, 1)$, and $P_a$ is the transition matrix displayed in (4.2). The blue triangle is the unit simplex in $\RR^3_+$, consisting of all row vectors $\psi \in \RR^3$ such that $\psi \geq 0$ and $\psi \1 = 1$. The unit simplex can be identified with $\dD(S)$ when $S = \{1, 2, 3\}$. Red dots in the figure are distributions in the sequence $(\psi P_a^t)$ for $t=0, \ldots, 20$. Figure 4.7 shows distribution dynamics for $P_a$ that start from initial condition $\psi = (0, 1/2, 1/2)$.

It seems that both of the sequences are converging. This turns out to be the case—the black dot in the figures is the limit of both sequences and, moreover, this point is a stationary distribution for $P_a$, as defined in Section 1.3.1.3. In fact we can—and will—also show that no other stationary distribution exists, and that $\psi P_a^t$ converges to the stationary distribution regardless of the choice of $\psi \in \dD(S)$. This is due to certain properties of $P_a$, related to connectivity and aperiodicity.

Figure 4.8 provides another view of a distribution sequence, this time generated from the matrix $P_B$ in (4.5). The initial condition $\psi_0$ was uniform. Each distribution shown was calculated as $\psi P_Q^t$ for different values of $t$. The distribution across wealth classes converges rapidly to what appears to be a long run limit. Below we confirm that this is so, and that the limit is independent of the initial condition. The rapid rate of convergence is due to the high level of mixing in the transition dynamics.

4.1.3Stationarity¶

In this section we examine stationary distributions and their properties. As we will see, stationary distributions can be regarded as steady states for the evolution of the sequence of marginal distributions. (Later, when we study ergodicity, stationary distributions will acquire another important interpretation.)

4.1.3.1Stationary Distributions¶

Recall from Section 1.3.1.3 that if $P$ is a stochastic matrix and $\psi \in \RR^n_+$ is a row vector such that $\psi \1 = 1$ and $\psi P = \psi$, then $\psi$ is called stationary for $P$. So now let $\mM$ be a finite Markov model with state space $S$ and transition matrix $P$. Translating to the notation of Markov chains, a distribution $\psi^* \in \dD(S)$ is stationary for $\mM$ if

We also write this expression as $\psi^* = \psi^* P$ and understand $\psi^*$ as a fixed point of the map $\psi \mapsto \psi P$ that updates distributions (cf., Equation (4.13)).

If $X_t \eqdist \psi^*$, then, for any $j \in \NN$, the fixed point property implies that $X_{t+j} \eqdist \psi^* P^j = \psi^*$. Hence

In Figure 4.6–Figure 4.7 all trajectories converge towards the stationary distribution. Not all stationary distributions have this “attractor” property, and in general there can be many stationary distributions. The next example illustrates.

4.1.3.2Existence and Uniqueness¶

From the Perron–Frobenius Theorem we easily obtain the following fundamental result.

The basic idea behind the uniqueness part of Theorem 4.1.1 is as follows: Suppose to the contrary that $\mM$ is strongly connected and yet two distinct stationary distributions $\psi^*$ and $\psi^{**}$ exist in $\pP(S)$. Since a $P$-Markov chain started at $\psi^*$ always has marginal distribution $\psi^*$ and likewise for $\psi^{**}$, different initial conditions lead to different long run outcomes. This contradicts strong connectedness in the following way: strong connectedness implies that both chains traverse the whole state space. Moreover, being Markov chains, they forget the past once they arrive at any state, so the starting draws should eventually be irrelevant.

(Actually, the story in the last paragraph is incomplete. Initial conditions can determine long run outcomes under strong connectedness in one sense: a “periodic” Markov model can traverse the whole space but only at specific times that depend on the starting location. If we rule out such periodicity, we get results that are even stronger than Theorem 4.1.1. This topic is treated in Section 4.2.2.)

4.1.3.3Brouwer’s Theorem¶

Another way to prove the existence claim in Theorem 4.1.1 is via the famous fixed point theorem of L. E. J. Brouwer (1881–1966).

The proof of Theorem 4.1.2 in one dimension is not difficult, while the proof in higher dimensions is challenging. See, for example, Aliprantis & Border (1999).

One advantage of Brouwer’s fixed point theorem is that its conditions are quite weak. One disadvantage is that it provides only existence, without uniqueness or stability. Figure 6.4 provides an example of how multiple fixed points can coexist under the conditions of the theorem.^[2]

4.1.3.4Computation¶

Let’s consider how to compute stationary distributions. While $\psi^* P = \psi^*$ is a finite set of linear equations that we might hope to solve directly for $\psi^*$, there are problems with this idea. For example, $\psi^* = 0$ is a solution that fails to lie in $\dD(S)$.

To restrict the solution to $\dD(S)$ we proceed as follows: Suppose $|S|=n$ and note that row vector $\psi \in \dD(S)$ is stationary if and only if $\psi(I - P) = 0$, where $I$ is the $n \times n$ identity matrix. Let $\1_n$ be the $1 \times n$ row vector $(1,\ldots,1)$. Let $\1_{n \times n}$ be the $n \times n$ matrix of ones.

Solving the linear system (4.15) produces a stationary distribution in any setting where the stationary distribution is unique. When this is not the case, problems can arise.

There are also graph-theoretic algorithms for computing all of the stationary distributions of an arbitrary stochastic matrix. (The Python and Julia libraries QuantEcon.py and QuantEcon.jl have efficient implementations of this type.)

4.2Asymptotics¶

In this section we turn to long run properties of Markov chains, including ergodicity. With these ideas in hand, we will then investigate the evolution of information over social networks.

4.2.1Ergodicity¶

Let’s begin with the fascinating and important topic of ergodicity. The simplest way to understand ergodicity is as an extension of the law of large numbers from IID sequences to more general settings, where the IID property holds only in a limiting sense.

4.2.1.1Harmonic Functions¶

Let $\mM$ be a finite Markov model with state space $S$ and transition matrix $P$. Fix $h \in \RR^S$ and let

If $h$ is understood as a column vector in $\RR^{|S|}$, then $Ph(x)$ is just element $x$ of the vector $Ph$. The map $h \mapsto Ph$ is sometimes called the “conditional expectation operator,” since, given that $P(x, y) = \PP\{X_{t+1}=y \given X_t = x\}$, we have

A function $h \in \RR^S$ is called $P$-harmonic if $P h = h$ pointwise on $S$. Thus, $P$-harmonic functions are fixed points of the conditional expectation operator $h \mapsto Ph$.

If $h$ is $P$-harmonic and $(X_t)$ is $P$-Markov, then

(A stochastic process with this property—i.e., that the current value is the best predictor of next period’s value—is called a martingale. Martingales are one of the foundational concepts in probability, statistics and finance.)

4.2.1.2Definition and Implications¶

Let $\mM$ be a finite Markov model with state space $S$ and transition matrix $P$. We know that every constant function in $\RR^S$ is $P$-harmonic. We call $\mM$ ergodic if the only $P$-harmonic functions in $\RR^S$ are the constant functions.

The examples discussed above suggest that, for a finite Markov model $\mM$, ergodicity depends on the connectivity properties of the digraph. The next result confirms this.

The implication in Proposition 4.2.1 is one way, as the next exercise asks you to confirm.

4.2.1.3Implications of Ergodicity¶

One of the most important results in probability theory is the law of large numbers (LLN). In the finite state setting, the classical version of this theorem states that

when $(X_t)_{t \geq 0}$ is an IID sequence of random variables with common distribution $\phi \in \dD(S)$ and $h$ is an arbitrary element of $\RR^S$.

This version of the LLN is classical in the sense that the IID assumption is imposed. It turns out that the IID assumption can be weakened to allow for a degree of dependence between observations, which leads us to ask whether or not the LLN holds for Markov chains as well.

The answer to this question is yes, provided that dependence between observations dies out fast enough. One candidate for this condition is ergodicity. In fact, it turns out that ergodicity is the exact necessary and sufficient condition required to extend the law of large numbers to Markov chains. The next theorem gives details.

The proof of Theorem 4.2.2 is given in Chapter 17 of Meyn & Tweedie (2009). We skip the proof but provide intuition through the following examples.

4.2.1.4Reinterpreting the Stationary Distribution¶

Ergodicity has many useful implications. One is a new interpretation for the stationary distribution. To illustrate this, let $\mM$ be an ergodic Markov model with state space $S$ and transition matrix $P$. Let $(X_t)$ be a $P$-chain and let

The value $\hat \psi_k (y)$ measures the fraction of time that the $P$-chain spends in state $y$ over the time interval $1, \ldots, k$. Under ergodicity, for fixed $y \in S$, we can use (4.18) with $h(x) = \1\{ x = y \}$ to obtain

Turning (4.19) around, we see that

Figure 4.10 illustrates this idea for a simulated Markov chain $(X_t)$ generated from the matrix $P_B$ introduced in (4.5). The figure compares $\hat \psi_k$ and $\psi^*$ for different values of $k$. As $k \to \infty$, the convergence claimed in (4.19) occurs.

Of course, we must remember that (4.20) is only valid under ergodicity. For example, if $P = I$, the identity, then every distribution is stationary, every $P$-Markov chain is constant, and (4.20) does not hold.

Notice that, in view of Theorem 4.2.2, the convergence in (4.18) occurs for any initial condition. This gives us, under ergodicity, a way of computing the stationary distribution via simulation (and (4.19)). While this method is slower than algebraic techniques (see, e.g., Section 4.1.3.4) for small problems, it can be the only feasible option when $|S|$ is large.

4.2.2Aperiodicity and Stability¶

In Section 4.2.1 we discussed sample path properties of Markov chains, finding that strong connectivity is sufficient for stability of time series averages. Next we turn to marginal distributions of the chain and their long run properties, which we examined informally in Section 4.1.2.2. We will see that, to guarantee convergence of these sequences, we also need a condition that governs periodicity.

4.2.2.1Convergence of Marginals¶

Let $\mM$ be a finite Markov model with state space $S$ and transition matrix $P$. We call $\mM$ globally stable if there is only one stationary distribution $\psi^*$ in $\dD(S)$ and, moreover,

In other words, marginal distributions of every $P$-Markov chain converge to the unique stationary distribution of the model.

There is a useful connection between global stability and absorbing sets. Intuitively, if $\mM$ is globally stable and has an absorbing set $A$ that can be reached from any $x \in S$, then any Markov chain generated by these dynamics will eventually arrive in $A$ and never leave. Hence the stationary distribution must put all of its mass on $A$. The next exercise asks you to confirm this.

4.2.2.2A Key Theorem¶

From Theorem 4.1.1 we saw that strong connectedness is sufficient for uniqueness of the stationary distribution. One might hope that strong connectedness is enough for global stability too, but this is not true. To see why, suppose for example that $S = \{0,1\}$ and $E = \{(0, 1), (1, 0)\}$. The transition matrix is

While this model is strongly connected, global stability fails. Indeed, if $(X_t)$ is $P_d$-Markov and starts at $0$, then $(X_t)$ will visit state 1 on odd dates and state 0 on even dates. That is, $P^t_d \, \delta_0 = \delta_{t \text{ mod } 2}$. This sequence does not converge.

The issue with $P_d$ is that, even though the chain traverses the whole state space, the distribution of $X_t$ will affect that of $X_{t+j}$ for all $j$ due to periodicity. This causes stability to fail. If, however, we rule out periodicity, then we have enough for stability to hold. This line of reasoning leads to the following famous theorem.

The aperiodicity condition in Theorem 4.2.3 is, in general, not stringent. On the other hand, the strong connectedness requirement is arguably quite strict. Weaker conditions for global stability are available, as we shall see in Section 4.2.3.

4.2.2.3Rates of Convergence: Spectral Gap¶

While global stability is a very useful property, the implications are qualitative rather than quantitative. In practice, we usually want to know something about the rate of convergence. There are several ways of looking at this. We cover the two most common in this section and the next.

As a first step, fixing a Markov model $\mM$ with state space $S$ and transition matrix $P$, we use (1.5) to write $P^t$ as

where each $\lambda_i$ is an eigenvalue of $P$ and $e_i$ and $\epsilon_i$ are the right and left eigenvectors corresponding to $\lambda_i$. We have also ordered the eigenvalues from smallest to largest, and used the Perron–Frobenius Theorem to infer that $\lambda_n = r(P) = 1$, as well as the arguments in the proof of Theorem 4.2.3 that showed $e_n = \1$ and $\epsilon_n^\top = \psi^*$.

Premultiplying $P^t$ by arbitrary $\psi \in \dD(S)$ and rearranging now gives

Recall that eigenvalues are ordered from smallest to largest and. Moreover, by the Perron–Frobenius Theorem, $\lambda_i < 1$ for all $i < n$ when $P$ is primitive (i.e., $\mM$ is strongly connected and aperiodic). Hence, after taking the Euclidean norm deviation, we obtain

Thus, the rate of convergence is governed by the modulus of the second largest eigenvalue.

The difference between the largest and second largest eigenvalue of a nonnegative matrix is often called the spectral gap. For this reason, we can also say that, for primitive stochastic matrices, the rate of convergence is determined by the (nonzero) spectral gap.

4.2.3The Markov–Dobrushin Coefficient¶

The rate of convergence of $\psi P^t$ to $\psi^*$ given in Section 4.2.2.3 restricts the Euclidean distance between these vectors as a function of $t$. There are, however, other metrics we could use in studying rates of convergence, and sometimes these other metrics give more convenient results. In fact, as we show in this section, a good choice of metric leads us to a more general stability result than the (better known) aperiodicity-based result in Section 4.2.2.

4.2.3.1An Alternative Metric¶

For the purposes of this section, For $\phi, \psi \in \dD(S)$, we set

which is just the $\ell_1$ deviation between $\phi$ and $\psi$ (see Section 2.3.1.1).

Property (ii) is called the nonexpansiveness property of stochastic matrices under the $\ell_1$ deviation. As we will see, we can tighten this bound when $P$ satisfies certain properties.

As a first step we note that, for the $\ell_1$ deviation, given any stochastic matrix $P$, we have

where

Here $a \wedge b := \min\{a, b\}$ when $a, b \in \RR$. We call $\alpha(P)$ the Markov–Dobrushin coefficient of $P$, although other names are also used in the literature. A proof of the bound in (4.27) can be found in Stachurski (2022) or Seneta (2006).^[3]

How should the Markov–Dobrushin coefficient be understood? The coefficient is large when the rows of $P$ are relatively similar. For example, if rows $P(x, \cdot)$ and $P(x', \cdot)$ are identical, the $\sum_{y \in S} [P(x,y) \wedge P(x', y)] = 1$. Similarity of rows is related to stability. The next exercise helps to illustrate.

Since powers of stochastic matrices are again stochastic, and since (4.27) is valid for any stochastic matrix, the bound in (4.29) can be generalized by replacing $P$ with $P^k$ for any given $k \in \NN$, which gives (with $t$ replaced by $\tau$)

Now observe that, for any $t \in \NN$, we can write $t = \tau k + j$, where $\tau \in \ZZ_+$ and $j \in \{0, \ldots, k-1\}$. Fixing $t$ and choosing $j$ to make this equality hold, we get

where the second inequality is due to the nonexpansive property of stochastic matrices (Exercise 4.2.4). Since $\tau$ is an integer satisfying $\tau = \lfloor t/k \rfloor$, where $\lfloor \cdot \rfloor$ is the floor function, we can now state the following.

To see why the global stability implication stated in Theorem 4.2.4 holds, suppose there exists a $k \in \NN$ such that $\alpha(P^k)>0$. Now substitute arbitrary $\psi \in \dD(S)$ and any stationary distribution $\psi^*$ for $P$ into (4.30) to obtain

for all $t \in \NN$, where the second bound is due to Exercise 4.2.4.

One of the major advantages of Theorem 4.2.4 is that strong connectivity of $\mM$ is not required. In the next section we will see an example of a finite Markov model $\mM$ where (i) strong connectivity fails but (ii) the conditions of Theorem 4.2.4 are satisfied.^[4]

4.2.3.2Sufficient Conditions¶

While the Markov–Dobrushin coefficient $\alpha(P^k)$ can be calculated for any given $k$ on a computer by stepping through all pairs of rows in $P^k$, this calculation is computationally intensive when $S$ is large. When applicable, the following lemma simplifies the problem by providing a sufficient condition for $\alpha(P^k) > 0$.

4.2.3.3Application: PageRank¶

In Section 1.4.3 we discussed centrality measures for networks. Centrality measures provide a ranking of vertices in the network according to their “centrality” or “importance.” One of the most important applications of ranking of vertices in a network is ranking the importance of web pages on the internet. Historically, the most prominent example of a ranking mechanism for the internet is PageRank, which transformed Google from a minor start up to a technology behemoth. In this section we provide a simple introduction to the original form of PageRank and connect it to previously discussed measures of centrality.

Consider a finite collection of web pages $W$ and let $L$ be the hyperlinks between them. We understand $(W, L)$ as a digraph $\gG$, where $W$ is the vertices and $L$ is the edges. Let $A$ be the associated adjacency matrix, so that $A(u, v) = 1$ if there is a link from $u$ to $v$ and zero otherwise. We set $n = |W|$, so that $A$ is $n \times n$.

To start our analysis, we consider the case where $\gG$ is strongly connected, such as the small network in Figure 4.12. Furthermore, we introduce a second matrix $P$ in which each row of $A$ has been normalized so that it sums to one. For the network in Figure 4.12, this means that

Now consider an internet surfer who, once per minute, randomly clicks on one of the $k$ outgoing links on a page, each link selected with uniform probability $1/k$. The idea of PageRank is to assign to each page $u \in W$ a value $g(u)$ equal to the fraction of time that this surfer spends on page $u$ over the long run. Intuitively, a high value for $g(u)$ indicates a heavily visited and hence important site.

The vector $g$ is easy to compute, given our knowledge of Markov chains. Let $\mM$ be the finite Markov model associated with the random surfer, with state space $W$ and adjacency matrix given by $P$. Since $\mM$ is strongly connected, the ergodicity theorem tells us that $P$ has a unique stationary distribution $\psi^*$, and that the fraction of time the surfer spends at page $u$ is equal to the probability assigned to $u$ under the stationary distribution (see, in particular, (4.20)). Hence $g = \psi^*$.

As $g$ is stationary and $r(P)=1$, we can write $g = (1/r(P)) g P$. Taking transposes gives $g^\top = (1/r(P)) P^\top g^\top$. Comparing with (1.34), we see that, for this simple case, the PageRank vector $g$ is just the authority-based eigenvector centrality measure of $\mM$. Thus, PageRank gives high ranking to pages with many inbound links, attaching high value to inbound links from pages that are themselves highly ranked.

There are two problems with the preceding analysis. First, we assumed that the internet is strongly connected, which is clearly violated in practice (we need only one page with no outbound links). Second, internet users sometimes select pages without using hyperlinks, by manually entering the URL.

The PageRank solution to this problem is to replace $P$ with the so-called Google matrix

where $\1$ is the $n \times n$ matrix of ones. The value $\delta \in (0, 1)$ is called the damping factor.

The Markov dynamics embedded in the stochastic matrix $G$ can be understood as follows: The surfer begins by flipping a coin with heads probability $\delta$. (See Exercise 1.3.6 and its solution for the connection between convex combinations and coin flips.) If the coin is heads then the surfer randomly selects and follows one of the links on the current page. If not then the surfer randomly selects and moves to any page on the internet.

For given $\delta$, the PageRank vector for this setting is adjusted to be the stationary distribution of the Google matrix $G$.

As a result of Exercise 4.2.11, we can always interpret the stationary of $G$ as telling us the fraction of time that the surfer spends on each page in the long run.

4.2.4Information and Social Networks¶

In recent years, the way that opinions spread across social networks has become a major topic of concern in many countries around the globe. A well-known mathematical model of this phenomenon is De Groot learning, which was originally proposed in DeGroot (1974). This mechanism has linear properties that make it relatively easy to analyze (although large and complex underlying networks can cause significant challenges).

In De Groot learning, a group of agents, labeled from $1$ to $n$, is connected by a social or information network of some type. Connections are indicated by a trust matrix $T$, where, informally,

In other words, $T(i,j)$ is large if agent $i$ puts a large positive weight on the opinion of agent $j$. The matrix $T$ is assumed to be stochastic.

We can view the trust matrix as an adjacency matrix for a weighed digraph $\sS$ with vertex set $V := \natset{n}$ and edges

Figure 4.13 shows two social networks $\sS_a$ and $\sS_b$ with trust matrices given by

respectively. In network A, agent 1 places no trust in anyone’s opinion but his own. In network B, he places at least some trust in the opinion of agent 4. Below we show how these differences matter for the dynamics of beliefs.

4.2.4.1Learning¶

At time zero, all agents have an initial subjective belief concerning the validity of a given statement. Belief takes values in $[0, 1]$, with 1 indicating complete (subjective) certainty that the statement is true. Let $b_0(i)$ be the belief of agent $i$ at time zero.

An agent updates beliefs sequentially based on the beliefs of others, weighted by the amount of trust placed in their opinion. Specifically, agent $i$ updates her belief after one unit of time to $\sum_{j =1}^n T(i, j) b_0(j)$. More generally, at time $t+1$, beliefs update to

In matrix notation this is $b_{t+1} = T b_t$, where each $b_t$ is treated as a column vector.

(Notice that this update rule is similar but not identical to the marginal distribution updating rule for Markov chains (the forward equation) discussed. Here we are postmultiplying by a column vector rather than premultiplying be a row vector.)

4.2.4.2Consensus¶

A social network $\sS$ is said to lead to consensus if $|b_t(i) - b_t(j)| \to 0$ as $t \to \infty$ for all $i, j \in V$. Consensus implies that all agents eventually share the same belief. An important question is, what conditions on the network lead to a consensus outcome?

Proposition 4.2.6 can be applied to the two social networks $\sS_a$ and $\sS_b$ in Figure 4.13. For example, in network $\sS_a$, for every node $i$, there exists a walk of length 2 from $i$ to node $1$. Hence, by Lemma 4.2.5, we have $\alpha(T^2) > 0$. In network $\sS_b$ the same is true.

4.2.4.3Influence of Authorities¶

Now let’s consider what beliefs converge to when consensus emerges. In particular, we are interested in discovering whose opinions are most influential under De Groot learning, for a given trust matrix.

To answer the question, let $\sS$ be a given social network with trust matrix $T$. Suppose that $\alpha(T^k) > 0$ for some $k \in \NN$. By Theorem 4.2.4, the network $\sS$ is globally stable when viewed as a finite Markov model. Let $\psi^*$ be the unique stationary distribution, so that $\psi^* = \psi^* T$.

Applying (4.34) with $\phi = \delta_i$ and $\psi = \psi^*$ yields

where

We conclude that the belief of every agent converges geometrically to $b^*$, which is a weighted average of the initial beliefs of all agents. In particular, those agents with high weighting under the stationary distribution have a large influence on these equilibrium beliefs.

We can interpret this through notions of centrality. Since $r(T)=1$, we have $(\psi^*)^\top = (1/r(T)) T^\top (\psi^*)^\top$, so $\psi^*$ is the authority-based eigenvector centrality measure on $\sS$. Thus, the influence of each agent on long run beliefs is proportional to their authority-based eigenvector centrality. This makes sense because such agents are highly trusted by many agents who are themselves highly trusted.