= Solution
The <global Markov property for a directed acyclic graph> requires, for all pairwise disjoint vertex sets $A,B,C$, that <D-separation> of $A$ and $B$ by $C$ in $G$ implies $Z_A\perp Z_B\mid Z_C$. Two <Markov equivalent directed acyclic graphs> encode exactly the same such <D-separations>. The structural characterization is that they have the same <skeleton of a directed graph> and the same <unshielded colliders>. A distribution has <faithfulness of a directed acyclic graph> when its <conditional independences> are exactly those encoded by <D-separation>; this includes the global Markov implication as well as its converse.
The population <PC algorithm> uses an exact <conditional independence> oracle. Start with the complete <undirected graph>, and conditioning-set size $\ell=0$. At each size, examine ordered adjacent pairs $(u,v)$. Test subsets $C\subseteq\operatorname{Adj}(u)\setminus\{v\}$ of size $\ell$ until independence $Z_u\perp Z_v\mid Z_C$ is found or all such subsets have been examined. On finding it, delete $u-v$ and record a symmetric separating set $\operatorname{Sep}(u,v)=\operatorname{Sep}(v,u)=C$. Ordered pairs ensure that subsets from either endpoint's neighbours are considered. Increase $\ell$ until no adjacent ordered pair has enough remaining neighbours to supply a set of that size. Rechecking eligibility after deletion, or freezing the neighbours at each level and then deleting, gives the same population skeleton under the hypothesis below.
Next, for each unshielded triple $u-v-w$ with $u,w$ nonadjacent, orient $u\to v\leftarrow w$ precisely when $v\notin\operatorname{Sep}(u,w)$. Propagate directions that are forced without introducing a directed cycle or an additional <unshielded collider>. In particular, $a\to b-c$ with $a,c$ nonadjacent forces $b\to c$; an undirected edge $a-b$ with a directed path from $a$ to $b$ forces $a\to b$; and $a-b,a-c,a-d,c\to b,d\to b$ with $c,d$ nonadjacent forces $a\to b$. The first avoids a new <unshielded collider>, the second a directed cycle. For the third, $b\to a$ would force $c\to a$ and $d\to a$ to avoid cycles, creating the prohibited <unshielded collider> $c\to a\leftarrow d$.
For a fully specified exact completion, list all acyclic orientations of the recovered skeleton which extend the collider arrows and have exactly the recorded <unshielded colliders>. Direct an edge if and only if all listed graphs orient it the same way; otherwise leave it undirected. This finite enumeration implements the definition of the <completed partially directed acyclic graph>; orientation propagation is the usual efficient way to obtain the same completion. The equivalence-class proof below uses the exact completion description and does not need an unproved completeness claim about a chosen subset of propagation rules.
To prove correctness, assume <faithfulness of a directed acyclic graph> to $G^0$. A true edge $u\to v$ cannot be <D-separated> by any set excluding its endpoints: its length-one path is always active. Thus a true edge is never deleted. Conversely, take nonadjacent $u,v$ and choose their order so that $u$ is earlier than $v$ in a <topological ordering> of $G^0$. Then $u$ is a nondescendant and nonparent of $v$. Its parent set $\operatorname{Pa}(v)$ gives <D-separation> of $u$ and $v$. To see this local graphical fact, a path beginning $v\leftarrow q$ is blocked by the conditioned parent $q$, a noncollider. A path beginning with an arrow out of $v$ must encounter a first <collider> before reaching the nondescendant $u$. That collider is a descendant of $v$, and neither it nor any of its descendants can be a parent of $v$ in an acyclic graph. Hence conditioning on $\operatorname{Pa}(v)$ does not open it.
All parent edges survive. If $u-v$ has not already been deleted, $\operatorname{Pa}(v)$ remains among $v$'s neighbours excluding $u$. It is therefore tested by size $|\operatorname{Pa}(v)|$, and faithfulness forces deletion. The size loop cannot stop prematurely while this set remains eligible. This proves exact recovery of the <skeleton of a directed graph>.
For an unshielded triple $u-v-w$, if it is a noncollider in $G^0$, its length-two path remains active unless $v$ is conditioned on. Thus every separator of $u,w$ contains $v$. If it is a collider, conditioning on $v$ opens the length-two path, so no separator can contain $v$. Faithfulness turns these graphical statements into the recorded separator test. Therefore the collider phase recovers precisely all <unshielded colliders>. By the <skeleton and collider characterization of Markov equivalence>, the acyclic extensions with exactly these colliders are exactly the <Markov equivalence of directed acyclic graphs> class of $G^0$. In particular that set is nonempty, and the completion returns its <CPDAG>. This proves <population PC correctness under faithfulness>.
For the four-variable example, the only removable pairs are $2,4$, with separator $\varnothing$, and $1,3$, with separator $\{2,4\}$. The remaining skeleton has edges $1-2,1-4,2-3,3-4$. The unshielded triples $2-1-4$ and $2-3-4$ both have center outside the separator of $2,4$, so both are <unshielded colliders>. Every remaining edge is thereby oriented:
$$
\boxed{G^0:\quad 2\longrightarrow1\longleftarrow4,\qquad 2\longrightarrow3\longleftarrow4.}
$$
The other two unshielded triples are noncolliders, consistent with the separator $\{2,4\}$ of $1,3$. There is no undirected edge left, so the equivalence class consists of this unique <Directed acyclic graph>. This identification is about the given faithful observational distribution; general <PC algorithm> outputs need not identify a unique causal direction.
Back to article page
