= Population PC correctness under faithfulness
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>.
Back to article page
