CMO-516: Random walks
1
Classifications of states (for Markov chains)
Def: Let
NB: By convention
The relation
- Reflecsive
$i \longleftrightarrow j$ - Symmetric
$i \longleftrightarrow j$ iff$j \longleftrightarrow i$ - Transitive
$i \longleftrightarrow j$ and$j \longleftrightarrow k$ yields$i \longleftrightarrow k$
Why is equivalence nice? The whole state space can be divided into disjunct equivalence classes.
Def: If there is a single equialence calss( i.r. all states cummunicate), we say that the chain is irreducible
If
Periodicy
Def: Let
2
Fact: In a given equivalence class, all states have the same period.
If there is a self loop in the graph, and the chain is irreducible, then the period is 1.
Recurrence & transience
Def:
- A state
$i \in S$ is recurrent if$f_{ii} = P(X_n = 1$ for some$n > 0 | X_0 ) i) = 1$ - A state
$i \in S$ is transient if$f_{ii} > 1$ .
Facts:
- In a given equivalence calss, either all states are recurrent, or all states are transient.
- In a finite chaing, an equivalence class is recurrent iff there is no arrow leading out of it.
3
- Consequence: a finite irreducible chain is alwaus recurrent.
Proposition: Let
Proof:
6
Example: Symmetric random walk in 1D or 2D
4
2D: Symmetric case:
5