Stochastic Processes

1. Definitions

Stochastic Process

$\{X(t), t \in T\}$

Family of random variables indexed by time $t$.

Each $X(t)$ is a random variable.

State Space $S$

Set of all possible values.

Discrete or Continuous.

Index Set $T$

Time parameter set.

$T = \{0,1,2,\ldots\}$ (discrete).

$T = [0,\infty)$ (continuous).

Trajectory/Path

Realization of process.

$\{x(t) : t \in T\}$ for fixed outcome.

All stochastic processes are defined on probability space $(\Omega, \mathcal{F}, P)$.

2. Classification

By Time

Discrete: $T = \mathbb{Z}$ or $\mathbb{N}$.

Continuous: $T = \mathbb{R}$ or $[0,\infty)$.

By State Space

Discrete: $S = \{1,2,3,\ldots\}$.

Continuous: $S = \mathbb{R}$ or intervals.

Classification Matrix

	Discrete T	Continuous T
Discrete S	Markov Chains	Jump Processes
Continuous S	Random Walks	Brownian Motion

3. Markov Chains

Markov Property

$P(X_{n+1}=j|X_n=i,\ldots,X_0) = P(X_{n+1}=j|X_n=i)$

Future depends only on present.

Memoryless property.

Transition Matrix $P$

$p_{ij} = P(X_{n+1}=j|X_n=i)$

$\sum_j p_{ij} = 1$ (rows sum to 1).

$P$ is stochastic matrix.

n-Step Transition

$p_{ij}^{(n)} = [P^n]_{ij}$

Probability of $i \to j$ in $n$ steps.

Chapman-Kolmogorov: $P^{(n+m)} = P^{(n)} P^{(m)}$

4. Chapman-Kolmogorov

Equations

$p_{ij}^{(n+m)} = \sum_k p_{ik}^{(n)} p_{kj}^{(m)}$

Sum over all intermediate states $k$.

Matrix Form

$P^{(n+m)} = P^{(n)} \cdot P^{(m)}$

Key property: Composition rule for transitions

Applications

Computing long-run behavior.

Recursive computation of $P^n$.

Stability analysis.

Matrix multiplication: $P^n = \underbrace{P \cdots P}_{n \text{ times}}$

5. State Classification

Recurrent

$P(\text{return to } i) = 1$

State visited infinitely often.

$f_{ii} = 1$

Transient

$P(\text{return to } i) < 1$

Visited finitely often.

$\sum_{n=1}^\infty p_{ii}^{(n)} < \infty$

Periodic

$d_i = \gcd\{n: p_{ii}^{(n)} > 0\}$

$d_i > 1$: periodic with period $d_i$.

$d_i = 1$: aperiodic.

Ergodic

Aperiodic + positive recurrent.

$\lim_{n \to \infty} p_{ij}^{(n)} = \pi_j$

6. Stationary Dist.

Definition

$\pi P = \pi$

$\sum_i \pi_i = 1, \quad \pi_i \geq 0$

Solving

Solve linear system $(P^T - I)\pi^T = 0$.

Normalize: $\sum \pi_i = 1$.

Interpretation

Long-run proportion in state $i$.

$\lim_{n \to \infty} P(X_n = i) = \pi_i$

Existence

Irreducible + positive recurrent: unique $\pi$ (aperiodicity governs convergence, not existence).

Multiple classes: one $\pi$ per class.

If ergodic, all states "forget" initial condition.

7. Absorbing Chains

Absorbing State

$p_{ii} = 1, \quad p_{ij} = 0$ for $j \neq i$

Once entered, never leaves.

Fundamental Matrix

$N = (I - Q)^{-1}$

$Q$: transition among transient states.

$N_{ij}$: expected visits to $j$ starting from $i$.

Absorption Probs

$B = NR$

$R$: transitions to absorbing states.

$B_{ij}$: prob absorb into $j$ from $i$.

Expected Time

$t_i = \sum_j N_{ij}$

Rows of $N$ sum to absorption time.

8. Continuous-Time MC

Generator Matrix $Q$

$q_{ij} = \lim_{h \to 0} \frac{p_{ij}(h)}{h}$

$q_{ii} = -\sum_{j \neq i} q_{ij}$

Forward Kolmogorov Eq.

$P'(t) = P(t)Q$

Solution: $P(t) = e^{Qt}$

Holding Times

$\tau_i \sim \text{Exp}(|q_{ii}|)$

Exponential sojourn time in state $i$.

Jump Chain

$\tilde{p}_{ij} = -q_{ij}/q_{ii}$

Discrete chain between jumps.

9. Poisson Process

Definition $N(t)$

Counts events with rate $\lambda > 0$.

$N(0) = 0$.

PMF

$P(N(t)=k) = \frac{e^{-\lambda t}(\lambda t)^k}{k!}$

Key Properties

Independent increments.

Stationary increments.

$E[N(t)] = \lambda t$, $\text{Var}(N(t)) = \lambda t$

Interarrival Times

$T_i \sim \text{Exp}(\lambda)$ iid

Arrival times: $S_n = T_1 + \cdots + T_n$

Fundamental process in continuous time.

10. Birth-Death Process

Rates

$\lambda_i$: birth rate from state $i$

$\mu_i$: death rate from state $i$

Infinitesimal Generator

Jumps: $i \to i+1$ (birth), $i \to i-1$ (death).

$q_i = \lambda_i + \mu_i$ (exit rate).

Stationary Distribution

$\pi_0 = \left(1 + \sum_{k=1}^\infty \prod_{j=0}^{k-1} \frac{\lambda_j}{\mu_{j+1}} \right)^{-1}$

$\pi_k = \pi_0 \prod_{j=0}^{k-1} \frac{\lambda_j}{\mu_{j+1}}$

Applications

Population growth models.

Queueing systems.

Epidemic models.

11. Queueing Theory

Kendall Notation

A/B/c: Arrival/Service/Servers.

M = Markovian (Poisson), D = Deterministic, G = General.

M/M/1 Queue

$\rho = \lambda/\mu$ (utilization)

Stable if $\rho < 1$

$\pi_n = (1-\rho)\rho^n$

M/M/1 Metrics

$L = \frac{\rho}{1-\rho}$ (avg in system)

$W = \frac{1}{\mu - \lambda}$ (avg wait)

$L_q = \frac{\rho^2}{1-\rho}$ (in queue)

Little's Law

$L = \lambda W$

Holds for any stable system.

12. M/M/c Queue

Setup

$c$ parallel servers.

$\rho = \lambda/(c\mu)$

Stable if $\rho < 1$.

Probability $P_0$

$P_0 = \left[ \sum_{n=0}^{c-1} \frac{(c\rho)^n}{n!} + \frac{(c\rho)^c}{c!(1-\rho)} \right]^{-1}$

Erlang C Formula

$P_w = \frac{(c\rho)^c}{c!(1-\rho)} \cdot P_0$

Prob of waiting.

Avg Wait (conditional)

$W_q | \text{wait} = \frac{1}{c\mu(1-\rho)}$

13. Renewal Theory

Renewal Process

$\{X_i\}$ iid positive random variables.

$S_n = X_1 + \cdots + X_n$ (n-th renewal).

$N(t) = \max\{n: S_n \leq t\}$ (renewal count).

Renewal Function

$m(t) = E[N(t)]$

Expected renewals by time $t$.

Elementary Renewal Thm

$\lim_{t \to \infty} \frac{N(t)}{t} = \frac{1}{E[X_1]}$ a.s.

Renewal Reward Thm

$\lim_{t \to \infty} \frac{R(t)}{t} = \frac{E[\text{reward/cycle}]}{E[\text{cycle length}]}$

Generalizes law of large numbers.

14. Martingales

Definition

$E[X_{n+1}|\mathcal{F}_n] = X_n$ a.s.

Fair game: future value = current value.

Submartingale

$E[X_{n+1}|\mathcal{F}_n] \geq X_n$

Expected to increase.

Supermartingale

$E[X_{n+1}|\mathcal{F}_n] \leq X_n$

Expected to decrease.

Examples

Simple random walk on $\mathbb{Z}$.

Stock prices in efficient market.

$X_n = B(n)$ (discretized BM).

Key: $E[X_n] = E[X_0]$ for martingales.

15. Brownian Motion

Definition $B(t)$

1. $B(0) = 0$.

2. Independent increments.

3. $B(t) - B(s) \sim N(0, t-s)$.

4. Continuous paths.

Properties

$E[B(t)] = 0$, $\text{Var}(B(t)) = t$

$\text{Cov}(B(s), B(t)) = \min(s,t)$

Martingale: $E[B(t)|\mathcal{F}_s] = B(s)$

Scaling

$B(ct) \stackrel{d}{=} \sqrt{c} B(t)$

Self-similar process.

Path Properties

Continuous but nowhere differentiable.

Unbounded variation on $[0,T]$.

Quadratic variation: $[B]_t = t$.

Fundamental in continuous-time finance.

16. Itô's Lemma

Itô Process

$dX_t = \mu(t) dt + \sigma(t) dB_t$

Drift $\mu(t)$ and volatility $\sigma(t)$.

Itô's Lemma

$df(X_t) = f'(X_t) dX_t + \frac{1}{2}f''(X_t) (dX_t)^2$

$(dB_t)^2 = dt$, $dt \cdot dB_t = 0$.

Expansion

$df = \left(f'(X_t)\mu + \frac{1}{2}f''(X_t)\sigma^2\right) dt + f'(X_t)\sigma \, dB_t$

Used to transform SDEs.

Applications

Black-Scholes PDE derivation.

Change of variables in SDEs.

Pricing derivatives.

Core tool of stochastic calculus.

17. Finance Apps

Geometric Brownian Motion

$dS_t = \mu S_t dt + \sigma S_t dB_t$

Standard stock price model.

Black-Scholes Formula

$C = S_0 N(d_1) - K e^{-rT} N(d_2)$

$d_1 = \frac{\ln(S_0/K) + (r+\sigma^2/2)T}{\sigma\sqrt{T}}$

$d_2 = d_1 - \sigma\sqrt{T}$

Greeks

$\Delta$: price sensitivity.

$\Gamma$: delta sensitivity.

$\nu$: volatility sensitivity.

$\Theta$: time decay.

18. Biology Apps

Population Growth

Birth-death processes model populations.

Branching processes: extinction probability.

Gillespie Algorithm

Simulate stochastic reactions.

Exponential waiting times between events.

SIS/SIR Epidemiology

Susceptible-Infected models.

Birth-death process transitions.

Neuron Firing

Poisson point process arrivals.

Integrate-and-fire model dynamics.

Stochastic effects crucial for rare events.

19. Network Apps

Queue Networks

Jackson networks: product form.

Routing probabilities between queues.

Information Diffusion

Poisson arrivals of information.

Branching process for cascade size.

Random Graphs

Erdős-Rényi model ($G_{n,p}$).

Percolation theory basics.

Markov Chain Monte Carlo

Metropolis-Hastings algorithm.

Sample from complex distributions.

Simulation of network dynamics.

20. Convergence

Law of Large Numbers

$\frac{1}{n}\sum_{i=1}^n X_i \xrightarrow{a.s.} E[X]$

SLLN for iid $X_i$.

Central Limit Theorem

$\frac{\sum X_i - n\mu}{\sqrt{n}\sigma} \xrightarrow{d} N(0,1)$

Joint convergence of aggregates.

Donsker's Theorem

Partial sums process $\to$ Brownian Motion

Functional CLT.

Convergence Modes

Almost sure ($a.s.$).

In probability ($\xrightarrow{P}$).

In distribution ($\xrightarrow{d}$).

$a.s. \Rightarrow P \Rightarrow d$

21. Key Inequalities

Markov Inequality

$P(X \geq a) \leq \frac{E[X]}{a}$ for $X \geq 0$

Chebyshev Inequality

$P(|X - \mu| \geq k\sigma) \leq \frac{1}{k^2}$

Chernoff Bound

$P(X \geq a) \leq e^{-ta} E[e^{tX}]$ for $t > 0$

Doob's Maximal Inequality

$P(\max_{k \leq n} |X_k| \geq a) \leq \frac{E[|X_n|^p]}{a^p}$

Martingale Concentration

Azuma's inequality for bounded increments.

Essential for tail bounds.

22. Summary Formulas

Exponential Distribution

$P(X > t) = e^{-\lambda t}$

$E[X] = 1/\lambda$, $\text{Var}(X) = 1/\lambda^2$

Gaussian Integral

$\int_{-\infty}^\infty e^{-x^2} dx = \sqrt{\pi}$

Laplace Transform

$\mathcal{L}_X(s) = E[e^{-sX}]$

Uniquely determines distribution.

Generating Function

$G(z) = E[z^X] = \sum P(X=k) z^k$

For discrete random variables.

Tools for exact computation.