On expressiveness of the AMP chain graph interpretation

In this paper we study the expressiveness of the Andersson- Madigan-Perlman interpretation of chain graphs. It is well known that all independence models that can be represented by Bayesian networks also can be perfectly represented by chain graphs of the Andersson-Madigan- Perlman interpretation but it has so far not been studied how much more expressive this second class of models is. In this paper we calculate the exact number of representable independence models for the two classes, and the ratio between them, for up to five nodes. For more than five nodes the explosive growth of chain graph models does however make such enumeration infeasible. Hence we instead present, and prove the correctness of, a Markov chain Monte Carlo approach for sampling chain graph models uniformly for the Andersson-Madigan-Perlman interpretation. This allows us to approximate the ratio between the numbers of independence models representable by the two classes as well as the average number of chain graphs per chain graph model for up to 20 nodes. The results show that the ratio between the numbers of representable independence models for the two classes grows exponentially as the number of nodes increases. This indicates that only a very small fraction of all independence models representable by chain graphs of the Andersson-Madigan-Perlman interpretation also can be represented by Bayesian networks. © 2014, Springer International Publishing Switzerland.