= PC algorithm
{c}
The <PC algorithm> learns conditional-independence structure from a collection of observed <random variables>. Its standard initialization is the \b[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\mathrel\perp Y\mid S$ is established, it removes $X-Y$ and records $S$ as a separating set.<Causation, Prediction, and Search by Peter Spirtes, Clark Glymour and Richard Scheines>[Chapter 5, section 5.4.2, printed p. 117: complete-graph initialization and adjacency-set skeleton search]{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\mathrel\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.
Back to article page
