随机算法 (Spring 2013)/Markov Chain and Random Walk

Markov Chain

A stochastic processes $\{X_t\mid t\in T\}$ is a collection of random variables. The index $t$ is often called time, as the process represents the value of a random variable changing over time. Let $\mathrm{\Omega }$ be the set of values assumed by the random variables $X_t$. We call each element of $\mathrm{\Omega }$ a state, as $X_t$ represents the state of the process at time $t$.

The model of stochastic processes can be very general. In this class, we only consider the stochastic processes with the following properties:

discrete time

The index set $T$ is countable. Specifically, we assume that $T=\{0,1,2,\dots \}$ and the process is $X_0,X_1,X_2,\dots$

discrete space

The state space $\mathrm{\Omega }$ is countable. We are especially interested in the case that $\mathrm{\Omega }$ is finite, in which case the process is called a finite process.

The next property is about the dependency structure among random variables. The simplest dependency structure for $X_0,X_1,\dots$ is no dependency at all, that is, independence. We consider the next simplest dependency structure called the Markov property.

Definition (the Markov property)

A process $X_0,X_1,\dots$ satisfies the Markov property if $Pr[X_{n+1}=x_{n+1}\mid X_0=x_0,X_1=x_1,\dots ,X_n=x_n]=Pr[X_{n+1}=x_{n+1}\mid X_n=x_n]$ for all $n$ and all $x_0,\dots ,x_{n+1}\in \mathrm{\Omega }$.

Informally, the Markov property means: "conditioning on the present, the future does not depend on the past." Hence, the Markov property is also called the memoryless property.

A stochastic process $X_0,X_1,\dots$ of discrete time and discrete space is a Markov chain if it has the Markov property.

Transition matrix

Let $P_{x,y}^{(t+1)}=Pr[X_{t+1}=y\mid X_t=x]$. For a Markov chain with a finite state space $\mathrm{\Omega }=[N]$. This gives us a transition matrix $P^{(t+1)}$ at time $t$. The transition matrix is an $N\times N$ matrix of nonnegative entries such that the sum over each row of $P^{(t)}$ is 1, since

$\begin{array}{r}\sum _y{P}_{x,y}^{(t+1)}=\sum _{y}Pr[X_{t+1}=y\mid X_t=x]=1\end{array}$.

In linear algebra, matrices of this type are called stochastic matrices.

Let ${\pi }^{(t)}$ be the distribution of the chain at time $t$, that is, $\begin{array}{r}{\pi }_x^{(t)}=Pr[X_t=x]\end{array}$. For a finite chain, ${\pi }^{(t)}$ is a vector of $N$ nonnegative entries such that $\begin{array}{r}\sum _x{\pi }_x^{(t)}=1\end{array}$. In linear algebra, vectors of this type are called stochastic vectors. Then, it holds that

$\begin{array}{r}{\pi }^{(t+1)}={\pi }^{(t)}{P}^{(t+1)}\end{array}$.

To see this, we apply the law of total probability,

$\begin{array}{rl}{\pi }_y^{(t+1)}& =Pr[X_{t+1}=y]\\ & =\sum _{x}Pr[X_{t+1}=y\mid X_t=x]Pr[X_t=x]\\ & =\sum _x{\pi }_x^{(t)}{P}_{x,y}^{(t+1)}\\ & =({\pi }^{(t)}{P}^{(t+1)}{)}_y.\end{array}$

Therefore, a finite Markov chain $X_0,X_1,\dots$ is specified by an initial distribution ${\pi }^{(0)}$ and a sequence of transition matrices $P^{(1)},P^{(2)},\dots$. And the transitions of chain can be described by a series of matrix products:

${\pi }^{(0)}\stackrel{P^{(1)}}{⟶}{\pi }^{(1)}\stackrel{P^{(2)}}{⟶}{\pi }^{(2)}\stackrel{P^{(3)}}{⟶}\cdots \cdots {\pi }^{(t)}\stackrel{P^{(t+1)}}{⟶}{\pi }^{(t+1)}\cdots$

A Markov chain is said to be homogenous if the transitions depend only on the current states but not on the time, that is

$P_{x,y}^{(t)}=P_{x,y}$ for all $t$.

The transitions of a homogenous Markov chain is given by a single matrix $P$. Suppose that ${\pi }^{(0)}$ is the initial distribution. At each time $t$,

$\begin{array}{r}{\pi }^{(t+1)}={\pi }^{(t)}P\end{array}$.

Expanding this recursion, we have

$\begin{array}{r}{\pi }^{(n)}={\pi }^{(0)}{P}^n\end{array}$.

From now on, we restrict ourselves to the homogenous Markov chains, and the term "Markov chain" means "homogenous Markov chian" unless stated otherwise.

Definition (finite Markov chain)

Let $P$ be an $N\times N$ stochastic matrix. A process $X_0,X_1,\dots$ with finite space $\mathrm{\Omega }=[N]$ is said to be a (homogenous) Markov chain with transition matrix $P$, if for all $n\ge 0,$ all $x,y\in [N]$ and all $x_0,\dots ,x_{n-1}\in [N]$ we have $\begin{array}{rl}Pr[X_{n+1}=y\mid X_0=x_0,\dots ,X_{n-1}=x_{n-1},X_n=x]& =Pr[X_{n+1}=y\mid X_n=x]\\ & =P_{x,y}.\end{array}$

To describe a Markov chain, we only need to specify:

• initial distribution ${\pi }^{(0)}$;
• transition matrix $P$.

Then the transitions can be simulated by matrix products:

${\pi }^{(0)}\stackrel{P}{⟶}{\pi }^{(1)}\stackrel{P}{⟶}{\pi }^{(2)}\stackrel{P}{⟶}\cdots \cdots {\pi }^{(t)}\stackrel{P}{⟶}{\pi }^{(t+1)}\stackrel{P}{⟶}\cdots$

The distribution of the chain at time $n$ can be computed by ${\pi }^{(n)}={\pi }^{(0)}{P}^n$.

Transition graph

Another way to picture a Markov chain is by its transition graph. A weighted directed graph $G(V,E,w)$ is said to be a transition graph of a finite Markov chain with transition matrix $P$ if:

• $V=\mathrm{\Omega }$, i.e. each node of the transition graph corresponds to a state of the Markov chain;
• for any $x,y\in V$, $(x,y)\in E$ if and only if $P_{x,y}>0$, and the weight $w(x,y)=P_{x,y}$.

A transition graph defines a natural random walk: at each time step, at the current node, the walk moves through an adjacent edge with the probability of the weight of the edge. It is easy to see that this is a well-defined random walk, since $\begin{array}{r}\sum _y{P}_{x,y}=1\end{array}$ for every $x$. Therefore, a Markov chain is equivalent to a random walk, so these two terms are often used interchangeably.

Stationary distributions

Suppose $\pi$ is a distribution over the state space $\mathrm{\Omega }$ such that, if the Markov chain starts with initial distribution ${\pi }^{(0)}=\pi$, then after a transition, the distribution of the chain is still ${\pi }^{(1)}=\pi$. Then the chain will stay in the distribution $\pi$ forever:

$\pi \stackrel{P}{⟶}\pi \stackrel{P}{⟶}\pi \stackrel{P}{⟶}\cdots \cdots$

Such $\pi$ is called a stationary distribution.

Definition (stationary distribution)

A stationary distribution of a finite Markov chain with transition matrix $P$ is a probability distribution $\pi$ such that $\begin{array}{r}\pi P=\pi \end{array}$.

Example

An $N\times N$ matrix is called double stochastic if every row sums to 1 and every column sums to 1. If the transition matrix $P$ of the chain is double stochastic, the uniform distribution ${\pi }_x=1/N$ for all $x$, is a stationary distribution. (Check by yourself.)

If the transition matrix $P$ is symmetric, the uniform distribution is a stationary distribution. This is because a symmetric stochastic matrix is double stochastic. (Check by yourself.)

Every finite Markov chain has a stationary distribution. This is a consequence of Perron's theorem in linear algebra.

For some Markov chains, no matter what the initial distribution is, after running the chain for a while, the distribution of the chain approaches the stationary distribution. For example, consider the transition matrix:

$P=\left[\begin{array}{ccc}0& 1& 0\\ \frac{1}{3}& 0& \frac{2}{3}\\ \frac{1}{3}& \frac{1}{3}& \frac{1}{3}\end{array}\right].$

Run the chain for a while, we have:

$P^5\approx \left[\begin{array}{ccc}0.2469& 0.4074& 0.3457\\ 0.2510& 0.3621& 0.3868\\ 0.2510& 0.3663& 0.3827\end{array}\right],P^{10}\approx \left[\begin{array}{ccc}0.2500& 0.3747& 0.3752\\ 0.2500& 0.3751& 0.3749\\ 0.2500& 0.3751& 0.3749\end{array}\right],P^{20}\approx \left[\begin{array}{ccc}0.2500& 0.3750& 0.3750\\ 0.2500& 0.3750& 0.3750\\ 0.2500& 0.3750& 0.3750\end{array}\right].$

Therefore, no matter what the initial distribution ${\pi }^{(0)}$ is, after 20 steps, ${\pi }^{(0)}{P}^{20}$ is very close to the distribution $(0.25,0.375,0.375)$, which is a stationary distribution for $P$. So the Markov chain converges to the same stationary distribution no matter what the initial distribution is.

However, this is not always true. For example, for the Markov chain with the following transition matrix:

$P=\left[\begin{array}{cccc}\frac{1}{2}& \frac{1}{2}& 0& 0\\ \frac{1}{3}& \frac{2}{3}& 0& 0\\ 0& 0& \frac{3}{4}& \frac{1}{4}\\ 0& 0& \frac{1}{4}& \frac{3}{4}\end{array}\right].$

And

$P^{20}\approx \left[\begin{array}{cccc}0.4& 0.6& 0& 0\\ 0.4& 0.6& 0& 0\\ 0& 0& 0.5& 0.5\\ 0& 0& 0.5& 0.5\end{array}\right].$

So the chain will converge, but not to the same stationary distribution. Depending on the initial distribution, the chain could converge to any distribution which is a linear combination of $(0.4,0.6,0,0)$ and $(0,0,0.5,0.5)$. We observe that this is because the original chain $P$ can be broken into two disjoint Markov chains, which have their own stationary distributions. We say that the chain is reducible.

Another example is as follows:

$P=\left[\begin{array}{cc}0& 1\\ 1& 0\end{array}\right].$

The chain oscillates between the two states. Then

$P^t=\left[\begin{array}{cc}0& 1\\ 1& 0\end{array}\right]$ for any odd $t$, and

$P^t=\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]$ for any even $t$.

So the chain does not converge. We say that the chain is periodic.

We will see that for finite Markov chains, being reducible and being periodic are the only two possible cases that a Markov chain does not converge to a unique stationary distribution.

Irreducibility and aperiodicity

Definition (irreducibility)

State $y$ is accessible from state $x$ if it is possible for the chain to visit state $y$ if the chain starts in state $x$, or, in other words, $\begin{array}{r}{P}^n(x,y)>0\end{array}$ for some integer $n\ge 0$. State $x$ communicates with state $y$ if $y$ is accessible from $x$ and $x$ is accessible from $y$. We say that the Markov chain is irreducible if all pairs of states communicate.

It is more clear to interprete these concepts in terms of transition graphs:

• $y$ is accessible from $x$ means that $y$ is connected from $x$ in the transition graph, i.e. there is a directed path from $x$ to $y$.
• $x$ communicates with $y$ means that $x$ and $y$ are strongly connected in the transition graph.
• A finite Markov chain is irreducible if and only if its transition graph is strongly connected.

It is easy to see that communicating is an equivalence relation. That is, it is reflexive, symmetric, and transitive. Thus, the communicating relation partition the state space into disjoint equivalence classes, called communicating classes. For a finite Markov chain, communicating classes correspond to the strongly connected components in the transition graph. It is possible for the chain to move from one communicating class to another, but in that case it is impossible to return to the original class.

Definition (aperiodicity)

The period of a state $x$ is the greatest common divisor (gcd) $\begin{array}{r}{d}_x=gcd\{n\mid (P^n{)}_{x,x}>0\}\end{array}$. A state is aperiodic if its period is 1. A Markov chain is aperiodic if all its states are aperiodic.

For example, suppose that the period of state $x$ is $d_x=3$. Then, starting from state $x$,

$x,◯,◯,◻,◯,◯,◻,◯,◯,◻,◯,◯,◻,\cdots \cdots$

only the squares are possible to be $x$.

In the transition graph of a finite Markov chain, $(P^n{)}_{x,x}>0$ is equivalent to that $x$ is on a cycle of length $n$. Period of a state $x$ is the greatest common devisor of the lengths of cycles passing $x$.

The next theorem shows that period is in fact a class property.

Theorem

If the states $x$ and $y$ communicate, then $d_x=d_y$.

Proof. For communicating $x$ and $j>x<$, there is a path $P_1$ from $x$ to $y$ of length $n_1$, and there is a path $P_2$ from $y$ to $x$ of length $n_2$. Then $P_1{P}_2$ gives a cycle starting at $x$ of length $n_1+n+2$, and for any cycle $C$ starting at $y$ of length $n$, $P_{1}C{P}_2$ gives a cycle starting at $x$ of length $n_1+n_2+n$. Since the period of $x$ is $d_x$, then both $(n_1+n_2)$ and $(n_1+n_2+n)$ are devisable by $d_x$. Subtracting the two, $n$ is devisable by $d_x$. Note that this holds for arbitrary cycle $C$ starting at $y$, then $d_x$ is the common divisor of all such $n$ that $P_{y,y}^n>0$. Since $d_y$ is defined to be the greatest common divisor of the same set of $n$, it holds that $d_y\ge d_x$. Interchanging the role of $x$ and $y$, we can show that $d_x\ge d_y$. Therefore $d_x=d_y$. $◻$

Due to the above theorem, an irreducible Markov chain is aperiodic if one of the states is aperiodic.

The Markov chain convergence theorem

Theorem (Markov chain convergence theorem)

Let $X_0,X_1,\dots ,$ be an irreducible aperiodic Markov chain with finite state space $\mathrm{\Omega }$, transition matrix $P$, and arbitrary initial distribution ${\pi }^{(0)}$. Then, there exists a stationary distribution $\pi$ such that $\pi P=\pi$, and $\underset{t\to \mathrm{\infty }}{lim}{\pi }^{(0)}{P}^t=\pi .$

The theorem says that if we run an irreducible aperiodic finite Markov chain for a sufficient long time $t$, then, regardless of what the initial distribution was, the distribution at time $t$ will be close to the stationary distribution $\pi$.

Three pieces of information are delivered by the theorem regarding the stationary distribution:

• Existence: there exists a stationary distribution.
• Uniqueness: the stationary distribution is unique.
• Convergence: starting from any initial distribution, the chain converges to the stationary distribution.

Neither irreducibility nor aperiodicity is necessary for the existence of a stationary distribution. In fact, any finite Markov chain has a stationary distribution. Irreducibility and aperiodicity guarantee the uniqueness and convergence behavior of the stationary distribution.

• For a reducible chain, there could be more than one stationary distributions. We have seen such examples. Note that there do exist reducible Markov chains with just one stationary distribution. For example, the chain

$P=\left[\begin{array}{cc}1/2& 1/2\\ 0& 1\end{array}\right]$

is reducible, but only has one stationary distribution $(0,1)$, because the transition graph is still weakly connected.

• For a periodic chain, the stationary probability ${\pi }_x$ of state $x$ is not the limiting probability of being in state $x$ but instead just the long-term frequency of visiting state $x$.

Coupling

The convergence theorem is proved by coupling, which is an important idea in probabilistic argument, and is a powerful tool for the analysis of Markov chains.

A Markov chain is a sequence of random variables

$\begin{array}{r}{X}_0,X_1,X_2\dots \end{array}$

where the distribution of $X_0$ is given by an initial distribution ${\pi }^{(0)}$; and for each $t=1,2,\dots$, assuming that $X_{t-1}=x$, the distribution of $X_t$ is given by the $x$th row of the transition matrix $P$, denoted as $P_x$.

So we can generate the chain by a sequence of uniform and independent random variables $U_0,U_1,\dots$ ranging over $[0,1]$. Initially

$X_0=y$ if $\sum _{z<y}{\pi }_z^{(0)}\le U_0<\sum _{z\le y}{\pi }_z^{(0)}$;

and for each $t=1,2,\dots$, assuming $X_{t-1}=x$,

$X_t=y$ if $\sum _{z<y}{P}_{x,z}\le U_0<\sum _{z\le y}P(x,z)$.

The Markov chain generated in this way is distributed exactly the same as having initial distribution ${\pi }^{(0)}$ and transition matrix $P$.

Let $X_0,X_1,\dots$ be a finite Markov chain with initial distribution ${\pi }^{(0)}$ and transition matrix $P$, and generated by the uniform and independent random variables $U_0,U_1,\dots$. Suppose that the Markov chain has a stationary distribution $\pi$, such that $\pi P=\pi$. We run another chain $X_0^{\prime },X_1^{\prime },\dots$ with the initial distribution $\pi$, transition matrix $P$, and independent random sources $U_0^{\prime },U_1^{\prime },\dots$. So we have two independent sequences:

$\begin{array}{r}{X}_0,X_1,X_2\dots \end{array}$ and $\begin{array}{r}{X}_0^{\prime },X_1^{\prime },X_2^{\prime }\dots \end{array}$.

We define another chain, which starts as $\begin{array}{r}{X}_0,X_1,X_2\dots \end{array}$ and for the first time that $X_n=X_n^{\prime }$, the chain switches to $X_n^{\prime },X_{n+1}^{\prime },X_{n+2},\dots$. The transitions are illustrated by the following figure.

$\begin{array}{cccccccc}{\pi }^{(0)}:& X_0& \to & X_1& \to & \cdots & \to & X_n\\ & \nparallel & & \nparallel & & \nparallel & & \parallel & \searrow \\ {\pi }^{}:& X_0^{\prime }& \to & X_1^{\prime }& \to & \cdots & \to & X_n^{\prime }& \to & X_{n+1}^{\prime }\to X_{n+2}^{\prime }\to \cdots \end{array}$

It is not hard to see that the distribution of the chain $\begin{array}{r}{X}_0,X_1,\dots ,X_n,X_{n+1}^{\prime },X_{n+2}^{\prime },\dots \end{array}$ is identically distributed as the original chain $\begin{array}{r}{X}_0,X_1,\dots \end{array}$, since we do nothing except switching the source of randomness from $U_0,U_1,\dots ,$ to the sequence $U_n^{\prime },U_{n+1}^{\prime },\dots$, which does not affect the distribution of the chain.

On the other hand, since the chain $\begin{array}{r}{X}_0^{\prime },X_1^{\prime },\dots \end{array}$ starts from a stationary distribution $\pi$, by the definition of stationary distribution, it will stay in that distribution forever. Thus, the distribution of every one of $\begin{array}{r}{X}_{n+1}^{\prime },X_{n+2}^{\prime },\dots \end{array}$ is $\pi$. Therefore, once $X_n=X_n^{\prime }$ for a finite $n$, the chain $\begin{array}{r}{X}_0,X_1,\dots \end{array}$ converges to the stationary distribution $\pi$.

Now we need to show that $X_n=X_n^{\prime }$ for some $n$ will eventually happen. To this end, let $M$ be the minimum integer such that $(P^M{)}_{x,y}>0$ for all $i,j\in \mathrm{\Omega }$, we have

$\begin{array}{rl}Pr[X_M=X_M^{\prime }]& \ge Pr(X_M=x\wedge X_M^{\prime }=x)\\ & =Pr[X_M=x]\cdot Pr[X_M^{\prime }=x]\\ & \ge c^2\end{array}$

where $c=min\{(P^M{)}_{x,y}\mid i,j\in \mathrm{\Omega }\}$ and hence it is a positive constant.

Similarly, we have

$\begin{array}{rl}Pr[X_{2M}\ne X_{2M}^{\prime }]& =Pr[X_M\ne X_M^{\prime }]\cdot Pr[X_{2M}\ne X_{2M}^{\prime }\mid X_M\ne X_M^{\prime }]\\ & \le (1-c^2{)}^2\end{array}$

Repeat the above argument, we have for every integer $\ell \ge 0$

$Pr[X_{\ell M}\ne X_{\ell M}^{\prime }]\le (1-c^2{)}^{\ell }$

This implies $Pr[X_n=X_n^{\prime }]\to 1$ as $n\to \mathrm{\infty }$.

Hitting time and the stationary distribution

We will see that the stationary distribution of a Markov chain is related to its hitting times. For a Markov chain starting from state $x$, let

$T_{x,y}=min\{n>0\mid X_n=y\}$,

which is the first time that a chain starting from state $x$ visits state $y$, with the convention that $T_{x,y}=\mathrm{\infty }$ if the chain never visit $y$. We define the hitting time

${\tau }_{x,y}=\mathbf{E}[T_{x,y}]$.

The special case ${\tau }_{x,x}$ gives the expected time a chain starting from state $x$ returns to state $x$.

Theorem

Any irreducible aperiodic Markov chain with finite state space $\mathrm{\Omega }$, and transition matrix $P$ has a stationary distribution $\pi$ such that ${\pi }_x=\underset{n\to \mathrm{\infty }}{lim}(P^n{)}_{y,x}=\frac{1}{{\tau }_{x,x}}$ for any $x\in \mathrm{\Omega }$.

Note that in the above theorem, the limit $\underset{n\to \mathrm{\infty }}{lim}(P^n{)}_{y,x}$ does not depend on the $y$, which means that $P^n$ in the limit has identical rows.

We will not prove the lemma, but only give an informal justification: the expected time between visits to state $x$ is ${\tau }_{x,x}$, and therefore state $x$ is visited $\frac{1}{{\tau }_{x,x}}$ of the time. Not that $\underset{n\to \mathrm{\infty }}{lim}(P^n{)}_{y,x}$ represents the probability a state chosen far in the future (at time $n\to \mathrm{\infty }$) is at state $x$ when the chain starts at state $y$, but if the future is far, who $y$ is does not really matter, and $\underset{n\to \mathrm{\infty }}{lim}(P^n{)}_{y,x}$ is the frequency that $x$ is visited, which is $\frac{1}{{\tau }_{x,x}}$.

PageRank

PageRank is the algorithm reportedly used by Google to assign a numerical rank to every web page. The rank of a page measures the "importance" of the page. A page has higher rank if it is pointed to by more high-rank pages. Low-rank pages have less influence on the rank of a page. If one page points to many others, it will have less influence on their ranking than if it just points to a few.

This intuitive idea can be formalized as follows. The world-wide-web is treated as a directed graph $G(V,E)$, with web pages as vertices and hyperlinks as directed edges. The rank of vertex $v$ is denoted $r(v)$, and is supposed to satisfy:

$r(v)=\sum _{u:(u,v)\in E}\frac{r(u)}{d_{+}(u)},(\ast )$

where $d_{+}(u)$ is the number of edges going out of $u$. Note that the sum is over edges going in to $v$.

This formula nicely models both the intuitions that a page gets higher rank if it is pointed by more high-rank pages, and that the influence of a page is penalized by the number of pages it points to. Let $P$ be a matrix with rows and columns corresponded to vertices, and $\mathrm{\forall }u,v\in V$,

$P(u,v)=\{\begin{array}{ll}\frac{1}{d_{+}(u)}& \text{if }(u,v)\in E,\\ 0& \text{otherwise}.\end{array}$

Then the formular $\begin{array}{r}(\ast )\end{array}$ can be expressed as

$\begin{array}{r}rP=r.\end{array}$

It is also easy to verify that $P$ is stochastic, that is, $\begin{array}{r}\sum _{v}P(u,v)=1\end{array}$ for all $u\in V$. Then the ranks of a pages is actually a stationary distribution of the Markov chain with transition matrix $P$. This is not entirely a coincidence. $P$ is the transition matrix for the random walk over the web pages, defined as that at each time, pick a uniform page pointed by the current page and walk to it. This can be imagined as a "tireless random surfer" who starts from an arbitrary page, randomly follows the hyperlinks, and given infinitely long time, will eventually approaches the stationary distribution. The importance of a web page is reflected by the frequency that the random surfer visits the page, which is the stationary probability.

We assume the world-wide-web is strongly connected, thus the Markov chain is irreducible. And given the huge number of webpages over the Internet, it is almost impossible that the lengths of all cycles have a common divisor greater than 1, thus the Markov chain is aperiodic. Therefore, the random surfer model indeed converges.

In practice, PageRank also consider a damping factor, since a typical surfer cannot browse the web forever. The damping factor effectively gives an upper bound on the number of hyperlinks the surfer would follow before he/she has a random start over.