|
|
Line 14: |
Line 14: |
|
| |
|
| A ''discrete time'' stochastic process <math>X_0,X_1,\ldots</math> is a '''Markov chain''' if it has the Markov property. | | A ''discrete time'' stochastic process <math>X_0,X_1,\ldots</math> is a '''Markov chain''' if it has the Markov property. |
|
| |
| === Stationary distributions ===
| |
| {|border="1"
| |
| |'''Definition (stationary distribution)'''
| |
| : A '''stationary distribution''' of a Markov chain is a probability distribution <math>\pi</math> such that
| |
| ::<math>\begin{align}\pi P=\pi\end{align}</math>.
| |
| |}
| |
|
| |
|
|
| |
|
Line 55: |
Line 48: |
| |} | | |} |
|
| |
|
| === The basic limit theorem === | | |
| | === Stationary distributions === |
| | {|border="1" |
| | |'''Definition (stationary distribution)''' |
| | : A '''stationary distribution''' of a Markov chain is a probability distribution <math>\pi</math> such that |
| | ::<math>\begin{align}\pi P=\pi\end{align}</math>. |
| | |} |
| | |
| | |
| {|border="1" | | {|border="1" |
| |'''Theorem (Basic limit theorem)''' | | |'''Theorem (Basic limit theorem)''' |
Revision as of 01:43, 28 April 2010
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.
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.
|
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.
|
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].
|
Random Walks on Graphs
Hitting and covering
Mixing