AbstractWe show how to sample acyclic digraphs uniformly at random through recursive enumeration. This provides an exactmethod which avoids the convergence issues of the alternative Markov chain methods. The limiting behaviour of thedistribution of acyclic digraphs also allows us to sample arbitrarily large acyclic digraphs. Finally we discuss howto include various restrictions in the combinatorial enumeration for efficient uniform sampling of the correspondinggraphs.Keywords: Random graph generation, acyclic digraphs, recursive enumeration, Bayesian networks1. IntroductionDirected acyclic graphs (DAGs) are the basic representation of the structure underlying Bayesian networks, whichin turn represent multivariate probability distributions (Lauritzen, 1996; Neapolitan, 2004). They are largely used inmany fields of applied statistics with especially important applications in biostatistics, such as the learning of epistaticrelationships (Jiang et al., 2011). The estimation of DAGs or their equivalence class is a hard problem and methodsfor their efficient reconstruction from data is a very active field of resea rch: a recent review is given by Daly et al.,2011 while some new methodological developments for estimating high dimensional sparse DAGs are discussed byKalisch and Bu¨hlmann, 2007; Colombo et al., 2012. For simulation studies aimed at assessing the performance oflearning algorithms which reconstruct a graph from data, it is crucial to be able to generate uniform samples fromthe space of DAGs so that any structure related bias is removed. The only currently available method relies on theconstruction of a Markov chain whose properties ensure that the limiting distribution is uniform over all DAGs witha given number of vertices n. The strategy is based on a well known idea first suggested by M adigan and York (1995)as a Markov Chain Monte Carlo (MCMC) scheme in the context of Bayesian graphical models to sample from theposterior distribution of graphs conditional on the data. A specific algorithm for uniform sampling of DAGs wasfirst provided by Melanc¸on et al. (2001), with the advantage over the standard MCMC scheme of not requiring theevaluation of the sampled graphs’ neighbourhood size, at the expense of a slower convergence. The method waslater extended by Ide and Cozman (2002); Ide et al. (2004); Melanc¸on and Philippe (2004) to limit the sampling torestricted sets of DAGs. An R implementation was also recently provided by Scutari (2010). Since Markov chainbased algorithms pose non-negligible convergence and computational issues, in practice random upper or lower tri-angular adjacency matrices are often sampled to generate random ensembles for simulation studies [as for exampleimplemented in the pcalg R package of Kalisch et al. (2012)]. This method however does not provide uniformly dis-tributed graphs on the space of DAGs and could for example perform poorly to obtain starting points for hill-climbingalgorithms or slowly converging Markov chains by increasing the risk of remaining within a small neighbourhood ofcertain graphs and more inefficiently exploring the space. Likewise uniform sampling allows the correct evaluationof reconstructing algorithms. Finally, when evaluating the prevalence of certain features in a population, a uniformsample is essential. Here we therefore present a sampling strategy based on the recursive enumeration of DAGs butwhere no explicit listing is required.