2022/09/09 by Dominik Schmid, Schmid, Dominik, Allan Sly +1 · 3 citations
Mathematics · #60H05 #60K99 #62H22 #68R99 #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Graph theory and applications #Probability (math.PR) #Random Matrices and Applications #Statistics Theory (math.ST)
paper · pdf · doi:10.48550/arxiv.2209.04395
openalex publication_date 2022/09/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In causal inference on directed acyclic graphs, the orientation of edges is in general only recovered up to Markov equivalence classes. We study Markov equivalence classes of uniformly random directed acyclic graphs. Using a tower decomposition, we show that the ratio between the number of Markov equivalence classes and directed acyclic graphs approaches a positive constant when the number of sites goes to infinity. For a typical directed acyclic graph, the expected number of elements in its Markov equivalence class remains bounded. More precisely, we prove that for a uniformly chosen directed acyclic graph, the size of its Markov equivalence class has super-polynomial tails.