Stochastic Processes

A stochastic process is a family of random variables indexed by time. The subject is organized by which dependence structure you keep: Markov chains keep “the future depends only on the present” (discrete time, then continuous); renewal theory keeps only “iid gaps between events”; martingales keep only “fair given the past”; Brownian motion is what survives every scaling limit. Two computational moves do most of the work in the entire subject: first-step analysis (condition on the first step, let the Markov property restart the clock) and optional stopping (a fair game stays fair at a well-behaved random time). The recurring destination: long-run behavior — stationary distributions, limit theorems, and the LLN/CLT shadows each structure casts.

1. Markov chains — the object

• A (discrete-time) Markov chain is a process $(X_n)$ on a countable state space $S$ with the Markov property:

$P(X_{n+1} = y \mid X_n = x, X_{n-1} = x_{n-1}, \ldots, X_0 = x_0) = P(X_{n+1} = y \mid X_n = x)$

The future is independent of the past given the present. The present state is a sufficient statistic for prediction.

• Time homogeneous: transition probabilities don’t depend on $n$. Then the chain is fully specified by two objects: the transition matrix $P(x,y) = P(X_1 = y \mid X_0 = x)$ (rows are probability distributions: entries ≥ 0, rows sum to 1) and the initial distribution $\pi^0$.
• Build the joint distribution by peeling one step at a time with the Markov property:

$P(X_0 = x_0, \ldots, X_n = x_n) = \pi^0(x_0)\,P(x_0, x_1)\,P(x_1, x_2)\cdots P(x_{n-1}, x_n)$

• n-step transitions are matrix powers. Condition on the intermediate state (Chapman–Kolmogorov):

$p^{m+n}(x, y) = \sum_k p^m(x, k)\,p^n(k, y) \;\iff\; P^{(m+n)} = P^{(m)}P^{(n)} \;\Rightarrow\; P^{(n)} = P^n$

and distributions evolve as a row vector hitting the matrix: $\pi^n = \pi^0 P^n$. This is track 2’s “powers and dynamics” section with a stochastic matrix — eigenvalues run the long-run show, and $\lambda = 1$ is always present.

• Numeric anchor — the 2-state chain $P = \begin{bmatrix} 1-a & a \\ b & 1-b \end{bmatrix}$:

$P^n = \frac{1}{a+b}\begin{bmatrix} b & a \\ b & a \end{bmatrix} + \frac{(1-a-b)^n}{a+b}\begin{bmatrix} a & -a \\ -b & b \end{bmatrix} \;\xrightarrow{n \to \infty}\; \begin{bmatrix} \frac{b}{a+b} & \frac{a}{a+b} \\ \frac{b}{a+b} & \frac{a}{a+b} \end{bmatrix}$

Identical rows in the limit: the chain forgets where it started. The decaying term is the second eigenvalue $1 - a - b$ doing exactly what track 2’s spectral-gap implication promised.

• The cast of examples to keep loaded: random walk on $Z$ (steps ±1), gambler’s ruin (absorbing ends), Ehrenfest urns (repelling ends), simple random walk on a graph ($p(x,y) = 1/\deg(x)$), success runs, iid sequences (all rows equal), branching processes. A warning from the deterministic-square example: a function of a Markov chain need not be Markov — lumping states can manufacture memory.

Core competency set

• State the Markov property and what “time homogeneous” adds; specify a chain by $(P, \pi^0)$.
• Derive $P^{(n)} = P^n$ from Chapman–Kolmogorov and evolve $\pi^n = \pi^0P^n$.
• Read the 2-state limit as eigenvalue decay; give an example where a function of a chain isn’t Markov.

2. First-step analysis — the workhorse

The single most-used computational move in the subject. To compute any “until” quantity — hitting probabilities, expected absorption times — condition on the first step; the Markov property restarts the chain from the new state; you get linear equations.

Set-up: hitting time $V_A = \min\{n \geq 0: X_n \in A\}$, return time $T_A = \min\{n \geq 1: X_n \in A\}$ (they differ only when you start in $A$). A state with $P(x,x) = 1$ is absorbing.

Worked anchor — gambler’s ruin with $p = 0.4$ up, $0.6$ down, states $\{0, \ldots, 4\}$, absorbing at 0 and 4. Let $h(x) = P_x(V_4 < V_0)$ — the probability of winning from $x$:

• Boundary values are free: $h(0) = 0$, $h(4) = 1$.
• Condition on the first step from state 1:

$h(1) = P(X_1 = 0 \mid X_0 = 1)\,h(0) + P(X_1 = 2 \mid X_0 = 1)\,h(2) = 0.6\,(0) + 0.4\,h(2)$

• Same at every interior state: $h(2) = 0.6\,h(1) + 0.4\,h(3)$, $h(3) = 0.6\,h(2) + 0.4$. Three linear equations; solving gives

$h(1) = \tfrac{8}{65}, \qquad h(2) = \tfrac{20}{65}, \qquad h(3) = \tfrac{38}{65}$

• Expected absorption time $g(x) = E_xV_{\{0,4\}}$ — identical move plus “+1” for the step taken:

$g(1) = 1 + 0.6\,g(0) + 0.4\,g(2), \quad g(0) = g(4) = 0, \ldots \;\Rightarrow\; g(1) = \tfrac{33}{13},\ g(2) = \tfrac{50}{13},\ g(3) = \tfrac{43}{13}$

• Patterns in coin flips, same machine. To find $E(\text{flips until HTH})$ with a fair coin, the state must capture current progress through the pattern — the length of the longest suffix of flips so far that is a prefix of HTH:
  • state 0: no usable progress; state 1: have H; state 2: have HT; state 3: HTH complete (absorbing).
  • Transitions read off “what does the next flip do to the longest matching prefix”: from 1 (H) a tail gives HT (state 2), a head keeps H (state 1); from 2 (HT) a head completes HTH (state 3), a tail drops to T which matches nothing useful (state 0).
• Let $g(x) = E_x(\text{flips to reach state 3})$, so $g(3) = 0$ and each interior state pays $+1$ for the flip taken:

$g(0) = 1 + \tfrac12 g(1) + \tfrac12 g(0), \quad g(1) = 1 + \tfrac12 g(1) + \tfrac12 g(2), \quad g(2) = 1 + \tfrac12 g(0)$

• Solve by elimination. Clear the self-loop in each of the first two (move the $\tfrac12 g$ term left, double):

$g(0) = 2 + g(1), \qquad g(1) = 2 + g(2)$

Chain them down to $g(2)$, then substitute the $g(2)$ equation:

$g(0) = 4 + g(2) = 4 + \big(1 + \tfrac12 g(0)\big) = 5 + \tfrac12 g(0)$

Collect $g(0)$: $\tfrac12 g(0) = 5$, so $\boxed{E = g(0) = 10}$. Designing the right state space is the skill — the state must capture exactly what the future needs.

Implications

• Absorption probabilities $U_{ik}$ and expected accumulated rewards before absorption all satisfy the same template $u(x) = (\text{immediate}) + \sum_y P(x,y)u(y)$ — one linear solve, many questions.
• The same equations return in continuous time with the generator (§9) and for Brownian motion via martingales (§12) — learn the move once.

Core competency set

• Set up and solve $h$ (hitting probability) and $g$ (expected time) systems from a blank page, boundary conditions first.
• Build a pattern-tracking state space (HTH) and explain why state design is the real work.

3. Stopping times and the strong Markov property

• A random time $T$ is a stopping time if for every $n$, the event $\{T \leq n\}$ is determined by $X_0, \ldots, X_n$ — you can tell when it happens that it happened, no future peeking. Gambling intuition: a quitting rule you could actually implement.
• Examples: hitting times, return times, $k$th return times. Non-example: the last visit to a set ($L_A = \sup\{n: X_n \in A\}$) — knowing it’s the last visit requires the future.
• Strong Markov property: the chain restarts not just at fixed times but at stopping times — conditional on $T < \infty$ and $X_T = x$, the process $(X_{T+m})_{m \geq 0}$ is a fresh copy of the chain started at $x$, independent of the pre-$T$ past.
• What it buys, immediately: successive return times to a state have iid gaps. Starting at $y$, each return restarts the chain at $y$, so

$P_y(T_y^{(k)} < \infty) = \rho_{yy}^k \qquad \text{where } \rho_{yy} = P_y(T_y < \infty)$

— returning $k$ times is just returning once, $k$ independent times. This single identity drives the entire classification theory of §4.

Implications — what restart-the-clock buys:

• The path decomposes into iid excursions between returns. That one consequence powers the classification theory (§4), the frequency identity $\pi(y) = \frac{1}{E_yT_y}$ (§5), and the ergodic theorem’s LLN-for-chains (§6).
• “You can’t peek” is the same license behind Wald’s equation (§10) and optional stopping (§11) — random times behave like fixed times precisely when the decision to stop never uses the future.

Core competency set

• Define stopping time; classify hitting/return/last-visit times correctly.
• State the strong Markov property and derive $\rho_{yy}^k$ from it.

4. Recurrence and transience — classifying states

• Recurrent: $\rho_{yy} = 1$ — the chain returns, hence (by §3) returns infinitely often. Transient: $\rho_{yy} < 1$ — each return is a coin flip that eventually fails; the number of visits $1 + N_y$ is Geometric, and

$E_yN_y = \frac{\rho_{yy}}{1 - \rho_{yy}} = \sum_{n \geq 1} p^n(y,y)$

So the practical test: $y$ is recurrent ⟺ $\sum_n p^n(y,y) = \infty$ (expected visits infinite).

• Communication: $x \to y$ if $\rho_{xy} > 0$; a set is closed if you can’t leave, irreducible if everything communicates with everything.
• The structural theorems, with their one-line mechanisms:
  • If $x \to y$ but $y \not\to x$ with certainty ($\rho_{yx} < 1$), then $x$ is transient — there’s a positive-probability escape route that never comes back.
  • Recurrence spreads through communication: $x$ recurrent and $x \to y$ ⟹ $y$ recurrent. Use the test recurrent $\iff \sum_n p^n(y,y) = \infty$, so the goal is to show returns to $y$ sum to infinity. Since $x$ and $y$ communicate, pick a $j$-step path $y \to x$ and an $l$-step path $x \to y$, both of positive probability: $p^j(y,x) > 0$, $p^l(x,y) > 0$. One way to return $y \to y$ in $j+k+l$ steps is to run $y \to x$ ($j$ steps), loop $x \to x$ ($k$ steps), then $x \to y$ ($l$ steps); keeping only that single route lower-bounds the full transition (Chapman–Kolmogorov sums over all intermediate paths):

$p^{j+k+l}(y,y) \;\geq\; p^j(y,x)\,p^k(x,x)\,p^l(x,y)$

Sum over $k$ and pull the two constants out of the sum:

$\sum_k p^{j+k+l}(y,y) \;\geq\; p^j(y,x)\Big(\sum_k p^k(x,x)\Big)p^l(x,y)$

$x$ is recurrent, so $\sum_k p^k(x,x) = \infty$; multiplied by the two positive constants the right side is $\infty$. The left side is a sub-series of $\sum_n p^n(y,y)$, so that diverges too — $y$ is recurrent.

• A finite closed set $C$ must contain a recurrent state. Suppose not — every state of $C$ is transient. A transient state $y$ has finite expected visits, $E_x N_y < \infty$ (the visit count is Geometric, §4 above), and $C$ is finite, so a finite sum of finite terms is finite:

$\sum_{y \in C} E_x N_y < \infty$

But $C$ is closed: the chain never leaves, so it takes infinitely many steps each landing somewhere in $C$, making total visits infinite:

$\sum_{y \in C} N_y = \infty \;\Rightarrow\; \sum_{y \in C} E_x N_y = \infty$

The two displays contradict, so some state of $C$ must be recurrent.

• Theorem: finite + closed + irreducible ⟹ all states recurrent.
• Decomposition theorem: any finite state space splits as $S = T \cup R_1 \cup \cdots \cup R_k$ — transient states plus closed irreducible recurrent classes. The chain falls out of $T$ into one of the $R_j$ and then lives there. (Gambler’s ruin: $T = \{1,\ldots,N-1\}$, $R_1 = \{0\}$, $R_2 = \{N\}$.)

The picture to hold (and redraw cold): the state space as islands — a transient region $T$ with one-way arrows leaking out of it into closed recurrent islands $R_1, \ldots, R_k$. Inside each island everything communicates; between islands, nothing. Every finite chain’s long-run story is: fall out of $T$, get trapped on one island, circulate there forever.

• Recurrence splits further by how long return takes: positive recurrent if $E_yT_y < \infty$, null recurrent if recurrent but $E_yT_y = \infty$.
• Worked trichotomy — the reflecting random walk on $\{0, 1, 2, \ldots\}$ (up with $p$, down with $1-p$, reflected at 0):

$p$	behavior	why
$p < 1/2$	positive recurrent	drift home; stationary distribution exists, $\pi(x) \propto (\frac{p}{1-p})^x$
$p = 1/2$	null recurrent	returns with probability 1 (Gambler’s-ruin limit $P_x(V_0 < V_N) = 1 - \frac{x}{N} \to 1$) but $E_0T_0 = \infty$
$p > 1/2$	transient	escape probability $P_1(T_0 = \infty) = 1 - \frac{1-p}{p} > 0$

Null recurrence is the genuinely new phenomenon infinite state spaces allow: certain to return, but on a timescale with no mean.

Core competency set

• Define recurrent/transient three equivalent ways ($\rho_{yy}$, infinitely-many-visits, $\sum p^n(y,y)$).
• Prove the finite-closed-irreducible theorem’s two lemmas in skeleton form.
• Reproduce the reflecting-walk trichotomy with the reason for each regime.

5. Stationary distributions

• $\pi$ is stationary if $\pi P = \pi$ — run the chain one step from $\pi$ and the distribution is unchanged. In track 2 language: $\pi$ is a left eigenvector of $P$ with eigenvalue 1, which a stochastic matrix always has.
• Detailed balance (stronger, easier to check): $\pi(x)p(x,y) = \pi(y)p(y,x)$ for all pairs. Sand picture: $\pi$ is sand piled on states, $p$ moves it; detailed balance says every pair of states exchanges equal sand, so certainly each state’s total is conserved. DBC ⟹ stationary in one line:

$\sum_x \pi(x)p(x,y) = \sum_x \pi(y)p(y,x) = \pi(y)\sum_x p(y,x) = \pi(y)$

• Where DBC is the fast route:
  • Birth–death chains (transitions only to neighbors — Ehrenfest, gambler’s ruin, reflecting RW): only adjacent pairs need checking. Ehrenfest with $N$ balls: $\pi(x) = 2^{-N}\binom{N}{x}$ — binomial, concentrated at $N/2$, the statistical-mechanics equilibrium.
  • SRW on a graph: guess $\pi(x) = c\deg(x)$; for an edge $x \sim y$, $\pi(x)p(x,y) = c\deg(x)\frac{1}{\deg(x)} = c$, symmetric in $x, y$ ✓. Normalize: $c = \frac{1}{2|E|}$. Time spent at a vertex ∝ its degree. Regular graph ⟹ uniform.
  • Doubly stochastic $P$ (columns also sum to 1) ⟹ uniform $\pi(x) = \frac{1}{N}$.
• Computing $\pi$ in general is linear algebra: solve $\pi(P - I) = 0$ with $\sum\pi = 1$ (drop one redundant equation, substitute the normalization). Numeric anchor — social mobility $P = \begin{bmatrix} .7 & .2 & .1 \\ .3 & .5 & .2 \\ .2 & .4 & .4 \end{bmatrix}$ gives $\pi = (\frac{22}{47}, \frac{16}{47}, \frac{9}{47})$.
• The frequency identity — what $\pi$ is: for irreducible recurrent chains,

$\pi(y) = \frac{1}{E_yT_y}$

Proof idea: returns to $y$ have iid gaps (strong Markov), so by the SLLN the long-run fraction of time at $y$ is one visit per $E_yT_y$ steps — a period’s reciprocal is a frequency. This also shows $\pi$ is unique (the formula has no free choices), and ties positive recurrence to $\pi(y) > 0$.

• Reversibility: run a stationary chain backwards and you get a Markov chain with $\hat{p}(x,y) = \frac{\pi(y)p(y,x)}{\pi(x)}$; DBC ⟺ the reversed chain has the same transition probabilities — the movie looks identical played backwards.

Core competency set

• Verify and exploit detailed balance; derive $\pi \propto \deg$ for SRW on a graph and uniform for doubly stochastic.
• Solve $\pi P = \pi$ by hand for a 3-state chain.
• State and explain $\pi(y) = 1/E_yT_y$ via iid return gaps.

6. Convergence, ergodicity, and MCMC

Two distinct questions about long-run behavior — keep them separate:

1. Does $\pi^n \to \pi$? Needs more than a stationary distribution. The flip-flop counterexample $P = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}$ has $\pi = (\frac{1}{2}, \frac{1}{2})$ but $\pi^n$ alternates forever — periodicity is the obstruction. Period of $x$ = gcd of possible return times; aperiodic = period 1. Convergence theorem: irreducible + aperiodic + stationary distribution exists ⟹ $p^n(x,y) \to \pi(y)$ for all $x$ — the chain forgets its start.
2. Do time averages converge? Needs less: Ergodic theorem — irreducible + stationary $\pi$ (no aperiodicity needed!):

$\frac{1}{n}\sum_{m=1}^n f(X_m) \xrightarrow{a.s.} \sum_x f(x)\pi(x) = E_\pi[f]$

An LLN for dependent, Markov data. With $f = \mathbf{1}_A$: the fraction of time in $A$ converges to $\pi(A)$ — even for the flip-flop chain, which never converges in distribution but spends exactly half its time in each state.

MCMC — the payoff. Goal: compute $E_\pi[f]$ for a $\pi$ too complicated to sum over (often known only up to a normalizing constant). Idea: build an irreducible chain whose stationary distribution is $\pi$, run it, and let the ergodic theorem average for you.

Metropolis–Hastings: propose moves from any convenient $Q(x,y)$, accept with probability

$R(x,y) = \min\left\{\frac{\pi(y)Q(y,x)}{\pi(x)Q(x,y)},\ 1\right\}$

(else stay put). The acceptance ratio is engineered to force detailed balance — check: WLOG $\pi(y)Q(y,x) > \pi(x)Q(x,y)$; then

$\pi(x)p(x,y) = \pi(x)Q(x,y)\cdot 1 \cdot \frac{\pi(y)Q(y,x)}{\pi(y)Q(y,x)} = \pi(y)Q(y,x)R(y,x) = \pi(y)p(y,x)$

• The killer feature: only the ratio $\frac{\pi(y)}{\pi(x)}$ appears — normalizing constants cancel. For the Ising model, $\pi_\beta(\sigma) = \frac{1}{Z(\beta)}e^{-\beta H(\sigma)}$ on $2^{|V|}$ configurations: $Z$ is hopeless to compute, but flip one spin and the ratio is a local quantity $e^{-2\beta\sum_{j \sim i}\sigma(i)\sigma(j)}$. This is why MCMC runs all of Bayesian computation (track 7) and statistical physics.
• Designing $Q$ is the art; mixing time (how long until the ergodic average is trustworthy) is the science — and it’s governed by the spectral gap $1 - |\lambda_2|$ of the transition matrix, exactly track 2’s convergence-rate implication made load-bearing. Famous instance: seven riffle shuffles ≈ mix a deck across its 52! states.

Core competency set

• Separate the two convergence questions; produce the flip-flop counterexample and what survives it (time averages).
• State both theorems with exact hypotheses (where aperiodicity is and isn’t needed).
• Derive M–H’s detailed balance and explain why normalizing constants cancel.

7. Branching processes — extinction by generating function

• Population model: each individual independently has children with offspring pmf $f$; $X_{n+1} = \sum_{m=1}^{X_n} Y_{n,m}$ (a random sum — track 1’s tower machinery). Let $\mu = E(Y)$.
• The mean evolves geometrically — condition on the current generation:

$E(X_{n+1} \mid X_n) = \mu X_n \;\Rightarrow\; E(X_n) = \mu^n E(X_0)$

• Extinction probability $\rho = P_1(T_0 < \infty)$. Two soft cases first: $\mu < 1$ ⟹ extinction certain, by Markov’s inequality (track 1’s tail bound, cashed in):

$P(X_n \geq 1) \leq E(X_n) = \mu^n \to 0$

And $f(0) = 0$ ⟹ no extinction, trivially.

• The general tool is the generating function $\phi(r) = \sum_k r^kf(k) = E(r^Y)$, with $\phi(1) = 1$, $\phi(0) = f(0)$, $\phi'(1) = \mu$, $\phi$ increasing and convex on $[0,1]$.
• First-step analysis on the family tree: for the line to die out, each of the $k$ first-generation children’s independent subtrees must die out — each with the same probability $\rho$:

$\rho = \sum_k f(k)\,\rho^k = \phi(\rho)$

Extinction probability is a fixed point of $\phi$. Iterating $\rho_n = \phi(\rho_{n-1})$ from $\rho_1 = f(0)$ climbs monotonically to the smallest fixed point in $[0,1]$ — that’s the theorem: $\rho$ = smallest solution of $\phi(r) = r$.

• Geometry: $\phi$ is convex, anchored at $(1,1)$ with slope $\mu$ there. If $\mu \leq 1$ the curve stays above the diagonal until 1 — only fixed point is 1, extinction certain (even at $\mu = 1$, the critical case). If $\mu > 1$ the curve dips below the diagonal — a second fixed point $\rho < 1$ appears, survival possible. This is the picture to redraw cold: the unit square, the diagonal $y = r$, the convex curve $\phi$ from $(0, f(0))$ up to $(1,1)$, with the slope at 1 (= $\mu$) deciding whether it crosses the diagonal early; iterating $\rho_n = \phi(\rho_{n-1})$ staircases up from $f(0)$ into the first crossing.
• Numeric anchor: $f(0) = \frac{1}{4}, f(1) = \frac{1}{4}, f(2) = \frac{1}{2}$ ⟹ $\mu = \frac{5}{4} > 1$;

$\phi(r) = \tfrac{1}{4} + \tfrac{1}{4}r + \tfrac{1}{2}r^2 = r \;\Rightarrow\; r \in \{\tfrac{1}{2}, 1\} \;\Rightarrow\; \rho = \tfrac{1}{2}$

(1 is always a root — use it to factor.) Coin-flip odds of a lineage lasting forever despite exponential expected growth.

Core competency set

• Derive $E(X_n) = \mu^n$ and the Markov-inequality argument for $\mu < 1$.
• Derive $\rho = \phi(\rho)$ by first-step analysis on subtrees; state and use “smallest fixed point”; sketch the convexity picture for the three regimes $\mu < 1, = 1, > 1$.

8. The Poisson process — exponential clocks

The continuous-time foundation. Everything flows from the memorylessness of the exponential (track 1’s characterization): $P(T > s + t \mid T > s) = P(T > t)$.

• Exponential races — the engine of all continuous-time constructions. For independent $T_i \sim \text{Exp}(\lambda_i)$, $S = \min_i T_i$, $I = \arg\min$:

$S \sim \text{Exp}(\lambda_1 + \cdots + \lambda_n), \qquad P(I = i) = \frac{\lambda_i}{\lambda_1 + \cdots + \lambda_n}, \qquad S \perp I$

Derivation of the first (the rate-adds fact). The minimum exceeds $t$ exactly when every clock does:

$P(S > t) = P(T_1 > t, \ldots, T_n > t)$

The $T_i$ are independent, so the joint survival probability factors:

$P(S > t) = \prod_i P(T_i > t) = \prod_i e^{-\lambda_i t}$

Collect exponents ($\prod_i e^{-a_i} = e^{-\sum_i a_i}$):

$P(S > t) = e^{-(\sum_i \lambda_i)\,t}$

which is the survival function of $\text{Exp}(\sum_i \lambda_i)$. Rates add; the winner is chosen proportional to rate; who wins tells you nothing about when.

• Poisson process $PP(\lambda)$, two equivalent descriptions (the equivalence is the theorem):
  1. Axioms: $N(0) = 0$; $N(t+s) - N(s) \sim \text{Pois}(\lambda t)$; increments over disjoint intervals independent.
  2. Construction: arrival gaps $\tau_1, \tau_2, \ldots$ iid $\text{Exp}(\lambda)$, $T_n = \sum_1^n \tau_i \sim \text{Gamma}(n, \lambda)$, $N(t) = \max\{n: T_n \leq t\}$. This is track 1’s “one process, three slices” (Pois counts / Exp first wait / Gamma $n$th wait) — now with the machinery to prove it. Memorylessness is what makes the restart-at-$s$ argument work: the time from $s$ to the next arrival is $\text{Exp}(\lambda)$ no matter how long you’ve waited.
• The closure operations, each with its one-line reason:
  • Superposition: independent $PP(\lambda_k)$ summed ⟹ $PP(\sum\lambda_k)$ — exponential races at every arrival.
  • Thinning: label each arrival type $k$ with probability $p_k$ independently ⟹ the type-$k$ processes are independent $PP(\lambda p_k)$ — the multinomial split of a Poisson count factors exactly.
  • Conditioning: given $N(t) = n$, the arrival times are distributed as $n$ iid Uniform$[0,t]$ points, sorted. (So given $N(t) = n$, $N(s) \sim \text{Bin}(n, \frac{s}{t})$.) Poisson arrivals carry no clustering information beyond their count.
  • Compound: $S(t) = \sum_{i=1}^{N(t)} Y_i$ (random sums again): $E[S] = \lambda t\,E[Y]$, $\operatorname{Var}(S) = \lambda t\,E[Y^2]$.
• Numeric anchor (races as thinning): trucks $PP(\lambda)$, cars $PP(\mu)$. Each arrival is independently a truck with probability $\frac{\lambda}{\lambda+\mu}$, so P(6 trucks before 4 cars) = P(≥6 of the first 9 arrivals are trucks) $= \sum_{k=6}^9\binom{9}{k}\big(\frac{\lambda}{\lambda+\mu}\big)^k\big(\frac{\mu}{\lambda+\mu}\big)^{9-k}$ — a continuous-time question collapsed to a binomial.

Core competency set

• Prove the three parts of exponential races; state both PP descriptions and why memorylessness links them.
• Apply superposition/thinning/conditioning, including the uniform-order-statistics fact.
• Convert a “race” question to a binomial via thinning.

9. Continuous-time Markov chains

• Same Markov property, continuous index. Specified by jump rates $q(x,y) = \lim_{t \to 0}\frac{p_t(x,y)}{t}$ — derivatives of transition probabilities at 0.
• Mechanics of the chain (the construction): sitting at $x$, every destination $y$ runs an independent $\text{Exp}(q(x,y))$ clock. The exponential race (§8) decides: leave at rate $\lambda(x) = \sum_{y \neq x} q(x,y)$ after an $\text{Exp}(\lambda(x))$ wait, jump to $y$ with probability $R(x,y) = \frac{q(x,y)}{\lambda(x)}$. The jump sequence alone is a discrete chain (the embedded chain with matrix $R$); the waits decorate it with continuous time.
• The generator packages everything: $Q(x,y) = q(x,y)$ off-diagonal, $Q(x,x) = -\lambda(x)$ (rows sum to 0). Then transition probabilities solve the Kolmogorov equations and exponentiate the generator —

$p_t' = Qp_t = p_tQ, \qquad p_t = e^{Qt}$

track 2’s matrix exponential and $f(A) = Sf(\Lambda)S^{-1}$, cashed in directly.

• Stationary distribution: $\pi$ stationary ⟺ $\pi Q = 0$. Written out: $\sum_{z \neq y}\pi(z)q(z,y) = \pi(y)\lambda(y)$ — rate in = rate out at every state, the continuous balance equation.
• No aperiodicity needed: exponential waits can’t synchronize, so irreducible + stationary ⟹ $p_t(x,y) \to \pi(y)$. Periodicity was a discrete-time disease.
• Numeric anchor — weather: sunny $\text{Exp}(1/3)$ → cloudy $\text{Exp}(1/4)$ → rain $\text{Exp}(1)$ → sunny. $Q = \begin{bmatrix} -1/3 & 1/3 & 0 \\ 0 & -1/4 & 1/4 \\ 1 & 0 & -1 \end{bmatrix}$; solving $\pi Q = 0$ with normalization: $\pi = (\frac{3}{8}, \frac{4}{8}, \frac{1}{8})$ — exactly the mean waits $(3, 4, 1)$ over the cycle length 8. Time-share = waiting time share.
• Standard models as rate bookkeeping: M/M/k queue — arrivals $q(n, n+1) = \lambda$; services race, $q(n, n-1) = \min(n, k)\mu$. Continuous branching — births $q(n, n+1) = \lambda n$, deaths $q(n, n-1) = \mu n$ ($n$ independent clocks each).
• Exit problems run on the embedded chain / generator submatrix: $h = -Q_C^{-1}v$ — first-step analysis again, in matrix clothing.

Core competency set

• Construct a CTMC from rates via exponential races; extract $\lambda(x)$ and the embedded $R$.
• Write $Q$, state $p_t = e^{Qt}$, and solve $\pi Q = 0$ reading it as rate-in = rate-out (weather example from scratch).
• Explain why aperiodicity disappears in continuous time.

10. Renewal theory — only iid gaps

Drop the exponential: gaps $X_1, X_2, \ldots$ iid from any nonnegative distribution, arrivals $S_n = \sum_1^n X_i$, count $N(t) = \sup\{n: S_n \leq t\}$, $\mu = E(X_1)$. The Poisson process is the special (memoryless) case. The pivot identity for everything: $\{N(t) \geq n\} = \{S_n \leq t\}$.

• Rate: with probability 1,

$\frac{N(t)}{t} \to \frac{1}{\mu}$

Proof skeleton — sandwich $t$ between the arrivals bracketing it, then let the SLLN drive. By the definition of $N(t)$, the $N(t)$-th arrival has happened by $t$ and the next overshoots:

$S_{N(t)} \;\leq\; t \;<\; S_{N(t)+1}$

Divide through by $N(t)$:

$\frac{S_{N(t)}}{N(t)} \;\leq\; \frac{t}{N(t)} \;<\; \frac{S_{N(t)+1}}{N(t)}$

As $t \to \infty$, $N(t) \to \infty$, and both ends $\to \mu$: the left is $S_n/n \xrightarrow{a.s.} \mu$ (SLLN), the right is $\tfrac{S_{n+1}}{n+1}\cdot\tfrac{n+1}{n} \to \mu\cdot 1$. The middle is squeezed:

$\frac{t}{N(t)} \to \mu \;\Rightarrow\; \frac{N(t)}{t} \to \frac{1}{\mu}$

• Wald’s equation: $N$ a stopping time for iid $X_i$, $E(N) < \infty$:

$E\Big[\sum_{i=1}^N X_i\Big] = E(N)\,E(X_1)$

The proof’s one trick, displayed. Rewrite the random-length sum as an infinite sum of censored terms:

$\sum_{i=1}^N X_i = \sum_{n=1}^\infty X_n\,\mathbf{1}\{N \geq n\}$

The event $\{N \geq n\} = \{N \leq n-1\}^c$ is determined by $X_1, \ldots, X_{n-1}$ — the past — hence independent of $X_n$. So expectations factor term by term:

$E\Big[\sum_{i=1}^N X_i\Big] = \sum_{n=1}^\infty E[X_n]\,P(N \geq n) = E(X_1)\sum_{n=1}^\infty P(N \geq n) = E(X_1)\,E(N)$

(the last step is the tail-sum formula for nonnegative integer RVs). Stopping times can’t peek — that is the entire theorem. Counterexample when the condition fails: the symmetric walk stopped at its first hit of 1 has $E(S_N) = 1 \neq 0 = E(N)E(X_1)$ — here $E(N) = \infty$ is the hypothesis that breaks.

• Elementary renewal theorem: $\frac{m(t)}{t} \to \frac{1}{\mu}$ for $m(t) = E[N(t)]$ (needs its own proof — convergence a.s. doesn’t give convergence of expectations; Wald + truncation does it). Blackwell sharpens: far from the origin, expected renewals in $(t, t+a]$ ≈ $\frac{a}{\mu}$ — every renewal process is asymptotically Poisson-like in its mean. The picture to hold (and redraw cold): the renewal staircase — $N(t)$ stepping up by 1 at each arrival $S_n$, the gaps $\tau_n$ laid along the time axis. Mark a time $t$ inside a gap: the age $A(t) = t - S_{N(t)}$ stretches back to the last arrival, the residual $Y(t) = S_{N(t)+1} - t$ stretches forward to the next. Every theorem in this section is a statement about that picture.

• The inspection paradox — the memorable payoff. Inspect the process at a large time $t$: the gap you land in has the size-biased distribution, density $\frac{xf(x)}{\mu}$ — long gaps cover more of the timeline, so you’re more likely to land in one. Limiting distributions (via the Key Renewal Theorem):

$\text{age } A(t) \text{ and residual } Y(t) \;\xrightarrow{d}\; \text{density } \frac{\bar{F}(x)}{\mu}, \qquad \text{total gap } X_{N(t)+1} \;\xrightarrow{d}\; \text{density } \frac{xf(x)}{\mu}$

Skeleton for the age limit (the KRT pattern, run once). The age $A(t) = t - S_{N(t)} \leq x$ says the last arrival before $t$ landed in $[t-x, t]$. Decompose over which renewal $n$ is that last one — it sits in $[t-x, t]$ and the following arrival overshoots $t$:

$P(A(t) \leq x) = \sum_n P\big(t - x \leq S_n \leq t,\ S_{n+1} > t\big)$

Condition on the arrival time $S_n = y$ (with law $dF_n(y)$); given $S_n = y$, the next gap $X_{n+1} = S_{n+1} - y$ must exceed $t - y$, an independent event of probability $\bar F(t-y)$:

$P(A(t) \leq x) = \sum_n \int_{t-x}^t \bar F(t-y)\,dF_n(y)$

Summing the arrival-time laws over $n$ is exactly the renewal measure, $\sum_n dF_n(y) = dm(y)$:

$P(A(t) \leq x) = \int_{t-x}^t \bar{F}(t-y)\,dm(y)$

(summing the arrival-time CDFs $dF_n$ over $n$ gives exactly the renewal measure $dm$). The Key Renewal Theorem then replaces $dm$ far from the origin by its long-run density $\frac{1}{\mu}\,dy$ (Blackwell):

$\lim_{t \to \infty} P(A(t) \leq x) = \frac{1}{\mu}\int_0^x \bar{F}(u)\,du$

Age and residual have the same limit (the process is a renewal process backwards too). Anchors: $\text{Exp}(\lambda)$ gaps ⟹ age is $\text{Exp}(\lambda)$ (memorylessness, consistently); $U(0,1)$ gaps ($\mu = \frac{1}{2}$) ⟹ age density $2(1-x)$ — piled near 0. Same phenomenon as “survey a random person about family size and you oversample big families.”

Core competency set

• Prove $N(t)/t \to 1/\mu$ by the sandwich; state the $N(t) \geq n \iff S_n \leq t$ pivot.
• Prove Wald via the indicator-independence trick and produce the counterexample.
• Explain the inspection paradox, give the size-biased density, and run the uniform anchor.

11. Martingales — fairness as structure

• $(Z_n)$ is a martingale if $E|Z_n| < \infty$ and

$E(Z_{n+1} \mid Z_1, \ldots, Z_n) = Z_n$

— a fair game: given the whole past, the expected next value is the current value. Taking expectations: $E(Z_n) = E(Z_1)$ for all fixed $n$. No Markov assumption anywhere — this is a different axis of structure.

• The stock examples, each one conditioning computation: sums of mean-zero independents ($S_n$); $S_n^2 - n$ (variance compensated); $\big(\frac{q}{p}\big)^{S_n}$ for biased walks (exponential compensated); products of mean-1 independents; Polya’s urn proportion (add a ball of the drawn color — the proportion is fair); $E(Y \mid X_1, \ldots, X_n)$ for any fixed $Y$ (accumulating information about a fixed quantity is always a martingale — Doob).
• Optional stopping theorem (MST): $E(Z_N) = E(Z_1)$ holds at a stopping time $N$ provided things don’t blow up — versions: (i) $N$ bounded; (ii) $P(N < \infty) = 1$ and $|Z_n| \leq C$ for $n \leq N$. You cannot beat a fair game with a quitting rule — unless you smuggle in unboundedness (the “double until you win” strategies live exactly in the failure cases).
• Maximal inequality — Markov for whole paths. For a nonnegative submartingale ($E(X_{n+1} \mid \text{past}) \geq X_n$; e.g. $Z_n^2$ for any martingale $Z$):

$P\Big(\max_{1 \leq i \leq n} X_i \geq a\Big) \leq \frac{E(X_n)}{a}$

Proof. Let $N$ be the first time $i \leq n$ with $X_i \geq a$, and $N = n$ if the threshold is never reached — a bounded stopping time. Optional stopping for a submartingale ($N \leq n$) bounds the stopped value by the endpoint:

$E(X_N) \leq E(X_n)$

Now bound $E(X_N)$ below using $X \geq 0$: on the event $\{\max_{i \leq n} X_i \geq a\}$ the threshold was hit so $X_N \geq a$, and off it $X_N \geq 0$, hence $X_N \geq a\,\mathbf{1}\{\max_i X_i \geq a\}$:

$E(X_N) \geq a\,P\Big(\max_{i \leq n} X_i \geq a\Big)$

Chain the two inequalities and divide by $a$:

$P\Big(\max_{i \leq n} X_i \geq a\Big) \leq \frac{E(X_n)}{a}$

Fairness lets the endpoint control the entire running maximum — the engine inside the convergence theorem below and the $L^2$ theory.

Gambler’s ruin, replayed entirely by optional stopping — the showcase. Start at $a$, target $b$, $T$ = first hit of $0$ or $b$. ($P(T < \infty) = 1$ via the block argument: some length-$b$ all-win block eventually occurs.)

• Fair case: $S_n$ is a bounded-before-$T$ martingale, so

$a = E(S_T) = b\,P(\text{hit } b) \;\Rightarrow\; P(\text{hit } b) = \frac{a}{b}$

• Expected duration: $(S_n - a)^2 - n$ is a martingale ⟹ $E(T) = E(S_T - a)^2 = (b-a)^2\frac{a}{b} + a^2\frac{b-a}{b} = a(b-a)$. Numbers: $a = 900, b = 1000$: win probability $0.9$, but $E(T) = 90{,}000$ plays.
• Biased case ($p \neq \frac{1}{2}$): $S_n$ isn’t a martingale but $Z_n = \big(\frac{q}{p}\big)^{S_n}$ is; optional stopping gives

$P(\text{hit } b) = \frac{(q/p)^a - 1}{(q/p)^b - 1}$

Numbers: roulette $p = \frac{18}{38}$, $a = 900$, $b = 1000$: $P \approx 0.000027$. A hair of house edge, compounded over the long duration, annihilates the 90% — the single most practical fact in the chapter.

• Concentration — Azuma–Hoeffding: a martingale with bounded increments $|Z_i - Z_{i-1}| \leq c$ satisfies

$P(|Z_n - \mu| \geq t) \leq 2e^{-t^2/2nc^2}$

(transform-then-Markov on $e^{\theta Z_n}$, the Chernoff move from track 1, run with conditional expectations). Corollary, the bounded difference inequality: any function of independent variables that changes by ≤ $c$ when one coordinate changes is concentrated within $O(\sqrt{n})$ of its mean — via the Doob martingale $Z_i = E(Y \mid X_1, \ldots, X_i)$. Applications: bin packing, chromatic number of a random graph — concentration without knowing the mean.

• Martingale convergence: a martingale with $\sup_n E|Z_n| < \infty$ — in particular any bounded or $L^2$-bounded martingale — converges a.s. Fair games settle down. Polya’s urn proportion converges to a random limit (Uniform(0,1) for the 1+1 start): fairness forces convergence but not to anything deterministic.

Core competency set

• Verify a martingale by one conditioning computation (do $S_n^2 - n$ and $(q/p)^{S_n}$ cold).
• State optional stopping with its conditions and why “double-until-you-win” evades them.
• Run all three gambler’s-ruin computations by optional stopping; quote the roulette number.
• State Azuma + bounded differences and what the Doob martingale construction does.

12. Brownian motion

• Standard BM: a random continuous function with $B(0) = 0$, increments $B(t) - B(s) \sim N(0, t-s)$, disjoint increments independent. It’s the scaling limit of random walks (Donsker): $\frac{S_{\lfloor nt\rfloor}}{\sqrt{n}} \Rightarrow B(t)$ for any iid mean-0 variance-1 steps — the CLT upgraded from a number to a whole path. Normal increments aren’t an assumption so much as a consequence: continuous paths + independent increments forces them.
• Character: nowhere differentiable, no interval of monotonicity — legitimately rough. Invariances worth keeping: scaling ($c^{-1/2}B(ct)$ is BM), symmetry ($-B$), time inversion ($tB(1/t)$).
• The covariance that determines everything — for $s \leq t$, split off the independent increment:

$\operatorname{Cov}(B(s), B(t)) = \operatorname{Cov}\big(B(s),\ B(t) - B(s)\big) + \operatorname{Var}(B(s)) = 0 + s = \min(s, t)$

BM is a Gaussian process (every finite collection of values jointly normal), and a Gaussian process is completely determined by its mean and covariance functions. So “mean 0, covariance $\min(s,t)$, continuous paths” is an equivalent definition — verifying a candidate process is BM reduces to two computations (that’s exactly how time inversion is checked).

• Markov and strong Markov: $B(T + t) - B(T)$ is a fresh BM independent of the past, for $T$ a stopping time.
• The martingales of BM (continuous-time versions of §11’s stock examples):

$B(t), \qquad B(t)^2 - t, \qquad e^{\lambda B(t) - \frac{\lambda^2}{2}t}$

• Gambler’s ruin in continuum — optional stopping, third performance. $T$ = first exit of $(a, b)$, $a < 0 < b$:

$E[B(T)] = 0 \;\Rightarrow\; P(\text{hit } b \text{ first}) = \frac{-a}{b - a}, \qquad E[B(T)^2 - T] = 0 \;\Rightarrow\; E(T) = -ab$

• Reflection principle: reflect the path after it first hits level $a$. Let $T_a$ be the first time $B$ reaches $a$ (with $a > 0$), and reflect everything after $T_a$ across the line $y = a$:

$\tilde B(s) = \begin{cases} B(s), & s \leq T_a \\ 2a - B(s), & s > T_a \end{cases}$

By the strong Markov property the post-$T_a$ increments are a fresh BM independent of the past, and by symmetry their reflection is equally likely — so $\tilde B$ is itself a standard BM. The picture to hold: a path rising to its first touch of $y = a$, then two continuations — the true one and its mirror image in the line — equally likely.

Now the running max. Reaching level $a$ by time $t$ is hitting $a$ by time $t$: $\{M(t) \geq a\} = \{T_a \leq t\}$. Split that hitting event by where the path ends:

$P(M(t) \geq a) = P(T_a \leq t,\ B(t) \geq a) + P(T_a \leq t,\ B(t) < a)$

First term: $B(t) \geq a$ forces the path to have already crossed $a$, so $\{B(t) \geq a\} \subseteq \{T_a \leq t\}$ and the term is just $P(B(t) \geq a)$. Second term: reflection sends each path with $T_a \leq t,\ B(t) < a$ to one with $\tilde B(t) = 2a - B(t) > a$, a measure-preserving bijection, so it equals $P(T_a \leq t,\ B(t) > a) = P(B(t) > a)$:

$P(M(t) \geq a) = P(B(t) \geq a) + P(B(t) > a) = 2P(B(t) \geq a)$

($B(t) = a$ has probability 0). Since $B(t) \sim N(0,t)$:

$M(t) = \max_{s \leq t}B(s) \overset{d}{=} |N(0, t)|$

And the hitting time of level $a$ has density $\frac{a}{\sqrt{2\pi}t^{3/2}}e^{-a^2/2t}$ — so heavy-tailed that $E(T) = \infty$: BM hits every level with probability 1, on a timescale with no mean (null recurrence again, in continuum).

• Drift: $B(t) + \mu t \to \pm\infty$ as $\mu \gtrless 0$ (since $B(t)/t \to 0$). For negative drift $-\mu$, the all-time max is exponential — via the exponential martingale with $\lambda = 2\mu$ and optional stopping:

$M = \max_t\big(B(t) - \mu t\big) \sim \text{Exp}(2\mu)$

• A taste of Itô (the bridge to track 8 and finance): stochastic integrals $\int_0^t X\,dB$ are martingales; the rules of the calculus compress to $(dB)^2 = dt$, $dB\,dt = 0$, $(dt)^2 = 0$, giving Itô’s formula

$f(B(t)) - f(B(0)) = \int_0^t f'(B(s))\,dB(s) + \frac{1}{2}\int_0^t f''(B(s))\,ds$

— the chain rule plus a second-order correction, because $B$ accumulates quadratic variation $t$. Flagship computation: geometric Brownian motion $dX = \sigma X\,dB + \mu X\,dt$ solves to

$X(t) = X(0)\exp\Big(\sigma B(t) + \big(\mu - \tfrac{\sigma^2}{2}\big)t\Big)$

with the punchline threshold: $X(t) \to \infty$ if $\mu > \frac{\sigma^2}{2}$, $\to 0$ if $\mu < \frac{\sigma^2}{2}$ — positive drift is not enough; you must beat half the variance. Volatility itself drags geometric growth down.

Core competency set

• Define BM by its three properties; state Donsker’s meaning in one sentence.
• Verify $B^2 - t$ and the exponential martingale; replay continuum gambler’s ruin ($\frac{-a}{b-a}$, $-ab$) by optional stopping.
• Derive $M(t) \overset{d}{=} |N(0,t)|$ from the reflection principle.
• State Itô’s formula, the $(dB)^2 = dt$ rule, the GBM solution, and the $\mu$ vs $\frac{\sigma^2}{2}$ threshold.

13. Memorize cold

The instant-recall layer — these should cost nothing to produce; the fluency flashcards drill exactly this list.

• Markov property; $\pi^n = \pi^0P^n$; Chapman–Kolmogorov $P^{(n)} = P^n$.
• First-step template: $h(x) = \sum_y P(x,y)h(y)$ with boundary values; $g(x) = 1 + \sum_y P(x,y)g(y)$.
• $P_y(k \text{ returns}) = \rho_{yy}^k$; recurrent ⟺ $\sum_n p^n(y,y) = \infty$; finite + closed + irreducible ⟹ recurrent.
• Reflecting-walk trichotomy: $p < \frac{1}{2}$ positive recurrent / $= \frac{1}{2}$ null recurrent / $> \frac{1}{2}$ transient.
• Stationarity $\pi P = \pi$; detailed balance $\pi(x)p(x,y) = \pi(y)p(y,x)$; SRW on graph $\pi(x) = \frac{\deg(x)}{2|E|}$; doubly stochastic ⟹ uniform; $\pi(y) = \frac{1}{E_yT_y}$.
• Convergence: I + A + S ⟹ $p^n(x,y) \to \pi(y)$; ergodic theorem: I + S ⟹ time averages → $E_\pi[f]$.
• M–H acceptance: $R(x,y) = \min\{\frac{\pi(y)Q(y,x)}{\pi(x)Q(x,y)}, 1\}$; ratios kill normalizing constants.
• Branching: $E(X_n) = \mu^n$; extinction $\rho$ = smallest root of $\phi(r) = r$, $\phi(r) = E(r^Y)$.
• Exponential races: $\min \sim \text{Exp}(\sum\lambda_i)$, winner $i$ w.p. $\frac{\lambda_i}{\sum\lambda_j}$, independent of when.
• PP: gaps iid $\text{Exp}(\lambda)$ ⟺ counts Pois($\lambda t$) + independent increments; thinning ⟹ independent $PP(\lambda p_k)$; superposition adds rates; given $N(t) = n$, arrivals ~ sorted Uniforms.
• CTMC: $\lambda(x) = \sum_y q(x,y)$; $R(x,y) = \frac{q(x,y)}{\lambda(x)}$; $p_t = e^{Qt}$; stationary ⟺ $\pi Q = 0$ (rate in = rate out); no aperiodicity needed.
• Renewal: $\frac{N(t)}{t} \to \frac{1}{\mu}$; Wald $E\sum_1^NX_i = E(N)E(X_1)$; size-biased density $\frac{xf(x)}{\mu}$; age/residual limit density $\frac{\bar{F}(x)}{\mu}$.
• Martingale definition; optional stopping conditions; the three gambler’s-ruin answers: $\frac{a}{b}$, $a(b-a)$, $\frac{(q/p)^a - 1}{(q/p)^b - 1}$.
• Azuma: $P(|Z_n - \mu| \geq t) \leq 2e^{-t^2/2nc^2}$; maximal inequality $P(\max_{i \leq n}X_i \geq a) \leq \frac{E(X_n)}{a}$ (nonnegative submartingale).
• BM: increments $N(0, t-s)$, independent; $\operatorname{Cov}(B(s), B(t)) = \min(s,t)$; martingales $B, B^2 - t, e^{\lambda B - \lambda^2t/2}$; exit answers $\frac{-a}{b-a}$, $E(T) = -ab$; $M(t) \overset{d}{=} |N(0,t)|$; $(dB)^2 = dt$; GBM $X(0)e^{\sigma B + (\mu - \sigma^2/2)t}$ with the $\frac{\sigma^2}{2}$ threshold.
• Named moves: first-step analysis; restart-the-clock (strong Markov); rate-in = rate-out; sandwich-then-SLLN (renewal rate); indicator-can’t-peek (Wald); compensate-then-stop (optional stopping with $S^2 - n$, $(q/p)^S$, $e^{\lambda B - \lambda^2t/2}$); reflect-the-path.