2017/05/26 by Megan Bernstein, Bernstein, Megan, Prasad Tetali +1
Computer Science · Mathematics · #05C81 #60J10 #60J20 #Bayesian Methods and Mixture Models #Bayesian Modeling and Causal Inference #Combinatorics (math.CO) #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.1705.09717
openalex publication_date 2017/05/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider sampling and enumeration problems for Markov equivalence classes. We create and analyze a Markov chain for uniform random sampling on the DAGs inside a Markov equivalence class. Though the worst case is exponentially slow mixing, we find a condition on the Markov equivalence class for polynomial time mixing. We also investigate the ratio of Markov equivalence classes to DAGs and a Markov chain of He, Jia, and Yu for random sampling of sparse Markov equivalence classes.