Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 6 (2013) 57–68
Markov chain algorithms for
generating sets uniformly at random
Alberto Policriti
Dipartimento di Matematica e Informatica, Università di Udine,
Via delle Scienze, 206, 33100 Udine, Italy
Alexandru I. Tomescu ∗
Dipartimento di Matematica e Informatica, Università di Udine,
Via delle Scienze, 206, 33100 Udine, Italy
Department of Computer Science, University of Bucharest,
Str. Academiei, 14, 010014 Bucharest, Romania
Received 30 November 2011, accepted 11 April 2012, published online 1 June 2012
Abstract
In this paper we tackle the problem of generating uniformly at random two representa-
tive types of sets with n elements: transitive sets and weakly transitive sets, that is, transi-
tive 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 di-
graphs 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, transitive set, set theory, random generation, Markov chain.
Math. Subj. Class.: 03E75, 05C81, 05C20
∗Corresponding author.
E-mail addresses: alberto.policriti@uniud.it (Alberto Policriti), alexandru.tomescu@uniud.it (Alexandru I.
Tomescu)
Copyright c© 2013 DMFA Slovenije
58 Ars Math. Contemp. 6 (2013) 57–68
1 Introduction
Sets are basic mathematical and computational objects, and for this reason one is some-
times interested—in order to perform tests and evaluate benchmarks, collect statistical data,
(dis)prove conjectures, etc.—in generating uniformly at random a set of given size. In this
paper we tackle this problem by building on results originally given in the context of graphs.
The sets we consider belong to the standard Zermelo-Fraenkel set theory and thus con-
tain only other sets as elements. We focus on two archetypal sets: transitive sets and
weakly transitive sets, that is, sets s whose elements are also subsets of s, and sets s whose
elements, unless disjoint from s, are also subsets of s. A weakly transitive set s can be
simply seen as a transitive set with atoms (or ur-elements), the atoms of s constituting the
collection of elements of s disjoint from s. Zermelo-Fraenkel sets stand at the basis of
programming languages such as SETL [15], or the more recent {log} [3] and CLP(SET )
[5], and of the automatic proof-verifier Referee [14].
Since sets are nested structures, they are best represented by digraphs: vertices will
stand for sets, while the arc relation will correspond to the inverse of the membership
relation between them (→ ≡ 3). Such digraphs are acyclic, since membership is well-
founded, and weakly extensional, in the sense that distinct non-sink vertices have distinct
collections of out-neighbors. This digraph interpretation was exploited in [13] to give a
recurrence relation for the number of weakly transitive sets with n elements, generalizing
the result of [12] for transitive sets with n elements.
Under this graph-theoretic interpretation, we show in this paper how a Markov chain
based procedure for generating acyclic digraphs, first introduced in [9], can be transferred
to our set-theoretic universe. This Markov chain algorithm was already modified in [10]
to generate simply connected acyclic digraphs. The random generation of elements from
a particular class of acyclic digraphs modeling Bayesian networks was proposed in [6].
Finally, the same approach was used in [2] to generate deterministic acyclic automata.
Each of these examples can be seen as a less basic case than the one tackled here.
The idea behind this Markov chain technique is to start with an arbitrary weakly exten-
sional acyclic digraph (w.e.a. digraph, for short) on n vertices and apply a certain number
T of random local transformations which preserve weak extensionality and acyclicity. The
uniformity of the resulting distribution is basically proved by showing that any w.e.a. di-
graph on n vertices can be thus transformed into any other w.e.a. digraph on n vertices.
Like in the acyclic digraph case, we argue that the transformation rules are symmetric and
always allow reaching a specific digraph among the collection of w.e.a. digraphs with n
vertices. In our case, however, the most natural target digraph for this purpose turns out
to be an acyclic tournament on n vertices, that is, the digraph whose interpretation in the
universe of sets is the von Neumann numeral of n, the unique transitive set with n elements
well-ordered by the membership relation.
We prove here only ‘correctness’ and defer to future work computational aspects such
as estimations for the choice of T or an analysis of the mixing time of the Markov chain
[8]. As next research steps we also mention the random generation of hypersets, objects
for which the acyclicity requirement is dropped, and weak extensionality is accordingly
strengthened by an equality criterion based on the notion of bisimulation [1].
The paper is organized as follows. In Section 2 we give some notation and formally
introduce the above-mentioned notions. In Section 3 we put forward a Markov chain for
generating weakly extensional acyclic digraphs, while in Section 4 we propose a Markov
chain for generating simply connected weakly extensional acyclic digraphs. The latter can
A. Policriti and A. I. Tomescu: Markov chain algorithms for generating sets uniformly. . . 59
be easily adapted to generate extensional acyclic digraphs. Finally, in Section 5, we present
a Markov chain for generating w.e.a. digraphs on n vertices and m arcs, 0 6 m 6
(
n
2
)
,
which can also serve to generate acyclic digraphs with a given number of vertices and of
arcs.
2 Notation and preliminaries
We consider only finite simple digraphs, that is, without parallel arcs or self-loops. Given
a digraph D, we denote by V (D) its vertex set and by E(D) the set of its arcs. For any
v ∈ V (D), N+(v) stands for the set {u ∈ V (D) | (v, u) ∈ E(D)}, which is called the
out-neighborhood of v in D. Similarly, N−(v) = {u ∈ V (D) | (u, v) ∈ E(D)} is the
in-neighborhood of v. We will use d+(v) = |N+(v)| and d−(v) = |N−(v)|. A vertex
v ∈ V (D) such that d+(v) = 0 will be called a sink; if d−(v) = 0, it will be called a
source; we denote by I(D) the set of the sinks of D.
A digraph D is said to be simply connected if the underlying (undirected) graph of D
is connected. If (i, j) ∈ E(D), we will employ D − (i, j) as a shorthand for the digraph
obtained from D by removing the arc (i, j). Analogously, D+(i, j) is the digraph obtained
from D by the addition of the arc (i, j).
Definition 2.1. A digraph D is said to be
• extensional, if for any distinct u, v ∈ V (D) it holds that N+(u) 6= N+(v);
• weakly extensional, if for any distinct vertices u, v ∈ V (D) \ I(D), it holds that
N+(u) 6= N+(v).
If u, v are distinct vertices of a digraph D having N+(u) = N+(v), we say that u and v
collide. Note that this is not the case if D is acyclic and there is a directed path from u to
v. In particular, in an acyclic tournament there are no collisions (a tournament is a digraph
D such that for any distinct u, v ∈ V (D) either (u, v) ∈ E(D) or (v, u) ∈ E(D) holds,
but not both). Moreover, any e.a. digraph is simply connected.
Under the Zermelo-Fraenkel axioms, each set is uniquely characterized by its elements
(Extensionality Axiom), and the membership relation is well-founded (Foundation Axiom).
The standard universe of sets is von Neumann’s cumulative hierarchy, whose subset of
hereditarily finite sets is defined as the union, over all natural numbers i, of Vi, where
V0 = ∅, each level Vi+1 is P(Vi), and P(·) stands for the power-set operator. For example,
V1 = {∅}, V2 =
{
∅, {∅}
}
, V3 =
{
∅, {∅}, {{∅}}, {∅, {∅}}
}
.
∅
{∅}
{{∅}} {∅, {∅}}
{{{∅}}, {∅, {∅}}}
Figure 1: The digraph representation of a transitive set.
To faithfully represent a set x as a digraph, one considers the digraph Dx defined as
60 Ars Math. Contemp. 6 (2013) 57–68
Dx = (x, {(u, v) | u, v ∈ x, v ∈ u}).
See Figure 1 for an example. Since the membership relation between sets is well-founded,
such digraphs are acyclic. Moreover, if x is transitive, then Dx is also extensional, while
if x is weakly transitive, then Dx is weakly extensional. To see this, observe that if dis-
tinct non-sink vertices have the same out-neighborhood, then from the (weak) transitivity
assumption they correspond to the same set, contradicting the definition of Dx; see also
[13].
Given n > 1, we denote byWn the set of all w.e.a. digraphs with vertex set {1, . . . , n},
while Wcn denotes its subset of simply connected w.e.a. digraphs. Analogously, Wn,m
denotes the set of all w.e.a. digraphs with vertex set {1, . . . , n} and m arcs.
Definition 2.2. A discrete time finite stochastic process is a sequence X = (Xt : t ∈ N),
where Xt are S-valued random variables and S is a finite set, called the state space of X .
We say that X is a Markov chain if
∀t ∈ N, Pr(Xt+1 = st+1 |Xt = st, . . . , X0 = s0) = Pr(Xt+1 = st+1 |Xt = st).
Moreover, a Markov chain X is said to be time-homogeneous if
∀s, s′ ∈ S, ∃pss′ , ∀t ∈ N, Pr(Xt+1 = s |Xt = s′) = pss′ .
Definition 2.3. A time-homogeneous Markov chain over the state space S is said to be:
• irreducible iff ∀s, s′ ∈ S, ∃t ∈ N, Pr(Xt = s′ |X0 = s) > 0;
• aperiodic iff ∀s ∈ S, gcd{t ∈ N | Pr(Xt = s |X0 = s) > 0} = 1;
• symmetric iff ∀s, s′ ∈ S, pss′ = ps′s.
A well-known result (see, e.g., [8]) states that any finite, irreducible, aperiodic and
symmetric time-homogeneous Markov chain converges toward the uniform distribution on
its state space. Therefore, all the Markov chains presented here will be shown to satisfy
these three properties.
3 A Markov chain algorithm for generating w.e.a. digraphs
Let M be a Markov chain overWn, defined in Figure 2. Observe that M differs from the
Markov chain of [9] for generating arbitrary acyclic digraphs in the fact that arc deletions
and additions are done only provided that the resulting digraph is w.e.a.
Notice that for any t ∈ N and any two distinct states s, s′ ∈ Wn, Pr(Xt+1 = s |Xt =
s′) > 0 if and only if Pr(Xt+1 = s′ | Xt = s) > 0. To be more precise, the probability
of passing from a state s ∈ Wn to any other state s′ 6= s is either 0 or 1/n2, hence M is
symmetric. Moreover, for every s ∈ Wn the probability of remaining in s at any t > 0 is
positive, for example by choosing diagonal pairs (i, i), with i ∈ {1, . . . , n}. Therefore, if
M turns out to be irreducible, then it will also be aperiodic.
The initial state of this Markov chain and of the ones given in the next section can be
taken to be a linear digraph consisting of a directed path (n, n − 1, . . . , 1). The acyclicity
of a digraph on n vertices and m arcs can be established by a depth-first visit, in time
O(n +m). To test whether a digraph is (weakly) extensional, the algorithm in [4, Sec. 4]
can be used, taking time O(n+m).
A. Policriti and A. I. Tomescu: Markov chain algorithms for generating sets uniformly. . . 61
Let Xt denote the state of the Markov chain at time t. Suppose a couple of
integers (i, j) has been drawn uniformly at random from the set
{1, . . . , n} × {1, . . . , n}.
(T1) if (i, j) ∈ E(Xt) and
Xt − (i, j) is w.e., then Xt+1 = Xt − (i, j)
else Xt+1 = Xt.
(T2) if (i, j) /∈ E(Xt) and
Xt + (i, j) is w.e.a., then Xt+1 = Xt + (i, j)
else Xt+1 = Xt.
Figure 2: A Markov chain algorithm for generating w.e.a. digraphs.
Lemma 3.1. Let D be a w.e.a. digraph with E(D) 6= ∅. There exists an arc (u, v) ∈ E(D)
such that the digraph D − (u, v) is w.e.a.
Proof. Observe first that there exists u ∈ V (D) such that ∅ 6= N+(u) ⊆ I(D). If this
were not the case, then for all u in V (D) with N+(u) 6= ∅, there would exist a vertex u′
in D with N+(u′) 6= ∅ such that (u, u′) ∈ E(D). Since the same property holds for u′
as well, and as the number of vertices of D is finite, we can find a finite directed cycle,
contradicting hence the acyclicity of D.
Let now U(D) be the set of vertices of D with the above property, that is, U(D) def=
{u ∈ V (D) | ∅ 6= N+(u) ⊆ I(D)}. Let u0 ∈ U(D) be a vertex of minimum out-degree,
i.e., d+(u0) = min{d+(u) : u ∈ U(D)}. Since N+(u0) 6= ∅, let v0 be an element
of N+(u0). The arc (u0, v0) can be removed and the resulting digraph remains w.e.a.
Indeed, since u0 is among the vertices of minimum out-degree in U(D), in D − (u0, v0)
it will either be a sink, or it will be the only vertex in U(D − (u0, v0)) with out-degree
d+(u) − 1, hence having its out-neighborhood different from that of any other vertex of
D − (u0, v0).
Theorem 3.2 (Irreducibility of M ). Let M be the Markov chain defined over the spaceWn
together with the transition rules T1 and T2. Given two distinct digraphs D and H inWn,
there exists in M a sequence of transitions D = D0 → D1 → · · · → Dp−1 → Dp = H ,
where p > 1 and Di ∈ Wn, for all 0 6 i 6 p. Such a sequence exists with length at most
n2 − n.
Proof. Since M is symmetric, it suffices to show that there exists a sequence of transitions
from any given w.e.a. digraph D ∈ Wn to a fixed element O inWn. For our purpose here,
we will choose O to be the unique totally disconnected digraph, that is, having E(O) = ∅.
From Lemma 3.1, we get that there exists an arc (u, v) ∈ E(D) such that D− (u, v) is
w.e.a. Using rule (T1), we can step from D to D − (u, v). Repeating the above argument
a finite number of steps, we arrive at O. The number of transitions from D to O is at most
n(n− 1)/2, and this is obtained when D is a tournament.
4 A Markov chain algorithm for generating e.a. digraphs
Instead of generating e.a. digraphs, we place ourselves in a more general setting, that of
generating simply connected w.e.a. digraphs. Afterwards, we will argue that, with minor
62 Ars Math. Contemp. 6 (2013) 57–68
changes, the proposed Markov chain can generate e.a. digraphs. Let M c be the Markov
chain overWcn whose transitions between states are given in Figure 3. This Markov chain
is adapted from [10], with the difference that arc deletions, additions, or reversals are done
only if the resulting digraph is simply connected and w.e.a. This simple modification,
however, requires a totally new and more involved proof of irreducibility.
Just as in the previous section, the probability of passing from a state s ∈ Wcn to any
other state s′ 6= s is either 0 or 1/n2, implying that M c is symmetric. Likewise, the
aperiodicity of M c will be implied by its irreducibility and by the fact that for every state
in Wcn there is a positive probability to remain in that state (by choosing diagonal pairs
(i, i)). Even if the two transition rules of M c are not entirely specular, one can think of M c
as having three basic transitions: (1) removal of an arc, (2) reversal of an arc, (3) addition
of an arc. According to this view, M c is entirely symmetric.
Let Xt denote the state of the Markov chain at time t. Suppose a couple of
integers (i, j) has been drawn uniformly at random from the set
{1, . . . , n} × {1, . . . , n}.
(Tc1) if (i, j) ∈ E(Xt) then
(a) if Xt − (i, j) is simply connected and w.e., then Xt+1 = Xt − (i, j),
else
(b) if Xt − (i, j) + (j, i) is w.e.a., then Xt+1 = Xt − (i, j) + (j, i),
(c) else Xt+1 = Xt.
(Tc2) if (i, j) /∈ E(Xt), then
(a) if Xt + (i, j) is w.e.a., then Xt+1 = Xt + (i, j),
(b) else Xt+1 = Xt.
Figure 3: A Markov chain algorithm for generating simply connected w.e.a. digraphs.
To show the irreducibility of the Markov chain M c, it is useful to partition the vertices
of an acyclic digraph according to the maximum length of a directed path to a sink of the
digraph. Complying with standard set-theoretic notation, we will make use of the following
notion.
Definition 4.1. Given an acyclic digraph D, the rank of a vertex v ∈ V (D) is recursively
defined as
rk(v) = 1 +max{rk(u) : (v, u) ∈ E(D)},
where rk(v) = 0 if v is a sink.
Clearly, the following lemma holds.
Lemma 4.2. Given an acyclic digraph D, if v, u ∈ V (D) and rk(v) 6= rk(u), then
N+(v) 6= N+(u) holds.
Throughout the subsequent two proofs we employ the following notation: given an
acyclic digraph D and a vertex v of D,
R(v)
def
= {u ∈ V (D) | u 6= v and rk(u) 6 rk(v)}.
A. Policriti and A. I. Tomescu: Markov chain algorithms for generating sets uniformly. . . 63
Theorem 4.3 (Irreducibility of M c). Let M c be the Markov chain defined over the space
Wcn together with the transition rules Tc1 and Tc2. Given two distinct digraphs D and H
inWcn, there exists in M c a sequence of transitions D = D0 → D1 → · · · → Dp−1 →
Dp = H , where p > 1 and Di ∈ Wcn, for all 0 6 i 6 p. Such a sequence exists with
length at most (3n2 − 7n+ 4)/2.
Proof. As before, first we will show that there exists a sequence of transitions from any
given w.e.a. digraph D ∈ Wcn to an element T (D) in Wcn, where T (D) is an acyclic
tournament, with the additional property that whenever rk(v) > rk(u) in D, rk(v) > rk(u)
also holds in T (D). Then, given any D and H inWcn, we will show that there is a sequence
of transitions from T (D) to T (H), completing hence the proof.
To show the former claim, we proceed as follows. Pick a vertex v ∈ V (D), in decreas-
ing order of rank (when more vertices of the same maximum rank exist, pick an arbitrary
one). Apply rule (Tc2) and add arcs from v to all the vertices u ∈ R(v) \ N+(v), in de-
creasing order on the rank of the elements of R(v) \ N+(v). Note that this is possible,
first of all, because the addition of an arc (v, u) does not create a cycle in the resulting
digraph. Second, observe that the subdigraph of D induced by the vertices V (D) \ R(v)
is an acyclic tournament. Therefore, an arc addition would create a collision only between
v and a vertex w ∈ R(v). This is however not the case, since after the first addition of
such an arc, rk(v) becomes strictly greater than rk(w), for all w ∈ R(v), and Lemma 4.2
guarantees the absence of collisions.
Denote by T (D) the acyclic tournament obtained at the end of this process. Since for
any vertex v we have added arcs only to those vertices of rank less than or equal to v, we
also have that whenever rk(v) > rk(u) in D, the same holds in T (D).1
Passing on to the latter point, observe that for any w.e.a. digraph D, since T (D) is a
tournament, there are no two distinct elements of the same rank in T (D), and thus {rk(v) :
v ∈ V (T (D))} = {0, . . . , n−1}. Hence, to each digraph T (D) we can uniquely associate
a linear order ≺T (D) on V (D) defined in the following way: for all u, v ∈ V (T (D))
u ≺T (D) v iff rk(u) < rk(v) in T (D).
We now show that given two orders x0 ≺T (D) x1 ≺T (D) · · · ≺T (D) xn−1 and
y0 ≺T (H) y1 ≺T (H) · · · ≺T (H) yn−1, where {xi : 0 6 i 6 n − 1} = {yi : 0 6
i 6 n− 1} = {1, . . . , n}, we can transform T (D) in T (H), applying rule (Tc1).
Observe first that for any two consecutive elements xi ≺T (D) xi+1 (0 6 i < n− 1) it
holds that N+(xi+1) = N+(xi) ∪ {xi}. Therefore, applying rule (Tc1) on T (D), the arc
(xi, xi+1) cannot be removed (by (a)), but can be reversed (by (b)). In the resulting acyclic
tournament T (D′), xi and xi+1 have swapped positions, i.e., xi+1 ≺T (D′) xi. Starting
from position i = 0 all the way to i = n − 1, apply the following procedure. If yi = xj ,
(i < j 6 n − 1), then bring xj to position i by iteratively reversing the arcs (xj , xj−1),
(xj , xj−2), . . . ,(xj , xi).
The maximum number of transitions to pass from D to T (D) is
(
n
2
)
− (n − 1) =
(n2 − 3n + 2)/2, number obtained when the underlying graph of D is a tree, thus having
n − 1 edges. To pass from T (D) to T (H),
(
n
2
)
transitions are required at most, when all
the arcs of T (D) have to be reversed. Hence, to pass between two arbitrary D and H in
Wcn, we need at most (3n2 − 7n+ 4)/2 transitions.
1However, the converse in general does not hold.
64 Ars Math. Contemp. 6 (2013) 57–68
Let us denote by En the set of all e.a. digraphs with vertex set {1, . . . , n}. The Markov
chain illustrated in Figure 3 can be transformed into an irreducible, aperiodic and symmet-
ric Markov chain, Me, for the generation of digraphs from En. The transitions between
two states in Me are given in Figure 4. The analogue of Theorem 4.3 holds for Me as well.
Let Xt denote the state of the Markov chain at time t. Suppose a couple of
integers (i, j) has been drawn uniformly at random from the set
{1, . . . , n} × {1, . . . , n}.
(Te1) if (i, j) ∈ E(Xt) then
(a) if Xt − (i, j) is extensional, then Xt+1 = Xt − (i, j),
else
(b) if Xt − (i, j) + (j, i) is e.a., then Xt+1 = Xt − (i, j) + (j, i),
(c) else Xt+1 = Xt.
(Te2) if (i, j) /∈ E(Xt), then
(a) if Xt + (i, j) is e.a., then Xt+1 = Xt + (i, j),
(b) else Xt+1 = Xt.
Figure 4: A Markov chain algorithm for generating e.a. digraphs.
5 A Markov chain algorithm for generating w.e.a. digraphs with a
given number of arcs
A Markov chain Ma for generating w.e.a. digraphs with vertex set {1, . . . , n} and m arcs is
given in Figure 5. It will immediately follow from the proof of its irreducibility—Theorem
5.1 below—that Ma can also generate uniformly at random acyclic digraphs with a given
number of vertices and a fixed number of arcs, by simply swapping two arcs if the resulting
digraph is acyclic. Note that controlling the number of arcs was already considered in
the literature: [9] proposed generating acyclic digraphs with a bounded number of arcs,
or whose vertices have a bounded degree; [7] proposed generating acyclic digraphs with
bounded induced width, a complexity measure arising from artificial intelligence.
The probability of passing from a state s ∈ Wn,m to any other state s′ 6= s is either 0
or 1/n4, implying that Ma is symmetric. As previously, for any state s ∈ Wn,m there is a
positive probability to remain in s. Our next theorem shows that Ma is indeed irreducible.
If m < n − 1, the initial state of the Markov chain can be a digraph whose arcs form a
directed path of length m. Otherwise, the initial state can be a directed path (n, n−1, . . . , 1)
together with m− (n− 1) arbitrary arcs of the form (i, j), where i > j.
Theorem 5.1 (Irreducibility of Ma). The Markov chain Ma is irreducible.
Proof. First, if m = 0,Wn,m consists only of the totally disconnected digraph. Assuming
that m > 0, we show that any digraph D ∈ Wn,m can be transformed, by transitions of
Ma, into a digraph K(D) ∈ Wn,m, satisfying the following two properties:
i) for all v ∈ V (D) such that rk(v) > 1 in K(D), it holds that N+(v) = R(v) in
K(D);
ii) there is only one v ∈ V (D) such that rk(v) = 1 in K(D).
A. Policriti and A. I. Tomescu: Markov chain algorithms for generating sets uniformly. . . 65
Let Xt denote the state of Ma at time t. Suppose two pairs of integers
(i1, jj) and (i2, j2) have been drawn uniformly at random and independently
from the set {1, . . . , n} × {1, . . . , n}.
if (i1, j1) ∈ E(Xt) and (i2, j2) /∈ E(Xt), then
if Xt − (i1, j1) + (i2, j2) is w.e.a., then Xt+1 = Xt − (i1, j1) + (i2, j2),
else Xt+1 = Xt.
Figure 5: A Markov chain algorithm for generating w.e.a. digraphs on n vertices and
m arcs.
To show this, we argue as in the proof of Theorem 4.3, paying particular attention to
preserving m arcs at each intermediate step. Observe that if D fails to satisfy i) or ii), then
it must own a vertex v such that N+(v) ( R(v). Indeed, first note that N+(v) ⊆ R(v)
holds for any vertex v, since D is acyclic. If D does not satisfy i) and v ∈ V (D) is a vertex
with rk(v) > 1 and N+(v) 6= R(v), then N+(v) ( R(v) immediately follows. If D owns
two distinct vertices v′ and v′′ of rank 1, then v′′ ∈ R(v′) \N+(v′).
Therefore, as long as D fails to satisfy one of the above conditions i) or ii), apply
the following transformation to it. Pick a vertex v ∈ V (D) inclusion-maximal among the
vertices of maximum rank having N+(v) ( R(v), and consider all the elements u ∈ R(v)\
N+(v), in decreasing order on rank. Take t ∈ V (D) a vertex whose out-neighborhood is
inclusion-minimal among the vertices of rank 1. Arguing as in the proof of Lemma 3.1, any
arc (t, s) leading from t to an arbitrary sink s ∈ V (D) can be removed without disrupting
the weak extensionality of D. Replace arc (t, s) with arc (v, u) by a transition of Ma.
This is possible, since, on the one hand, the addition of the arc (v, u) does not create a
cycle in the resulting digraph. On the other hand, as before, the subdigraph of D induced
by the vertices V (D)\R(v) is an acyclic tournament. Therefore, one such arc addition can
create a collision only between v and some vertex w ∈ R(v). This is not the case, since
after the first addition of an arc from v to a maximum rank vertex in R(v), rk(v) becomes
strictly greater than rk(w), for all w ∈ R(v), and Lemma 4.2 guarantees the absence of
collisions. It should be clear that the above procedure stops after a finite number of steps,
and that the final digraph satisfies conditions i) and ii).
It remains to show that, given two digraphs D and H inWn,m, there exists a sequence
of transitions in Ma from K(D) to K(H). To any acyclic digraph K whose vertices
of positive rank have pairwise distinct ranks we can associate a partial order ≺K in the
following way: for all u, v ∈ V (K),
u ≺K v iff rk(u) < rk(v) in K.
For expository purposes, assume that we also order the sinks of K is an arbitrary way so
that ≺K is a linear order on the vertices of K. Therefore, we have to show that we can
transform any order x0 ≺K(D) x1 ≺K(D) · · · ≺K(D) xn−1 into y0 ≺K(H) y1 ≺K(H)
· · · ≺K(H) yn−1, where {xi : 0 6 i 6 n− 1} = {yi : 0 6 i 6 n− 1} = {1, . . . , n}.
Like in the proof of Theorem 4.3, given a digraph K(D) satisfying i) and ii), we show
that we can obtain, by transitions of Ma, a digraph K(D′), still satisfying i) and ii), and
in which a given pair of consecutive elements xi ≺K(D) xi+1, 0 6 i < n − 1, have
swapped positions. If such consecutive elements xi and xi+1 are both sinks, then since
66 Ars Math. Contemp. 6 (2013) 57–68
their order has been imposed arbitrarily, they can be swapped without changing the digraph.
Otherwise, we have to consider two cases.
If rk(xi+1) > 1, then N+(xi+1) = N+(xi)∪{xi}. The arc (xi+1, xi) can be reversed,
by the application of the transition of Ma on the arcs (xi+1, xi) and (xi, xi+1). Indeed,
the resulting digraph K ′ remains acyclic; K ′ is also w.e. since, on the one hand, vertices
xi, xi+1, . . . , xn−1 induce an acyclic tournament in K ′, by conditions i) and ii). On the
other hand, any non-sink xj , 0 ≤ j < i, is an out-neighbor of both xi and xi+1. Moreover,
if rk(xi+1) was equal to 2 in K(D) (and hence rk(xi) = 1), then in K ′ we may have
N+(xi) 6= R(xi). However, it suffices to swap arcs out-going from xi+1, the unique
vertex of rank 1 in K ′, to xi. The digraph obtained after these transformations satisfies
conditions i) and ii), thus is equal to some K(D′); the vertices of K(D′) have the same
ranks as in K(D), with the exception of xi and xi+1 which have swapped ranks.
When however rk(xi+1) = 1, we have that rk(xi) = 0. Since xi+1 is the unique vertex
of rank 1, there must be an arc from xi+1 to a sink s (s can even be xi) which can be
removed in order to add the arc (xi, xi+1). After this first arc swap, continue changing
all arcs (xi+1, s) into (xi, s), with s an arbitrary sink. The resulting digraph K ′ satisfies
conditions i) and ii) and is equal to some K(D′); moreover, the vertices of K(D′) have the
same ranks as in K(D), with the exception of xi and xi+1 which, as before, have swapped
ranks.
In order to transform K(D) into K(H), apply the following procedure, starting from
position i = 0 all the way to i = n − 1. If yi = xj , (i < j 6 n − 1), then bring xj
to position i by iteratively reversing the arcs (xj , xj−1), (xj , xj−2), . . . ,(xj , xi). Finally,
change the out-going arcs of the unique vertex of rank 1 so that it has precisely the same
out-neighborhood as it has in K(H).
Figure 6 illustrates the transitions indicated by the above proof in order to pass between
two digraphs inW5,6.
6 Critical remarks and future work
Although the Markov chains M , M c and Me are similar to the Markov chains of [9, 10],
the proofs of their irreducibility are different and more involved. In the case of M , the fixed
element which can be reached by a chain of transitions from every element D ofWn is the
same as in [9], namely the totally disconnected digraph. However, the arcs of D must be
removed in a particular order, respecting the weak extensionality of D. Second, on the one
hand, in [10] the fixed element is an arbitrary digraph having a path as underlying graph,
which cannot be the case for M c or Me since (weak) extensionality would be violated. On
the other hand, our proof takes this fixed element to be an acyclic tournament on n vertices,
ensuring that the proof proposed here can also show the irreducibility of (a slightly modified
version of) the chain of [10]. Lastly, as already noted, the Markov chain Ma can be easily
adapted to generate uniformly at random acyclic digraphs on a given number of labeled
vertices and a given number of arcs, a result which we have not found in the literature.
Given this dual usability of the Markov chains considered here, and the fact that the
acyclic tournament on n vertices (that is, the digraph isomorphic to the von Neumann
numeral of n) is a rich structure in which many types of digraphs can be embedded, it
would be interesting to give a general characterization of the classes of digraphs whose
elements can be generated uniformly at random by these Markov chains.
We regard the generation of digraphs on n vertices, possibly having directed cycles,
A. Policriti and A. I. Tomescu: Markov chain algorithms for generating sets uniformly. . . 67
5
4
2
3
1
(a) (4, 5)↔ (3, 5)
5
4
2
3
1
(b) (2, 4)↔ (3, 4)
5
4
2
3
1
(c) 2 ≺ 4 ≺ 5 ≺ 1 ≺ 3
(1, 5)↔ (5, 1)
(1, 4)↔ (5, 4)
5
4
2
3
1
(d) 1 ≺ 2 ≺ 4 ≺ 5 ≺ 3
(3, 5)↔ (5, 3)
(3, 2)↔ (5, 2)
5
4
2
3
1
(e) 1 ≺ 2 ≺ 4 ≺ 3 ≺ 5
(3, 4)↔ (4, 3)
(3, 1)↔ (4, 1)
5
4
2
3
1
(f) 1 ≺ 2 ≺ 3 ≺ 4 ≺ 5
Figure 6: The sequence of transitions of Ma that transforms D ∈ W5,6 (Fig. (a)) into
K(D) ∈ W5,6 (Fig. (c)), and then into a digraph K(H) ∈ W5,6 (Fig. (f))
but deprived of distinct bisimilar vertices (the standard interpretation of a hyperset [1]) as
the next natural step to take. It is interesting to study whether a Markov chain algorithm
consisting of three basic operations: addition of an arc, removal of an arc, move of an arc,
is irreducible for the class of such digraphs.
As already mentioned in the introduction, the problem of analyzing the mixing times [8]
of our proposed Markov chains remains open; this is important from a practical viewpoint.
Finally, since a peculiarity of the sets treated in this paper is to be sets whose elements
are themselves sets, it would be interesting to investigate what role our results can play
in the theory of random sets ([11], elements taking as values subsets of some space), for
example as a tool to generate such objects uniformly.
Acknowledgements
The authors are grateful to the anonymous referees for their useful suggestions and com-
ments which greatly improved the original version of this paper.
68 Ars Math. Contemp. 6 (2013) 57–68
References
[1] P. Aczel, Non-Well-Founded Sets, volume 14 of CSLI Lecture Notes, CSLI, Stanford, CA,
1988.
[2] V. Carnino and S. De Felice, Random Generation of Deterministic Acyclic Automata Us-
ing Markov Chains, in: B. Bouchou-Markhoff, P. Caron, J.-M. Champarnaud and D. Maurel
(eds.), Implementation and Application of Automata, volume 6807 of LNCS, Springer Berlin /
Heidelberg, 2011, pp. 65–75.
[3] A. Dovier, E. G. Omodeo, E. Pontelli and G. Rossi, {log}: A Language for Programming in
Logic with Finite Sets, J. Log. Program. 28 (1996), 1–44.
[4] A. Dovier, C. Piazza and A. Policriti, An efficient algorithm for computing bisimulation equiv-
alence, Theor. Comput. Sci. 311 (2004), 221–256.
[5] A. Dovier, C. Piazza, E. Pontelli and G. Rossi, Sets and constraint logic programming, ACM
Trans. Program. Lang. Syst. 22 (2000), 861–931.
[6] J. S. Ide and F. G. Cozman, Random Generation of Bayesian Networks, in: G. Bittencourt and
G. L. Ramalho (eds.), 16th Brazilian Symposium on Artificial Intelligence, SBIA 2002, volume
2507 of LNAI, Springer Berlin / Heidelberg, 2002, pp. 366–376.
[7] J. S. Ide, F. G. Cozman and F. T. Ramos, Generating random bayesian networks with constraints
on induced width, in R. López de Mántaras and L. Saitta (eds.), ECAI, IOS Press, 2004, pp.
323–327.
[8] D. A. Levin, Y. Peresand and E. Wilmer, Markov Chains and Mixing Times, AMS, Providence,
2009.
[9] G. Melançon, I. Dutour, and M. Bousquet-Mélou, Random generation of directed acyclic
graphs, in J. Nesetril, M. Noy and O. Serra (eds.), Comb01, Euroconference on Combinatorics,
Graph Theory and Applications, volume 10 of Electronic Notes in Discrete Mathematics, 2001,
pp. 202–207.
[10] G. Melançon and F. Philippe, Generating connected acyclic digraphs uniformly at random,
Information Processing Letters, 90 (2004), 209–213.
[11] I. Molchanov, Theory of Random Sets, Springer-Verlag London, 2005.
[12] R. Peddicord, The number of full sets with n elements, Proc. Amer. Math. Soc 13 (1962),
825–828.
[13] A. Policriti and A. I. Tomescu, Counting extensional acyclic digraphs, Information Processing
Letters 111 (2011), 787–791.
[14] J. T. Schwartz, D. Cantone and E. G. Omodeo, Computational Logic and Set Theory, Springer,
2011.
[15] J. T. Schwartz, R. B. K. Dewar, E. Dubinsky and E. Schonberg, Programming with Sets: An
Introduction to SETL, Texts and Monographs in Computer Science, Springer-Verlag, New
York, 1986.