Graphical Markov models determined by acyclic digraphs (ADGs), also called
directed acyclic graphs (DAGs), are widely studied in statistics, computer
science (as Bayesian networks), operations research (as influence diagrams),
and many related fields. Because different ADGs may determine the same Markov
equivalence class, it long has been of interest to determine the efficiency
gained in model specification and search by working directly with Markov
equivalence classes of ADGs rather than with ADGs themselves. A computer
program was written to enumerate the equivalence classes of ADG models as
specified by Pearl & Verma's equivalence criterion. The program counted
equivalence classes for models up to and including 10 vertices. The ratio of
number of classes to ADGs appears to approach an asymptote of about 0.267.
Classes were analyzed according to number of edges and class size. By edges,
the distribution of number of classes approaches a Gaussian shape. By class
size, classes of size 1 are most common, with the proportions for larger sizes
initially decreasing but then following a more irregular pattern. The maximum
number of classes generated by any undirected graph was found to increase
approximately factorially. The program also includes a new variation of orderly
algorithm for generating undirected graphs.

本文介绍了使用 Pearl 和 Verma 的等价标准确定的 ADGs 模型的等价类的枚举程序，分析了模型的各种属性，并且发现了等效类数量与 ADGs 数量之间的一个近似 0.267 的渐进比率。

无向无环图模型的马尔可夫等价类枚举

Enumerating Markov Equivalence Classes of Acyclic Digraph Models

In this paper, we unify the Markov theory of a variety of different types of
graphs used in graphical Markov models by introducing the class of loopless
mixed graphs, and show that all independence models induced by $m$-separation
on such graphs are compositional graphoids. We focus in particular on the
subclass of ribbonless graphs which as special cases include undirected graphs,
bidirected graphs, and directed acyclic graphs, as well as ancestral graphs and
summary graphs. We define maximality of such graphs as well as a pairwise and a
global Markov property. We prove that the global and pairwise Markov properties
of a maximal ribbonless graph are equivalent for any independence model that is
a compositional graphoid.

本文介绍了无环混合图这一类新的图形类型，研究显示在此类图形上满足 $m$-separation 的独立性模型都是组合图。文章进一步关注了一类特殊的无环混合图 —— 裸带图，证明了对于任何独立性模型，裸带图的全局和成对的马尔可夫性质是等价的。