PC algorithm

The PC algorithm learns conditional-independence structure from a collection of observed random variables. Its standard initialization is the complete undirected graph, which represents every pair as a candidate adjacency. It then tests conditional independence over increasing conditioning-set sizes, using subsets of current neighboring vertices. Whenever $X\perp Y\mid S$ is established, it removes $X-Y$ and records $S$ as a separating set.^[ref]

For an unshielded triple $X-Z-Y$ with $X,Y$ nonadjacent, a recorded separating set that excludes $Z$ supports the collider orientation $X\to Z\leftarrow Y$. Further orientation rules propagate directions while avoiding directed cycles and unsupported new collider patterns. For example, a chain $X\to Z\to Y$ typically has $X\perp Y\mid Z$, so its separating set contains $Z$; a collider $X\to Z\leftarrow Y$ instead has marginal independence in the simple three-variable graph, so the empty separating set identifies the collider.

The oracle guarantee assumes an acyclic causal model over the observed variables, causal sufficiency, correct conditional independence decisions and faithfulness of a directed acyclic graph. The output represents a class under Markov equivalence of directed acyclic graphs; it need not identify every arrow of one unique causal graph.

An arbitrary incomplete initial graph does not satisfy that guarantee. With only two genuinely adjacent dependent variables, starting with their edge absent cannot recover it: the skeleton stage only removes edges. PC initialization from a conditional independence graph is a qualified screening construction that retains the true skeleton and records the required separating information for absent pairs. In finite samples, incorrect early independence decisions can propagate through both edge removal and orientation.

With an exact conditional independence oracle and faithfulness of a directed acyclic graph, the skeleton phase of the PC algorithm deletes precisely the nonedges. A true edge cannot be D-separated by a set excluding its endpoints. For nonadjacent vertices, choose the later vertex $v$ in a topological ordering; its parents separate it from the earlier nonparent. True parent edges survive throughout, so this separator remains available among the algorithm's candidate neighbour sets. For an unshielded triple $u-v-w$, any recorded separator of $u,w$ excludes $v$ exactly when the triple is an unshielded collider. The skeleton and collider characterization of Markov equivalence therefore identifies the correct equivalence class. Directions compelled throughout that class give its completed partially directed acyclic graph.

Initialize the PC skeleton search with an estimated conditional independence graph to reduce candidate pairs and conditioning sets. An exact graph contains the true directed acyclic graph skeleton because it equals its moral graph under faithfulness. For initially absent pairs record the full complement as a separating set; an empty default can create false collider orientations. Estimation errors can affect this screening step.