Randomized Algorithms (Spring 2010)/Markov chains and random walks

Markov Chains

The Markov property and transition matrices

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

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 [math]\displaystyle{ T }[/math] is countable. Specifically, we assume the process is [math]\displaystyle{ X_0,X_1,X_2,\ldots }[/math]

discrete space

The state space [math]\displaystyle{ \mathcal{S} }[/math] is countable. We are especially interested in the case that [math]\displaystyle{ \mathcal{S} }[/math] 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 [math]\displaystyle{ X_0,X_1,\ldots }[/math] 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 [math]\displaystyle{ X_0,X_1,\ldots }[/math] satisfies the Markov property if [math]\displaystyle{ \Pr[X_{n+1}=x_{n+1}\mid X_{0}=x_{0}, X_{1}=x_{1},\ldots,X_{n}=x_{n}]=\Pr[X_{n+1}=x_{n+1}\mid X_{n}=x_{n}] }[/math] for all [math]\displaystyle{ n }[/math] and all [math]\displaystyle{ x_0,\ldots,x_{n+1}\in \mathcal{S} }[/math].

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 [math]\displaystyle{ X_0,X_1,\ldots }[/math] of discrete time and discrete space is a Markov chain if it has the Markov property.

Let [math]\displaystyle{ P^{(t)}_{i,j}=\Pr[X_{t+1}=j\mid X_t=i] }[/math]. For a Markov chain with a finite state space [math]\displaystyle{ \mathcal{S}=[N] }[/math]. This gives us a transition matrix [math]\displaystyle{ P^{(t)} }[/math] at time [math]\displaystyle{ t }[/math]. The transition matrix [math]\displaystyle{ P^{(t)} }[/math] is an [math]\displaystyle{ N\times N }[/math] matrix of nonnegative entries such that the sum over each row of [math]\displaystyle{ P^{(t)} }[/math] is 1, since

[math]\displaystyle{ \begin{align}\sum_{j}P^{(t)}_{i,j}=\sum_{j}\Pr[X_{t+1}=j\mid X_t=i]=1\end{align} }[/math].

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

Let [math]\displaystyle{ \pi_t }[/math] be the distribution of the chain at time [math]\displaystyle{ t }[/math], that is, [math]\displaystyle{ \begin{align}\pi_t(i)=\Pr[X_t=i]\end{align} }[/math]. [math]\displaystyle{ \pi_t }[/math] can be seen as a vector of [math]\displaystyle{ N }[/math] nonnegative entries such that [math]\displaystyle{ \begin{align}\sum_{i}\pi_t(i)=1\end{align} }[/math]. In linear algebra, vectors of this type are called stochastic vectors. Then, it holds that

[math]\displaystyle{ \begin{align}\pi_{t+1}=\pi_tP^{(t)}\end{align} }[/math].

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

[math]\displaystyle{ \begin{align} \pi_{t+1}(j) &= \Pr[X_{t+1}=j]\\ &= \sum_{i}\Pr[X_{t+1}=j\mid X_t=i]\Pr[X_t=i]\\ &=\sum_{i}\pi_t(i)P^{(t)}_{i,j}\\ &=(\pi_tP^{(t)})(j). \end{align} }[/math]

Therefore, a finite Markov chain [math]\displaystyle{ X_0,X_1,\ldots }[/math] is specified by an initial distribution [math]\displaystyle{ \pi_0 }[/math] and a sequence of transition matrices [math]\displaystyle{ P^{(0)},P^{(1)},\ldots }[/math].

[math]\displaystyle{ \pi_0\stackrel{P^{(0)}}{\longrightarrow}\pi_1\stackrel{P^{(1)}}{\longrightarrow}\pi_2\stackrel{P^{(2)}}{\longrightarrow}\cdots\cdots\pi_t\stackrel{P^{(t)}}{\longrightarrow}\pi_{t+1}\cdots }[/math]

A Markov chain is said to be homogenous if [math]\displaystyle{ P^{(n)}_{i,j}=P_{i,j} }[/math] for all [math]\displaystyle{ n\ge 0 }[/math], i.e. the transitions depend only on the current states but not on the time. In this class, we restrict ourselves to the homogenous Markov chains, and the term "Markov chain" means "homogenous Markov chian" unless stated otherwise.

Irreducibility and aperiodicity

Definition (irreducibility) State [math]\displaystyle{ j }[/math] is accessible from state [math]\displaystyle{ i }[/math] if it is possible for the chain to visit state [math]\displaystyle{ j }[/math] if the chain starts in state [math]\displaystyle{ i }[/math], or, in other words, [math]\displaystyle{ \begin{align}P^n(i,j)\gt 0\end{align} }[/math] for some integer [math]\displaystyle{ n\ge 0 }[/math]. State [math]\displaystyle{ i }[/math] communicates with state [math]\displaystyle{ j }[/math] if [math]\displaystyle{ j }[/math] is accessible from [math]\displaystyle{ i }[/math] and [math]\displaystyle{ i }[/math] is accessible from [math]\displaystyle{ j }[/math]. We say that the Markov chain is irreducible if all pairs of states communicate.

Definition (aperiodicity) The period of a state [math]\displaystyle{ i }[/math] is the greatest common divisor (gcd) [math]\displaystyle{ \begin{align}d_i=\gcd\{n\mid (P^n)_{i,i}\gt 0\}\end{align} }[/math]. A state is aperiodic if its period is 1. A Markov chain is aperiodic if all its states are aperiodic.

Stationary distributions

Definition (stationary distribution) A stationary distribution of a Markov chain is a probability distribution [math]\displaystyle{ \pi }[/math] such that [math]\displaystyle{ \begin{align}\pi P=\pi\end{align} }[/math].

Theorem (Basic limit theorem) Let [math]\displaystyle{ X_0,X_1,\ldots, }[/math] be an irreducible, aperiodic Markov chain having a stationary distribution [math]\displaystyle{ \pi }[/math]. Let [math]\displaystyle{ X_0 }[/math] have the distribution [math]\displaystyle{ \pi_0 }[/math], an arbitrary initial distribution. Then [math]\displaystyle{ \lim_{n\rightarrow\infty}\pi_n(i)=\pi(i) }[/math] for all states [math]\displaystyle{ i }[/math].

Recurrence and Ergodicity*

Definition (recurrence) A state [math]\displaystyle{ i }[/math] is recurrent if [math]\displaystyle{ \Pr[T_i\lt \infty\mid X_0=i]=1 }[/math]. If [math]\displaystyle{ i }[/math] is not recurrent, it is called transient. A recurrent state [math]\displaystyle{ i }[/math] is null recurrent if [math]\displaystyle{ h_{i,i}=\infty }[/math]. Otherwise, it is positive recurrent.

Definition (ergodicity) An aperiodic, positive recurrent state is an ergodic state. A Markov chain is ergodic if all its states are ergodic.