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, 108 flashcards. Below is a complete table-by-table outline of this topic, spanning foundational concepts through advanced details.
A jump-to index of every table row in this cheat sheet.
An interactive map of every table and concept in this topic.
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 $n$th 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$ | ||
$P(X_{n+1}=j \mid X_n=i)$ does not depend on $n$ | • Transition probabilities are constant over time • assumed unless stated otherwise | ||
$\mathcal{S} = {0, 1, 2, \ldots}$ (countable) | • Set of all possible values the chain can take • may be finite or countably infinite | ||
$i \to j$ if $(P^n)_{ij} > 0$ for some $n \ge 0$ | State $j$ is accessible from $i$ if it can be reached in finitely many steps | ||
$i \leftrightarrow j$ if $i \to j$ and $j \to i$ | Equivalence relation partitioning $\mathcal{S}$ into communicating classes |