Markov chains and stochastic processes form the mathematical backbone of probabilistic modeling across machine learning, finance, biology, and operations research. This cheat sheet covers the complete landscape — from discrete-time Markov chains and their classification through continuous-time processes, hidden models, MCMC sampling, stochastic calculus, and modern applications. Each section pairs formal definitions with concrete formulas and usage patterns so you can move from theory to implementation quickly.
What This Cheat Sheet Covers
This topic spans 14 focused tables and 111 indexed concepts. Below is a complete table-by-table outline of this topic, spanning foundational concepts through advanced details.
Discrete-Time Markov Chains (DTMC) — FoundationsState ClassificationStationary Distribution and ConvergenceAbsorbing Markov ChainsContinuous-Time Markov Chains (CTMC)Poisson ProcessBirth-Death Processes and QueuesHidden Markov Models (HMMs)MCMC MethodsRandom Walks on GraphsMarkov Reward Processes and MDPsBrownian Motion and Stochastic CalculusApplicationsConvergence Diagnostics for MCMC
Discrete-Time Markov Chains (DTMC) — Foundations
| Concept | Example | Description |
|---|---|---|
P(X_{n+1}=j \mid X_n=i, X_{n-1},\ldots) = P(X_{n+1}=j \mid X_n=i) | • Future state depends only on present state, not history • "memorylessness" in the discrete setting | |
P = [p_{ij}], p_{ij} \ge 0, \sum_j p_{ij}=1 | Row-stochastic matrix P where entry p_{ij} is the one-step probability of moving from state i to state j | |
P^{(m+n)} = P^{(m)} P^{(n)} | • n-step transition probabilities obtained by matrix multiplication• (P^n)_{ij} gives P(X_n=j \mid X_0=i) | |
(P^n)_{ij} = P(X_n = j \mid X_0 = i) | Computed by raising the transition matrix to the nth power | |
\mu_0 = [\mu_0(1), \ldots, \mu_0(k)], \mu_n = \mu_0 P^n | • Row vector of initial probabilities • marginal at time n is \mu_0 P^n |