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

Markov Chains

The Markov property and transition matrices

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].

The Markov property describes the memoryless property of a Markov chain: "conditioning on the present, the future does not depend on the past."

A discrete time stochastic process [math]\displaystyle{ X_0,X_1,\ldots }[/math] is a Markov chain if it has the Markov property.

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].

The basic limit theorem

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].

Definition (irreducible) 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.