# Lower Bounds on the Size of Markov Equivalence Classes

arXiv: https://arxiv.org/abs/2506.20933 · HTML: https://mlsanity.com/paper/2506.20933/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 41 references that are in the map.
- First posted on arXiv 26 Jun 2025.

## Builds on (most cited first, 11 of 11)

- [Learning Bayesian Networks: The Combination of Knowledge and Statistical Data](https://mlsanity.com/paper/1302.6815/) (2013)
- [Causal Inference in the Presence of Latent Variables and Selection Bias](https://mlsanity.com/paper/1302.4983/) (2013)
- [Learning Equivalence Classes of Bayesian Networks Structures](https://mlsanity.com/paper/1302.3566/) (2013)
- [Causal Networks: Semantics and Expressiveness](https://mlsanity.com/paper/1304.2379/) (2013)
- [A Transformational Characterization of Equivalent Bayesian Network Structures](https://mlsanity.com/paper/1302.4938/) (2013)
- [Partition MCMC for inference on acyclic digraphs](https://mlsanity.com/paper/1504.05006/) (2015)
- [Directed Cyclic Graphical Representations of Feedback Models](https://mlsanity.com/paper/1302.4982/) (2013)
- [Size of Interventional Markov Equivalence Classes in Random DAG Models](https://mlsanity.com/paper/1903.02054/) (2019)
- [Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs with Applications](https://mlsanity.com/paper/2205.02654/) (2022)
- [A Polynomial-Time Algorithm for Deciding Markov Equivalence of Directed Cyclic Graphical Models](https://mlsanity.com/paper/1302.3600/) (2013)
- [Enumerating Markov Equivalence Classes of Acyclic Digraph Models](https://mlsanity.com/paper/1301.2272/) (2013)

## Built on by (most cited first, 1 of 1)

- [A Topological Sorting Criterion for Random Causal Directed Acyclic Graphs](https://mlsanity.com/paper/2605.06288/) (2026)

## Abstract (arXiv)

Causal discovery algorithms typically recover causal graphs only up to their Markov equivalence classes unless additional parametric assumptions are made. The sizes of these equivalence classes reflect the limits of what can be learned about the underlying causal graph from purely observational data. Under the assumptions of acyclicity, causal sufficiency, and a uniform model prior, Markov equivalence classes are known to be small on average. In this paper, we show that this is no longer the case when any of these assumptions is relaxed. Specifically, we prove exponentially large lower bounds for the expected size of Markov equivalence classes in three settings: sparse random directed acyclic graphs, uniformly random acyclic directed mixed graphs, and uniformly random directed cyclic graphs.