On the number and size of Markov equivalence classes of random directed acyclic graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2022
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916412873768960 |
|---|---|
| author | Schmid, Dominik Sly, Allan |
| author_facet | Schmid, Dominik Sly, Allan |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2209_04395 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | On the number and size of Markov equivalence classes of random directed acyclic graphs Schmid, Dominik Sly, Allan Probability Combinatorics Statistics Theory 62H22, 60K99, 60H05, 68R99 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. |
| title | On the number and size of Markov equivalence classes of random directed acyclic graphs |
| topic | Probability Combinatorics Statistics Theory 62H22, 60K99, 60H05, 68R99 |
| url | https://arxiv.org/abs/2209.04395 |