PC algorithm and Markov-equivalence structure learning

If $i$ and $j$ are adjacent, the one-edge path between them has no internal vertices, so it is active given every $S\subseteq V\setminus \{i,j\}$ by [F1]. Hence no such $S$ d-separates them.

Suppose $i$ and $j$ are nonadjacent. Acyclicity implies that at least one of $i,j$ is not a descendant of the other; after interchanging labels, assume $j$ is not a descendant of $i$. Since $i,j$ are nonadjacent, $j$ is a non-descendant non-parent of $i$. Put $S={\mathrm{pa}}_G(i)$. Then $S$ excludes both endpoints. Consider any path $i=v_0,v_1,\dots ,v_r=j$. If its first arrow points into $i$, then $v_1\in S$ and the occurrence of $v_1$ is a noncollider, because the arrow $v_1\to i$ has its tail at $v_1$; the path is blocked. If the first arrow points out of $i$, follow arrows that point forward along the path until the first arrow that points backward. Such a reversal must occur because $j$ is not a descendant of $i$. At the reversal vertex $v_t$, both incident arrows point into $v_t$, so it is a collider and the initial segment is a directed path $i\to \cdots \to v_t$. If $v_t$ had a descendant $p\in S$, then $i\to \cdots \to v_t\to \cdots \to p\to i$ would be a directed cycle. Thus this collider has no descendant in $S$, and the path is blocked by [F1]. Every path is blocked, so $S$ d-separates $i$ and $j$.

The adjacent and nonadjacent cases prove both implications.

Put $P={\mathrm{pa}}_G(x)$, so ${\mathrm{pa}}_G(y)=P\cup \{x\}$. If reversing the arrow created a directed cycle, that cycle would use the new arrow $y\to x$, and the remaining part would be a directed path $x\to \cdots \to z\to y$ in $G$ with $z\mathrm{\ne }x$. Then $z\in P$, so $z\to x$ is also in $G$, making the directed cycle $x\to \cdots \to z\to x$ in $G$, a contradiction. Thus $G^{\mathrm{\prime }}$ is acyclic.

The full moral graphs of $G$ and $G^{\mathrm{\prime }}$ coincide. Their skeletons coincide. The only changed parent sets are ${\mathrm{pa}}_G(x)=P$, ${\mathrm{pa}}_G(y)=P\cup \{x\}$ and ${\mathrm{pa}}_{G^{\mathrm{\prime }}}(x)=P\cup \{y\}$, ${\mathrm{pa}}_{G^{\mathrm{\prime }}}(y)=P$. Any pair newly married at $y$ in $G$ or at $x$ in $G^{\mathrm{\prime }}$ already belongs to the clique on $P\cup \{x,y\}$: pairs involving $x$ or $y$ are skeleton edges, and pairs in $P$ are married at both $x$ and $y$. All other parent sets are unchanged, so the moral edge sets are identical.

Fix pairwise disjoint query sets $A,B,S$ and put $T=A\cup B\cup S$. The ancestor sets of $T$ in $G$ and $G^{\mathrm{\prime }}$ differ, if at all, only by $x$ or $y$. Indeed, a directed path whose existence changes must use the reversed edge. A path in $G$ that uses $x\to y$ and starts at $v\mathrm{\ne }x$ enters $x$ from some $p\in P$; in $G^{\mathrm{\prime }}$ replace $p\to x\to y$ by the unchanged arrow $p\to y$. Therefore only $x$ can cease to be an ancestor. Symmetrically, a path in $G^{\mathrm{\prime }}$ using $y\to x$ and starting at $v\mathrm{\ne }y$ enters $y$ from $p\in P={\mathrm{pa}}_{G^{\mathrm{\prime }}}(y)$; in $G$ replace $p\to y\to x$ by $p\to x$. Therefore only $y$ can become an ancestor. If $x$ is lost, $y$ belongs to both ancestor sets; if $y$ is gained, $x$ belongs to both.

If the ancestor sets are equal, step 1.2 shows the induced ancestral moral graphs are equal. Suppose instead that $x$ is an ancestor only in $G$. Then $x\mathrm{\notin }T$ and $y$ is a common ancestor of $T$. In the moral graph induced on ${\mathrm{An}}_G(T)$, every neighbor of $x$ is in $P\cup \{y\}$: its parents lie in $P$; among its children only $y$ can be ancestral, since any other child has an unchanged arrow from $x$ and would make $x$ an ancestor in $G^{\mathrm{\prime }}$; and a marriage through a child other than $y$ would have the same consequence, while a marriage through $y$ uses another parent in $P$. The vertices in $P\cup \{y\}$ form a clique because they are parents of $y$ in $G$. Hence $x$ is simplicial in the ancestral moral graph. The case that $y$ is gained only in $G^{\mathrm{\prime }}$ is symmetric, with its neighbors contained in the clique $P\cup \{x\}$.

Removing an unconditioned simplicial vertex does not change separation between $A$ and $B$ after deleting $S$: the vertex is not in $T$, and any path through it can be shortened by replacing its two incident edges with the edge joining its neighbors, which exists because the neighborhood is a clique. Conversely, every path in the smaller graph remains in the larger graph. Thus the two ancestral moral graphs separate $A$ and $B$ by $S$ in exactly the same cases. By [F1], $G$ and $G^{\mathrm{\prime }}$ have the same d-separation relations.

We first show by induction on the number of vertices that a connected noncomplete chordal graph has two nonadjacent simplicial vertices. Choose nonadjacent vertices $a,b$ and an inclusion-minimal separator $S$ whose removal disconnects them. Let $C_a,C_b$ be the components of $H-S$ containing $a,b$. For every $s\in S$, minimality gives a path from $a$ to $b$ after restoring only $s$, so $s$ has a neighbor in each of $C_a,C_b$. If $x,y\in S$ were nonadjacent, shortest paths from $x$ to $y$ with internal vertices in $C_a$ and in $C_b$ would form an induced cycle of length at least four: each path is chordless by shortestness, there are no edges between the two components, and $x,y$ are nonadjacent. This contradicts chordality, so $S$ is a clique. The induced graphs on $C_a\cup S$ and $C_b\cup S$ are smaller connected chordal graphs. By induction, each is either complete, in which case any vertex in its nonempty component $C_a$ or $C_b$ is simplicial, or noncomplete, in which case it has two nonadjacent simplicial vertices and at least one lies outside the clique $S$. Such a vertex has no neighbors outside its component together with $S$, so it is simplicial in $H$. The chosen vertices from $C_a$ and $C_b$ are nonadjacent. Complete connected graphs have every vertex simplicial, and disconnected graphs have a simplicial vertex in each component. Therefore every nonempty finite chordal graph has a simplicial vertex.

Repeatedly remove a simplicial vertex. Each induced subgraph remains chordal, so step 1.1 supplies a simplicial vertex until the graph is empty. The removal order $v_1,\dots ,v_n$ is a perfect elimination order because the neighbors of $v_t$ that remain at its removal are pairwise adjacent.

For each $t$, let $K_t=\{v_t\}\cup N_t^{+}$, where $N_t^{+}$ is the set of neighbors of $v_t$ later in the elimination order. Each $K_t$ is a clique by step 2.1. If $N_t^{+}$ is nonempty, let $p(t)$ be its earliest vertex and join the clique node $K_t$ to $K_{p(t)}$. The index strictly increases along parent edges, so these edges form a forest. Since $N_t^{+}$ is a clique, every vertex of $N_t^{+}$ other than $p(t)$ is a later neighbor of $p(t)$; hence $K_t\cap K_{p(t)}=N_t^{+}$. If a vertex $x$ belongs to $K_t$ with $t<x$, then $x\in N_t^{+}$ and this membership propagates to the parent node, eventually to $K_x$. Thus the clique nodes containing any fixed vertex form a connected subtree. Every graph edge lies in some $K_t$ by taking its earlier endpoint. This is a clique forest with the running-intersection property.

Root every tree of this forest and concatenate their postorders into one order of the clique nodes. Each vertex $x$ belongs to a connected subtree of clique nodes in one rooted tree, so there is a unique root-nearest node $C_x$ containing it. List the vertices owned by each node $C_x$ in any order within that node's block. For any neighbor $y$ of $x$, a clique node $D$ contains both. The nodes $C_x,C_y,D$ lie in the connected subtrees of cliques containing $x$ and $y$, so $C_x,C_y$ are comparable along the root-to-$D$ path in the same tree. If $C_y$ is an ancestor of $C_x$, the running-intersection property gives $y\in C_x$; if it is a strict descendant of $C_x$, its block is earlier in postorder; and if it is $C_x$, both vertices are in the same clique block. Thus any neighbor $y$ later than $x$ belongs to the clique $C_x$. All later neighbors of $x$ therefore lie in the clique $C_x$, so this order is a perfect elimination order.

Direct every edge from its later endpoint in this order to its earlier endpoint. The orientation is acyclic because every arrow decreases the order. The parents of any vertex are among its later neighbors, which form a clique by step 4.1; hence there is no unshielded collider.

Since $\{u,v\}$ is an edge, some clique node $C$ contains both. Root its clique tree at $C$. Then $C$ is the root-nearest node containing each of $u,v$, so both are owned by its vertex block. List $v$ before $u$ in that block; step 5.1 directs $u\to v$. Reversing their order directs $v\to u$. The remaining vertices in the block may retain any order, and other trees may be rooted and ordered independently. Both resulting orientations are acyclic and collider-free by steps 4.1–5.1.

If $i\to k\leftarrow j$, then $k$ is a collider on the length-two path from $i$ to $j$. If $k\in S$, it is its own conditioned descendant, so this path is active by [F1], contradicting that $S$ separates the endpoints. Therefore $k\mathrm{\notin }S$.

If the unshielded triple is not a v-structure, then $k$ is a noncollider on its length-two path. If $k\mathrm{\notin }S$, that path has no conditioned internal noncollider and no collider, so it is active by [F1], again contradicting separation. Hence a noncollider requires $k\in S$.

The two implications prove the equivalence.

First assume that $G_1,G_2$ have the same skeleton and the same unshielded colliders. A finite DAG has a topological order: if every remaining vertex had an incoming arrow, following incoming arrows in the finite graph would repeat a vertex and create a directed cycle; remove a source and repeat. Fix such an order $\prec$ for $G_1$. If the DAGs differ, choose the $\prec$-earliest vertex $\beta$ with ${\mathrm{pa}}_{G_1}(\beta )\setminus {\mathrm{pa}}_{G_2}(\beta )\mathrm{\ne }\mathrm{\varnothing }$, and choose the $\prec$-latest $\alpha$ in that difference. Then $\alpha \to \beta$ occurs in $G_1$ and $\beta \to \alpha$ in $G_2$.

Conversely, assume $G_1,G_2$ are Markov equivalent. If their skeletons differed, [F2] would give a pair separated in one graph but not the other. Thus their skeletons agree. If an unshielded collider $i\to k\leftarrow j$ occurred in $G_1$ but not in $G_2$, then $i,j$ are nonadjacent in both. By [F2] choose $S$ that d-separates $i,j$ in $G_1$. The path $i\to k\leftarrow j$ shows that no descendant of $k$, including $k$, can lie in $S$, because otherwise that path would be active. In $G_2$, the same unshielded triple has a noncollider at $k$; since $k\mathrm{\notin }S$, the two-edge path is active, so $S$ does not d-separate $i,j$ there. This contradicts Markov equivalence. Interchanging $G_1,G_2$ rules out a collider present only in $G_2$.

Let $\gamma \mathrm{\ne }\alpha$ be another parent of $\beta$ in $G_1$. If $\gamma$ were not a parent of $\alpha$, then either $\gamma$ and $\alpha$ would be nonadjacent, making $\alpha \to \beta \leftarrow \gamma$ an unshielded collider absent from $G_2$, or they would be adjacent with $\alpha \to \gamma$ in $G_1$. The first case contradicts equality of colliders; in the second case, $G_2$ cannot retain both $\alpha \to \gamma$ and $\gamma \to \beta$, because together with $\beta \to \alpha$ they form a directed cycle. If $\alpha \to \gamma$ is reversed in $G_2$, then $\gamma \prec \beta$ is an earlier vertex with a differing parent; if $\gamma \to \beta$ is reversed, then $\gamma$ is a later member than $\alpha$ of ${\mathrm{pa}}_{G_1}(\beta )\setminus {\mathrm{pa}}_{G_2}(\beta )$. Both contradict the choices in step 1.1. Hence every parent of $\beta$ other than $\alpha$ is a parent of $\alpha$.

To prove ${\mathrm{pa}}_{G_1}(\alpha )\subseteq {\mathrm{pa}}_{G_1}(\beta )$, suppose instead that $\gamma \to \alpha$ in $G_1$ but $\gamma \mathrm{\notin }{\mathrm{pa}}_{G_1}(\beta )$. Minimality of $\beta$ implies $\gamma \to \alpha$ is also present in $G_2$; otherwise the earlier vertex $\alpha$ would already have a differing parent. If $\gamma$ were not adjacent to $\beta$, then $G_2$ would contain the unshielded collider $\beta \to \alpha \leftarrow \gamma$, while $G_1$ has the noncollider chain $\gamma \to \alpha \to \beta$, contradicting equality of colliders. Thus $\gamma$ is adjacent to $\beta$. In $G_1$ it must be oriented $\gamma \to \beta$, since $\beta \to \gamma$ would make a directed cycle with $\gamma \to \alpha \to \beta$. This contradicts the assumption that $\gamma$ is not a parent of $\beta$. Therefore the inclusion holds. Together with step 2.1, ${\mathrm{pa}}_{G_1}(\beta )={\mathrm{pa}}_{G_1}(\alpha )\cup \{\alpha \}$, so $\alpha \to \beta$ is covered.

Reverse this covered arrow in $G_1$. By [F3] the result remains a DAG and is Markov equivalent to $G_1$. It has the same skeleton, and it has the same unshielded colliders: an edge in an unshielded collider cannot be covered, because the other parent of the collider would then also be a parent of the edge's tail and hence adjacent to it. Exactly one edge now agrees with $G_2$, so the finite number of edge-orientation disagreements decreases by one. If any disagreement remains, choose the earliest differing parent set again; the argument in steps 1.1–3.1 applies because the skeleton and collider set are unchanged. Thus finitely many covered reversals transform $G_1$ into $G_2$, and each reversal preserves d-separation.

The two directions prove the equivalence.

Partition $X=(Y,Z)$ with $Y=(X_i,X_j)$ and $Z=X_S$; if $S=\mathrm{\varnothing }$, omit the $Z$ block. For nonempty $S$, ${\mathrm{\Sigma }}_{S,S}$ is positive definite because every nonzero vector supported on $S$ has positive $\mathrm{\Sigma }$-quadratic form, so it is invertible. Put $A={\mathrm{\Sigma }}_{Y,S}{\mathrm{\Sigma }}_{S,S}^{-1}$ and $U=Y-{\mu }_Y-A(Z-{\mu }_Z)$. Then $\mathrm{Cov}(U,Z)=0$ and $\mathrm{Cov}(U)=K_{ij\mid S}$. For every nonzero $u\in {\mathbb{R}}^2$, the quadratic form of $\mathrm{\Sigma }$ at $(u,-{\mathrm{\Sigma }}_{S,S}^{-1}{\mathrm{\Sigma }}_{S,Y}u)$ equals $u^T{K}_{ij\mid S}u>0$. Thus $K_{ij\mid S}$ is positive definite; for empty $S$ this follows directly from the principal $2\times 2$ covariance block.

The vector $(U,Z)$ is a linear image of $X$, hence is jointly Gaussian by [F1]. Its covariance is block diagonal with blocks $K_{ij\mid S}$ and ${\mathrm{\Sigma }}_{S,S}$. By [F2], the joint density factors as the product of the two Gaussian densities, since the inverse and determinant of a block-diagonal covariance split by blocks. Integrating over measurable rectangles shows $U$ and $Z$ are independent by [F5]. It follows that, conditionally on $Z$, $Y$ is the translate ${\mu }_Y+A(Z-{\mu }_Z)+U$ and has conditional covariance $K_{ij\mid S}$.

If $(K_{ij\mid S}{)}_{12}=0$, the positive-definite bivariate Gaussian density of $U$ factors into its one-coordinate densities. Thus the coordinates of $U$ are independent. Since $U$ is independent of $Z$, the conditional law of $X_i,X_j$ given $Z$ is the product of its conditional marginals. Integrating bounded measurable functions against this product conditional law gives the identity in [F3], hence conditional independence.

Conversely assume the conditional independence in the Statement. Apply [F3] to the sine and cosine functions of each coordinate and combine the four real identities to obtain factorization of the conditional characteristic function at $(1,1)$. By step 2.1, the joint conditional characteristic function is the product of the marginal factors times $\exp (-(K_{ij\mid S}{)}_{12})$. All other factors are nonzero; therefore $\exp (-(K_{ij\mid S}{)}_{12})=1$. The covariance entry is real, so $(K_{ij\mid S}{)}_{12}=0$.

The diagonal entries of $K_{ij\mid S}$ are positive by step 1.1. Its off-diagonal entry is zero exactly when the normalized entry ${\rho }_{ij\mid S}$ is zero, proving both implications.

Put $Y=(X_i,X_j)$ and $Z=X_S$. For nonempty $S$, define $B={\mathrm{\Sigma }}_{Y,S}{\mathrm{\Sigma }}_{S,S}^{-1}$ and $U=Y-{\mu }_Y-B(Z-{\mu }_S)$. Covariance algebra gives $\mathrm{Cov}(U)=K_{ij\mid S}$ and $\mathrm{Cov}(U,Z)=0$. The vector $(U,Z)$ is jointly Gaussian by [F5], since every scalar projection is an affine scalar projection of $X$. Its covariance is block diagonal and positive definite by [F3] and positive definiteness of ${\mathrm{\Sigma }}_{S,S}$. Its density from [F4] factors into the Gaussian densities of $U$ and $Z$: both the determinant and the quadratic form split by blocks. Integrating over rectangles proves independence of $U$ and $Z$. For empty $S$, take $U=Y-{\mu }_Y$ with covariance $K_{ij\mid \mathrm{\varnothing }}$; independence from the empty conditioning tuple is automatic. Across observations the residual pairs are independent, and their entire sample is independent of the conditioning sample, because the joint observation densities multiply. The $S$ coordinates have a nondegenerate Gaussian density because their covariance is a positive-definite principal submatrix. If $\mathrm{\mid }S\mathrm{\mid }=0$, the intercept design has rank one. If $s=\mathrm{\mid }S\mathrm{\mid }>0$, successive independent sample points in ${\mathbb{R}}^s$ are affinely independent until there are $s+1$: after $r\le s$ affinely independent points, their affine span has dimension $r-1<s$, and the next point has a density, so lies in that span with probability zero by [F4]. Thus the intercept and $S$ design has rank $s+1$ almost surely. Conditional on that design, an orthonormal basis of its orthogonal complement has dimension $m=n-\mathrm{\mid }S\mathrm{\mid }-1$. In that basis the projected residual pairs are $m$ independent copies of this Gaussian residual; standardizing the two coordinates does not change their sample correlation. Thus the sample partial correlation has the same distribution as $R_m=\frac{{\sum }_{r=1}^m{U}_r{V}_r}{({\sum }_{r=1}^m{U}_r^2{)}^{1\mathrm{/}2}({\sum }_{r=1}^m{V}_r^2{)}^{1\mathrm{/}2}},m=n-\mathrm{\mid }S\mathrm{\mid }-1,$ for $m$ independent copies $(U_r,V_r)$ of the standardized pair, whose correlation is $\rho ={\rho }_{ij\mid S}$ by [F1]. The hypothesis gives $m\ge 3$. Their covariance block is positive definite by [F3], so the first residual sample column is nonzero almost surely, and conditional on that column the second has a density in ${\mathbb{R}}^m$. Its probability of lying in the first column's one-dimensional span is zero by [F4], since $m\ge 2$. Thus the two residual columns have rank two almost surely. Together with the full-rank intercept and $S$ design, this makes the centered sample covariance block on $\{i,j\}\cup S$ positive definite. Therefore $R_m\in (-1,1)$ almost surely and the Fisher transform is defined.

Represent $U_r=X_r$ and $V_r=\rho X_r+\sqrt{1-{\rho }^2}{E}_r$ with independent standard normal vectors $X,E\in {\mathbb{R}}^m$. Put $A=\mathrm{\parallel }X\mathrm{\parallel }$, $Z=⟨E,X\mathrm{/}A⟩$, and $W=\mathrm{\parallel }E-ZX\mathrm{/}A\mathrm{\parallel }$. Rotational invariance of the standard Gaussian density implies that $A^2\sim {\chi }_m^2$, $Z\sim N(0,1)$, and $W^2\sim {\chi }_{m-1}^2$ are independent. Direct substitution gives $R_m=\frac{q}{\sqrt{q^2+W^2}},q=\frac{\rho A}{\sqrt{1-{\rho }^2}}+Z,$ and hence $g(R_m)=\mathrm{arsinh}(q\mathrm{/}W)$. Rotational invariance follows directly from the standard Gaussian density, and it makes $A,Z,W$ independent. Also $\mathrm{arsinh}(\rho \mathrm{/}\sqrt{1-{\rho }^2})=g(\rho )$.

Let $B=M\mathrm{/}\sqrt{1-M^2}$ and $L=4B+2$. On the event $\mathrm{\mid }A\mathrm{/}\sqrt{m}-1\mathrm{\mid }\le \delta ,\mathrm{\mid }W\mathrm{/}\sqrt{m}-1\mathrm{\mid }\le \delta ,\mathrm{\mid }Z\mathrm{\mid }\mathrm{/}\sqrt{m}\le \delta ,$ where $0<\delta \le 1\mathrm{/}2$, one has $\mid \frac{q}{W}-\frac{\rho }{\sqrt{1-{\rho }^2}}\mid \le \frac{(2B+1)\delta }{1-\delta }\le L\delta \mathrm{.}$ Since $\mathrm{\mid }{\mathrm{arsinh}}^{\mathrm{\prime }}(x)\mathrm{\mid }=1\mathrm{/}\sqrt{1+x^2}\le 1$, step 2.1 yields $\mathrm{\mid }g(R_m)-g(\rho )\mathrm{\mid }\le L\delta$.

For $Q\sim {\chi }_k^2$, its moment generating function, obtained by multiplying the $k$ one-dimensional Gaussian integrals, is $\mathbb{E}{e}^{sQ}=(1-2s{)}^{-k\mathrm{/}2}$ for $s<1\mathrm{/}2$. For $\delta >0$, Markov's inequality optimized at $s=\delta \mathrm{/}[2(1+\delta )]$ gives $\mathbb{P}(Q\mathrm{/}k\ge 1+\delta )\le e^{-k(\delta -\log (1+\delta ))\mathrm{/}2}$. For $0<\delta <1$, the negative choice $s=-\delta \mathrm{/}[2(1-\delta )]$ gives $\mathbb{P}(Q\mathrm{/}k\le 1-\delta )\le e^{-k(-\delta -\log (1-\delta ))\mathrm{/}2}$. Put ${\delta }_{+}=2u+u^2\le 3$ and ${\delta }_{-}=2u-u^2\ge u$. The inequalities $\delta -\log (1+\delta )={\int }_0^{\delta }x\mathrm{/}(1+x)dx\ge {\delta }^2\mathrm{/}8$ for $0\le \delta \le 3$ and $-\delta -\log (1-\delta )\ge {\delta }^2\mathrm{/}2$ imply $\mathbb{P}(\mathrm{\mid }\sqrt{Q\mathrm{/}k}-1\mathrm{\mid }>u)\le 2e^{-k{u}^2\mathrm{/}8}(0<u<1)\mathrm{.}$ Applying this to $A^2$ and $W^2$, and using $\mathrm{\mid }\sqrt{(m-1)\mathrm{/}m}-1\mathrm{\mid }\le 1\mathrm{/}m\le \delta \mathrm{/}2$, shows that $\mathrm{\mid }W\mathrm{/}\sqrt{m}-1\mathrm{\mid }>\delta$ implies $\mathrm{\mid }W\mathrm{/}\sqrt{m-1}-1\mathrm{\mid }>\delta \mathrm{/}2$. Thus for $2\mathrm{/}m\le \delta \le 1\mathrm{/}2$, $\mathbb{P}(\mathrm{\mid }A\mathrm{/}\sqrt{m}-1\mathrm{\mid }>\delta \text{ or }\mathrm{\mid }W\mathrm{/}\sqrt{m}-1\mathrm{\mid }>\delta )\le 4e^{-m{\delta }^2\mathrm{/}64}\mathrm{.}$ The standard normal moment generating function $\mathbb{E}{e}^{sZ}=e^{s^2\mathrm{/}2}$, with Markov's inequality optimized at $s=\delta \sqrt{m}$, gives $\mathbb{P}(\mathrm{\mid }Z\mathrm{\mid }\mathrm{/}\sqrt{m}>\delta )\le 2e^{-m{\delta }^2\mathrm{/}2}$. For $0<\delta <2\mathrm{/}m$, the trivial bound $1\le 6e^{-m{\delta }^2\mathrm{/}64}$ applies. Thus the complement of the event in step 3.1 has probability at most $6e^{-m{\delta }^2\mathrm{/}64}$ for every $0<\delta \le 1\mathrm{/}2$.

Set $\delta =t\mathrm{/}L$. Since $L\ge 2$ and $0<t\le 1$, step 3.1 applies and its complement contains the event in the Statement. Step 4.1 therefore bounds that event by $6\exp (-m{t}^2\mathrm{/}(64L^2))$. Taking $C_M=6$ and $c_M=(64L^2{)}^{-1}$ proves the claim.

Every consistent extension of a current pattern must respect each R1–R3 conclusion. For R1, the opposite orientation would create the new unshielded collider $i\to j\leftarrow k$ with $i,k$ nonadjacent. For R2, the opposite orientation would close the directed path $i\to k\to j$ into a directed cycle. For R3, if $j\to i$, acyclicity forces $k\to i$ and $\mathrm{\ell }\to i$ (the alternatives $i\to k$ or $i\to \mathrm{\ell }$ each close a directed cycle through $j$); these arrows create the new unshielded collider $k\to i\leftarrow \mathrm{\ell }$, since $k,\mathrm{\ell }$ are nonadjacent. Each contradiction is forbidden for a consistent extension. Thus all rule orientations are compelled, and the original DAG $G$ remains a consistent extension at every stage.

Every finite DAG has a topological order. In any nonempty induced subgraph, if every vertex had an incoming arrow, repeatedly following incoming arrows would revisit a vertex and create a directed cycle. Thus a source exists; remove one source and repeat on the remaining finite DAG. Listing the removed vertices in order gives a topological order, because an arrow's tail must be removed before its head. This argument uses only finite choices.

The R1–R3 closure reaches a final pattern after finitely many applications. Each scan checks finitely many rule instances on the finite vertex set; every nonterminal scan directs at least one previously undirected edge, and there are at most $\left(\genfrac{}{}{0px}{}{\mathrm{\mid }V\mathrm{\mid }}{2}\right)$ such edges. Therefore after finitely many scans a full scan applies no rule, so the final closed pattern $P$ used below exists.

Write $P$ for the final closed pattern. We claim that whenever $a\to b$ and $b-c$ is undirected in $P$, the edge $a-c$ is directed $a\to c$. If $a,c$ were nonadjacent, R1 would orient $b-c$ as $b\to c$, contradicting closure. If $c\to a$, then $c\to a\to b$ and R2 would orient $c-b$ as $c\to b$, also contradicting closure. It remains to rule out $a-c$ undirected.

Suppose such an undirected $a-c$ exists, and choose a counterexample for which the arrow $a\to b$ was first oriented as early as possible in the finite sequence of rule applications. If $a\to b$ was initially oriented as part of a collider $a\to b\leftarrow d$, then $a,d$ are nonadjacent. Since $d\to b-c$ cannot satisfy R1, $d$ is adjacent to $c$. If $c\to d$, R2 on $c-b$ applies along $c\to d\to b$. If $d\to c$, R1 on $d\to c-a$ gives $c\to a$, and R2 on $c-b$ then applies along $c\to a\to b$. If $d-c$ is undirected, R3 on $c-b$ applies with its other two vertices $a,d$. Each case contradicts that $P$ is closed.