论文标题
关于马尔可夫等效类的数量和大小随机定向无环图
On the number and size of Markov equivalence classes of random directed acyclic graphs
论文作者
论文摘要
在定向无环图的因果推断中，边缘的方向通常仅回收到马尔可夫等效类。我们研究了马尔可夫等效类别的均匀随机定向的无环图。使用塔分解，我们表明马尔可夫等效类数量和定向无环形图之间的比率在地点数量进入无穷大时接近正常数。对于典型的定向无环图，其Markov等效类中的预期元素数量保持界限。更确切地说，我们证明，对于均匀选择的定向无环图，其Markov等效类的大小具有超多项式尾巴。
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.
