Stochastic Processes

Markov chains, martingales, Brownian motion and Itô.

Stochastic Processes

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 (Xt)(X_t) indexed by time tt. Time can be discrete (t=0,1,2,…t = 0, 1, 2, \dots) or continuous (t≥0t \ge 0). Ft\mathcal{F}_t denotes the information available up to time tt, meaning everything observed about the process so far.

Stopping time – A random time τ\tau such that whether "τ≤t\tau \le t" has happened can be decided from Ft\mathcal{F}_t 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:

P(Xt+1=j∣Xt=i,Xt−1,… )=P(Xt+1=j∣Xt=i)=PijP(X_{t+1} = j \mid X_t = i, X_{t-1}, \dots) = P(X_{t+1} = j \mid X_t = i) = P_{ij}

Transition matrix – PP collects the probabilities PijP_{ij}, so each row sums to 1. If πt\pi_t is the row vector of state probabilities at time tt, then πt+1=πtP\pi_{t+1} = \pi_t P and πt=π0Pt\pi_t = \pi_0 P^t.

Stationary distribution – A distribution π\pi that one step of the chain leaves unchanged, π=πP\pi = \pi P. 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 π\pi from any start. Moreover πi=1/E[time to return to i]\pi_i = 1/\mathbb{E}[\text{time to return to } i].

Detailed balance – If πiPij=πjPji\pi_iP_{ij} = \pi_jP_{ji} for all i,ji, j, then π\pi is stationary. Markov chain Monte Carlo methods are built this way. Metropolis–Hastings proposes moving from ii to jj with probability qijq_{ij} and accepts the move with probability

min⁡(1,πjqjiπiqij)\min\Big(1, \frac{\pi_jq_{ji}}{\pi_iq_{ij}}\Big)

Absorbing chains – Some states, once entered, are never left. Order the states so that P=(QR0I)P = \begin{pmatrix}Q & R\\ 0 & I\end{pmatrix}, with QQ holding the moves among the non-absorbing (transient) states. The fundamental matrix N=(I−Q)−1N = (I - Q)^{-1} gives the expected number of visits to each transient state. N1N\mathbf{1} gives the expected time until absorption, and NRNR the probability of ending in each absorbing state.

Random walks and martingales

Simple random walk – Sn=X1+⋯+XnS_n = X_1 + \dots + X_n with independent steps Xi=+1X_i = +1 with probability pp and −1-1 with probability q=1−pq = 1 - p. It is symmetric when p=12p = \tfrac12. 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 nn, E∣Sn∣≈2n/π\mathbb{E}\lvert S_n\rvert \approx \sqrt{2n/\pi}.

Martingale – A process whose expected next value, given everything observed so far, is its current value: a fair game.

E[Mt+1∣Ft]=Mt\mathbb{E}[M_{t+1} \mid \mathcal{F}_t] = M_t

For the symmetric walk, both SnS_n and Sn2−nS_n^2 - n are martingales. For the biased walk, (q/p)Sn(q/p)^{S_n} is.

Optional stopping theorem – Stopping a martingale at a stopping time τ\tau does not change its expectation, E[Mτ]=M0\mathbb{E}[M_\tau] = M_0. This holds when τ\tau is bounded, or more generally when Eτ\mathbb{E}\tau is finite and the steps are bounded.

Example (gambler's ruin): a symmetric walk starts at kk and stops at 00 or NN. Applying optional stopping to SnS_n gives N⋅P(hit N)=kN \cdot P(\text{hit } N) = k, so P(hit N)=k/NP(\text{hit } N) = k/N. Applying it to Sn2−nS_n^2 - n gives N2⋅kN−Eτ=k2N^2 \cdot \tfrac{k}{N} - \mathbb{E}\tau = k^2, so Eτ=k(N−k)\mathbb{E}\tau = k(N-k). For a biased walk with r=q/pr = q/p, P(hit N)=1−rk1−rNP(\text{hit } N) = \frac{1 - r^k}{1 - r^N}.

Wald's identity – For i.i.d. steps XiX_i and a stopping time τ\tau with finite mean:

E[∑i=1τXi]=Eτ⋅EX\mathbb{E}\Big[\sum_{i=1}^{\tau}X_i\Big] = \mathbb{E}\tau \cdot \mathbb{E}X

Reflection principle – A path that reaches level aa can be reflected after its first visit, which pairs it with a path ending above aa. For the symmetric walk this gives P(max⁡k≤nSk≥a)=2P(Sn>a)+P(Sn=a)P(\max_{k\le n}S_k \ge a) = 2P(S_n > a) + P(S_n = a). It also proves the ballot theorem: if candidate A gets pp votes and B gets qq votes with pp more than qq, A stays strictly ahead throughout the count with probability p−qp+q\frac{p-q}{p+q}.

Brownian motion

Brownian motion – A continuous-time process WtW_t, also called a Wiener process, that is the scaling limit of a random walk. It satisfies:

  • W0=0W_0 = 0 and the paths are continuous, though nowhere differentiable.
  • Increments over non-overlapping intervals are independent, and Wt−Ws∼N(0,t−s)W_t - W_s \sim \mathcal{N}(0, t-s).

Cov⁡(Ws,Wt)=min⁡(s,t)\operatorname{Cov}(W_s, W_t) = \min(s,t). WtW_t, Wt2−tW_t^2 - t and eθWt−θ2t/2e^{\theta W_t - \theta^2t/2} are all martingales.

Quadratic variation – Summing squared increments over finer and finer grids on [0,t][0,t] gives exactly tt. Informally, (dW)2=dt(dW)^2 = dt. This is why ordinary calculus fails for Brownian paths.

Hitting and exit – The reflection principle carries over: P(max⁡s≤tWs≥a)=2P(Wt≥a)P(\max_{s\le t}W_s \ge a) = 2P(W_t \ge a). Started at 0 and stopped on leaving the interval (−a,b)(-a, b), P(exit at b)=aa+bP(\text{exit at } b) = \frac{a}{a+b} and Eτ=ab\mathbb{E}\tau = ab.

Itô calculus

Stochastic differential equation (SDE) – dXt=μ dt+σ dWtdX_t = \mu\,dt + \sigma\,dW_t. The drift μ\mu is the deterministic trend per unit time, and the volatility σ\sigma scales the random shocks. Both may depend on tt and XtX_t.

Itô's lemma – The chain rule for a smooth function f(t,Xt)f(t, X_t). It has an extra second-derivative term because (dW)2=dt(dW)^2 = dt, while dt dWdt\,dW and (dt)2(dt)^2 vanish.

df=(ft+μfx+12σ2fxx)dt+σfx dWdf = \Big(f_t + \mu f_x + \tfrac12\sigma^2f_{xx}\Big)dt + \sigma f_x\,dW

Itô isometry – The variance of a stochastic integral:

E[(∫0tHs dWs)2]=E∫0tHs2 ds\mathbb{E}\Big[\Big(\int_0^tH_s\,dW_s\Big)^2\Big] = \mathbb{E}\int_0^tH_s^2\,ds

Example: Itô's lemma applied to f=W2f = W^2 gives d(W2)=2W dW+dtd(W^2) = 2W\,dW + dt, so ∫0tW dW=12(Wt2−t)\int_0^tW\,dW = \tfrac12(W_t^2 - t), not 12Wt2\tfrac12W_t^2 as ordinary calculus would suggest.

Geometric Brownian motion (GBM) – dS=μS dt+σS dWdS = \mu S\,dt + \sigma S\,dW: the percentage changes are Gaussian, the standard model for stock prices. Itô's lemma on log⁡S\log S gives the solution

St=S0exp⁡((μ−12σ2)t+σWt)S_t = S_0\exp\Big(\big(\mu - \tfrac12\sigma^2\big)t + \sigma W_t\Big)

so StS_t is lognormal with ESt=S0eμt\mathbb{E}S_t = S_0e^{\mu t}.

Ornstein–Uhlenbeck (OU) process – A mean-reverting process, pulled back toward the level μ\mu at speed θ\theta:

dX=θ(μ−X) dt+σ dWdX = \theta(\mu - X)\,dt + \sigma\,dW

Its long-run distribution is N(μ,σ2/2θ)\mathcal{N}(\mu, \sigma^2/2\theta), and deviations halve every ln⁡2/θ\ln 2/\theta 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 ϕ\phi of yesterday's plus independent noise εt\varepsilon_t with variance σ2\sigma^2. It is the discrete-time version of the OU process.

xt=ϕxt−1+εtx_t = \phi x_{t-1} + \varepsilon_t

It is stationary when ∣ϕ∣\lvert\phi\rvert is less than 1, with variance σ2/(1−ϕ2)\sigma^2/(1-\phi^2) and lag-kk autocorrelation ϕk\phi^k.

Unit root – With ϕ=1\phi = 1 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 xtx_t and xt−kx_{t-k}. The partial autocorrelation function (PACF) gives the same correlation after removing the effect of the lags in between. An AR(pp) model's PACF cuts off after lag pp. A moving-average MA(qq) model, xt=εt+θ1εt−1+⋯+θqεt−qx_t = \varepsilon_t + \theta_1\varepsilon_{t-1} + \dots + \theta_q\varepsilon_{t-q}, has an ACF that cuts off after lag qq.