CMO-516: Random walks

Tags:

1

Classifications of states (for Markov chains)

Def: Let $i, j$ be two states if $S$: $i$ and $j$ communicate if $\exists n, m \geq 0, s.t. p_{ij} > 0$ and $p_{ji} > 0$.

NB: By convention $p_{ij}(0) = $ TODO!

The relation $\longleftrightarrow$ is an equivalence relation (i.r. reflexsive, symmetric, transitive,

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 $p_{ii} = 1, \forall n$, the state $i$ is absorbing.

Periodicy

Def: Let $i \in S$. Define $d_i = GCD(n \geq 1: p_{ii} > 0)$

$i$ is periodic with period $d_i$ if $d_i > 1$.

$i$ is aperiodic with period $d_i = 1$.

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 $i \in S$. Then $f_{ii} = 1$ iff $ \sum_{n \geq 1} p_{ii}(n) = + \infty$.

Proof: $p_{ii}(n) = P(C_i=n | X_0 = i), p_{ii}(0) = 0$.

6

Example: Symmetric random walk in 1D or 2D

4

2D: Symmetric case:$p_{\vec{0}\vec{0}}(2n) \simeq P(u_{2n} = v_{2n} | u_0 = v_0 = 0)$ = $P(u_{2n} = v_{2n})P(u_0 = v_0 = 0) \simeq \frac{1}{2 \pi n}$.

5

Written by

Martin Hallén

Last updated: Wed, 9 Mar 2016 08:18:27 +0100 .