5. Foundations III: Markov Chains, Stochastic Time, and Causal Graphs (DAGs)

Learning Objectives. By the end of this chapter, you will be able to define Conditional Independence ($X \perp!!!\perp Z \mid Y$) and build Discrete-Time Markov Chains ($X \to Y \to Z$) using row-stochastic transition matrices $W$; explain the Quadratic Variation of Random Walks ($(\Delta W_t)^2 \approx \Delta t$) and why continuous stochastic calculus requires a second-order Taylor term; distinguish Additive Ensemble Averages from Multiplicative Time Averages; master the three elementary Directed Acyclic Graph (DAG) junctions (Chain, Fork/Confounder, and Collider/Berkson’s Paradox); and distinguish observational conditioning $P(Y \mid X = x)$ from Judea Pearl’s Graph-Surgery Intervention $P(Y \mid \mathrm{do}(X = x))$.

Step 1 — Intuition and the Real-World Paradox

When Controlling for a Variable Invents a Fake Disease

Suppose an emergency-room director wants to know whether having a broken bone ($X \in {0, 1}$) causes pneumonia ($Y \in {0, 1}$).

• In the general city population of $10\text{,}000$ citizens, broken bones ($10%$ prevalence) and pneumonia ($10%$ prevalence) are completely independent: $P(Y=1 \mid X=1) = P(Y=1 \mid X=0) = 10%$.
• However, the director does not sample the city street. Instead, he downloads the database of hospitalized patients ($C = 1$)—and a person is admitted to the hospital ($C = 1$) if they have either a broken bone ($X = 1$) or pneumonia ($Y = 1$).

When the hospital data scientist runs a regression inside the hospital database ($C = 1$), he discovers a shocking negative correlation:

• Among hospitalized patients without a broken bone ($X = 0, C = 1$), $100%$ have pneumonia ($Y = 1$) (otherwise why would they be in the hospital?).
• Among hospitalized patients with a broken bone ($X = 1, C = 1$), only $10%$ have pneumonia ($Y = 1$)!

The data scientist proudly announces: “Breaking a bone cuts your risk of pneumonia by $90%$!”

This famous trap is Berkson’s Paradox (Collider Bias). Notice the arrow structure: broken bones cause hospitalization ($X \to C$), and pneumonia also causes hospitalization ($Y \to C$). So $C$ is a common effect (a collider) $X \to C \leftarrow Y$. When you condition on a common cause (a confounder $X \leftarrow U \to Y$), you remove spurious correlation; when you condition on a common effect (a collider $X \to C \leftarrow Y$), you create spurious correlation out of thin air!

Before entering Chapter 6 (The Five Transversal Lenses—Information, Time, Tail, Causal Structure, and Decision), we must lay down the three mathematical foundations that make those five lenses transparent:

1. Markov Chains ($X \to Y \to Z$) and Stochastic Matrices $W$ (the backbone of the Information Lens and MCMC mixing);
2. Multiplicative Compounding and the $(\Delta W_t)^2 = \Delta t$ Scaling of Brownian Motion (the backbone of the Time and Tail Lenses);
3. Directed Acyclic Graphs (DAGs), $d$-Separation, and Graph Surgery $\mathrm{do}(X=x)$ (the backbone of the Causal Structure and Decision Lenses).

Step 2 — Foundations and Mathematical Formalization

5.1 Conditional Independence and Markov Chains ($X \to Y \to Z$)

What Does Conditional Independence Mean?

Recall from the Preface that two random variables $X$ and $Z$ are marginally independent ($X \perp!!!\perp Z$) if $P(X = x, Z = z) = P(X = x)P(Z = z)$.

Now suppose there is an intermediate state $Y$ between $X$ and $Z$. We say that $X$ and $Z$ are conditionally independent given $Y$, written:

$$X \perp!!!\perp Z \mid Y$$

if, once you know the exact present state $Y = y$, learning the past state $X = x$ gives you zero additional information about the future state $Z = z$:

$$P(Z = z \mid X = x, Y = y) = P(Z = z \mid Y = y)$$

Discrete-Time Markov Chains and Row-Stochastic Matrices $W$

A sequence of random variables $X \to Y \to Z$ satisfying $X \perp!!!\perp Z \mid Y$ is called a Markov Chain: given the present ($Y$), the future ($Z$) is independent of the past ($X$).

When the state space is finite with $m$ states ${1, 2, \dots, m}$, the step from $X$ to $Y$ is completely described by an $m \times m$ Row-Stochastic Transition Matrix $W$:

$$W_{ij} = P(Y = j \mid X = i) \ge 0, \qquad \sum_{j=1}^m W_{ij} = 1 \quad \forall i \in {1, \dots, m}$$

Why must each row sum to $1$? Because starting from state $X = i$, the system must land in some state $Y = j \in {1, \dots, m}$ with total probability $100%$. If we represent a probability distribution over states as a row vector $\mathbf{p} = (p_1, \dots, p_m)$, then after one step through the channel $W$, the new probability distribution $\mathbf{q}$ is simply the vector-matrix product:

$$\mathbf{q} = \mathbf{p} W \qquad \left(q_j = \sum_{i=1}^m p_i W_{ij}\right)$$

And across a two-step Markov chain $X \xrightarrow{W_1} Y \xrightarrow{W_2} Z$, the composite transition matrix from $X$ to $Z$ is the matrix product $W_{12} = W_1 W_2$ (Chapman-Kolmogorov Equation).

Worked Example 5.1: How a Noisy Channel Mixes Distributions Together

Consider a binary communication channel (or noisy sensor) with symmetric flip error $\varepsilon = 0.20$:

$$W = \begin{bmatrix} 0.80 & 0.20 \ 0.20 & 0.80 \end{bmatrix}$$

Suppose hypothesis $A$ puts $100%$ probability on state $1$, $\mathbf{p} = (1, 0)$, and hypothesis $B$ puts $100%$ probability on state $2$, $\mathbf{p}’ = (0, 1)$. Before passing through $W$, the Total Variation distance between $\mathbf{p}$ and $\mathbf{p}‘$ is $\frac{1}{2}\sum |p_j - p’_j| = 1.00$ (completely distinguishable). After passing through $W$:

• $\mathbf{q} = \mathbf{p}W = (0.80, 0.20)$
• $\mathbf{q}’ = \mathbf{p}’W = (0.20, 0.80)$

Now the Total Variation distance between $\mathbf{q}$ and $\mathbf{q}’$ has shrunk to $|0.80 - 0.20| = \mathbf{0.60} = 1 - 2\varepsilon$! Every noisy Markov step $W$ blends rows together, irreversibly contracting the distinguishability of distributions. In Chapter 6 (Lens 1), this elementary matrix fact will give us the Data Processing Inequality (DPI) and the exact hierarchy of Strong Contraction Constants ($\eta_{\chi^2}(W) \le \eta_{\mathrm{KL}}(W) \le \eta_{\mathrm{TV}}(W)$).

5.2 Multiplicative Compounding and the $(\Delta W_t)^2 = \Delta t$ Rule of Stochastic Time

Why Arithmetic Averages Lie About Multiplicative Trajectories

In an additive game, if you win $+$50$ on Monday and lose $-$50$ on Tuesday, your net change is $+50 - 50 = $0$.

In a multiplicative system (compound interest, population biology, portfolio returns, evolutionary fitness), changes multiply your current state $W_t$:

• Suppose you start with $W_0 = $100$.
• On Monday your wealth grows by $+50%$ ($r_1 = +0.50$), reaching $W_1 = 100 \times 1.50 = $150$.
• On Tuesday your wealth drops by $-50%$ ($r_2 = -0.50$), reaching $W_2 = 150 \times 0.50 = \mathbf{$75}$!

Look at the paradox:

• Your arithmetic average return per day is $\frac{+50% + (-50%)}{2} = \mathbf{0.0%}$.
• Yet your actual wealth dropped by $-25%$ in two days (a geometric compounding rate of $\sqrt{1.50 \times 0.50} - 1 = \sqrt{0.75} - 1 \approx -13.4%$ per day)!

Why? Because multiplication is linear in logarithms: $\ln(W_T / W_0) = \sum_{t=1}^T \ln(1 + r_t)$. And as we learned in Chapter 1, the function $f(x) = \ln(1 + x)$ is strictly concave ($f’’(x) = -\frac{1}{(1+x)^2} < 0$). By our second-order Taylor expansion of Jensen’s Inequality around $r = \mu$:

$$\mathbb{E}[\ln(1 + r)] \approx \mu - \frac{1}{2}\sigma^2$$

Every bit of variance $\sigma^2$ in a multiplicative process drags down the long-run growth rate by $-\frac{1}{2}\sigma^2$.

Why Brownian Motion Has $(\Delta W_t)^2 = \Delta t$ (The Intuition Behind Itô’s Lemma)

In classical deterministic calculus, if a smooth variable $x(t)$ changes by $\Delta x = v,\Delta t$ over a tiny time step $\Delta t$, then its square is $(\Delta x)^2 = v^2 (\Delta t)^2$, which vanishes much faster than $\Delta t$ as $\Delta t \to 0$. That is why ordinary calculus stops at the first derivative: $df(x) = f’(x),dx$.

Now consider a continuous-time Brownian motion (random walk) $W_t$. Over a time interval of length $\Delta t$, the increment $\Delta W_t = W_{t+\Delta t} - W_t$ has mean $0$ and variance equal to the elapsed time $\Delta t$:

$$\mathbb{E}[\Delta W_t] = 0, \qquad \mathrm{Var}(\Delta W_t) = \mathbb{E}[(\Delta W_t)^2] = \Delta t$$

Notice what $\mathbb{E}[(\Delta W_t)^2] = \Delta t$ means for the size of a typical step:

$$\Delta W_t = \pm \sqrt{\Delta t} \implies (\Delta W_t)^2 = \left(\pm\sqrt{\Delta t}\right)^2 = \Delta t$$

The square of a Brownian increment is of first order $\Delta t$, not $(\Delta t)^2$! Therefore, when we expand any smooth function $f(X_t)$ of a stochastic process in a Taylor series, we cannot drop the second-order term $\frac{1}{2}f’’(X_t)(\Delta X_t)^2$:

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

This single equation—born directly from $(\pm\sqrt{\Delta t})^2 = \Delta t$—is Itô’s Lemma, which we will use in Chapter 6 (Lens 2) to derive exact time-average growth rates, optimal Kelly fractions, and absorbing ruin probabilities.

5.3 Directed Acyclic Graphs (DAGs): Chains, Forks, Colliders, and $\mathrm{do}(X = x)$

How do we represent cause-and-effect relationships mathematically so we never fall into Berkson’s Paradox or confounding bias? Judea Pearl showed that causal structure can be drawn as a Directed Acyclic Graph (DAG) $G = (V, E)$, where each node is a variable and each directed arrow $A \to B$ means that $A$ is a direct physical mechanism entering the structural equation $B = f_B(A, \dots, \varepsilon_B)$.

Every causal graph, no matter how large, is built out of just three elementary 3-node junctions (illustrated in Panel 3 of Figure 5.1):

Seeing vs. Doing: Observational $P(Y \mid X = x)$ vs. Interventional $P(Y \mid \mathrm{do}(X = x))$

Suppose a Fork confounder $X \leftarrow U \to Y$ is present:

1. Seeing ($P(Y \mid X = x)$, Rung 1 of Pearl’s Ladder): When we passively observe $X = x$, information flows both forward along causal arrows $X \to Y$ AND backward along the back-door fork $X \leftarrow U \to Y$ (because observing high ice-cream sales $X$ tells us it is a hot day $U$, which predicts sunburns $Y$).
2. Doing ($P(Y \mid \mathrm{do}(X = x))$, Rung 2 of Pearl’s Ladder): When we physically intervene to force $X := x$ (for example, handing out free ice cream on a random Tuesday), we perform Graph Surgery: we delete all incoming arrows into $X$ (severing $U \to X$) while keeping all outgoing arrows $X \to Y$ intact!

When the confounder $U$ is observed, Pearl’s Back-Door Adjustment Formula computes the interventional distribution from observational data by averaging over $U$:

$$P(Y = y \mid \mathrm{do}(X = x)) = \sum_u P(Y = y \mid X = x, U = u) , P(U = u)$$

And what if $U$ is partially unobserved or we have data across multiple environments $e \in \mathcal{E}$ (such as different seasons, hospitals, or experimental vs. observational cohorts)? In Chapter 6 (Lens 4), we will see how Invariant Causal Prediction (ICP), Rosenbaum’s $\Lambda^\ast$, and Cinelli-Hazlett’s Robustness Value $RV_q$ audit causal claims under environmental shifts and hidden confounding!

Step 3 — Auditable Laboratory in Rust and Exercises

The building blocks of this chapter power the pure-Rust engines in crates/stochology-lenses and crates/stochology-siga:

• DpiMarkovChain (crates/stochology-lenses/src/information.rs): Constructs row-stochastic matrices $W_1, W_2$ for 3-step Markov chains $X \to Y \to Z$ and verifies contraction constants.
• TimeErgodicitySummary (crates/stochology-lenses/src/time.rs): Simulates multiplicative trajectories and measures the Itô volatility drain $-\frac{1}{2}\sigma^2$.
• evaluate_filter_2_independence_and_blanket (crates/stochology-siga/src/funnel.rs): Enforces Markov Blanket hygiene and rejects any model that conditions on a Berkson collider (colliders_conditioned == 0).

Run Lab 3 and Lab 5 to inspect these mechanisms in action:

cargo run --release --bin labs -- --lenses
cargo run --release --bin labs -- --siga

Exercises

1. Row-Stochastic Matrix Multiplication: Given initial state distribution $\mathbf{p} = (0.9, 0.1)$ and transition matrix $W = \begin{bmatrix} 0.7 & 0.3 \ 0.4 & 0.6 \end{bmatrix}$:
   • Compute $\mathbf{q} = \mathbf{p}W$ after one step and check that $q_1 + q_2 = 1$.
   • Find the stationary distribution $\boldsymbol{\pi} = (\pi_1, \pi_2)$ satisfying $\boldsymbol{\pi} W = \boldsymbol{\pi}$ and $\pi_1 + \pi_2 = 1$.
2. Numerical Proof of Berkson’s Collider Paradox: Suppose two independent fair coins $X \in {0, 1}$ and $Y \in {0, 1}$ ($P(X=1)=0.5$, $P(Y=1)=0.5$) determine whether a bell rings: $C = \mathbf{1}{X + Y \ge 1}$.
   • Write out the $4$ equally likely outcomes $(X, Y) \in {(0,0), (0,1), (1,0), (1,1)}$ and verify that $\mathrm{Cov}(X, Y) = 0$ across all $4$ rows.
   • Now filter to the $3$ rows where the bell rang ($C = 1$): compute $P(Y = 1 \mid X = 0, C = 1)$ vs. $P(Y = 1 \mid X = 1, C = 1)$, and show that conditioning on the collider $C = 1$ creates a negative correlation $\rho_{X, Y \mid C=1} = -0.50$!
3. Arithmetic vs. Geometric Compounding: An asset alternates deterministically between $+60%$ in odd years and $-40%$ in even years. Compute its arithmetic average annual return vs. its 2-year multiplier $(1.60 \times 0.60)$, and determine how much wealth remains after $20$ years starting from $$1\text{,}000$.