Core Module

8-12 Hours

Discrete Time Markov Chains

Modeling systems with memoryless transitions: from random walks to Google's PageRank

Markov Transition Calculator

Calculate n-step transition probabilities

Number of States

Transition Matrix P

P0:

P1:

Steps (n)

From State

To State

Markov Property & Definition - The Markov Property

A discrete-time stochastic process $\{X_n, n \geq 0\}$ has the Markov property if:

P(X_{n+1} = j | X_n = i, X_{n-1} = i_{n-1}, \dots, X_0 = i_0) = P(X_{n+1} = j | X_n = i)

The future depends only on the current state, not on the history. This is the "memoryless property".

Transition Matrix

The one-step transition probabilities form a matrix $P = (p_{ij})$ where:

p_{ij} = P(X_{n+1} = j | X_n = i)

Properties: $p_{ij} \geq 0$ and $\sum_j p_{ij} = 1$ for all $i$ .

Chapman-Kolmogorov Equations - n-Step Transitions

The probability of going from $i$ to $j$ in $n+m$ steps:

p_{ij}^{(n+m)} = \sum_{k \in S} p_{ik}^{(n)} p_{kj}^{(m)}

In matrix form: $P^{(n)} = P^n$

State Classification - Recurrent vs Transient

Recurrent: State $i$ is recurrent if $P(\text{return to } i) = 1$ .

Transient: State $i$ is transient if $P(\text{return to } i) < 1$ .

Periodicity

The period of state $i$ is the GCD of all $n$ such that $p_{ii}^{(n)} > 0$ . If period is 1, the state is aperiodic.

Stationary Distributions - Definition & Balance Equations

A probability distribution $\pi = (\pi_j)$ is stationary if:

\pi = \pi P, \quad \sum_j \pi_j = 1, \quad \pi_j \geq 0

Component-wise: $\pi_j = \sum_i \pi_i p_{ij}$ (balance equations).

Fundamental Theorems - Ergodic Theorem

For an irreducible, aperiodic, positive recurrent Markov chain:

\lim_{n \to \infty} p_{ij}^{(n)} = \pi_j

The n-step transition probabilities converge to the unique stationary distribution, regardless of the starting state.

Worked Examples - Example 1: Two-State Chain

Problem:

Find the stationary distribution for $P = \begin{pmatrix} 0.6 & 0.4 \\ 0.3 & 0.7 \end{pmatrix}$ .

Solution:

Solve $\pi = \pi P$ and $\pi_0 + \pi_1 = 1$ :

\pi_0 = 0.6\pi_0 + 0.3\pi_1, \quad \pi_1 = 0.4\pi_0 + 0.7\pi_1

Solving: $\pi_0 = 3/7, \pi_1 = 4/7$ .

Example 2: Random Walk on {0,1,2}

Problem:

A particle moves on states {0,1,2} with $p_{i,i+1} = 0.5$ and $p_{i,i-1} = 0.5$ (with reflecting boundaries). Classify states.

Solution:

All states communicate, so the chain is irreducible. All states are recurrent and aperiodic (period 1).

Example 3: Gambler's Ruin

Problem:

A gambler starts with $i and wins $1 with probability p, loses $1 with probability q=1-p. States 0 and N are absorbing. Find absorption probabilities.

Solution:

Let $u_i$ be the probability of reaching N before 0 starting from i. Using first-step analysis:

u_i = p u_{i+1} + q u_{i-1}, \quad u_0 = 0, u_N = 1

Solving this recurrence gives the absorption probabilities.

Practice Quiz

Questions

Correct

Accuracy

What is the Markov property?

Not attempted

Given transition matrix

P = \begin{pmatrix} 0.6 & 0.4 \\ 0.3 & 0.7 \end{pmatrix}

, find

p_{01}^{(2)}

(2-step transition from state 0 to state 1).

Not attempted

What property must a transition matrix satisfy?

Not attempted

What is a stationary distribution

\pi

Not attempted

What is the difference between a recurrent and transient state?

Not attempted

What does it mean for a Markov chain to be irreducible?

Not attempted

What is an absorbing state?

Not attempted

How do you calculate the n-step transition matrix

P^{(n)}

Not attempted

What is the period of a state?

Not attempted

What is the Ergodic Theorem for Markov chains?

Not attempted

Frequently Asked Questions

What exactly is the 'Memoryless Property'?

The memoryless property (Markov property) means that the future state depends only on the current state, not on the sequence of events that preceded it. Mathematically, P(X_{n+1}=j | X_n=i, X_{n-1}=i_{n-1}, ...) = P(X_{n+1}=j | X_n=i). It simplifies modeling by ignoring history.

What is the difference between a stationary distribution and a limiting distribution?

A stationary distribution π is a vector such that πP = π; if you start in this distribution, you stay in it. A limiting distribution is what the process converges to as n→∞, regardless of the starting state. For irreducible, aperiodic, positive recurrent chains, they are the same.

Can a Markov chain have multiple stationary distributions?

Yes, if the chain is reducible (has multiple closed communicating classes). For example, if you have two disconnected components, any linear combination of their stationary distributions is also stationary. However, an irreducible chain has at most one stationary distribution.

What does 'ergodic' mean in this context?

An ergodic Markov chain is one that is irreducible, aperiodic, and positive recurrent. For such chains, the time average of the process equals the state space average (stationary distribution) with probability 1. It means the system explores all states proportionally to their stationary probabilities.

How do I calculate the n-step transition matrix?

If P is the 1-step transition matrix, the n-step transition matrix P^(n) is simply the matrix power P raised to n. This is a direct consequence of the Chapman-Kolmogorov equations.