Randomized Algorithms (Spring 2010)/Markov chains and random walks: Difference between revisions
imported>WikiSysop |
imported>WikiSysop |
||
Line 24: | Line 24: | ||
A stochastic process <math>X_0,X_1,\ldots</math> of discrete time and discrete space is a '''Markov chain''' if it has the Markov property. | A stochastic process <math>X_0,X_1,\ldots</math> of discrete time and discrete space is a '''Markov chain''' if it has the Markov property. | ||
Let <math>P^{(t)}_{i,j}=\Pr[X_{t+1}=j\mid X_t=i]</math>. For a Markov chain with a finite state space <math>\mathcal{S}=[N]</math>. This gives us a '''transition matrix''' <math>P^{(t)}</math> at time <math>t</math>. The transition matrix <math>P^{(t)}</math> is an <math>N\times N</math> matrix of nonnegative entries such that the sum over each row of <math>P^{(t)}</math> is 1, since | |||
:<math>\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>\pi_t</math> be the distribution of the chain at time <math>t</math>, that is, <math>\begin{align}\pi_t(i)=\Pr[X_t=i]\end{align}</math>. <math>\pi_t</math> can be seen as a vector of <math>N</math> nonnegative entries such that <math>\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>\begin{align}\pi_{t+1}=\pi_tP^{(t)}\end{align}</math>. | |||
To see this, we apply the law of total probability, | |||
:<math> | |||
\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>X_0,X_1,\ldots</math> is specified by an initial distribution <math>\pi_0</math> and a sequence of transition matrices <math>P^{(0)},P^{(1)},\ldots</math>. | |||
:<math>\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>P^{(n)}_{i,j}=P_{i,j}</math> for all <math>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 === | === Irreducibility and aperiodicity === |
Revision as of 03:43, 28 April 2010
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)
|
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)
|
Definition (aperiodicity)
|
Stationary distributions
Definition (stationary distribution)
|
Theorem (Basic limit theorem)
|
Recurrence and Ergodicity*
Definition (recurrence)
|
Definition (ergodicity)
|