Most of statistics treats observations as independent draws. Many data are not. The number of deaths in a week depends on the weeks before it, the page a reader opens next depends on the page open now, and the time to the next large earthquake is one of a sequence of such times. A stochastic process is a collection of random variables indexed by time, and what makes it interesting is how the variables depend on one another. This unit treats the processes that the rest of the site uses: Markov chains, the Poisson process, random walks and martingales, stationary time series and their linear models, and hidden Markov models.
The course pages meet these processes without the theory. The Poisson Distribution counts events in time; The Central Limit Theorem assumes an independence that weekly series do not have. The information retrieval course runs Markov chains in PageRank, and a bigram language model (The Bigram Language Model) generates text by a Markov chain on characters. The library uses them too: Markov Chain Monte Carlo runs chains on continuous spaces, Resampling Dependent and Clustered Data resamples blocks of a dependent series, and The EM Algorithm is the general form of the algorithm that fits hidden Markov models. This unit supplies the theorems beneath them.
What it assumes. Probability Theory, in particular Conditional Expectation and the Laws of Total Expectation and Variance, The Laws of Large Numbers and Convergence in Distribution and the Proof of the Central Limit Theorem. For fitting, Likelihood and Estimation, and for hidden Markov models The EM Algorithm. Some linear algebra: matrix powers, eigenvalues, and the real spectral theorem as cited in Covariance Matrices and Quadratic Forms.
What is proved and what is cited. The unit proves its results for finitely many states, for sums of independent pieces, and for processes defined by their first two moments, and cites the general theory beyond that. Proved: the Chapman–Kolmogorov equations; that every finite Markov chain has a stationary distribution, unique and positive when the chain is irreducible, with each stationary probability the reciprocal of a mean return time; that irreducible aperiodic chains are regular and converge to stationarity at a geometric rate; the ergodic theorem for time averages, from the strong law of large numbers; the fundamental matrix of an absorbing chain; detailed balance, the random walk on a graph and a spectral bound for reversible chains; the forward, backward and Viterbi algorithms of hidden Markov models, with scaling and the Baum–Welch updates; the equivalence of the three definitions of the Poisson process, the memoryless property, uniform arrival times given the count, thinning, superposition and compound Poisson moments; the gambler's ruin, the optional stopping theorem for bounded stopping times and bounded stopped processes, Wald's identity, Ville's maximal inequality and the error bounds of Wald's sequential probability ratio test; that autocovariance functions are exactly the even nonnegative definite functions (the converse given Kolmogorov's extension theorem), the variance of a mean under any covariances, the exact bias of the sample autocovariance, a central limit theorem for $m$-dependent sequences and from it the laws of the sample autocorrelations of noise and of the portmanteau tests; the stationary solutions of autoregressions, causality and invertibility of ARMA models from the roots of their polynomials, the Yule–Walker equations, best linear prediction and the Durbin–Levinson recursion, and the asymptotic normality of the estimates of a first-order autoregression with Gaussian noise. Cited, among others: the convergence and ergodic theory of chains on infinite and continuous state spaces, the absence of the eigenvalue $-1$ for irreducible aperiodic chains, the central limit theorem for Markov chains, Kolmogorov's extension theorem, the Cramér–Wold device, the general conditions for optional stopping, Kolmogorov's zero-one law, the strong law of large numbers under a finite mean, Bartlett's formula in general, and the asymptotic theory of ARMA estimation beyond the first order (Hannan, 1973).
Notation. Discrete-time chains are written $X_0, X_1, \ldots$ with time $n$, on a finite state space $S$ with states $i, j, k$; the transition matrix is $P = (p_{ij})$, a stochastic matrix whose rows sum to 1, and $n$-step probabilities are the entries $p_{ij}^{(n)}$ of $P^n$. Distributions are row vectors: the initial distribution is $\mu$, the distribution at time $n$ is $\mu P^n$, and a stationary distribution $\pi$ solves $\pi P = \pi$. Hitting and return times are $T_A = \min\{n \ge 0 : X_n \in A\}$ and $T_i^+ = \min\{n \ge 1 : X_n = i\}$, with mean return time $m_i = E_i[T_i^+]$. An absorbing chain has canonical blocks $Q$ and $R$ and fundamental matrix $N = (I - Q)^{-1}$. A hidden Markov model has hidden states $Z_1, \ldots, Z_T$ in $\{1, \ldots, K\}$ with transition matrix $P$ and initial distribution $\mu$, observations $Y_1, \ldots, Y_T$ with emission distributions $f_k$, forward and backward variables $\alpha_t(k)$ and $\beta_t(k)$, and posterior probabilities $\gamma_t(k)$. The Poisson process is $N(t)$ with rate $\lambda$, interarrival times $X_1, X_2, \ldots$ and arrival times $S_n$; a random walk is $S_n = S_0 + X_1 + \cdots + X_n$, and a stopping time is $\tau$. A time series is $X_t$ with mean $\mu$, autocovariance $\gamma(h) = \operatorname{Cov}(X_t, X_{t+h})$ and autocorrelation $\rho(h) = \gamma(h)/\gamma(0)$; white noise is $Z_t \sim \mathrm{WN}(0, \sigma^2)$, and an ARMA model is $\phi(B)X_t = \theta(B)Z_t$ with the backshift operator $B$. The word "stationary" has two uses here. A stationary distribution of a Markov chain is a distribution that one step leaves unchanged; a stationary time series is one whose means and autocovariances do not change with time. A chain started in its stationary distribution is a stationary process in the second sense, and each article says which it means. The letter $Z_t$ also has two uses, as in the sources: hidden states in the hidden Markov model article and white noise in the time-series articles.
Data. The site's own link graph, its 825 pages at one commit joined by 9,200 links, on which a random reader is a Markov chain. The weekly counts of deaths from all causes in Iowa, 2014 to 2019, from the National Center for Health Statistics (313 weeks), used before on the course page Overdispersion in Count Data and in Resampling Dependent and Clustered Data: here their autocorrelation, their ARMA models and their winter and summer seasons read as hidden states. The U.S. Geological Survey's catalog of earthquakes of magnitude 6 and over, 1975 to 2024, for the Poisson process. A simulated A/B test for random walks and sequential testing. Every number is computed by a script in tools/experiments/statistics/.
Articles
Markov chains
- Markov Chains and Stationary Distributions: the theory of finite Markov chains proved in full. The Chapman–Kolmogorov equations; existence of a stationary distribution for every finite chain, uniqueness and positivity for irreducible chains, and $\pi_i = 1/m_i$; periodicity, the equivalence of regular with irreducible and aperiodic, and convergence at a geometric rate by a contraction coefficient; the ergodic theorem from the strong law; absorbing chains and the fundamental matrix; reversibility, the random walk on a graph and a spectral bound. On the site's link graph at one commit, a reader who only follows links is caught by three pages after a median of about 30,000 clicks, a cluster of 45 algebra pages, left by a single link, slows mixing, and PageRank's teleportation brings every start within 0.04 of stationarity in 20 clicks.
- Hidden Markov Models: a Markov chain seen only through noisy signals. The likelihood as a sum over paths and the forward algorithm that computes it in time proportional to $TK^2$; the backward algorithm and the posterior probability of each hidden state; Viterbi decoding proved optimal; scaling against underflow; the Baum–Welch updates derived as an EM algorithm; and the autocorrelation a two-state model implies. On Iowa's weekly deaths a two-state Poisson model finds a low and a high season, fits far better than a Poisson or negative binomial model and decodes 91 of the 104 weeks of December to March as high; simulations measure decoding accuracy, parameter recovery and local maxima.
Events in time and walks
- The Poisson Process: what the hypothesis that events form a Poisson process asserts, in three equivalent forms, each turned into a test. Independent Poisson increments, independent exponential gaps and the infinitesimal definition proved equivalent; the exponential proved the only memoryless waiting time; arrival times given the count proved to be uniform order statistics; thinning and superposition; the moments of a compound Poisson count. On 6,992 earthquakes of magnitude 6 and over from 1975 to 2024 every test fails, because earthquakes cluster and the yearly rate drifts, and the compound Poisson model predicts the excess variance of monthly counts; the Fisher information of a page's change rate estimated from visits that only see whether it changed.
- Random Walks and Martingales: why a test checked after every batch of users eventually rejects a true null hypothesis, and how to check as often as one likes without losing the level. The gambler's ruin by first-step equations; martingales and the optional stopping theorem for bounded stopping times and bounded stopped processes, with the general conditions cited; Wald's identity; Ville's maximal inequality; likelihood ratios and Bayes factors as martingales under the null hypothesis, and the error bounds and termination of Wald's sequential probability ratio test. In a simulated A/B test, peeking after every 100 pairs of users raises the false positive rate from 0.05 to 0.43, while a test martingale stays below 0.05.
Time series
- Autocorrelation and Stationarity: what stationarity means and what dependence does to a mean, a t-test and the sample autocorrelations. Strict and weak stationarity; autocovariance functions proved to be exactly the even nonnegative definite functions (the converse given Kolmogorov's extension theorem); the variance of a mean and the expected sample variance for any covariances; the large-sample level of the nominal 5% t-test for an autoregressive series; the sample autocovariance proved nonnegative definite, with its exact bias; a central limit theorem for $m$-dependent sequences, and from it the laws of the sample autocorrelations of noise and of the Box–Pierce and Ljung–Box statistics; trend, seasonality and differencing, on Iowa's weekly deaths from all causes and from cancer.
- Autoregressive and Moving Average Models: the ARMA models of a stationary series, fitted and used to forecast. Stationary solutions of the first-order autoregression; the cutoff of moving-average autocovariances; causality and invertibility from the roots of the polynomials; the Yule–Walker equations; best linear prediction, the Durbin–Levinson recursion and the cutoff of partial autocorrelations; asymptotic normality of the estimates of a Gaussian first-order autoregression, with the general theory cited; forecasts and their intervals, with regression on ARMA errors; model choice and residual tests. Iowa's weekly deaths for 2014 to 2018 are fitted by a trend, an annual cycle and ARMA errors, and 2019 is forecast and checked against the seasonal naive method.
Where the unit leads
The chains here have finitely many states and move in discrete time; chains on continuous spaces are the samplers of Markov Chain Monte Carlo, and the general theory of both is cited where it is needed. The hidden Markov model treats each observation as independent given its hidden state, and its article shows what that leaves out: a trend and a fixed annual cycle. The time-series articles stop at linear models of one stationary series. Dependence of another kind, between questions of a benchmark that share a source, is the subject of Clustered Standard Errors in Statistics of Model Evaluation, and the next unit of the collection, Statistical Learning Theory, returns to independent data to bound the error of learned predictors.
References
Each article lists its own references. The sources on which the unit draws throughout: record · 4 pages
- Brockwell, P. J., and Davis, R. A. (2016). Introduction to Time Series and Forecasting (3rd ed.). Springer. https://doi.org/10.1007/978-3-319-29854-2 record · 3 pages
- Durrett, R. (2019). Probability: Theory and Examples (5th ed.). Cambridge University Press. record · 15 pages
- Grinstead, C. M., and Snell, J. L. (1997). Introduction to Probability (2nd rev. ed.). American Mathematical Society. record · 22 pages
- Hannan, E. J. (1973). The asymptotic theory of linear time-series models. Journal of Applied Probability, 10, 130–145. https://doi.org/10.1017/S0021900200042145 record · 2 pages
- Levin, D. A., and Peres, Y. (2017). Markov Chains and Mixing Times (2nd ed., with contributions by E. L. Wilmer). American Mathematical Society. https://doi.org/10.1090/mbk/107 record · 3 pages
- Norris, J. R. (1997). Markov Chains. Cambridge University Press. record · 3 pages