Markov Chains

Why It Matters

Markov Property

Transition Matrix

State Distribution

The state distribution at time is obtained by multiplying the initial distribution by . If we start in a specific state , then (the -th standard basis vector), and is the -th row of .

n-Step Transitions

This is equivalent to matrix multiplication: .

Stationary Distribution

Ergodicity

Absorbing States

For an absorbing chain with transient states and absorbing states , the fundamental matrix is:

where is the submatrix of transitions among transient states. The entry of gives the expected number of times the chain visits transient state starting from transient state before absorption.

Python Implementation

Applications in AI/ML

PageRank

def pagerank(adjacency: np.ndarray, d: float = 0.85, max_iter: int = 100) -> np.ndarray:
    """Compute PageRank via power iteration."""
    n = adjacency.shape[0]
    col_sums = adjacency.sum(axis=0)
    col_sums[col_sums == 0] = 1  # Handle dangling nodes
    M = adjacency / col_sums
    r = np.ones(n) / n
    for _ in range(max_iter):
        r_new = (1 - d) / n + d * M @ r
        if np.allclose(r, r_new, atol=1e-8):
            break
        r = r_new
    return r

# Example: 4-page web
links = np.array([[0, 1, 0, 1],
                  [1, 0, 1, 0],
                  [0, 1, 0, 1],
                  [1, 0, 1, 0]])
print("PageRank:", pagerank(links))

Markov Chain Monte Carlo (MCMC)

def metropolis_hastings(target_log_prob, proposal, n_samples, x0):
    """Generic Metropolis-Hastings sampler."""
    samples = [x0]
    x = x0
    for _ in range(n_samples):
        x_prop = proposal(x)
        log_alpha = target_log_prob(x_prop) - target_log_prob(x)
        if np.log(np.random.uniform()) < log_alpha:
            x = x_prop
        samples.append(x)
    return np.array(samples)

# Example: Sample from N(0,1)
target = lambda x: -0.5 * x**2
proposal = lambda x: x + np.random.normal(0, 0.5)
samples = metropolis_hastings(target, proposal, 10000, 0.0)
print(f"Mean: {samples.mean():.4f}, Std: {samples.std():.4f}")

Hidden Markov Models (HMMs)

Common Mistakes

Mistake	Why It's Wrong	Correct Approach
Assuming rows sum to 1 for column-stochastic matrices	PageRank uses column-stochastic matrices; rows may not sum to 1	Check the convention; normalize columns for PageRank
Confusing left and right eigenvectors	Stationary distribution is a left eigenvector:	Solve , not
Forgetting the normalization constraint	The stationary distribution must satisfy	Always normalize the eigenvector to sum to 1
Assuming all chains have a stationary distribution	Periodic or reducible chains may not converge	Verify ergodicity (irreducible + aperiodic) first
Ignoring dangling nodes in PageRank	Pages with no outgoing links break the Markov chain	Add teleportation or connect dangling nodes to all pages
Using power iteration without convergence check	May run too many or too few iterations	Check
Confusing transient with absorbing states	Not all states with are absorbing	An absorbing state requires exactly