Random Sampling of Labeled Tournaments

Lisa McShine School of Mathematics, Georgia Institute of Technology Atlanta GA 30332-1060, USA

                          mcshine@math.gatech.edu ∗

Submitted: January 5, 2000; Accepted February 23, 2000

Abstract

This note extends a recent result of Kannan, Tetali and Vempala to completely solve, via a simple proof, the problem of random generation of a labeled tournament with a given score vector. The proof uses the method of path coupling applied to an appropriate Markov chain on the set of labeled tournaments with the same score vector. MRS: 65C05, 05C20.

1 Introduction

A tournament is an oriented complete graph, which models a real-life round robin tournament with no ties. The score vector of a tournament is the sequence of outdegrees of the vertices of the tournament. In general, given a score vector with n scores, there can be an exponential (in n) number of labeled (and unlabeled) tournaments which have the given score vector (see e.g. [7], [6], and references therein). Although the problem of counting the number of labeled (or unlabeled) tournaments with the same score vector exactly seems very difficult, no #P-hardness result is known to that effect.

In this work we show that a simple algorithm based on the Markov chain Monte Carlo method is actually a very efficient algorithm for generating a labeled tournament uniformly at random from among the set of all tournaments with a given score vector.

The problem we consider is one of two problems studied in a recent paper of Kannan, Tetali and Vempala [6]: namely, randomly generating labeled bipartite graphs with a given degree sequence, and randomly generating labeled tournaments with a given score vector. For each of the two problems they designed an appropriate Markov chain whose stationary distribution is uniform on the state space of the desired structures (namely, bipartite graphs and tournaments), and under certain assumptions of “near regularity” of the degree sequences (and score vectors, respectively) they showed that the chains converged to stationarity in polynomial time.

∗This research is in part supported by P. Tetali’s NSF Grant, DMS-9800351.

In this note we solve the tournament problem in full generality – we show that without any restrictions on the score vector, given a score vector, a simple Markov chain on the set of all labeled tournaments with the given score vector converges to the (uniform) stationary distribution in time O(n^{3} log n). Thus our main contribution is the extension of the result of [6] to all score vectors with a simple proof.

Following [6], we use the Markov chain Monte Carlo method to solve this problem. However, in contrast to [6], which made use of canonical path techniques, we use the technique of path coupling which was introduced by Bubley and Dyer [2, 3]. The presentation of our proof follows the notation and terminology used by Jerrum [5]. For brevity, we omit the motivation behind the problem and refer the reader to [6] and to references therein. Section 2 introduces all the terms used in this paper along with the notation. Section 3 describes the Markov chain formally and also the proof of rapid convergence to stationarity.

2 Preliminaries on Markov Chains

This section will review the definitions for rapid mixing of a discrete time Markov chain, following the exposition in Sinclair [8], and Jerrum [5]. Let (Ω, P, π) denote an irreducible and aperiodic Markov chain, 𝔐, (thus, the chain is ergodic), with finite state space Ω, transition probability matrix P, and stationary distribution π. Here P is non-negative and row-stochastic.

We assume that the chain is reversible, i.e., that it satisfies the detailed balance conditions, π(x)P (x, y) = π(y)P (y, x), for all x, y ∈ Ω. For x, y ∈ Ω, and t ∈ ℤ^{+}, P^{t}(x, y) will denote the t-step probability of going from x to y.

The time a Markov chain takes to reach the stationary distribution can be measured at time t by the total variation distance between P^{t} and π, which is given by

||P^{t}, π||_{tv} = max_{x∈Ω} \frac{1}{2} ∑_{y∈Ω} |P^{t}(x, y) − π(y)|.

For ϵ > 0, the mixing time τ(ϵ) is defined

τ(ϵ) = min{t : ||P^{t′}, π||_{tv} ≤ ϵ, ∀t′ ≥ t}

One method of bounding the mixing time of 𝔐 is given by the following lemma, the “Coupling Lemma”, originally due to Doeblin [4], and our formulation is from [5].

Lemma 1 Suppose that 𝔐 is a countable ergodic Markov chain with transition probability matrix P, and let ((X_{t}, Y_{t}) : t ∈ ℕ) be a Markovian coupling, i.e., a Markov process satisfying

ℙ(X_{t+1} = x′ | X_{t} = x ∧ Y_{t} = y) = P (x, x′)

and

ℙ(Y_{t+1} = y′ | X_{t} = x ∧ Y_{t} = y) = P (y, y′)

Suppose further that t : (0, 1] → ℕ is a function such that ℙ(X_{t(ϵ)} ≠ Y_{t(ϵ)}) ≤ ϵ for all ϵ ∈ (0, 1], uniformly over the choice of initial state (X_{0}, Y_{0}). Then the mixing time τ(ϵ) of 𝔐 is bounded above by t(ϵ).

The last definition needed is that of rapid mixing, as defined in Sinclair [8].

Definition 2 A family of Markov chains, the size of whose state spaces is parameterized by n, is rapidly mixing iff there exists a polynomially bounded function q : ℕ × ℝ^{+} → ℕ such that the mixing time τ_{n}(ϵ) of the chain on the nth member of the family satisfies

τ_{n}(ϵ) ≤ q(n, ln ϵ^{−1})

for all n and ϵ ∈ (0, 1].

3 The Markov Chain on Tournaments

This Markov chain will be studied by using the method of path coupling, introduced by Bubley and Dyer [2, 3]. Path coupling is an extension of the coupling method, in which the coupling is first defined on pairs of “adjacent” states and then is extended to arbitrary pairs of states using shortest paths. The Coupling Lemma mentioned above is still used. The state space must have an adjacency structure and a distance function which will be defined below.

3.1 The State Space

Let T_{n} denote a labeled tournament on n vertices. The score vector, S(T_{n}), of a tournament T_{n} is a sequence s = (s_{1}, s_{2}, …, s_{n}), such that 0 ≤ s_{1} ≤ s_{2} ≤ ⋯ ≤ s_{n}, and each s_{i} is the out-degree of one of the vertices of T_{n}. Performing a Δ-reversal is reversing the orientation of the arcs in a 3-cycle in the tournament. Let the state space Ω = T (s) be the set of all labeled tournaments on n vertices with score vector s = (s_{1}, s_{2}, …, s_{n}). We will use the facts that T (s) is closed under Δ-reversals, that is, Δ-reversals preserve the score vector, and also that any tournament on n vertices can be transformed to any other tournament on n vertices with the same score vector by performing successive Δ-reversals. Note that T_{n} has precisely N_{s} = \binom{n}{3} − ∑_{i} \binom{s_{i}}{2} labeled 3-cycles (see [1]). The set of 3-cycles will be denoted by N_{Δ}.

For completeness we provide here a short proof that the state space is irreducible. (This is proved in a similar way in [1]).

Lemma 3 If two tournaments on n vertices, T and T′, have the same score vector, then T can be transformed to T′ by a finite sequence of Δ-reversals.

Proof. The key observation is that two different tournaments sharing the same score vector differ in the orientation of an edge-disjoint collection of cycles. The proof will proceed by induction on the length of the cycle. If the cycle is length 3, then reversing its orientation is performing a Δ-reversal.

Now suppose that we can reverse a cycle of length ≤ k by using a finite sequence of Δ-reversals. Consider a cycle of length k + 1, passing through the vertices v_{1}, …, v_{k}, v_{k+1}, v_{1}, in that order. There are two cases: either v_{i} → v_{1} for some i ≠ k + 1, or v_{1} → v_{i} for some i ≠ 2.

In the first case, (v_{1}, v_{2}, …, v_{i}) is a cycle of length i ≤ k, which may be reversed by a sequence of Δ-reversals. After this we have reversed the orientation of the cycle (v_{1}, v_{2}, …, , v_{i}). Now since the orientation of arc (v_{i}, v_{1}) has been reversed, we have a cycle (v_{1}, v_{i}, v_{i+1}, …, v_{k+1}). Again this is a cycle of length ≤ k, so by the inductive hypothesis we can reverse its orientation using Δ-reversals. Now all the arcs in the cycle (v_{1}, …, v_{k}, v_{k+1}) have been reversed and the arc (v_{1}, v_{i}) has been reversed twice, so it remains in it original orientation.

In the second case, the first cycle to reverse is (v_{1}, v_{i}, v_{i+1}, …, v_{k+1}), and after that, since we will then have v_{i} → v_{1}, reverse the cycle (v_{1}, v_{2}, …, , v_{i}) using the inductive hypothesis. □

Remark 1. The proof of Lemma 3 in fact shows that we can reverse a cycle of length m in m − 2 Δ-reversals. This is easy to see, once it is noted that a 4-cycle can be reversed in 2 Δ-reversals. A cycle of length m is reversed (following the inductive step above) by reversing a cycle of length i + 1 and then a cycle of length m − i + 1. This takes (i + 1 − 2) + (m − i + 1 − 2) = m − 2 Δ-reversals.

Let T ⊕ T′ denote the edge-disjoint collection of cycles in which two tournaments from T (s) differ. Let cycle i ∈ T ⊕ T′ have length m_{i}. Then the diameter of the interchange graph on T (s) is ≤ ∑_{i∈T ⊕T′}(m_{i} − 2). Since ∑_{i} m_{i} ≤ \binom{n}{2}, the diameter is ≤ \binom{n}{2} − 2(# cycles in T ⊕ T′) ≤ \binom{n}{2} − 2.

Remark 2. Brualdi and Qiao [1] give an example of a class of tournaments on n vertices for which the diameter of the interchange graph is n − 2, and showed that the diameter of the interchange graph on regular (resp. near-regular) tournaments on n vertices with score vector s is at least (n − 1)^{2}/4, (resp. n(n − 2)/4). They conjecture that this is the actual diameter of those interchange graphs. The difficulty in determining the diameter of the interchange graph (and consequently a lower bound on the mixing time of the Markov chain 𝔐) reduces to determining the number of cycles and their lengths in a tournament from the set T (s).

We will define an adjacency structure on the state space so that we may apply path coupling. The most natural definition is to declare two states x and x′ (labeled tournaments on n vertices with the same score vector) adjacent iff x′ may be obtained from x with precisely one Δ-reversal. We will identify the state space with the vertices of a graph whose edges join adjacent states, as defined above. This graph will be referred to as the interchange graph. The distance between two states in the state space, namely, the distance d(x, x′), is the least number of Δ-reversals needed to transform x into x′. With this definition, the interchange graph is an unweighted, undirected graph, with vertex set Ω, and d is the ordinary graph distance on it.

3.2 The Markov Chain

The natural Markov chain 𝔐 on Ω = T (s), which is a random walk on the interchange graph, is defined as follows:

• Let X_{t} be the current state of the chain, X_{t} ∈ Ω, so that X_{t} is a tournament with score vector s.

• Pick a 3-cycle uniformly at random (u.a.r) from the N_{s} 3-cycles in X_{t}.

• Pick r ∈ {0, 1} u.a.r. If r = 0, X_{t+1} = X_{t}, if r = 1, perform the Δ-reversal, which we will denote X_{t+1} = X_{t} ∘ Δ.

T (s) is closed under Δ-reversals, and the interchange graph on T (s) is connected under Δ-reversals, so 𝔐 is irreducible. Hence it has a unique stationary distribution π. Since P (x, y) = P (y, x) for all x, y ∈ Ω, 𝔐 is symmetric and hence the stationary distribution is uniform over the state space. The self-loop probabilities are defined to be non-zero, so 𝔐 is also aperiodic. Now we are ready to state our main result formally:

Theorem 4 The mixing time of the Markov chain on Ω = T (s) described above is bounded from above by c_{1}N_{s}(ln n + ln ϵ^{−1}), for ϵ ∈ [0, 1), where c_{1} > 0 is an absolute constant and N_{s} is number of 3-cycles in any tournament with s as the score vector.

3.3 The Coupling

The Markov chain on the set of all labeled tournaments on n vertices with the same score vector is given above.

It is only necessary to define the path coupling for adjacent states, because the coupling can then be extended via shortest paths in the interchange graph to arbitrary pair of states.

Suppose the current pair of states is (X_{t}, Y_{t}), and that X_{t} is adjacent to Y_{t}, i.e., Y_{t} = X_{t} ∘ Δ_{i} for some 3-cycle Δ_{i} ∈ N_{Δ}(X_{t}). For convenience, denote Δ_{i} = (a, b, c), that is, a → b → c. Let S_{Δ}(X_{t}, Y_{t}) denote the set of 3-cycles which is common to both X_{t} and Y_{t}. Let D_{Δ}(X_{t}) = N_{Δ}(X_{t}) \ S_{Δ}(X_{t}, Y_{t}) and likewise, D_{Δ}(Y_{t}) = N_{Δ}(Y_{t}) \ S_{Δ}(X_{t}, Y_{t}). There is a one-to-one correspondence between D_{Δ}(X_{t}) and D_{Δ}(Y_{t}), because X_{t} and Y_{t} are both tournaments with the same fixed score vector.

We define the coupling via a map σ : N_{Δ}(X_{t}) → N_{Δ}(Y_{t}), where σ(Δ) = Δ if Δ ∈ S_{Δ}(X_{t}, Y_{t}), and the other cases are illustrated in Figure 1. The latter six cases arise from considering all possible relationships between v and the vertices in the 3-cycle (a, b, c).

Recall that the only arcs that differ between X_{t} and Y_{t} are those in the 3-cycle a → b → c (resp. a → c → b).

The transition from (X_{t}, Y_{t}) to (X_{t+1}, Y_{t+1}) is given by the following experiment:

• Pick an ordered pair (Δ, σ(Δ)) uniformly at random from N_{Δ}(X_{t}) × N_{Δ}(Y_{t}).

• Pick r_{X} ∈ {0, 1} uniformly at random

• If (Δ, σ(Δ)) = ((a, b, c), (a, c, b)), set r_{Y} = 1 − r_{X}, otherwise set r_{Y} = r_{X}

• \begin{matrix}r_{X} = r_{Y} = 0 & (X_{t+1}, Y_{t+1}) = (X_{t}, Y_{t}) \\ r_{X} = r_{Y} = 1 & (X_{t+1}, Y_{t+1}) = (X_{t} ∘ Δ, Y_{t} ∘ σ(Δ)) \\ r_{X} = 1, r_{Y} = 0 & (X_{t+1}, Y_{t+1}) = (X_{t} ∘ (a, b, c), Y_{t}) \\ r_{X} = 0, r_{Y} = 1 & (X_{t+1}, Y_{t+1}) = (X_{t}, Y_{t} ∘ (a, c, b)) \end{matrix}

Figure 2 shows (X_{t}, Y_{t}) and (X_{t+1}, Y_{t+1}) for one of the cases mentioned above. This is typical of all the cases, except where σ(Δ) = Δ (in which case X_{t+1} and Y_{t+1} also differ precisely in the 3-cycle (a, b, c)), and where (Δ, σ(Δ)) = ((a, b, c), (a, c, b)), (in which case X_{t+1} and Y_{t+1} are identical).

Lemma 5 For adjacent states X_{t} and Y_{t},

𝔼(d(X_{t+1}, Y_{t+1})|X_{t}, Y_{t}) ≤ (1 − ρ)d(X_{t}, Y_{t}),  (1)

where \frac{1}{ρ} = N_{s}.

Proof. As explained above and illustrated in Fig. 1, in all except one of the N_{s} cases, d(X_{t+1}, Y_{t+1}) = d(X_{t}, Y_{t}) = 1, and in the last case d(X_{t+1}, Y_{t+1}) = d(X_{t}, Y_{t}) − 1 = 0, so that we obtain the inequality stated in the lemma. This is basically because in a strong tournament on four vertices, there are two distinct 3-cycles and if one of them is where X_{t} and Y_{t} differ, then the coupling is designed in such a way as to map the reversal of the other 3-cycle of X_{t+1} with that of Y_{t+1}; and this either preserves the distance between X_{t} and Y_{t} or reduces it. □

The following lemma is due to Bubley and Dyer, and our formulation of it follows Jerrum [5]:

Figure 1: The map σ : N_{Δ}(X_{t}) → N_{Δ}(Y_{t})

Figure 2: The top picture shows (X_{t}, Y_{t}), and the bottom shows (X_{t+1}, Y_{t+1})

Lemma 6 Suppose a coupling (X_{t}, Y_{t}) has been defined for 𝔐 on adjacent pairs of states, and suppose that the coupling satisfies the contraction condition (1) on adjacent pairs. Then the coupling can be extended to all pairs of states in such a way that (1) holds unconditionally.

Proof of Theorem 4. As shown in Lemma 5, the Markov chain satisfies the contraction property required by Lemma 6. Iteration of Lemma 5 gives E(d(X_{t}, Y_{t})|X_{0}, Y_{0}) ≤ (1 − ρ)^{t}d(X_{0}, Y_{0}). Next, the interchange graph is connected via Δ-reversals, and as shown in Remark 1, the diameter of the interchange graph is ≤ \binom{n}{2} − 2. Thus d(X_{0}, Y_{0}) < \binom{n}{2}, and

ℙ(X_{t} ≠ Y_{t}) ≤ 𝔼(d(X_{t}, Y_{t})) ≤ (1 − ρ)^{t}n^{2}/2.

The latter quantity is less than ϵ if t ≥ N_{s}(2 ln n + ln(2ϵ)^{−1}). □

Remark 3. We may use Theorem 6.11 from the survey article on tournaments by Reid and Beineke [7] to bound N_{s}. Let C(n, 3) denote the maximum number of 3cycles in a tournament on n vertices. Then Theorem 6.11 [7] yields C(n, 3) = \frac{1}{24}n(n^{2}− 1), if n is odd, and C(n, 3) ≤ \frac{1}{24}n(n^{2} − 4), if n is even. Hence N_{s} ≤ C(n, 3) ≤ n^{3}/24, and so

τ(ϵ) ≤ (n^{3}/24)(2 ln n + ln(2ϵ)^{−1}),

as claimed in the introduction.

Acknowledgments. The author thanks Prasad Tetali and an anonymous referee for their helpful comments.

References

[1] R.A. Brualdi and L. Qiao. The interchange graph of tournaments with the same score vector, Progress in Graph Theory, Academic Press, Canada, 1984, pp. 128– 151.

[2] R. Bubley and M. Dyer. Path coupling, Dobrushin uniqueness, and approximate counting, Report 97.04, School of Computer Studies, University of Leeds, 1997.

[3] R. Bubley and M. Dyer. Path coupling: a technique for proving rapid mixing in Markov chains, Proc. 38th IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, 1997, pp. 223–231.

[4] W. Doeblin. Exposé de la théorie des chaines simples constantes de Markov à un nombre fini d’états, Revue Mathématique de l’Union Interbalkanique, 2 (1933), pp. 77–105.

[5] M. Jerrum. Mathematical foundations of the Markov chain Monte Carlo method, Probabilistic Methods for Algorithmic Discrete Mathematics, Algorithms and combinatorics 16, eds. M. Habib, C. McDiarmid, J. Ramirez-Alfonsin and B. Reed, Springer, 1998, pp. 116–165.

[6] R. Kannan, P. Tetali, S. Vempala. Simple Markov-chain algorithms for generating bipartite graphs and tournaments, Random Struct. Alg., 14, 1999, pp. 293–308.

[7] K.B. Reid and L.W. Beineke. Tournaments, Ch. 7, Selected Topics in Graph Theory, eds. L.W. Beineke and R.J. Wilson, Academic Press, New York, 1978, pp. 169–204.

[8] A.J. Sinclair. Algorithms for random generation and & counting: a Markov chain approach. Birkhäuser, Boston, 1993.