Counting and Uniform Sampling from Markov Equivalent DAGs

Directed acyclic graphs (DAGs) are the most commonly used graphical model to represent causal relationships among a set of variables. In a DAG representation, a directed edge indicates a direct causal relationship between the corresponding variables. Under Markov property and faithfulness assumptions, conditional d-separation of variables in a DAG is in bijective correspondence with conditional independencies of the variables in the underlying joint probability distribution (Spirtes et al., 2000), and hence, a DAG representation demonstrates conditional independencies among its variables. The general approach for learning a causal structure is to use statistical data from the variables to find a DAG which is the most consistent with the conditional independencies in the given data. However, a DAG representation of a set of conditional independencies is not always unique. 1 This restricts the learning of the causal structure to Markov equivalence classes (MECs), where elements of each class represent the same set of conditional independencies.