Random Generation of Directed Acyclic Graphs

We propose a simple algorithm based on a Markov chain for generating acyclic digraphs with a given number of vertices uniformly at random. In addition, standard combinatorial techniques allow us to describe the overall shape and average edge density of an acyclic digraph. As an application, we were able to estimate the density function of classical statistics on acyclic digraphs.