Geodesic
Markov chain algorithms for generating sets uniformly at random
Ars Mathematica Contemporanea, Tome 6 (2013) no. 1, pp. 57-68.

Voir la notice de l'article provenant de la source Ars Mathematica Contemporanea website

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.
DOI : 10.26493/1855-3974.286.93a
Keywords: Extensional digraph, transitive set, set theory, random generation, Markov chain. 
@article{10_26493_1855_3974_286_93a,
     author = {Alberto Policriti and Alexandru I. Tomescu},
     title = {Markov chain algorithms for generating sets uniformly at random},
     journal = {Ars Mathematica Contemporanea},
     pages = {57--68},
     publisher = {mathdoc},
     volume = {6},
     number = {1},
     year = {2013},
     doi = {10.26493/1855-3974.286.93a},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.286.93a/}
}
TY  - JOUR
AU  - Alberto Policriti
AU  - Alexandru I. Tomescu
TI  - Markov chain algorithms for generating sets uniformly at random
JO  - Ars Mathematica Contemporanea
PY  - 2013
SP  - 57
EP  - 68
VL  - 6
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.286.93a/
DO  - 10.26493/1855-3974.286.93a
LA  - en
ID  - 10_26493_1855_3974_286_93a
ER  - 
%0 Journal Article
%A Alberto Policriti
%A Alexandru I. Tomescu
%T Markov chain algorithms for generating sets uniformly at random
%J Ars Mathematica Contemporanea
%D 2013
%P 57-68
%V 6
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.286.93a/
%R 10.26493/1855-3974.286.93a
%G en
%F 10_26493_1855_3974_286_93a
Alberto Policriti; Alexandru I. Tomescu. Markov chain algorithms for generating sets uniformly at random. Ars Mathematica Contemporanea, Tome 6 (2013) no. 1, pp. 57-68. doi : 10.26493/1855-3974.286.93a. http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.286.93a/

Cité par Sources :