|
|
| Line 30: |
Line 30: |
| </math> | | </math> |
| :for all states <math>i</math>. | | :for all states <math>i</math>. |
| |}
| |
|
| |
| ==== Irreducibility and aperiodicity ====
| |
| {|border="1"
| |
| |'''Definition (irreducibility)'''
| |
| :State <math>j</math> is '''accessible from''' state <math>i</math> if it is possible for the chain to visit state <math>j</math> if the chain starts in state <math>i</math>, or, in other words,
| |
| ::<math>\begin{align}P^n(i,j)>0\end{align}</math>
| |
| :for some integer <math>n\ge 0</math>. State <math>i</math> '''communicates with''' state <math>j</math> if <math>j</math> is accessible from <math>i</math> and <math>i</math> is accessible from <math>j</math>.
| |
| :
| |
| :We say that the Markov chain is '''irreducible''' if all pairs of states communicate.
| |
| |}
| |
|
| |
|
| |
| {|border="1"
| |
| |'''Definition (aperiodicity)'''
| |
| :The '''period''' of a state <math>i</math> is the greatest common divisor (gcd)
| |
| ::<math>\begin{align}d_i=\gcd\{n\mid P^n(i,i)>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 ====
| |
|
| |
| {|border="1"
| |
| |'''Definition (recurrence)'''
| |
| :A state <math>i</math> is '''recurrent''' if <math>\Pr[T_i<\infty\mid X_0=i]=1</math>. If <math>i</math> is not recurrent, it is called '''transient'''.
| |
| :A recurrent state <math>i</math> is '''null recurrent''' if <math>h_{i,i}=\infty</math>. Otherwise, it is '''positive recurrent'''.
| |
| |}
| |
|
| |
|
| |
| {|border="1"
| |
| |'''Definition (ergodicity)'''
| |
| :An aperiodic, positive recurrent state is an '''ergodic''' state. A Markov chain is ergodic if all its states are ergodic.
| |
| |} | | |} |
|
| |
|
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].
|
Random Walks on Graphs
Hitting and covering
Mixing