Markov chain algorithms for generating sets uniformly at random

Alberto Policriti, Alexandru I. Tomescu


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.


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

Full Text:



ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications