Markov chain algorithms for generating sets uniformly at random - Policriti, Alberto (Ars mathematica contemporanea, 2013)
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.
Keywords: extensional digraph; Markov chain; random generation; set theory; transitive set