Day 56: Identification Algorithms & Non-Identifiable Queries

Theory

From latent DAGs to ADMGs

If an unobserved $U$ has exactly two observed children, $A \leftarrow U \to B$ , replace it by a bidirected edge $A \leftrightarrow B$ . More generally, the latent projection keeps the observed nodes, draws $A \to B$ when $A$ causes $B$ through latent nodes only, and $A \leftrightarrow B$ when they share a latent ancestor through latent paths. The result is an acyclic directed mixed graph (ADMG): directed edges are causal, bidirected edges are unmeasured confounding. All identification results can be stated on the ADMG.

c-components

Two nodes are in the same c-component (confounded component, or district) if they are connected by a path made only of bidirected edges. c-components partition the observed nodes. Write $S_X$ for the c-component containing $X$ .

The c-component factorisation

For each c-component $S$ , define $Q[S] = P(\mathbf s \mid \operatorname{do}(\mathbf v \setminus \mathbf s))$ . Tian and Pearl showed that

P(\mathbf v) = \prod_j Q[S_j], \qquad Q[S_j] = \prod_{i:\, V_i \in S_j} P\big(v_i \mid v_1, \dots, v_{i-1}\big),

with the variables in a topological order. So every $Q[S_j]$ is identified from observational data.

Tian's criterion (single treatment)

The interventional distribution $P(\mathbf v \setminus x \mid \operatorname{do}(x))$ is identified if and only if there is no bidirected path from $X$ to any of its children; equivalently, no child of $X$ is in $S_X$ . Then

P(\mathbf v \setminus x \mid \operatorname{do}(x)) = \frac{P(\mathbf v)}{Q[S_X]}\sum_x Q[S_X].

Marginalise to get $P(y \mid \operatorname{do}(x))$ .

Beyond the simple criterion

Tian's criterion is about all outcomes at once. A particular $P(y \mid \operatorname{do}(x))$ can still be identified when the criterion fails (the "napkin" graph, Exercise 10). The general ID algorithm (Shpitser & Pearl, 2006) recursively decomposes the query into c-components and either returns a formula or finds a hedge, a structure that proves non-identification. It is sound and complete, and it is implemented in software (R's causaleffect, Python's y0).

When the answer is "not identified"

Two classic non-identified designs: the bow ( $X \to Y$ , $X \leftrightarrow Y$ ) and the instrument ( $Z \to X \to Y$ , $X \leftrightarrow Y$ ). Options:

add assumptions (linearity or monotonicity make the IV design work, Phase 5);
report bounds (Day 79);
run a sensitivity analysis (Day 95);
collect new variables or run an experiment.

Part 1 · Warm-up

Exercise 1 · Find the c-components

ADMG: $A \to B \to C \to D$ , $A \leftrightarrow C$ , $B \leftrightarrow D$ , $E \to D$ . List the c-components.

Show solution

Step 1. Follow bidirected edges only: $A \leftrightarrow C$ gives $\{A, C\}$ ; $B \leftrightarrow D$ gives $\{B, D\}$ .

Step 2. $E$ has no bidirected edges: $\{E\}$ .

Answer: $\{A, C\}$ , $\{B, D\}$ , $\{E\}$ .

Exercise 2 · Apply Tian's criterion

Is the effect of $X$ identified? (a) $X \to Y$ , $X \leftrightarrow Y$ . (b) $X \to M \to Y$ , $X \leftrightarrow Y$ . (c) $Z \to X \to Y$ , $Z \leftrightarrow Y$ . (d) $X \to M \to Y$ , $X \leftrightarrow M$ .

Show solution

Step 1. (a) Child $Y$ is in $S_X = \{X, Y\}$ : not identified (the bow).

Step 2. (b) $S_X = \{X, Y\}$ ; child $M$ is not in it: identified (the front door).

Step 3. (c) $S_X = \{X\}$ : identified (adjust for $Z$ ).

Step 4. (d) $S_X = \{X, M\}$ contains the child $M$ : not identified.

Exercise 3 · Q factors for the front door

For the ADMG $X \to M \to Y$ , $X \leftrightarrow Y$ (order $X, M, Y$ ), write $Q[\{X, Y\}]$ and $Q[\{M\}]$ .

Show solution

Step 1. $Q[\{X, Y\}] = P(x)\,P(y \mid x, m)$ (the factors for $X$ and $Y$ , each given all predecessors).

Step 2. $Q[\{M\}] = P(m \mid x)$ .

Step 3. Check: the product is $P(x)P(m \mid x)P(y \mid x, m) = P(x, m, y)$ .

Exercise 4 · The instrument graph

In $Z \to X \to Y$ , $X \leftrightarrow Y$ , is $P(y \mid \operatorname{do}(x))$ identified nonparametrically? Is $P(y \mid \operatorname{do}(z))$ ?

Show solution

Step 1. For $X$ : $S_X = \{X, Y\}$ contains the child $Y$ : not identified.

Step 2. For $Z$ : $S_Z = \{Z\}$ (no bidirected edges at $Z$ ): identified, and since $Z$ has no parents, $P(y \mid \operatorname{do}(z)) = P(y \mid z)$ .

Answer: the intention-to-treat effect of the instrument is identified; the effect of $X$ needs extra assumptions (linearity, or monotonicity for a LATE).

Exercise 5 · Latent projection

Latent DAG: $U_1 \to X$ , $U_1 \to M$ , $U_2 \to M$ , $U_2 \to Y$ , $X \to Y$ , with $U_1, U_2$ unobserved and $M$ observed. Draw the ADMG and decide whether the effect of $X$ on $Y$ is identified.

Show solution

Step 1. $U_1$ has observed children $X, M$ : draw $X \leftrightarrow M$ . $U_2$ : draw $M \leftrightarrow Y$ .

Step 2. ADMG: $X \to Y$ , $X \leftrightarrow M \leftrightarrow Y$ .

Step 3. $S_X = \{X, M, Y\}$ contains the child $Y$ : Tian's criterion fails for the full distribution $P(m, y \mid \operatorname{do}(x))$ .

Step 4. But for $Y$ alone, the back-door criterion holds with $\varnothing$ (the M-structure, Day 53): $P(y \mid \operatorname{do}(x)) = P(y \mid x)$ .

Answer: identified for $Y$ (not for the joint with $M$ ), which illustrates why the criterion concerns all outcomes.

Part 2 · Proofs

Exercise 6 · c-components partition the nodes

Prove that "connected by a bidirected path (or equal)" is an equivalence relation.

Show solution

Step 1. Reflexive: by definition each node is related to itself.

Step 2. Symmetric: bidirected edges have no direction, so a bidirected path from $A$ to $B$ reversed is one from $B$ to $A$ .

Step 3. Transitive: join a bidirected path from $A$ to $B$ with one from $B$ to $C$ ; the result is a bidirected walk from $A$ to $C$ , which contains a bidirected path.

Step 4. Equivalence classes partition the node set. $\blacksquare$

Exercise 7 · The front door from c-components

Use the identification formula in the theory to derive the front-door formula for $X \to M \to Y$ , $X \leftrightarrow Y$ .

Show solution

Step 1. $S_X = \{X, Y\}$ , with $Q[S_X] = P(x)P(y \mid x, m)$ (Exercise 3).

Step 2. $P(\mathbf v)/Q[S_X] = P(m \mid x)$ .

Step 3. $\sum_x Q[S_X] = \sum_{x'} P(x')P(y \mid x', m)$ .

Step 4. Multiply: $P(m, y \mid \operatorname{do}(x)) = P(m \mid x)\sum_{x'} P(x')P(y \mid x', m)$ .

Step 5. Sum over $m$ : the front-door formula (Day 54). $\blacksquare$

Exercise 8 · Why children outside the district matter

Let $Q[S] = P(\mathbf s \mid \operatorname{do}(\mathbf v \setminus \mathbf s))$ . Argue that if $X \in S$ has no children in $S$ , then $\sum_x Q[S] = Q[S \setminus \{X\}]$ .

Show solution

Step 1. $\sum_x Q[S] = P(\mathbf s \setminus x \mid \operatorname{do}(\mathbf v \setminus \mathbf s))$ : marginalising over $x$ in the intervened world.

Step 2. $Q[S \setminus \{X\}] = P(\mathbf s \setminus x \mid \operatorname{do}(\mathbf v \setminus \mathbf s), \operatorname{do}(x))$ .

Step 3. These are equal if, in the world where $\mathbf v \setminus \mathbf s$ is fixed, $X$ has no causal effect on $\mathbf S \setminus \{X\}$ (Rule 3).

Step 4. Any causal path from $X$ starts with an edge to a child; every child is outside $S$ , hence in $\mathbf v \setminus \mathbf s$ , which is fixed by intervention. So all causal paths are cut. $\blacksquare$

This is the step that fails when a child of $X$ shares its c-component.

Exercise 9 · No confounding at the treatment

Show that if $X$ has no bidirected edges, the identification formula reduces to the truncated factorisation $P(\mathbf v \setminus x \mid \operatorname{do}(x)) = P(\mathbf v)/P(x \mid \operatorname{pa}(x))$ in the Markovian case.

Show solution

Step 1. $S_X = \{X\}$ , so $Q[S_X] = P(x \mid v_1, \dots, v_{i-1})$ , which equals $P(x \mid \operatorname{pa}(x))$ in a Markovian model (Day 47).

Step 2. $\sum_x Q[S_X] = 1$ .

Step 3. So $P(\mathbf v \setminus x \mid \operatorname{do}(x)) = P(\mathbf v)/P(x \mid \operatorname{pa}(x))$ , which is the truncated factorisation (divide out $X$ 's factor). $\blacksquare$

Exercise 10 · The napkin

In the "napkin" ADMG $W \to Z \to X \to Y$ , $W \leftrightarrow X$ , $W \leftrightarrow Y$ , show that Tian's criterion fails. The ID algorithm nevertheless gives

P(y \mid \operatorname{do}(x)) = \frac{\sum_w P(x, y \mid z, w)P(w)}{\sum_w P(x \mid z, w)P(w)}

(for any $z$ ). Explain why there is no back-door or front-door set.

Show solution

Step 1. $S_X = \{W, X, Y\}$ (via $X \leftrightarrow W \leftrightarrow Y$ ); the child $Y$ is in it: the criterion fails, so $P(w, z, y \mid \operatorname{do}(x))$ is not identified.

Step 2. Back-door paths from $X$ to $Y$ : $X \leftarrow Z \leftarrow W \leftrightarrow Y$ (open with no conditioning) and $X \leftrightarrow W \leftrightarrow Y$ (collider at $W$ ).

Step 3. Conditioning on $W$ blocks the first path but opens the collider on the second. Conditioning on $Z$ blocks the first path but also opens the second, because $Z$ is a descendant of the collider $W$ . So no set of observed variables is admissible.

Step 4. Front door: $X$ has the single child $Y$ , so no mediator exists.

Answer: identification uses $Z$ as a conditioning device that is then integrated out over $W$ : a formula no single adjustment produces. The code verifies that it equals the truth in a model with strong latent confounding, while the naive comparison and adjustment for $Z$ are biased.

Part 3 · Applied

Exercise 11 · Minimum wage with unobserved local demand

Counties' minimum wage $X$ is set by states; local labour demand $D$ (unobserved) affects both state policy and teen employment $Y$ . Teen wages $W$ respond to $X$ and affect $Y$ ; $X$ also affects $Y$ directly through hours rules. Draw the ADMG and decide identifiability. What changes if $X$ had no direct arrow to $Y$ ?

Show solution

Step 1. ADMG: $X \to W \to Y$ , $X \to Y$ , $X \leftrightarrow Y$ (via $D$ ).

Step 2. $S_X = \{X, Y\}$ contains the child $Y$ : not identified.

Step 3. Without the direct arrow, the children of $X$ are $\{W\}$ , outside $S_X$ : identified by the front door through wages.

Answer: identification hinges on whether the minimum wage can affect employment only via wages, a substantive claim to defend or reject.

Exercise 12 · Statins and frailty

Elderly patients' frailty (unobserved) affects both statin prescription $X$ and mortality $Y$ . Frailty also affects adherence $A$ . Statins affect cholesterol $C$ , which affects mortality; adherence affects cholesterol. Observed: $X, A, C, Y$ . Draw the ADMG and apply Tian's criterion to the effect of prescription.

Show solution

Step 1. Directed: $X \to C$ , $A \to C$ , $C \to Y$ . Bidirected (frailty): $X \leftrightarrow Y$ , $X \leftrightarrow A$ , $A \leftrightarrow Y$ .

Step 2. $S_X = \{X, A, Y\}$ . Children of $X$ : $\{C\}$ , not in $S_X$ .

Step 3. Criterion satisfied: identified, with a front-door-like formula that treats $C$ as the mediator and adjusts for $(X, A)$ in its second stage.

Answer: identified, if cholesterol is the only channel for statins' effect, which pharmacology makes debatable (statins also reduce inflammation).

Exercise 13 · Job training with an observed confounder

Graph: motivation (unobserved) affects training $T$ and earnings $Y$ ; prior earnings $P$ (observed) affects $T$ and $Y$ ; training affects $Y$ . Is the effect identified? What if motivation instead affected only $P$ and $Y$ ?

Show solution

Step 1. First case: $T \leftrightarrow Y$ and $Y$ is a child of $T$ : not identified.

Step 2. Second case: bidirected edge $P \leftrightarrow Y$ ; $S_T = \{T\}$ : identified. $\{P\}$ satisfies the back-door criterion (the path $T \leftarrow P \leftrightarrow Y$ is blocked at $P$ ).

Answer: whether unobserved factors touch the treatment directly or only through observed pre-treatment variables decides everything.

Exercise 14 · A school health programme (napkin)

A family's health culture $W$ (observed index) affects participation in a school health programme $Z$ , which affects children's exercise habits $X$ , which affect BMI $Y$ . Unobserved household factors link $W$ with $X$ , and other unobserved factors link $W$ with $Y$ . Is the effect of exercise on BMI identified? How would you compute it?

Show solution

Step 1. ADMG: $W \to Z \to X \to Y$ , $W \leftrightarrow X$ , $W \leftrightarrow Y$ : the napkin.

Step 2. Tian's criterion fails, but the ID algorithm returns the napkin formula of Exercise 10.

Step 3. Computation: for a chosen $z$ , compute $\sum_w P(x, y \mid z, w)P(w)$ and divide by $\sum_w P(x \mid z, w)P(w)$ .

Answer: identified. The formula is unusual and estimation can be noisy; a practical analyst would also check whether some simpler design applies.

Exercise 15 · When the answer is no

A ministry asks for the effect of hospital ownership type (public vs private) on patient outcomes. Patients choose hospitals partly on unrecorded health status. No mediator captures the whole effect, and no instrument is available. What can you deliver?

Show solution

Step 1. The ADMG contains the bow $X \to Y$ , $X \leftrightarrow Y$ (after adjusting for observed covariates): not identified.

Step 2. Options: worst-case or monotone bounds on the effect (Day 79); a sensitivity analysis showing how strong unobserved selection must be to overturn the sign (Day 95).

Step 3. Better data: look for an instrument (distance to the nearest public hospital, ambulance assignment rules) or a natural experiment (ownership conversions over time, Phase 5).

Answer: be explicit that the point effect is not identified, report bounds and sensitivity, and propose a design that would identify it.

Verify in Python

import itertools
import numpy as np
import networkx as nx

def districts(nodes, bidirected):
    """c-components: connected components of the bidirected part."""
    B = nx.Graph(); B.add_nodes_from(nodes); B.add_edges_from(bidirected)
    return [sorted(c) for c in nx.connected_components(B)]

def tian_identified(directed, bidirected, x):
    nodes = {v for e in directed + bidirected for v in e} | {x}
    Sx = next(set(c) for c in districts(nodes, bidirected) if x in c)
    children = {b for a, b in directed if a == x}
    return not (children & Sx)

print("Ex 1:", districts("ABCDE", [("A", "C"), ("B", "D")]))
cases = {"bow": ([("X", "Y")], [("X", "Y")]),
         "front door": ([("X", "M"), ("M", "Y")], [("X", "Y")]),
         "adjust Z": ([("Z", "X"), ("X", "Y")], [("Z", "Y")]),
         "instrument": ([("Z", "X"), ("X", "Y")], [("X", "Y")]),
         "statins": ([("X", "C"), ("A", "C"), ("C", "Y")], [("X", "Y"), ("X", "A"), ("A", "Y")]),
         "napkin": ([("W", "Z"), ("Z", "X"), ("X", "Y")], [("W", "X"), ("W", "Y")])}
for k, (d, b) in cases.items():
    print(f"{k:11s} Tian criterion satisfied: {tian_identified(d, b, 'X')}")

# Exercise 10: the napkin formula in a random model with two latent confounders
pU1, pU2 = .5, .4
pW = np.array([[.1, .5], [.5, .9]]); pZ = np.array([.2, .8])             # pW[u1, u2], pZ[w]
pX = np.array([[.1, .8], [.3, .9]]); pY = np.array([[.1, .7], [.3, .9]])  # pX[z, u1], pY[x, u2]
b = lambda p, v: p if v else 1 - p
P = {}
for u1, u2, w, z, x, y in itertools.product((0, 1), repeat=6):
    P[w, z, x, y] = P.get((w, z, x, y), 0) + b(pU1, u1) * b(pU2, u2) * b(pW[u1, u2], w) * b(pZ[w], z) * b(pX[z, u1], x) * b(pY[x, u2], y)
m = lambda **kw: sum(v for k, v in P.items() if all(k["wzxy".index(a)] == val for a, val in kw.items()))
truth = {x: sum(b(pU2, u2) * pY[x, u2] for u2 in (0, 1)) for x in (0, 1)}
for x in (0, 1):
    napkin = [sum(m(x=x, y=1, z=z, w=w) / m(z=z, w=w) * m(w=w) for w in (0, 1)) /
              sum(m(x=x, z=z, w=w) / m(z=z, w=w) * m(w=w) for w in (0, 1)) for z in (0, 1)]
    naive = m(x=x, y=1) / m(x=x)
    adjZ = sum(m(x=x, y=1, z=z) / m(x=x, z=z) * m(z=z) for z in (0, 1))
    print(f"x={x}: truth {truth[x]:.4f}  napkin (z=0, z=1) {napkin[0]:.4f}, {napkin[1]:.4f}  naive {naive:.4f}  adjust Z {adjZ:.4f}")

Key takeaways

Bidirected edges encode unmeasured confounding; c-components group variables linked by it, and each c-component's factor is identified.
Tian's criterion: the effect of a single $X$ on all other variables is identified exactly when no child of $X$ shares its c-component.
The ID algorithm is complete; when it says "not identified", turn to bounds, sensitivity analysis, extra assumptions or new data.

Day 56. Identification Algorithms & Non-Identifiable Queries

Theory

From latent DAGs to ADMGs

c-components

The c-component factorisation

Tian's criterion (single treatment)

Beyond the simple criterion

When the answer is "not identified"

Part 1 · Warm-up

Exercise 1 · Find the c-components

Exercise 2 · Apply Tian's criterion

Exercise 3 · Q factors for the front door

Exercise 4 · The instrument graph

Exercise 5 · Latent projection

Part 2 · Proofs

Exercise 6 · c-components partition the nodes

Exercise 7 · The front door from c-components

Exercise 8 · Why children outside the district matter

Exercise 9 · No confounding at the treatment

Exercise 10 · The napkin

Part 3 · Applied

Exercise 11 · Minimum wage with unobserved local demand

Exercise 12 · Statins and frailty

Exercise 13 · Job training with an observed confounder

Exercise 14 · A school health programme (napkin)

Exercise 15 · When the answer is no

Verify in Python

Key takeaways

Simulation Lab: c-Components & Tian's Criterion