Markov Chains

1. Markov Chain Definition & Basic Properties

The Markov Property (Memoryless Property)

Core Definition

A stochastic process $\{X_n; n=0,1,2,\ldots\}$ with discrete state space $I$ (such as $\{0,1,2,\ldots\}$ or finite sets) is called a Markov chain if for any $k \geq 1$ , time instants $0 \leq n_0 < n_1 < \cdots < n_k$ , and states $i_0, i_1, \ldots, i_k, j \in I$ , it satisfies:

P\{X_{n_k+1}=j \mid X_{n_0}=i_0, X_{n_1}=i_1, \ldots, X_{n_k}=i_k\} = P\{X_{n_k+1}=j \mid X_{n_k}=i_k\}

Intuitive Meaning: "Given the present, the future is independent of the past" — predicting the future requires only the current state information, not the historical states.

Time-Homogeneous Markov Chains

If the transition probability $P\{X_{n+1}=j \mid X_n=i\}$ is independent of time $n$ , the chain is called time-homogeneous. We denote the one-step transition probability as:

p_{ij} = P\{X_{n+1}=j \mid X_n=i\}, \quad \forall i,j \in I, n \geq 0

Transition Matrix Properties

The one-step transition matrix $\mathbf{P} = (p_{ij})_{I \times I}$ satisfies:

Non-negativity: $p_{ij} \geq 0$ (probabilities are non-negative)
Row stochastic: $\sum_{j \in I} p_{ij} = 1$ (from state $i$ , transition to some state)

Example: Binary Transmission System

In a binary communication system with correct transmission probability $p$ and error probability $q = 1-p$ . State space $I = \{0,1\}$ , transition matrix:

\mathbf{P} = \begin{pmatrix} p & q \\ q & p \end{pmatrix}

This represents: $p_{00} = p$ (0 transmitted correctly as 0), $p_{01} = q$ (0 transmitted incorrectly as 1), etc.

2. Chapman-Kolmogorov Equations & Multi-Step Transitions

Multi-Step Transition Probabilities

The $n$ -step transition probability from state $i$ to state $j$ is defined as:

p_{ij}(n) = P\{X_{n+m}=j \mid X_m=i\}, \quad \forall m \geq 0, n \geq 1

The corresponding $n$ -step transition matrix is $\mathbf{P}(n) = (p_{ij}(n))_{I \times I}$ , with $\mathbf{P}(1) = \mathbf{P}$ .

Chapman-Kolmogorov Equations (Core Formula)

For any $i,j \in I$ and positive integers $u,v \geq 1$ :

p_{ij}(u+v) = \sum_{k \in I} p_{ik}(u) p_{kj}(v)

Matrix form:

\mathbf{P}(u+v) = \mathbf{P}(u) \cdot \mathbf{P}(v)

Interpretation: The probability of going from

i

j

u+v

steps equals the sum over all intermediate states

k

of "going from

i

k

u

steps, then from

k

j

v

steps."

Key Consequence

This leads to the fundamental result:

\mathbf{P}(n) = \mathbf{P}^n

So $\mathbf{P}(2) = \mathbf{P}^2$ , $\mathbf{P}(3) = \mathbf{P}^3$ , etc.

Example: Two-Step Transition Calculation

For the binary transmission system with $\mathbf{P} = \begin{pmatrix} p & q \\ q & p \end{pmatrix}$ , the two-step transition probability $p_{00}(2)$ is:

p_{00}(2) = p_{00}p_{00} + p_{01}p_{10} = p^2 + q^2

This matches the direct calculation: "two transmissions both correct OR both incorrect."

3. State Classification & Properties

First Passage Times & Hitting Probabilities

First Passage Time

The first passage time from state $i$ to state $j$ is:

\tau_{ij} = \min\{n \geq 1 \mid X_n = j \mid X_0 = i\}

with convention $\min \emptyset = \infty$ .

Hitting Probability

The probability of ever reaching state $j$ from state $i$ :

f_{ij} = P\{\tau_{ij} < \infty \mid X_0 = i\}

Recurrent vs Transient States

Recurrent State

Definition: $f_{ii} = 1$
Returns to itself with probability 1
Equivalent: $\sum_{n=1}^\infty p_{ii}(n) = \infty$
Visits infinitely often

Transient State

Definition: $f_{ii} < 1$
Positive probability of never returning
Equivalent: $\sum_{n=1}^\infty p_{ii}(n) < \infty$
Visits finitely often

Positive vs Null Recurrence

For a recurrent state $i$ , define the mean return time:

\mu_i = E[\tau_{ii} \mid X_0 = i] = \sum_{n=1}^\infty n \cdot P\{\tau_{ii} = n \mid X_0 = i\}

Positive Recurrent

$\mu_i < \infty$
Finite mean return time
In stationary distribution: $\pi_i = 1/\mu_i$

Null Recurrent

$\mu_i = \infty$
Infinite mean return time
Stationary probability: $\pi_i = 0$

Key Result: Finite state Markov chains have no null recurrent states. If the state space is finite, all recurrent states are positive recurrent.

Periodicity

The period of state $i$ is defined as:

d(i) = \gcd\{n \geq 1 \mid p_{ii}(n) > 0\}

where $\gcd$ denotes the greatest common divisor.

Aperiodic

$d(i) = 1$
Can return at irregular intervals
Most common in applications

Periodic

$d(i) > 1$
Returns only at multiples of $d(i)$
Example: Bipartite graphs have period 2

4. Stationary Distributions & Long-term Behavior

Definition of Stationary Distribution

A probability distribution $\{\pi_j; j \in I\}$ is called stationary if it satisfies:

Normalization: $\sum_{j \in I} \pi_j = 1$
Balance equations: $\pi_j = \sum_{i \in I} \pi_i p_{ij}$

Matrix form:

\boldsymbol{\pi} = \boldsymbol{\pi} \mathbf{P}

where $\boldsymbol{\pi} = (\pi_0, \pi_1, \pi_2, \ldots)$ is the stationary distribution vector.

Existence & Uniqueness Conditions

Chain Type	Stationary Distribution
Irreducible, aperiodic, positive recurrent	Unique stationary distribution exists $\pi_j = 1/\mu_j$
Irreducible, null recurrent or transient	No stationary distribution (or only trivial $\pi_j = 0$ )
Reducible (multiple closed classes)	Multiple stationary distributions (convex combinations possible)

Computing Stationary Distributions

For Finite State Spaces

Given state space $I = \{0,1,\ldots,m\}$ and transition matrix $\mathbf{P} = (p_{ij})$ :

Write balance equations: $\pi_j = \sum_{i=0}^m \pi_i p_{ij}$ (m+1 equations, m independent)
Add normalization: $\sum_{j=0}^m \pi_j = 1$
Solve the linear system

Example: Binary Transmission System

For $\mathbf{P} = \begin{pmatrix} 0.8 & 0.2 \\ 0.3 & 0.7 \end{pmatrix}$ :

Balance equations: $\pi_0 = 0.8\pi_0 + 0.3\pi_1$
Normalization: $\pi_0 + \pi_1 = 1$
Solution: $\pi_0 = 0.6, \pi_1 = 0.4$

5. Classic Applications

Gambler's Ruin Problem

Player A starts with $i$ dollars, Player B with $m-i$ dollars. Each game, A wins \$1 with probability $p$ or loses \$1 with probability $q=1-p$ . Game continues until one player is ruined.

Ruin Probabilities

Fair Game ( $p = 0.5$ )

h_i = \frac{m-i}{m}

Unfair Game ( $p \neq 0.5$ )

h_i = \frac{(q/p)^i - (q/p)^m}{1 - (q/p)^m}

Expected Game Duration

Fair Game

E[T_i] = i(m-i)

Unfair Game

E[T_i] = \frac{i}{q-p} - \frac{m}{q-p} \cdot \frac{(q/p)^i - 1}{(q/p)^m - 1}

PageRank Algorithm

Google's PageRank algorithm models web surfing as a Markov chain where:

• States represent web pages
• Transitions represent clicking on links
• From page $i$ with $k_i$ outbound links, transition probability to linked page $j$ is $p_{ij} = 1/k_i$

Key Insight: The PageRank vector is the stationary distribution

\boldsymbol{\pi}

of this web-surfing Markov chain. Pages with higher

\pi_j

are ranked higher.

Queueing Systems

Model: Single server + 2 waiting positions (state space $I = \{0,1,2,3\}$ ), where $X_n$ = number of customers at time $n\Delta t$ .

Transition Rules

• Customer arrival probability: $q$ per time unit
• Customer service completion probability: $p$ per time unit
• $p_{01} = q$ (arrival when empty), $p_{10} = p$ (service completion)
• $p_{32} = p$ (service completion when full)

The stationary distribution $\boldsymbol{\pi}$ gives long-term probabilities of having 0, 1, 2, or 3 customers in the system.

1. Markov Chain Definition & Basic Properties

Core Definition

Time-Homogeneous Markov Chains

Transition Matrix Properties

2. Chapman-Kolmogorov Equations & Multi-Step Transitions

Key Consequence

3. State Classification & Properties

First Passage Time

Hitting Probability

Recurrent State

Transient State

Positive Recurrent

Null Recurrent

Aperiodic

Periodic

4. Stationary Distributions & Long-term Behavior

For Finite State Spaces

Example: Binary Transmission System

5. Classic Applications

Ruin Probabilities

Fair Game (p=0.5p = 0.5p=0.5)

Unfair Game (p≠0.5p \neq 0.5p=0.5)

Expected Game Duration

Fair Game

Unfair Game

Transition Rules

Ready to Practice?

Fair Game ( $p = 0.5$ )

Unfair Game ( $p \neq 0.5$ )