Past exam of the mathematics course of the University of Cambridge / 2026 / iii / Paper 205 / 4

The graph has edges $1\to 2\leftarrow 3$, $1\to 4$, $2\to 4$, $3\to 5$, $4\to 5$, $4\to 6$, and $6\to 5$. Any D-separating set for 1 and 6 must contain 4 because of the directed path $1\to 4\to 6$. Conditioning on 4 activates the collider $1\to 4\leftarrow 2$ and, through its descendant, the collider $1\to 2\leftarrow 3$. The remaining route through $3\to 5\leftarrow 6$ is open exactly when 5 is conditioned on and 3 is not. Hence all separating sets, among the nonendpoint vertices, are

For the second graph, $2\perp \perp 5\mid 1,6$ forces colliders on the unblocked two-edge paths: $2\to 3\leftarrow 5$ and $2\to 4\leftarrow 5$. Acyclicity then forces $1\to 4$ and $6\to 4$. Thus its edges are

Solved by gpt-5.6-sol high.

Choose the given topological ordering. Since $j$ precedes $k$, $j$ is not a descendant of $k$; since they are nonadjacent, it is not a parent of $k$. The local Markov property of a directed acyclic graph says that a node is d-separated from all its nondescendants other than its parents by its parent set. Therefore $j$ and $k$ are d-separated by $\mathrm{pa}(k)$.

It follows that adjacency of $Z_1,Z_2$ is certified by rejecting every null hypothesisIf the vertices were nonadjacent, the theorem would supply one such separating parent set, whichever vertex comes later.

To certify that $X_1$ is a parent of $Y$, first rejectfor every $S\subseteq \{2,\dots ,d\}$, which forces adjacency. Then rejectfor every such $S$. If the adjacent edge were $Y\to X_1$, then $I\to X_1\leftarrow Y$ would orient $X_1$ as a collider, and the parent-set argument would provide a separator not containing $X_1$, contradicting the second collection of rejections. Hence the edge is $X_1\to Y$.

Solved by gpt-5.6-sol high.