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.
翻译：在定向环流图的因果推断中,边缘方向一般只恢复到马尔科夫等等值等级。我们研究了统一随机定向环状图的马尔科夫等值类别。我们用塔分解法来显示,当点数达到无限时,Markov等值类别和定向环状图之间的比例接近正常数。对于典型定向环状图来说,其马科夫等值类中的预期元素数量仍然被捆绑。更确切地说,我们证明,对于统一选择的定向环状图来说,其Markov等值类的大小有超极效尾。
相关内容
微信扫码咨询专知VIP会员