Markov chain algorithms for generating sets uniformly at random


  • Alberto Policriti University of Udine, Italy
  • Alexandru I. Tomescu University of Udine, Italy and University of Bucharest, Romania



Extensional digraph, transitive set, set theory, random generation, Markov chain.


In this paper we tackle the problem of generating uniformly at random two representative types of sets with n elements: transitive sets and weakly transitive sets, that is, transitive sets with atoms. A set is said to be transitive if any of its elements is also a subset of it; a set is weakly transitive if any of its elements, unless disjoint from it, is also a subset of it. We interpret such sets as (weakly) extensional acyclic digraphs—that is, acyclic digraphs whose (non-sink) vertices have pairwise different out-neighborhoods—and employ a Markov chain technique already given for acyclic digraphs. We thus propose Markov chain-based algorithms for generating uniformly at random (weakly) extensional acyclic digraphs with a given number of vertices. The Markov chain is then refined to generate such digraphs which are also simply connected, and digraphs in which the number of arcs is fixed.





Special Issue Bled'11