Markov equivalence of directed acyclic graphs

Two Directed acyclic graphs are Markov equivalent when they encode the same D-separations for all disjoint sets of vertices. They consequently impose the same global Markov property for a directed acyclic graph, although their causal interpretations can differ.

The completed partially directed acyclic graph of a Markov equivalence of directed acyclic graphs class has their common skeleton of a directed graph. An edge is directed exactly when its orientation agrees in every member of the class, and is otherwise undirected. It can be constructed by enumerating all acyclic orientations with the prescribed unshielded colliders and retaining only the common directions; practical PC algorithms use orientation propagation instead of enumeration.

Two Directed acyclic graphs are Markov equivalent directed acyclic graphs if and only if they have the same skeleton of a directed graph and the same unshielded colliders. Thus these two structures determine the observational equivalence class. This structural theorem is what converts the skeleton and collider phases of the PC algorithm into identification of an equivalence class.