Stochastic Processes
Markov chains, martingales, Brownian motion and Itô.
This note covers random quantities that evolve over time: Markov chains, random walks, martingales, Brownian motion, Itô calculus and basic time series.
Foundations
Stochastic process – A collection of random variables indexed by time . Time can be discrete () or continuous (). denotes the information available up to time , meaning everything observed about the process so far.
Stopping time – A random time such that whether "" has happened can be decided from alone, without looking ahead. The first time a process hits a level is a stopping time; the last time it does is not.
Markov chains
Markov property – The future depends on the past only through the present state:
Transition matrix – collects the probabilities , so each row sums to 1. If is the row vector of state probabilities at time , then and .
Stationary distribution – A distribution that one step of the chain leaves unchanged, . A finite chain that is irreducible (every state can reach every other) and aperiodic (it doesn't cycle with a fixed period) converges to a unique from any start. Moreover .
Detailed balance – If for all , then is stationary. Markov chain Monte Carlo methods are built this way. Metropolis–Hastings proposes moving from to with probability and accepts the move with probability
Absorbing chains – Some states, once entered, are never left. Order the states so that , with holding the moves among the non-absorbing (transient) states. The fundamental matrix gives the expected number of visits to each transient state. gives the expected time until absorption, and the probability of ending in each absorbing state.
Random walks and martingales
Simple random walk – with independent steps with probability and with probability . It is symmetric when . In one and two dimensions a symmetric walk returns to its start with probability 1; in three or more it may never return (Pólya). For large , .
Martingale – A process whose expected next value, given everything observed so far, is its current value: a fair game.
For the symmetric walk, both and are martingales. For the biased walk, is.
Optional stopping theorem – Stopping a martingale at a stopping time does not change its expectation, . This holds when is bounded, or more generally when is finite and the steps are bounded.
Example (gambler's ruin): a symmetric walk starts at and stops at or . Applying optional stopping to gives , so . Applying it to gives , so . For a biased walk with , .
Wald's identity – For i.i.d. steps and a stopping time with finite mean:
Reflection principle – A path that reaches level can be reflected after its first visit, which pairs it with a path ending above . For the symmetric walk this gives . It also proves the ballot theorem: if candidate A gets votes and B gets votes with more than , A stays strictly ahead throughout the count with probability .
Brownian motion
Brownian motion – A continuous-time process , also called a Wiener process, that is the scaling limit of a random walk. It satisfies:
- and the paths are continuous, though nowhere differentiable.
- Increments over non-overlapping intervals are independent, and .
. , and are all martingales.
Quadratic variation – Summing squared increments over finer and finer grids on gives exactly . Informally, . This is why ordinary calculus fails for Brownian paths.
Hitting and exit – The reflection principle carries over: . Started at 0 and stopped on leaving the interval , and .
Itô calculus
Stochastic differential equation (SDE) – . The drift is the deterministic trend per unit time, and the volatility scales the random shocks. Both may depend on and .
Itô's lemma – The chain rule for a smooth function . It has an extra second-derivative term because , while and vanish.
Itô isometry – The variance of a stochastic integral:
Example: Itô's lemma applied to gives , so , not as ordinary calculus would suggest.
Geometric Brownian motion (GBM) – : the percentage changes are Gaussian, the standard model for stock prices. Itô's lemma on gives the solution
so is lognormal with .
Ornstein–Uhlenbeck (OU) process – A mean-reverting process, pulled back toward the level at speed :
Its long-run distribution is , and deviations halve every units of time.
Time series
Stationarity – A series is (weakly) stationary if its mean, variance and autocovariances do not change over time.
Autoregressive model of order 1, AR(1) – Today's value is a fraction of yesterday's plus independent noise with variance . It is the discrete-time version of the OU process.
It is stationary when is less than 1, with variance and lag- autocorrelation .
Unit root – With the series is a random walk, which is non-stationary. Test for it with the augmented Dickey–Fuller test. Regressing one random walk on another produces spurious correlation, so difference the series first, or test whether a combination of them is stationary (cointegration).
ACF and PACF – The autocorrelation function (ACF) gives the correlation between and . The partial autocorrelation function (PACF) gives the same correlation after removing the effect of the lags in between. An AR() model's PACF cuts off after lag . A moving-average MA() model, , has an ACF that cuts off after lag .