Emmanuel Tsukerman
email: e.tsukerman@berkeley.edu

Lauren Williams
email: williams@math.berkeley.edu

Bruhat interval polytopes

Keywords: Bruhat order, symmetric group, R-polynomials

Introduction

The classical permutohedron is the convex hull of all permutation vectors (z(1), z(2), . . . , z(n)) ∈ R n where z is an element of the symmetric group S n . It has many beautiful properties: its edges are in bijection with cover relations in the weak Bruhat order; its faces can be described explicitly; it is the Minkowski sum of matroid polytopes; it is the moment map image of the complete flag variety.

The main subject of this paper is a natural generalization of the permutohedron called a Bruhat interval polytope. Let u and v be permutations in S n , with u ≤ v in (strong) Bruhat order. The Bruhat interval polytope (or pairmutohedron (i) ) Q u,v is the convex hull of all permutation vectors z = (z(1), z(2), . . . , z(n)) with u ≤ z ≤ v. Note that when u = e and v = w 0 are the shortest and longest elements of the symmetric group, Q e,w0 is the classical permutohedron. Bruhat interval polytopes were recently studied in [START_REF] Kodama | The full Kostant-Toda hierarchy on the positive flag variety[END_REF] by Kodama and the second author, in the context of the Toda lattice and the moment map on the flag variety Fl n . A basic fact is that Q u,v is the moment map image of the Richardson variety R u,v ⊂ Fl n . Moreover, Q u,v is a Minkowski sum of matroid polytopes (in fact of positroid polytopes [START_REF] Ardila | Positroids and non-crossing partitions[END_REF]) [START_REF] Kodama | The full Kostant-Toda hierarchy on the positive flag variety[END_REF], which implies that Q u,v is a generalized permutohedron (in the sense of Postnikov [START_REF] Postnikov | Permutohedra, associahedra, and beyond[END_REF]).

The goal of this paper is to study combinatorial aspects of Bruhat interval polytopes. We give a dimension formula for Bruhat interval polytopes, an inequality description of Bruhat interval polytopes, and prove that every face of a Bruhat interval polytope is again a Bruhat interval polytope. In particular, each edge corresponds to some edge in the (strong) Bruhat order. The proof of our result on faces uses the classical result (due to Edelman [START_REF] Paul | The Bruhat order of the symmetric group is lexicographically shellable[END_REF] in the case of the symmetric group, and subsequently generalized by Proctor [START_REF] Proctor | Classical Bruhat orders and lexicographic shellability[END_REF] and then Bjorner-Wachs [START_REF] Björner | Bruhat order of Coxeter groups and shellability[END_REF]) that the order complex of an interval in Bruhat order is homeomorphic to a sphere. Our proof also uses a generalization of the lifting property, which appears to be new and may be of interest in its own right. This Generalized lifting property says that if u < v in S n , then there exists an inversion-minimal transposition (ik) (see Definition 3.2) such that u ≤ v(ik) v and u u(ik) ≤ v. One may compare this with the usual lifting property, which says that if u < v and the simple reflection s i ∈ D r (v) \ D r (u) is a right-descent of v but not a right-descent of u, then u ≤ vs i v and u us i ≤ v. Note that in general such a simple reflection s i need not exist.

The usual lifting property is closely related to the R-polynomials R u,v (q). Recall that the R-polynomials are used to define Kazhdan-Lusztig polynomials [START_REF] Kazhdan | Representations of Coxeter groups and Hecke algebras[END_REF], and also have an interesting geometric interpretation: the Richardson variety R u,v may be defined over a finite field F q , and the number of points it contains is given by the

R-polynomial R u,v (q) = #R u,v (F q ). A basic result about the R-polynomials is that if s i ∈ D r (v) \ D r (u), then R u,v (q) = qR us,vs (q)+(q -1)R u,vs (q). We generalize this result, showing that if t = (ik) is inversion-minimal, then R u,v (q) = qR ut,vt (q) + (q -1)R u,vt (q).
The structure of this paper is as follows. In Section 2 we provide background and terminology for posets, Coxeter groups, permutohedra, matroid polytopes, and Bruhat interval polytopes. In Section 3 we state and prove the Generalized lifting property for the symmetric group. We then use this result in Section 4 to prove that the face of a Bruhat interval polytope is a Bruhat interval polytope. Section 4 also provides a dimension formula for Bruhat interval polytopes, and an inequality description for Bruhat interval polytopes. In Section 5 we give a generalization of the usual recurrence for R-polynomials, using the notion of an inversion-minimal transposition on the interval (u, v).

Background

In this section we will quickly review some notation and background for posets and Coxeter groups. We will also review some basic facts about permutohedra, matroid polytopes, and Bruhat interval polytopes. We will assume knowledge of the basic definitions of Coxeter systems and Bruhat order; we refer the reader to [START_REF] Björner | Combinatorics of Coxeter groups[END_REF] for details. Note that throughout this paper, Bruhat order will refer to the strong Bruhat order.

Let P be a poset with order relation <. We will use the symbol to denote a covering relation in the poset: u v means that u < v and there is no

z such that u < z < v. Additionally, if u < v then [u, v] denotes the (closed) interval from u to v; that is, [u, v] = {z ∈ P | u ≤ z ≤ v}. Similarly, (u, v) denotes the (open) interval, that is, (u, v) = {z ∈ P | u < z < v}.
The natural geometric object that one associates to a poset P is the geometric realization of its order complex (or nerve). The order complex ∆(P ) is defined to be the simplicial complex whose vertices are the elements of P and whose simplices are the chains x 0 < x 1 < • • • < x k in P . Abusing notation, we will also use the notation ∆(P ) to denote the geometric realization of the order complex.

Let (W, S) be a Coxeter group generated by a set of simple reflections S = {s i | i ∈ I}. We denote the set of all reflections by T = {wsw -1 | w ∈ W }. Recall that a reduced word for an element w ∈ W is a minimal length expression for w as a product of elements of S, and the length (w) of w is the length of a reduced word. For w ∈ W , we let D R (w) = {s ∈ S | ws w} be the right descent set of w and D L (w) = {s ∈ S | sw w} the left descent set of w. We also let T R (w) = {t ∈ T | (wt) < (w)} and T L (w) = {t ∈ T | (tw) < (w)} be the right associated reflections and left associated reflections of w, respectively.

The (strong) Bruhat order on W is defined by u ≤ v if some substring of some (equivalently, every) reduced word for v is a reduced word for u. The Bruhat order on a Coxeter group is a graded poset, with rank function given by length.

When W is the symmetric group S n , the reflections are the transpositions T = {(ij) | 1 ≤ i < j ≤ n}, the set of permutations which act on {1, . . . , n} by swapping i and j. The simple reflections are the reflections of the form (ij) where j = i+1. We also denote this simple reflection by s i . An inversion of a permutation z = (z(1), . . . , z(n)) ∈ S n is a pair (ij) with 1 ≤ i < j ≤ n such that z(i) > z(j). It is well-known that (z) is equal to the number of inversions of the permutation z.

Note that we will often use the notation (z 1 , . . . , z n ) instead of (z(1), . . . , z(n)).

We now review some facts about permutohedra, matroid polytopes, and Bruhat interval polytopes.

Definition 2.1 The usual permutohedron Perm n in R n is the convex hull of the n! points obtained by permuting the coordinates of the vector (1, 2, . . . , n).

Bruhat interval polytopes, as defined below, were introduced and studied by Kodama and the second author in [START_REF] Kodama | The full Kostant-Toda hierarchy on the positive flag variety[END_REF], in connection with the full Kostant-Toda lattice on the flag variety. Definition 2.2 Let u, v ∈ S n such that u ≤ v in (strong) Bruhat order. We identify each permutation z ∈ S n with the corresponding vector (z(1), . . . , z(n)) ∈ R n . Then the Bruhat interval polytope Q u,v is defined as the convex hull of all vectors (z(1), . . . , z(n)) for z such that u ≤ z ≤ v.

See Figure 1 for some examples of Bruhat interval polytopes. We next explain how Bruhat interval polytopes are related to matroid polytopes, generalized permutohedra, and flag matroid polytopes.

Definition 2.3 Let M be a nonempty collection of k-element subsets of [n] such that: if I and J are distinct members of M and i ∈ I \ J, then there exists an element j ∈ J \ I such that (I \ {i}) ∪ {j} ∈ M. Then M is called the set of bases of a matroid of rank k on the ground set [n]; or simply a matroid.

Definition 2.4 Given the set of bases M ⊂ [n] k of a matroid, the matroid polytope Γ M of M is the convex hull of the indicator vectors of the bases of M:

Γ M := Conv{e I | I ∈ M} ⊂ R n ,
where e I := i∈I e i , and {e 1 , . . . , e n } is the standard basis of R n .

Note that "a matroid polytope" refers to the polytope of a specific matroid in its specific position in R n .

Definition 2.5 The flag variety Fl n is the variety of all flags

Fl n = {V • = V 1 ⊂ V 2 ⊂ • • • ⊂ V n = R n | dim V i = i} of vector subspaces of R n . Definition 2.6 The Grassmannian Gr k,n is the variety of k-dimensional subspaces of R n Gr k,n = {V ⊂ R n | dim V = k}.
Note that there is a natural projection

π k : F l n → Gr k,n taking V • = V 1 ⊂ • • • ⊂ V n to V k .
Note also that any element V ∈ Gr k,n gives rise to a matroid M(V ) of rank k on the ground set [n]. First represent V as the row-span of a full rank k × n matrix A. Given a k-element subset I of {1, 2, . . . , n}, let ∆ I (A) denote the determinant of the k × k submatrix of A located in columns I. This is called a Plücker coordinate. Then V gives rise to a matroid M(V ) whose bases are precisely the k-element subsets I such that ∆ I (A) = 0.

One result of [KW13, Section 6] (see also [START_REF] Kodama | The full Kostant-Toda hierarchy on the positive flag variety[END_REF]Appendix]) is the following.

Proposition 2.7 Choose u ≤ v ∈ S n . Let V • = V 1 ⊂ • • • ⊂ V n be
any element in the positive part of the Richardson variety R u,v;>0 . Then the Bruhat interval polytope Q u,v is the Minkowski sum of n -1 matroid polytopes:

Q u,v = n-1 k=1 Γ M(V k ) .
In fact each of the polytopes Γ M(V k ) is a positroid polytope, in the sense of [START_REF] Ardila | Positroids and non-crossing partitions[END_REF], and Q u,v is a generalized permutohedron, in the sense of Postnikov [START_REF] Postnikov | Permutohedra, associahedra, and beyond[END_REF].

We can compute the bases M(V k ) from the permutations u and v as follows.

M(V k ) = {I ∈ [n] k | there exists z ∈ [u, v] such that I = {z(1), . . . , z(k)}}. (1)
Therefore we have the following.

Proposition 2.8 For any u ≤ v ∈ S n , the Bruhat interval polytope Q u,v is the Minkowski sum of n -1 matroid polytopes

Q u,v = n-1 k=1 Γ M k ,
where

M k = {I ∈ [n] k | there exists z ∈ [u, v] such that I = {z(1), . . . , z(k)}}.
Positroid polytopes are a particularly nice class of matroid polytopes coming from positively oriented matroids. A generalized permutohedron is a polytope which is obtained by moving the vertices of the usual permutohedron in such a way that directions of edges are preserved, but some edges (and higher dimensional faces) may degenerate. See [START_REF] Ardila | Positroids and non-crossing partitions[END_REF] and [START_REF] Postnikov | Permutohedra, associahedra, and beyond[END_REF] for more details on positroid polytopes and generalized permutohedra.

There is a generalization of matroid called flag matroid, due to Gelfand and Serganova [START_REF] Gel | Combinatorial geometries and the strata of a torus on homogeneous compact manifolds[END_REF], [BGW03, Section 1.7], and a corresponding notion of flag matroid polytope. A convex polytope ∆ in the real vector space R n is called a (type A n-1 ) flag matroid polytope if the edges of ∆ are parallel to the roots of type A n-1 and there exists a point equidistant from all of its vertices.

The following result follows easily from Proposition 2.7.

Proposition 2.9 Choose u ≤ v ∈ S n . Then the Bruhat interval polytope Q u,v is a flag matroid polytope.

We can use Proposition 2.9 to prove the following useful result.

Proposition 2.10 Let Q u,v be a Bruhat interval polytope. Consider a face F of Q u,v . Let N be the set of permutations which label vertices of F . Then N contains an element x and an element y such that

x ≤ z ≤ y ∀z ∈ N .
3 The generalized lifting property for the symmetric group

The main result of this section is Theorem 3.3, which is a generalization (for the symmetric group) of the classical lifting property for Coxeter groups. This result will be a main tool for proving that every face of a Bruhat interval polytope is a Bruhat interval polytope. We start by recalling the usual lifting property.

Proposition 3.1 (Lifting property) Suppose u < v and s ∈ D R (v) \ D R (u). Then u ≤ vs v and u us ≤ v.

Definition 3.2 Let u, v ∈ S n . A transposition (ik) is inversion-minimal on (u, v) if the interval [i, k]
is the minimal interval (with respect to inclusion) which has the property

v i > v k , u i < u k . Theorem 3.3 (Generalized lifting property) Suppose u < v in S n . Choose a transposition (ij) which is inversion- minimal on (u, v). Then u ≤ v(ij) v and u u(ij) ≤ v.
We note that there are pairs u < v where D R (v) \ D R (u) is empty, and hence one cannot apply the Lifting property. In contrast, Lemma 3.4 below shows that for any pair u < v in S n , there exists an inversion-minimal transposition (ij). Hence it is always possible to apply the Generalized lifting property.

Lemma 3.4 Let (W, S) be a Coxeter group. Take u, v ∈ W distinct. If (v) ≥ (u) then there exists a reflection t ∈ T such that v > vt, u < ut.

Lemma 3.4 directly implies the following corollary.

Corollary 3.5 Let v, u ∈ S n be two distinct permutations. If (v) ≥ (u) then there exists an inversion-minimal transposition on (u, v).

In preparation for the proof of Theorem 3.3, it will be convenient to make the following definition.

Definition 3.6 A pattern of length n is an equivalence class of sequences x 1 x 2 • • • x n of distinct integers. Two such sequences x 1 x 2 • • • x n , y 1 y 2 • • • y n are
in the same equivalence class ("have the same pattern") if

x i > x j ⇐⇒ y i > y j for all i, j such that 1 ≤ i, j ≤ n.

Denote by Patt n the set of patterns of length n.

There is a canonical representative for each pattern x ∈ Patt n obtained by replacing each x i with

xi := #{j ∈ [n] : x j ≤ x i }.
For example, the canonical representative of 523 is 312.

Definition 3.7 Let x, y ∈ Patt n for some n. Call (x, y) an Inversion-Inversion pair if the following condition holds:

for all i < j, x i > x j =⇒ y i > y j .
Notice that this statement is independent of the choice of representatives.

It is easy to see that if (x, y) is an Inversion-Inversion pair, then so is

(x 1 • • • xk • • • x n , y 1 • • • ŷk • • • y n ) for any k.
In preparation for the proof of Theorem 3.3, we first state and prove Lemmas 3.8, 3.10, and 3.11.

Lemma 3.8 Let u, v ∈ S n . The following are equivalent:

(i). The transposition (ik) is inversion-minimal on (u, v) Lemma 3.11 Suppose that (ik) is inversion-minimal on (u, v). Then for every i < j < k, we have Example 3.12 The following example shows that the converse to Theorem 3.3 does not hold: it is not necessarily the case that if the Bruhat relations

(ii). The patterns x = x i . . . x k := v i • • • v k and y = y i . . . y k := u k u i+1 u i • • • u k-2 u k-1 u i form
u j > u i ⇐⇒ u j > u k ⇐⇒ v j > v k ⇐⇒ v j > v i . u = 2143 3142 2341 v = 3241 t = (24) (14) t = (24) (12)
v(ik) v u u(ik) u ≤ v(ik) u(ik) ≤ v hold, then (ik) is inversion-minimal on (u, v). Take v = 4312, u = 1243 and (ik) = (24). Then v(ik) v u u(ik) u ≤ v(ik) u(ik) ≤ v but also v 2 > v 3 and u 2 < u 3 .
As a corollary of Generalized lifting, we have the following result, which says that in an interval of the symmetric group we may find a maximal chain such that each transposition connecting two consecutive elements of the chain is a transposition that comes from the atoms, and similarly, for the coatoms.

Corollary 3.13 Let [u, v] =⊂ S n and let T (v) := {t ∈ T : v vt ≥ u} and T (u) := {t ∈ T : u ut ≤ v}. There exist maximal chains C v : u = x (0) x (1) x (2) . . . x (l) = v and C u : u = y (0) y (1) y (2) . . . y (l) = v in I such that x -1 (i) x (i+1) ∈ T (v) and y -1 (i) y (i+1) ∈ T (u) for each i.

Results on Bruhat interval polytopes

In this section we give some results on Bruhat interval polytopes. We show that the face of a Bruhat interval polytope is a Bruhat interval polytope; we give a dimension formula; and we give an inequality description.

Faces of Bruhat interval polytopes are Bruhat interval polytopes

The main result of this section is the following.

Theorem 4.1 Every face of a Bruhat interval polytope is itself a Bruhat interval polytope.

Our proof of this result uses the following theorem. It was first proved for the symmetric group by Edelman [START_REF] Paul | The Bruhat order of the symmetric group is lexicographically shellable[END_REF], then generalized to classical types by Proctor [START_REF] Proctor | Classical Bruhat orders and lexicographic shellability[END_REF], and then proved for arbitrary Coxeter groups by Bjorner and Wachs [START_REF] Björner | Bruhat order of Coxeter groups and shellability[END_REF].

Theorem 4.2 [BW82] Let (W, S) be a Coxeter group. Then for any u ≤ v in W , the order complex ∆(u, v) of the interval (u, v) is PL-homeomorphic to a sphere S (u,v)-2 . In particular, the Bruhat order is thin, that is, every rank 2 interval is a diamond. In other words, whenever u ≤ v with (v) -(u) = 2, there are precisely two elements z (1) , z (2) such that u < z (i) < v.

We will identify a linear functional ω with a vector (ω 1 , . . . , ω n ) ∈ R n , where ω : R n → R is defined by ω(e i ) = ω i (and extended linearly).

Proposition 4.3 Choose u ≤ v in S n , and let ω : R n → R be a linear functional which is constant on a maximal chain C from u to v. Then ω is constant on all permutations z where u ≤ z ≤ v.

The dimension of Bruhat interval polytopes

In this section we will give a dimension formula for Bruhat interval polytopes. We will then use it to determine which Richardson varieties in Fl n are toric varieties, with respect to the usual torus action on Fl n . Recall that a Richardson variety R u,v is the intersection of opposite Schubert (sometimes called Bruhat) cells. Definition 4.5 Let u ≤ v be permutations in S n , and let C : u = x (0) x (1) x (2) . . . x (l) = v be any maximal chain from u to v. Define a labeled graph G C on [n] having an edge between vertices a and b if and only if the transposition (ab) equals x -1 (i) x (i+1) for some 0 ≤ i ≤ l -1. Define B C = {B 1 , B 2 , . . . , B r } to be the partition of [n] = {1, 2, . . . , n} whose blocks B j are the connected components of G C . Let #B C denote r, the number of blocks in the partition.

We will show in Corollary 4.8 that the partition B C is independent of C; and so we will denote this partition by B u,v .

Theorem 4.6 The dimension dim Q u,v of the Bruhat interval polytope Q u,v is dim Q u,v = n -#B u,v .
The equations defining the affine span of Q u,v are

i∈B j x i = i∈B j u i (= i∈B j v i ), j = 1, 2, . . . , #B u,v .
(2)

Before proving Theorem 4.6, we need to show that B u,v is well-defined. Given a subset A ⊂ [n], let e A denote the 0 -1 vector in R n with a 1 in position a if and only if a ∈ A.

Lemma 4.7 Let C be a maximal chain in [u, v] ⊂ S n . Let B C = {B 1 , . . . , B r } be the associated partition of [n]. Then a linear functional ω : R n → R is constant on the interval [u, v] if and only if ω = r j=1 c j e B j
for some coefficients c j .

We now turn to the question of when the Richardson variety R u,v is a toric variety.

Proposition 4.12 The Richardson variety R u,v in Fl n is a toric variety if and only if the number of blocks

#B u,v of the partition B u,v satisfies #B u,v = n -(v) + (u).
Equivalently, R u,v is a toric variety if and only if the labeled graph G C is a forest (with no multiple edges).

Given a labeled graph G, we will say that a cycle

(v 0 , v 1 , . . . , v k ) with v k = v 0 is increasing if v 0 < v 1 < . . . < v k-1 .
We shall call a labeled graph with no increasing cycles an increasing-cycle-free labeled graph.

Lemma 4.13 The labeled graphs G at and G coat are increasing-cycle-free. In particular, they are simple and trianglefree.

Following Björner and Brenti [START_REF] Björner | Combinatorics of Coxeter groups[END_REF], we call the face poset of a k-gon a k-crown. Any length 3 interval in a Coxeter group is a k-crown [BB05, Corollary 2.7.8]. It is also known that in S n , the values of k can only be 2, 3 or 4.

Remark 4.14 Using Proposition 4.10 and Lemma 4.13, it is easy to show that any k-crown must have k ≤ 4. Indeed, the graph G C has 3 edges, and therefore at least n -3 connected components. By Proposition 4.10, the graph G at has the same connected components as G C and k edges. By Lemma 4.13 it is simple and triangle-free. Consequently, if k > 4 then G at must have at most n -4 components.

Lemma 4.15 Let [u, v] be a 4-crown and let C : u = x (0) x (1) x (2) x (3) = v be any maximal chain. The graph G C is a forest. In particular, if we set t i := x -1 (i) x (i+1) for 0 ≤ i ≤ 2, then t 0 = t 2 since there are no multiple edges. Corollary 4.16 A Richardson variety R u,v in Fl n with (v) -(u) = 3 is a toric variety if and only if [u, v] is a 3-crown or a 4-crown.

An inequality description of Bruhat interval polytopes

Using Proposition 2.8, which says that Bruhat interval polytopes are Minkowski sums of matroid polytopes, we will provide an inequality description of Bruhat interval polytopes.

We first need to recall the notion of the rank function r M of a matroid M. Suppose that M is a matroid of rank k on the ground set [n]. Then the rank function r M : 2 [n] → Z ≥0 is the function defined by

r M (A) = max I∈M |A ∩ I| for all A ∈ 2 [n] .
There is an inequality description of matroid polytopes, using the rank function.

Proposition 4.17 [START_REF] Dominic | Matroid theory[END_REF]) Let M be any matroid of rank k on the ground set [n], and let r M : 2 [n] → Z ≥0 be its rank function. Then the matroid polytope Γ M can be described as

Γ M =    x ∈ R n | i∈[n] x i = k, i∈A x i ≤ r M (A) for all A ⊂ [n]    .
Using Proposition 4.17 we obtain the following result. Then

Q u,v =    x ∈ R n | i∈[n] x i = n + 1 2 , i∈A x i ≤ n-1 j=1 r Mj (A) for all A ⊂ [n]    .
Example 4.19 Consider u = 1324 and v = 2431 in S 4 . We will compute the inequality description of Q u,v . First note that [u, v] = {1324, 1342, 1423, 1432, 2314, 2341, 2413, 2431}. We then compute:

• M 1 = {{1}, {2}}, a matroid of rank 1 on [4]. • M 2 = {{1, 3}, {1, 4}, {2, 3}, {2, 4}}, a matroid of rank 2 on [4]. • M 3 = {{1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}}, a matroid of rank 3 on [4].
Now using Proposition 4.18, we get

Q u,v = {x ∈ R 4 | i∈[4] x i = 10, x 1 + x 2 + x 3 ≤ 6, x 1 + x 2 + x 4 ≤ 6, x 1 + x 3 + x 4 ≤ 6, x 2 + x 3 + x 4 ≤ 6, x 1 + x 2 ≤ 4, x 1 + x 3 ≤ 5, x 1 + x 4 ≤ 5, x 2 + x 3 ≤ 5, x 2 + x 4 ≤ 5, x 3 + x 4 ≤ 3, x 1 ≤ 3, x 2 ≤ 3, x 3 ≤ 2, x 4 ≤ 2.}

A generalization of the recurrence for R-polynomials

The well-known R-polynomials were introduced by Kazhdan and Lusztig as a useful tool for computing Kazhdan-Lusztig polynomials [START_REF] Kazhdan | Representations of Coxeter groups and Hecke algebras[END_REF]. R-polynomials also have a geometric interpretation in terms of Richardson varieties. More specifically, the Richardson variety R u,v may be defined over a finite field F q , and the number of points it contains is given by the R-polynomial R u,v (q) = #R u,v (F q ). The R-polynomials may be defined by the following recurrence.

Theorem 5.1 [BB05, Theorem 5.1.1] There exists a unique family of polynomials {R u,v (q)} u,v∈W ⊂ Z[q] satisfying the following conditions:

1. R u,v (q) = 0, if u ≤ v. 2. R u,v (q) = 1, if u = v. 3. If s ∈ D R (v), then R u,v (q) = R us,vs (q) if s ∈ D R (u), qR us,vs (q) + (q -1)R u,vs (q) if s ∈ D R (u).
It is natural to wonder whether one can replace s with a transposition t whenever the Generalized lifting property holds. More precisely, suppose that t is a transposition such that vt v u ut u ≤ vt ut ≤ v.

(3)

Is it true that R u,v (q) = qR ut,vt (q) + (q -1)R u,vt (q)? (4)

In general, the answer is no. For example, one can check that u = 1324, v = 4231 and t = (24) give a counterexample. However, when t is an inversion-minimal transposition on (u, v), (4) does hold. We'll use the next lemma to prove this.

Lemma 5.2 Let u, v ∈ S n and suppose that (ik) is inversion-minimal on (u, v). Assume further that v j > v j+1 and u j > u j+1 for some j such that i < j < k -1. Then (ik) is inversion-minimal on (vs j , us j ).

Proposition 5.3 Let u, v ∈ S n with v ≥ u. Let t = (ij) be inversion-minimal on (u, v). Then R u,v (q) = qR ut,vt (q) + (q -1)R u,vt (q).

Remark 5.4 The above statement holds mutatis mutandis for the R-polynomials, which are a renormalization of the R-polynomials.

Example 5.5 Take u = 21345, v = 53421 and t = (13). We have R u,v (q) = q 8 -4q 7 + 7q 6 -8q 5 + 8q 4 -8q 3 + 7q 2 -4q + 1 R ut,vt (q) = q 6 -4q 5 + 7q 4 -8q 3 + 7q 2 -4q + 1 and R u,vt (q) = q 7 -4q 6 + 7q 5 -8q 4 + 8q 3 -7q 2 + 4q -1.

Definition 5.6 A matching of a graph G = (V, E) is an involution M : V → V such that {v, M (v)} ∈ E for all v ∈ V .

Definition 5.7 Let P be a graded poset. A matching M of the Hasse diagram of P is a special matching if for all x, y ∈ P such that x y, we have M (x) = y or M (x) ≤ M (y).

It is known that special matchings can be used to compute R-polynomials:

Theorem 5.8 [BCM06, Theorem 7.8] Let (W, S) be a Coxeter system, let w ∈ W , and let M be a special matching of the Hasse diagram of the interval [e, w] in Bruhat order. Then R u,w (q) = q c R M (u),M (w) (q) + (q c -1)R u,M (w) (q) for all u ≤ w, where c = 1 if M (u) u and c = 0 otherwise.

One might guess that the Generalized lifting property is compatible with the notion of special matching. More precisely, one might speculate that if [u, v] ⊂ S n and t is inversion-minimal on (u, v) then there is a special matching M of [u, v] such that M (u) = ut and M (v) = vt. The following gives an example of this.

Example 5.9 Take u = 143265 and v = 254163. Then t = (36) is inversion-minimal on (u, v). Suppose that a special matching M of [u, v] (see Figure 6) satisfies M (v) = vt and M (u) = ut. Then we must have M (154263) = 153264 and M (243165) = 245163. Observe that the result is a multiplication matching. Similarly, if we take t = (14), another inversion-minimal transposition on (u, v), we again obtain a multiplication matching.

The following example shows that it is not the case that an inversion-minimal transposition must be compatible with a special matching. This makes Proposition 5.3 all the more surprising, and shows that it cannot be deduced using special matchings.

Figure 1 :

 1 Figure 1: The two polytopes are the permutohedron Q e,w0 = Perm 4 , and the Bruhat interval polytope Q u,v with v = (2, 4, 3, 1) and u = (1, 2, 4, 3).

Figure 2 :

 2 Figure 2: Generalized lifting property Lemma 3.10 Let x, y ∈ Patt n with xn = x1 + 1 and ȳn = ȳ1 + 1. If (x, y) is an Inversion-Inversion pair, then x1 = ȳ1 .

Figure 3 :

 3 Figure 3: Example of Theorem 3.3

Corollary 4. 4

 4 If a linear functional ω : R n → R, when restricted to [u, v], attains its maximum value on u and v, then it is constant on [u, v].

Corollary 4. 8

 8 The partition B C is independent of the choice of C. Definition 4.9 Let u ≤ v be permutations in S n , and let T (u) := {t ∈ T : u ut ≤ v} and T (v) := {t ∈ T : v vt ≥ u} be the transpositions labeling the cover relations corresponding to the atoms and coatoms in the interval. Define a labeled graph G at (resp. G coat ) on [n] such that G at (resp. G coat ) has an edge between a and b if and only if the transposition (ab) ∈ T (u) (resp. (ab) ∈ T (v)). Let B at u,v be the partition of [n] whose blocks are the connected components of G at . Similarly, define partition B coat u,v whose blocks are the connected components of G coat . Proposition 4.10 Let [u, v] ⊂ S n . The partitions B at u,v and B coat u,v are equal to B u,v . Consequently, the labeled graphs G C , G at and G coat all have the same connected components.

Example

Proposition 4 .

 4 18 Choose u ≤ v ∈ S n , and for each 1 ≤ k ≤ n -1, define the matroidM k = {I ∈ [n] k | there exists z ∈ [u, v]such that I = {z(1), . . . , z(k)}}.

Example 5 .

 5 10 Take u = 1324 and v = 4312. Then t = (24) is inversion-minimal on (u, v). Suppose that a special matching M of [u, v] (Figure 7) satisfies M (v) = vt, i.e., sends 4312 to 4213. Then M (4132) = 4123, M (1432) = 1423, M (1342) = 1324, M (3142) = 3124, M (3412) = 3214, M (2413) = 2314. But M (2314) = 2413 ≥ 1342 = M (1324), which is a contradiction.

  Figure 7

  4.11 Consider the intervals [1234, 1432] and [1234, 3412] in Figures4 and 5. We see that B 1234,1432 = |1|234| and B 1234,3412 = |1234|, so that the dimensions are 2 and 3, respectively.

			3412
	(13)	(14)	(23)	(24)
	1432	2413	3142	3214
	(13)
	1423	1342	3124	2314
	(23)
	1243		1324	2134
	(34)	(23)	(12)
			1234
			1432
	(34)		(23)
	1423	(24)	(24)	1342
	(23)				(34)
	1243			1324
	(34)		(23)
			1234
			Figure 4

Acknowledgements E.T. is grateful to Francesco Brenti for sending his Maple code for computing R-polynomials. L.W. would like to thank Yuji Kodama for their joint work on the Toda lattice, which provided motivation for this project. She is also grateful to Konni Rietsch and Robert Marsh for generously sharing their ideas about the Gelfand-Serganova stratification. Finally, we would like to thank Fabrizio Caselli, Allen Knutson, Thomas Lam, Robert Proctor, and Alex Woo for helpful conversations.

This material is based upon work supported by the National Science Foundation Graduate Research Fellowship under Grant No. DGE 1106400, and the National Science Foundation CAREER Award DMS-1049513. Any opinion, findings, and conclusions or recommendations expressed in this material are those of the authors(s) and do not necessarily reflect the views of the National Science Foundation.

supported by a NSF Graduate Research Fellowship under Grant No. DGE 1106400. partially supported by an NSF CAREER award DMS-1049513.


Nicolas Gast

Inria Bruno Gaujal

COMPUTING ABSORBING TIMES VIA FLUID APPROXIMA-TIONS

Keywords: Markov chain, Fluid approximation, Extreme values, Coupon collector, Coupling time 2010 Mathematics Subject Classification: Primary 05D40 Secondary 60J10;37A25

come

Introduction.

Analyzing stochastic discrete event dynamic systems by constructing deterministic fluid approximations (sometimes called hydrodynamic limits) has been very popular in recent years. This technique is very powerful to get fast and accurate performance evaluation of computer based systems [START_REF] Benaïm | A class of mean field interaction models for computer and communication systems[END_REF][START_REF] Chaintreau | The age of gossip: spatial mean field regime[END_REF][START_REF] Gast | A mean field model of work stealing in large-scale systems[END_REF]. It can be applied quite generally to study the transient behavior or the convergence to stationary or quasi-stationary distributions [START_REF] Boudec | The stationary behaviour of fluid limits of reversible processes is concentrated on stationary points[END_REF][START_REF] Kang | Asymptotic approximations for the stationary distributions of many-server queues[END_REF][START_REF] Chazottes | Asymptotics for the quasi-stationary distribution of birth-and-death processes[END_REF].

In this paper, we rather consider the case where we want to approximate a finite (but large) stochastic system over a stopping time of the process. We consider a Markov chain X := (X 1 . . . X n ), where X i is called the ith component. The components are all Markov chains that have an absorbing state (say state 0) and respective transition matrices P 1 , . . . , P n . The evolution of X is as follows: At step t, a single component is chosen according to a fixed probability vector (p 1 , . . . , p n ) and the chosen component (say i) makes one transition, according to its kernel P i . Our goal is to compute the first instant T n when all components have reached their absorbing state.

The simplest example of such a system is the coupon collector. Each coupon is seen as a Markov chain with two states. The absorbing state (0) corresponds to the presence of the coupon in the current collection and the other state [START_REF] Anceaume | New results on a generalized coupon collector problem using markov chains[END_REF] to its absence:

Contributions In this paper, we compute an asymptotic equivalent t n of the absorbing time T n under weak assumptions on p n (see Section 3.2 for a precise statement). The approximation t n is obtained by defining a fluid approximation of X := (X 1 . . . X n ) and by computing the time when this fluid approximation is at a distance 1/n from the absorbing state. Our main result is to show that T n is asymptotic equal (in distribution) to t n plus a Gumbel distribution with mode 0 and scale 1/(-ν min i p i ), plus a negligible sub-linear term o(n). The exponent -ν depends on the eigenvalues of the transition matrices. We also provide closed forms expressions for the asymptotic expectation of T n and its moments.

The deterministic time t n is easier to compute that its stochastic time T n . When all chains have the same transition matrix and p i = 1/n, we show that t n = (-1/ν)n log n+ (k -1)n log log n + O(n), where ν is the largest eigenvalue of transition matrix. We apply this to the coupon collector (see Section 4) as well as to random walks in finite grids (see Section 5 where we give an equivalent to the coupling time in grids with or without drifts). We also provide bounds on t n based on the absorbing time of a single component in Section 4.4. In the heterogeneous and/or non-uniform cases, t n can often only be computed numerically (see Section 4.3 for a numerical application to the coupon collector with rare coupons).

Our proofs rely on two ingredients. First, we use a classical "Poissonization technique" to transform the system of n coupled Markov chains into a continuous time Markov chains made of n independent components. Second, we use ideas from extreme value theory to relate T n and the time when the fluid approximation approaches 1/n.

Road-map

The rest of the paper is organized as follows. We introduce the model and the definition of t n is Section 2. We develop the equivalence theorems between t n and T n is Section 3. We present the applications to the coupon collector in Section 4, where we also show how to compute a bound (Theorem 4.1). Next, we show how this can be applied to compute the coupling time of random walks in Section 5. Finally, we conclude in Section 6.

Problem statement.

We consider a discrete-time finite Markov chain X made of n chains: X 1 , . . . , X n . The chain X i called component i in the following. All components have an absorbing state 0 and respective transition matrices P 1 , . . . , P n . The component X i lives in a finite state space {0 . . . k} and 0 is an absorbing state: P i (0, 0) = 1. We assume that the state 0 is reachable from any initial state, which implies that with probability one, each component hits 0 in finite time. For reasons that will become clear in the next section, the transition matrix P i will be decomposed as

P i = 1 0 q i I + Q i , (1)
where Q i is a k × k rate matrix with the following properties: Q i is non-singular, for all a, b Q i (a, b) ≤ 0 and there exists at least one state a such that b Q i (a, b) < 0. Let p = (p 1 ≥ • • • ≥ p n ) a probability distribution on {1 . . . n}. The discrete-time Markov chain X = (X 1 . . . X n ) is defined by the following dynamics. At time 0, each X i (0) is picked independently according to an initial distribution α i . Then at each time step t, one coordinate i is picked with probability p i , independently of the past. Then, the ith coordinate, X i , makes one transition according to the matrix P i .

In what follows, we characterize T n , the hitting time of (0, 0, . . . , 0):

T n := inf{t such that ∀i ∈ {1 . . . n} : X i (t) = 0}
We distinguish several cases in the analysis of this problem. We say that the chain is homogeneous if all components X 1 . . . X n have the same transition matrix P , and the same initial distribution α. From this point on, we assume homogeneity, unless it is specified otherwise. The non-homogeneous case is treated in Section 3.3. We say that X is uniform if the choice probabilities among the components are all equal: (p 1 , . . . , p n ) = (1/n, . . . , 1/n). In the following, we will show that when n is large, T n is well approximated by a deterministic time t n that we define below.

2.1. Definition of t n in the uniform and homogeneous case.

In the uniform and homogeneous case, we define t n to be the unique solution of the following equation, using Q = Q i for all i, as defined in [START_REF] Anceaume | New results on a generalized coupon collector problem using markov chains[END_REF], and α, the initial distribution of each component.

1 n = α exp(Qt n /n)1. ( 2
)
This definition is justified by using a dynamical system that is a mean field limit of the Markov chain. We define the empirical measure, (M 0 , M 1 , . . . , M k ) of the chain:

M a (t) := 1 n n i=1 1 {Xi(t)=a} .
By the definition of Q given in [START_REF] Anceaume | New results on a generalized coupon collector problem using markov chains[END_REF], for all a = 0, we have

E [M a (t + 1) -M a (t)|M(t)] = 1 n b M b (t)Q(b, a).
When the number of components becomes large, the empirical measure (M 0 , M 1 , . . . , M k ) converges to a deterministic population (m 0 , m 1 , . . . , m k ) whose dynamics is given by an ordinary differential equation (ODE) (see [START_REF] Kurtz | Strong approximation theorems for density dependent Markov chains[END_REF] for example). In matrix form, and focusing on the k-dimensional vector m := (m 1 , . . . , m k ) (removing the coordinate m 0 ), this equation can be written

ṁ(t) = 1 n m(t)Q. ( 3
)
This ODE is linear and its solution can be computed explicitly. The sum m(t

) := m • 1 is equal to m(t) = α exp(Qt/n)1.
When n is large, the proportion of components not yet in state 0 can be approximated by m(t). However, unlike in the finite case, it never reaches 0. To get a good fluid approximation of the stopping time T n , we define

t n := inf{t > 0 such that m(t) = 1 n }. (4)
This definition implies that t n is the solution of Equation (2).

2.2. Definition of t n in the non-uniform or non-homogeneous case.

Let us now consider the non-homogeneous, non-uniform case, with a general choice vector (p 1 , . . . , p n ). We always assume with no loss of generality that p 1 ≥ p 2 ≥ • • • ≥ p n . We do not construct explicitly the population dynamics but jump directly to the analog of Equation [START_REF] Benaïm | A class of mean field interaction models for computer and communication systems[END_REF].

If one considers the evolution of the ith chain, independently of the rest, it is a Markov chain with transition matrix

1 0 p i q i I + p i Q i .
In particular, the probability for X i to be equal to 0 at time t is:

P (X i (t) = 0) = α i (I + p i Q i ) t 1, which is close to α i exp(p i Q i t)1 as p i is small and t is large. We define m(t) = n -1 n i=1 α i exp(p i Q i t)
1 the fluid approximation of the process X and define as t n the time for the fluid approximation to reach 1/n, as in the uniform case:

t n := inf{t > 0 such that m(t) = 1 n }. (5)
In the non-uniform case, the behavior of T n depends on how the choice probabilities (p 1 , . . . , p n ) evolve when n goes to infinity. In Section 3.2, we provide general conditions on (p 1 , . . . , p n ) under which t n is a good approximation of T n .

Convergence results.

This section contains the main results of our paper, namely Theorems 3.1, 3.2 and 3.3. We will first remove the difficulty in dealing with the dependencies between the components by using a classical Poissonization trick. We Once this is done, we focus on the homogeneous case in Section 3.2. The heterogeneous case follows from the homogeneous case by compacity arguments (Theorem 3.3).

Removing the dependence ("Poissonization" trick)

The first difficulty in dealing with the discrete-time Markov chain X is that the components X 1 , . . . , X n are not independent: If component X i takes a step, then all the others remain still, by the mutual exclusion principle. We remove this difficulty by using the classical trick that consists in constructing a continuous time Markov chain that approximates the discrete time evolution of X and makes all components independent, in continuous time. We detail this construction below.

Let (Z 1 , Z 2 , . . .) be a real Poisson process with rate 1. Let us define a continuous time Markov chain Y, associated with X, whose jumps occur at times Z 1 , Z 2 , . . .. More precisely, Y is a piecewise constant cadlag function such that for all n, Y(Z n ) = X(n). Let T n be the time when Y gets absorbed. By definition, T n = Z Tn .

By construction, T n can be viewed as the maximum of n independent random variable. Indeed, Y has the same law as a process composed of n independent continuous time Markov chains (Y 1 , • • • , Y n ), where Y i is a continuous time Markov chain of kernel p i Q i . In particular, P(

T n ≤ t) = n i=1 P (Y i (t) = 0) = n i=1 (1 -α i exp(p i Q i t)

Convergence in the homogeneous case.

To prove the concentration of T n around t n , we make the following scaling assumptions on the way the probability vector evolves as n grows. To emphasize the dependence on n, let (p

(n) 1 . . . p (n)
n ) denotes the probability vector for the chain with n components. We assume that:

For each n: p (n) i ≥ p (n) i+1 and p (n) i+1 /p (n) i decreases with i (6)
For any : lim

n→∞ p (n) n p (n) n- = 1. ( 7
)
These two assumptions are satisfied by any distribution that is close enough to the uniform distribution (p

(n) i = 1/n),
or the almost uniform distribution with a popular element used for example in [START_REF] Anceaume | New results on a generalized coupon collector problem using markov chains[END_REF] (p

(n) 1 = c > 0 and p (n) i = (1-c)/(n-1) for i > 1)
. They are also satisfied by distributions of the form p (n) i = a i / j=1 a j , where a i > 0 is a positive sequence that decreases slower than any exponential, for example with p (n) i := i r / n j=1 j r or p (n) i := (log i) r / n j=1 (log j) r for r ≤ 0. Note that Assumptions (6)- [START_REF] Doumas | The coupon collector's problem revisited: Generalizing the double dixie cup problem of newman and shepp[END_REF] generalize the conditions (2.23) of [START_REF] Doumas | The coupon collector's problem revisited: Generalizing the double dixie cup problem of newman and shepp[END_REF]. Theorem 3.1. Assume that the probability distribution (p 6) and [START_REF] Doumas | The coupon collector's problem revisited: Generalizing the double dixie cup problem of newman and shepp[END_REF]. Then, for any x, the hitting time T n for the stochastic system composed of the n chains satisfies:

(n) 1 . . . p (n) n ) satisfies (
lim n→∞ P T n ≤ t n + x p (n) n = exp(-e -νx ). ( 8
)
This theorem essentially shows that the asymptotic distribution of p

(n)
n (T n -t n ) converges to a Gumbel distribution with mode 0 and scale 1/ν. An interesting property of this result is that the shape of the distribution only depends on the smallest value of the distribution, p (n) n (even when this distribution is far from uniform, as in the case p

(n) i = 2i/(n 2 + n)). The proof is postponed in Appendix A.
Next, we show in Theorem 3.2 that the convergence also holds for the moments. Theorem 3.2. Assume that the sequence of distributions (p 6) and [START_REF] Doumas | The coupon collector's problem revisited: Generalizing the double dixie cup problem of newman and shepp[END_REF]. Let M m be the mth moment of the standard Gumbel distribution. Then, the hitting time T n for the stochastic system composed of the n chains satisfies:

(n) 1 . . . p (n) n ) satisfies Equa- tions (
lim n→∞ E (p (n) n (T n -t n )) m = ν -m M m . (9)
In particular, this theorem implies that:

lim n→∞ p (n) n (E [T n ] -t n ) = γ ν , lim n→∞ var p (n) n T n = π 2 6ν 2 ,
where γ is the Euler-Mascheroni constant γ = lim n→∞ ( n k=1 (1/k) -log(n)). This theorem provides asymptotic closed form values for the absorbing time of the chain, not only bounds, or O(.) limits, as it is sometimes done. Again, as for the distribution, the moments only depend on the smallest probability p (n) n . The proof is postponed in Appendix B.

Heterogeneous case.

To deal with different kernels, we simplify the assumptions ( 6) and ( 7) on the choice vector. They are replaced by Assumption (10): We assume that there exists a constant c such that for any component i, p

(n) i ≥ c/n. ( 10
)
We now consider a collection of matrix (Q (θ) ), indexed by a parameter θ ∈ Θ, where Θ ⊂ R d is a compact set. We assume that Q (θ) ij is a continuous function of θ and that for all θ ∈ Θ, Q θ is non-singular and such that for all a = b Q θ (a, b) ≥ 0, for all a:

b Q θ (a, b) ≤ 0 and for at least one a: b Q θ (a, b) < 0. The evolution of the component i depends on the matrix Q (θi) , for a given θ i . If the component i starts with a distribution α i , the probability that this component i has reached its absorbing state at time-slot nt is therefore α i (1 + Q (θi) /n) nt 1. We define the quantity m θ1...θn (t) as

m θ1...θn (t) := 1 n n i=1 α i exp(Q (θi) t)1.
The hitting time t θ1...θn is defined similarly to t n :

t θ1...θn = inf t : m θ1...θn (t) ≤ 1 n . (11)
For each θ ∈ Θ, let -ν θ be the eigenvalue of Q θ with the greatest real part. ν θ is a continuous function of θ. Let ν max = max θ∈Θ ν θ and ν min = min θ ν θ .

Theorem 3.3. For all x, there exists ν θ1...θn (x) ∈ [ν min , ν max ] such that the hitting time T θ1...θn satisfies

lim n→∞ P (T θ1...θn ≥ n(t θ1...θn + x)) -exp(-e -ν θ 1 ...θn (x)x ) = 0 Moreover, there exists ν θ1...θn ∈ [ν min , ν max ] such that lim n→∞ E [T θ1...θn ] -t θ1...θn + γ ν θ 1 ...θn n = 0
The proof is postponed in Appendix C

Why approximating T n by t n helps ?

We claim that t n is a simpler quantity to work with than T n . In this section, we illustrate this claim in four different contexts.

1. First we show that t n admits an asymptotic expansion when n goes to infinity that can be expressed using the spectral decomposition of Q (Subsection 4.1).

2. We also show in Subsection 4.2 that sometimes t n admits an asymptotic closed form. This is the case of the coupon collector problem, for which we retrieve the classical formula due to Erdos [START_REF] Erdös | On a classical problem of probability theory[END_REF], rather effortlessly.

3. In Subsection 4.3, we show that t n can be computed numerically with a high precision, beating the computing effort needed to sample T n by simulation.

4. Finally, Subsection 4.4 shows that efficient bounds on t n can be found by using simple linear algebra properties.

Asymptotic expansion of t n .

Let us recall that in the homogeneous and uniform case, t n is the solution of

1 n = α exp(Qt n /n)1.
Without loss of generality, assume that any state can be reached from the support of the initial measure α (if some states are not reachable, they can be suppressed). All the lines in Q sum to non-positive numbers (with at least one line summing to a negative number), hence the eigenvalue of Q with the largest real part is a real negative number, that we denote -ν. According to Theorem 2.7.2 of [START_REF] Latouche | Introduction to matrix analytic methods in stochastic modeling[END_REF], there exists a constant a > 0 and an integer d ∈ {1 . . . k} such that:

α exp(Qt)1 = at d-1 e -νt (1 + o(t)). (12)
Together, ( 2) and ( 12) yield almost directly

t n = n ν log(n) + d -1 ν n log log(n) + n(d -1) ν log(ν) - n ν log a + o(n). (13)
It should be noted that, as long as all states are reachable from the initial measure α, the only quantity in ( 12) that depends on the initial measure is a. In the asymptotic expansion ( 13), the initial measure α appears only in the O(n)-term but does not affect the first two terms in n log n and n log log n.

We call d the degree of ν. In linear algebraic terms, d corresponds to the dimension of the largest Jordan block in Q for eigenvalue -ν, that can be reached under α. It is smaller or equal to the multiplicity of the largest eigenvalue of Q. The degree d can also be computed in the following way. Using an adequate permutation of the states, Q can be recomposed into a block upper triangular matrix.

Q =      Q 1,1 Q 1,2 • • • Q 1, 0 Q 2,2 • • • Q 2, . . . . . . . . . . . . 0 0 • • • Q ,      (14)
where each Q j,j is an irreducible square matrix. We denote by -ν j the maximal eigenvalue of the jth block Q j,j . Since Q j,j is irreducible, -ν j is real, negative, and simple by Perron-Frobenius. We say that block Q j,j is communicating with block Q v,v , v > j , if the block Q j,v is not null. By definition, the communication graph of Q is acyclic. Let us tag the components whose maximal eigenvalues are maximal among all -ν j 's. The degree d of Q is defined as the maximal number of tagged components over any path in the communication graph.

Irred. compo. 1 -ν 1 Irred. compo. 2 -ν Irred. compo. 3 -ν Irred. compo. 4 -ν Irred. compo. 5 -ν 5 0 Figure 1:
Example of a communication graph over the irreducible components of a matrix Q. Each component j has a maximal eigenvalue -νj that is simple. The dashed lines to 0 are just a reminder that the sums over some lines in Q are negative, corresponding to a transition to the absorbing state (0) in matrix P .

To illustrate this definition, let us consider the transition graph of Figure 1 and assume that -

ν 2 = -ν 3 = -ν 4 = -ν are maximal. The degree is d = 3 because the path Q 1,1 → Q 2,2 → Q 3,3 → Q 4,4 contains 3 tagged components.

Classical coupon collector and double-dixie problems.

As mentioned in the introduction, the coupon collector can be seen as the simplest instance of our problem. We use it as an illustration of how to use Theorems 3.1 and 3.2. It shows the usefulness of our approach: the well-known formulas for the classical coupon collector are obtained directly using our approach.

We consider the classical coupon collector problem: there are n different types of coupon. At each time step, a coupon of type i is picked at random, uniformly among all coupon types, until k coupons of each kind are collected. It is proved in [START_REF] Newman | The double dixie cup problem[END_REF] that the expectation of T n (average time to collect k coupon of each type is bounded by n(log n + (k -1) log log n + O(1)). In this section, we show that our approach allows one to retrieve this result directly and even get the more precise statement given in [START_REF] Erdös | On a classical problem of probability theory[END_REF]: We also provide the asymptotic distribution of T n and the asymptotics of its moments.

The transition graph of each coupon type is

0 1 . . . k 1 1 1 1
This is certainly the simplest chain with an absorbing state and, in isolation, the absorbing time for each component is trivial and is equal to k. This case is homogeneous (all coupon types have the same transition matrix) and uniform (uniform choice among all coupon types).

The matrix Q (defined in ( 1)) corresponding to this Markov chain is a k × k matrix that has -1 on its diagonal and 1 on its sub-diagonal. It has one eigenvalue ν = -1 that has a degree k. In the homogeneous and uniform case, the ODE (3) becomes

       d dt M k (t) = - 1 n M k (t) d dt M i (t) = - 1 n M i (t) + 1 n M i+1 (t) for 0 < i < k with M k (0) = 1 and M i (t) = 0 for i ∈ {0 . . . k -1}. M 0 (t)
is the cumulative distribution function of an Erlang variable of parameter (k, 1) (i.e. the sum of k i.i.d. exponential variables of parameter 1) which can be written:

M 0 (t) = 1 - i-1 i=0 (t/n) i e -t/n i! = 1 - (t/n) k-1 e -t/n (k -1)! + O((t/n) k-2 e -t/n ).
The solution in t of

(t/n) k-1 e -t/n (k-1)! = 1/n is -n(k -1)W -1 -1 k-1 (k-1)! n 1/n
, where W -1 is the second branch of the Lambert W function. Since W -1 (x) = log(-x)log(-log(-x))+o(1) when x < 0 approaches 0, one gets t n = n(log n+(k-1) log log nlog((k -1)!)) + o(n). Using Theorems 3.1, and 3.2, this shows that the time T n to collect k coupons of each type satisfies:

lim n→∞ P (T n ≤ n[log n+(k -1) log log n + x]) = e -e -x (k-1)! E [T n ] = n log n+(k-1)n log log n+n(γ-log((k-1)!) + o(n) var [T n ] = π 2 n 2 6 + o(n 2 ).
It is interesting to notice that the variance of T n does not depend on k when n is large, and more generally that the asymptotic distribution of T n is Gumbel and its shape does not depend on k.

To illustrate this result and give a grasp on the respective behaviors of T n and t n with n, we ran several simulations of the coupon collector (with k = 1) and display the corresponding values of T n and t n . Figure 2 shows the empirical proportion of coupons collected up to time t, M 0 (t) and its fluid approximation 1 -m(t) (using the notations of Section 2.1). Although these plots only show a single trajectory and its fluid limit, they are rather typical. They illustrate the fact that T n and t n are very close to each other. We have also computed the empirical distribution of T n and tested it against its limit Gumbel distribution. Figure 3 shows the cumulative empirical distribution of T n as well as the cumulative distribution of a Gumbel distribution with different values of n. In the case k = 1, the convergence appears to be quick and the cumulative distribution of (T n -t n )/n seems to coincide with the one of the Gumbel distribution for n ≥ 100. For k = 5, even if one can convince oneself that there is convergence to the limit distribution, this convergence appears to be slow.

Numerical methods for t n : an example with non-uniform probabilities.

The case when probabilities to get the different coupons are not uniform is also well studied (see for example [START_REF] Berenbrink | The weighted coupon collector's problem and applications[END_REF] and references therein). Most papers provide bounds on the collection time. When the probability vector (p 1 , . . . , p n ) satisfy Assumptions ( 6) and ( 7)), Theorem 3.

2 shows that E [T n ] = t n + nγ/ν + o(n), where t n satisfies n i=1 α exp(p i Qt n )1 = 1. ( 15
)
There is in general no closed-form formula for t n . Yet, Equation ( 15) is easy to solve numerically (using a classical Newton's method for example) with a very good precision. This can be done by using a numerical computation of the exponential of the matrix Q. Similarly, the value of the largest eigenvalue of Q can be computed Gumbel dist. numerically. This numerical computation provides an alternative method to estimate T n , much faster than the repetition of simulations.

k = 1 k = 5
We illustrate this method and show its accuracy by computing the time to collect k coupons that have non-uniform probabilities, under the two following probability distributions, that we call p log and p square . These distributions p log and p square select the chain i with probabilities respectively proportional to (log(1 + i)) -1 and i -2 . For a system with n chains, these probabilities are:

p log i = (log(1 + i)) -1 n j=1 (log(1 + j)) -1 p square i = i -2 n j=1 j -2
We implemented a simulator of the non-uniform coupon collector and a numerical algorithm that computes the quantity t n + γ/p n . We compare the value E [T n ] (computed by averaging 1000 runs of the simulator) with the quantity t n + γ/p n . We report the results in Table 1 for three different probability distribution: uniform (p i = 1/n), log (p i ∝ 1/ log(1 + i)) and square (p i ∝ 1/i 2 ). We observe that in all cases, there is a good match between the approximation and the simulation. Also, as expected, the average hitting time E [T n ] is the smallest for the uniform distribution and is the largest for the square distribution.

The time taken by our simulator to compute 1000 simulation for n = 50 and k = 5 is about ten minutes. In contrast, it takes less than a second to compute the value t n with a non-optimize implementation of the numerical algorithm that uses a dichotomic search and the standard matrix exponential function of python numpy to compute t n . The most costly operation of our implementation is the evaluation of the left hand side of Equation ( 15) that requires the computation of n exponentials of k × k matrices. Moreover, by Theorem 3.2, the variance of the simulation for the square distribution grows as n 2 , which leads to confidence intervals that grow with n. This makes the numerical computation of t n much faster than the simulation for large value of n. The general formula for t n involves the largest eigenvalue of Q. For the classical coupon collector, this eigenvalue is easy to compute in closed form. This is not true in general. As for non-uniform probabilities, a numerical algorithm can always be used to compute t n . In this section, we provide an alternative by showing that an upper bound on t n can be computed by using T 1 , the hitting time of 0 for a single component. This quantity is often much easier to compute. We consider the system made of a single component. The quantity E [T 1 | X 1 (0) = x] is the expected hitting time of 0 starting from a state x. We define the quantity T max 1 to be the largest expected hitting time, over all possible initial states x:

T max 1 = max x∈{1...k} E [T 1 | X 1 (0) = x] . (16)
Our next result uses the fact that T max 1 is an upper bound on -1/ν, with possible equality only if the degree is one. It implies that in particular that the expectation of the hitting time T n satisfies

E [T n ] ≤ T max 1 (n log n + nγ) + o(n). ( 17
)
This inequality is most of the time strict. For example, for the coupon collector with k coupons,

T max 1 = k and t n = n log n + (k -1)n log log n + O(n) kn log n + O(n).
Also, the inequality is in general strict, even when the matrix Q is irreducible. An example is the case of the erasure channel, shown in this section: The upper bound reported in Figure 4 is strict while the original matrix Q is irreducible. Theorem 4.1. Let T max 1 be defined as in Equation [START_REF] Latouche | Introduction to matrix analytic methods in stochastic modeling[END_REF]. Then, in the case of uniform probabilities p i = 1/n:

t n ≤ T max 1 n log n + o(n).
Proof. Theorem 3.2 combined with Equation [START_REF] Kang | Asymptotic approximations for the stationary distributions of many-server queues[END_REF] shows that E [T n ] = (1/ν)n log n+ ((d-1)/ν)n log log n-n log(aν 1-d )/ν +nγ/ν +o(n), where -ν is the largest eigenvalue of Q and d is the degree of the eigenvalue -ν. We now show that 1/ν ≤ T max 1 with possible equality only in a special case, treated later.

As Q is non-singular, we have:

E [T 1 | X 1 (0) = x] = ∞ t=0 P (T 1 ≥ t | X 1 (0) = x) = ∞ t=0 k j=1 (I + Q) t xj = - k j=1 (Q -1 ) xj .
The largest eigenvalue of Q -1 is -1/ν. Moreover, the term Q -1 xj is a sum of nonnegative terms and is therefore non-negative. By Perron-Frobenius theorem, this implies that

-1/ν ≤ max x j -Q -1 xj = T max 1 .
If the inequality is strict, we get the desired result, namely t n ≤ T max 1 n log n + o(n). Now, the inequality becomes an equality only when the eigenvalue -1/ν of Q -1 admits 1 as an eigenvector. This implies that exp(Qt) also admits 1 as an eigenvector for eigenvalue exp(-νt). In this case, the quantity α exp(Qt)1 used in the definition of t n can be computed exactly and is equal to α exp(-νt)1 = exp(-νt), because α1 = 1. Therefore t n admits an exact form,

t n = 1 ν n log n = T max 1 n log n.
Let us illustrate this theorem with the following chain for each component:

0 1 2 . . . k-1 k q 1 -q q 1 -q q 1 -q q 1 -q q 1 -q
This is a natural model of the lifetime of an erasure channel system. An erasure channel transmits bits and each of them gets erased with probability p. The state of the channel is the current number of consecutive bits that have been erased. When this number reaches some value k (that depends on the forward error correction that is used), the message transmitted on the channel cannot be corrected anymore and the channel is declared faulty. Here we consider a communication system made of n parallel independent erasure channels and we look at its lifetime: When all channels become faulty, the communication stops.

For this example, the quantity T max 1 can be easily computed in closed form. Indeed, let h j := E [T 1 | X 1 (0) = j] be the expected hitting time of 0 starting from j. We have h 0 = 0 and for j ∈ {1, . . . , k}:

h j = 1 + qh j-1 + (1 -q)h k .
One can verify that the vector h such that h j = j-1 i=0 q i-k is the unique solution of the above system of equations. This implies that T max 1 = max j∈{0,...,d} h j = k-1 i=0 q i-k = (q -k -1)/(1 -q). Hence, Theorem 4.1 implies that for this example:

E [T n ] ≤ q -k -1 (1 -q) (n log n + γ) + o(n). ( 18
)
We implemented a simulator of the erasure model as well as a numerical algorithm to compute the asymptotically exact approximation t n +nγ/ν. We restrict our comparison to the case of uniform probabilities. To compute numerically t n , we use a dichotomic algorithm similar to the one of Section 4.3 and we use functions from numpy standard library to compute the eigenvalue -ν. In Figure 4, we compare numerically the bound provided by Equation ( 18), with the asymptotically exact bound of Theorem 3.2. We report the results for n = 10. We also computed the results for larger values of n. They are similar and not reported in the paper. We observe that, for this model, the approximation t n + nγ/ν is very close to the value obtained by simulation, even when n = 10. Second, as expected, T max 1 (n log n+γ) is an upper bound on this value. For large values of q, this upper bound is loose (roughly twice as large as t n + nγ/ν). This bound becomes tighter as q decreases (about 3% off the correct value when q = 0.7).

Coupling time of random walks.

In general, computing coupling times of Markov chains is useful because they provide bounds on their mixing times, [START_REF] Levin | Markov Chains and Mixing Times[END_REF]. They also correspond to the average time complexity of perfect simulation algorithms [START_REF] Propp | Exact sampling with coupled Markov chains and applications to statistical mechanics[END_REF]. As for random walks, they are often used to model discrete event systems, such as queuing networks. Here we consider a random walk on a finite grid {1, . . . , k} n . We first analyze a non-lazy random walk. It is usually more difficult to deal with coupling times in non-lazy random walks, while it makes no difference with our approach.

The random walk is defined as follows. From a position (x 1 , . . . , x i , . . . , x n ) the walker moves to a neighboring position (x 1 , . . . , x i + 1, . . . , x n ) with probability q i and to (x 1 , . . . , x i -1, . . . , x n ) with probability r i . On the borders, with probability q i (resp. r i ) the walker remains at the same position if x i = k (resp. x i = 1). In the following we will consider several possible values of (q i ) and (r i ) satisfying assumptions ( 6) and [START_REF] Doumas | The coupon collector's problem revisited: Generalizing the double dixie cup problem of newman and shepp[END_REF]. The random walk in dimension two is displayed in Figure 5. We consider a coupling of k n versions (X x ) x∈{1...k} n , of the chain X, one per possible initial state, under which all chains take the same transitions. We are interested in computing the first time T n such that the state of the system does not depend on the initial state, i.e., such that for any initial state x and y: X x (T n ) = X y (T n ) (note that by assumption on the coupling, this implies that X x (t) = X y (t) for t ≥ T n ).

q 2 q 2 q 2 r 2 r 2 r 2 r 1 r 1 r 1 q 1 q 1 q 1 r 1 q 2 r 2
By monotonocity of the random walk, the coupling time T n is equal to the coupling time of the two extreme chains L and U starting respectively in the extreme points, namely L(0) = (1, . . . , 1) and U(0) = (k, . . . , k). Another property of this coupling is that whenever coalescence occurs in one coordinate, say i, (L i (t 0 ) = U i (t 0 )) then this partial coalescence remains: ∀t ≥ t 0 , L i (t) = U i (t).

We consider the Markov chain X := (L, U). Each component, corresponding to one coordinate, X i := (L i , U i ), is selected with probability p i := q i + r i . Once a coordinate has been chosen, the two walks U i and L i take the same step: They both increase (resp. decrease) their i-th coordinate with probability q i /p i (resp. r i /p i ), if possible. Each component has two absorbing states corresponding to the coalescence of L i and U i , namely (1, 1) and (k, k). Note that it makes no difference with the case with a single absorbing state because one can always merge all absorbing states into one.

All this implies that this chain fits in our general framework by using the transition matrix for each component depicted in Figure 6. At time 0, the difference is maximum:

(L i (0), U i (0)) = (1, k).
If the chain is a state (a, b) (with a < b), it jumps to the state (a + 1, min(b + 1, k)) with probability q i /p i and to the state (max(a -1, 0), b -1) with probability 1 -q i /p i .

Homogeneous and uniform case.

Let us first consider the homogeneous and uniform case. In our context, this means that q i and r i do not depend on i. Of course this implies that p i = q i + r i = 1/n. However homogeneity and uniformity do not imply that q i = r i . Therefore, the walk can still have a drift. In the rest of this subsection, the index i is useless and will be dropped.

1,k 1,k-1 2,k k-1,k 1,2 2,3 1,1 k,k k
The asymptotics of T n depend on the largest eigenvalue of Q. As seen in Figure 6, this matrix is block lower triangular because the difference U -L cannot increase. Therefore, the largest eigenvalue of Q is the largest eigenvalue of one of its block diagonal matrices. It should be clear that the block with the largest eigenvalue is the the largest block, corresponding to the level U i -L i = 1 in Figure 6. The sub-matrix of Q corresponding to this (k -1) × (k -1) block is

A =         -(c + d) c d -(c + d) c d . . . . . . . . . . . . c d -(c + d)         , (19)
with c = nq and d = nr. It is shown in [START_REF] Kulkarni | Eigenvalues of tridiagonal pseudo-toeplitz matrices[END_REF] that the eigenvalues of this matrix are -(d+c)+2 √ cd cos(jπ/k) = -1 + 2 n 2 qr cos(jπ/k), j ∈ {1, . . . , k}. Hence, the eigenvalue with the largest real part is -1 + 2n √ qr cos(π/k) and has a multiplicity 1.

• When p = q, Theorem 3.2, together with cos(π/k) ≤ 1, imply that the coupling time T n satisfies

E [T n ] = 1 -1 + 2n √ qr cos(π/k) n log n + O(n) 1 -1 + 2 √ cd n log n + O(n),
where c := nq and d := nr are the normalized probabilities that do not depend on n. Note that the approximation cos(π/k) ≈ 1 becomes more accurate as k grows.

• The case q = r = 1 2n corresponds to the random walk with no drift. In this case one can use the second order Taylor expansion cos(π/k) -1 ≈ π 2 /(2k 2 ). This implies

E [T n ] = 1 cos π k -1 n log n + O(n) ≈ 2k 2 π 2 n log n + O(n).
At this point, one can notice that this approach provides an equivalent to the coupling time rather than an upper bound, as usually done in the literature [START_REF] Levin | Markov Chains and Mixing Times[END_REF]. Also note that the asymptotic behavior of the random walk with a drift is very different from the case with no drift: in the drift case, the asymptotic coupling time does not depend on k, the size of the grid, while in the no-drift case, the coupling time grows as k 2 .

Heterogeneous cases.

We first consider the heterogeneous case with uniform choices, i.e., q i + r i = 1/n so that the coordinate i is chosen with probability 1/n. To comply with conditions ( 6) and ( 7), and with the assumptions of Theorem 3.3, we assume that q i is of the form c i /n for all i (where c i is a constant). Uniformity implies that r i = (1 -c i )/n.

By applying the results of Theorem 3.3 and the general form of the eigenvalues of the matrix of Equation ( 19), there exists c ∈ [min c i , max c i ] such that the coupling time is:

E [T n ] = 1 2 c(1 -c) cos π k -1 n log n + O(n).
Let us now consider a random walk with heterogeneous as well as non-uniform transitions. This is the case when, for example, for all i, p i = c i /n and q i = d i /n but c i + d i is not necessarily equal to 1. In that case, Theorem 3.3 says that there exist c ∈ [min c i , max c i ] and d ∈ [min d i , max d i ] such that the coupling time is:

E [T n ] = 1 2 √ c d cos π k -d - c n log n + O(n).
This result calls for several comments.

• First, the behavior of the heterogeneous and/or non-uniform case is very similar to the homogeneous and uniform random walk with a drift: when n is large:

E [T n ] ≈ Cn log n
where C is a constant that does not depend on k, the size of the state space.

• Up to our knowledge, this is the first time an asymptotic of the coupling of a random walk with general probabilities (not dependent on the position) is computed in closed form.

Lazy random walk on the torus.

Other random walks can be analyzed with this approach. In this section, we compute the coupling time of the uniform lazy chain on the torus {0 . . . k -1} n mod (k, . . . , k), analyzed in Chapter 5 of [START_REF] Levin | Markov Chains and Mixing Times[END_REF]. At each step, the lazy random walk remains at its current position with probability 1/2. With probability 1/2, one coordinate i is picked and X i (t + 1) = X i (t) + 1, or X i (t) -1, with probability 1/2. We show that the coupling time of the lazy chain is similar to the previous one.

We consider the following coupling of two lazy random walks X and Y that start at x and y respectively. At each step, we first pick one of the n coordinates at random. If the positions of the two walks agree in the chosen coordinate, we move both of the walks by +1, -1 or 0 in that coordinate, with respective probabilities 1/4, 1/4 and 1/2. If the positions of the two walks differ in the chosen coordinate, we randomly choose one of the chains to move, leaving the other fixed. We then move the selected walk by +1 or -1 in the chosen coordinate, with probability 1/2.

The coupling time of the chain is the first time when X and Y agree in all coordinates. For each coordinate, the clockwise difference min{(X i -Y i ) mod k, (Y i -X i ) mod k} has the transition matrix displayed in Figure 7. This transition matrix is the same as A, the largest diagonal block of the previous chain, given in [START_REF] Neal | The generalised coupon collector problem[END_REF], but with size k instead of k -1, and folded in two by the middle. Therefore, the coupling time of the lazy walk on the torus is asymptotically the same:

0 1 2 . . . k/2 1/2 1/2 1/2 1 1/2 0 1 2 . . . k-1 2 1/2 1/2 1/2 1/2 1/2 1/2
E [T n ] = 1 cos π k+1 -1 n log n + O(n) ≈ 2(k + 1) 2 π 2 n log n + O(n).
This is a more precise statement than the results given in [START_REF] Levin | Markov Chains and Mixing Times[END_REF] that only give bounds.

Conclusions and Future work.

In this paper, we have shown how fluid approximations can be used to get precise and efficient estimations of the absorbing time of discrete time Markov chains made of several components. Our approach allows us to obtain closed form results or numerical methods that have shown to be accurate as the number of chains n tends to infinity. We applied this approach get closed form formulas for the coupon collector, the lifetime of erasure channels and coupling times in finite random walks.

One of the main feature of our model is the fact that the components are independent of each other (up to the mutual exclusion). One could think of extending our approach to interacting components, with transition matrices that depend on the state of other components. We believe that the absorbing time of all the components can still be computed using a similar approach. One natural application of this would be the computation of the time of extinction in SIR models of infections. We use the notations introduced in the paper before Theorem 3.1, without recalling them here. Note that to ease the notations, we avoid to write explicitly the dependence of p on n and write (p 1 . . . p n ) instead of (p

(n) 1 . . . p (n) n ). For a fixed n, the distribution p i satisfies p 1 ≥ p 2 • • • ≥ p n . Let f (t) = α exp(Qt)1.
The function f is non-increasing and positive. Hence, for all , by definition of t n in Equation ( 5), we have:

1 = n i=1 f (p i t n ) ≥ i=1 f (p i t n ) ≥ f (p n-t n )
This shows that for all , f (p n-t n ) ≤ 1/ . By the Assumption (7), the quantity p n-/p n converges to 1 as n goes to infinity. This implies that f (p n t n ) converges to 0 and therefore that p n t n converges to infinity as n grows. Moreover, by Equation ( 12), there exists a constant a such that f

(t) = at d-1 exp(νt)(1 + o(t)). As p 1 ≥ • • • ≥ p n , we have n i=1 f (p n t n ) ≥ nf (p i t n ). This implies that t n = O( 1
pn log 1 pn ). We define g n (x) = P (T n ≤ t n + x/p n ) and gn (x) = P T n ≤ t n + x/p n . The quantity p n t n goes to infinity as n grows. Hence for all x, t n + x/p n converges to infinity as n grows and is such that t n + x/p n = o(x/p n ). By Section 3.1, this shows that lim n→∞ |g n (x) -gn (x)| = 0.

As g corresponds to independent variables, we have

log(g n (x)) = log n i=1 (1 -f (p i (t n + x/p n ))) = n i=1 log(1 -f (p i (t n + x/p n )))
By using log(1 -x) = 1 -x + o x→1 (x) and Equation ( 12), we have:

log gn (x) = - n i=1 f (p i (t n + x/p n )) + o(1) = - n i=1 a(p i (t n + x p n )) k e -νpi(tn+ x pn ) + o(1) = -a n i=1 (p i t n ) k e -νpi(tn+ x pn ) (1 + x t n p n ) k + o(1) = -a n i=1 (p i t n ) k e -νpi(tn+ x pn ) + o(1). (20)
Let assume that x ≥ 0. The proof for x ≤ 0 is similar, by inverting most of the signs "≥" and "≤". As p i ≥ p n , we have e -νpix/pn < e -νx , which implies

Similarly, by using the union bound, for x > 0, we have:

g n (x) = n i=1 (1 -f (p i (t n + x/p n ))) ≥ 1 - n i=1 f (p i (t n + x/p n )) ≥ 1 -e -νx (1 + εn (x)), (22)
where the first inequality comes from Equation [START_REF] Shank | Coupon collector problem for non-uniform coupons and random quotas[END_REF]. Similarly, we have

When n goes to infinity, p n t n goes to infinity, which implies that Equation ( 26) is uniformly bounded in n and converges to 0 as n goes to infinity. Combining Equations (23,24,26) shows that for all m ≥ 1, the quantity [p n ( Tnt n )] m is uniformly integrable. By Theorem 3.1 this implies that all moments of p n ( Tnt n ) converges to the moment the Gumbel distribution of parameter ν. In particular, its mean converges to γν and its variance to π 2 ν 2 /6.

We conclude by showing that the moments of p n ( Tn -t n ) and the ones of p n (T n -t n ) are asymptotically the same. Recall that Tn is an Erlang variable of parameters (T n , 1) (i.e., the sum of T n independent exponential variables of mean 1). Hence As p i decreases with n and f is increasing in n, we have:

1 = i=1 f (p i t n ) ≤ nf (p n t n ) = na(p n t n ) k e -νpntn (1 + n )
As p n t n increases with n and n converges to 0, for n large enough, this is smaller than n(2a)e -1 2 νpntn . This shows that e

We define g similarly to the g of the proof of Theorem 3.1: gθ1...θn (x) = P (T θ1...θn ≥ t θ1...θn + x) .

As in Equation ( 20), we have:

log g(x) = - n i=1
(t n /n) k e -νitn/n e -νix + o(1).

By the intermediate value theorem and the definition of t n , this implies that there exists ν(θ 1 . . . θ n ) ∈ [ν min , ν max ] such that log g(x) = -e -ν θ 1 ...θn x + o(1).

The proof is similar for the moments and makes again use of the intermediate value theorem.

  1). By Wald's equation and the law of total variance, we have E[ Tn ] = E [T n ] and var[ Tn ] = var[T n ] + E[T n ]. This implies that for any sequence x n going to infinity, there exists a sequence y n such that |y n -x n | = O( √ x n ) and lim n→∞ |P(T n ≤ x n ) -P( Tn ≤ y n )| = 0.

Figure 2 :

 2 Figure 2: Collecting n coupons. Comparison of the stochastic hitting time Tn with the fluid approximation tn for n = 20 and n = 200.

Figure 3 :

 3 Figure3: Empirical cumulative distribution of (Tn -tn)/n and its limit Gumbel distribution.

4. 4 .

 4 Bounding T n by using T 1 : Example of erasure channels.

Figure 4 :

 4 Figure 4: Erasure channel: Comparison of an estimation of E [Tn] computed by simulation, the asymptotic result of Theorem 3.2 and the upper bound of Theorem 4.1 as a function of the success probability p. The simulation results are averages over 10 4 values. The confidence intervals on the mean are plotted on the figure but they are too small to be visible.

Figure 5 :

 5 Figure 5: Random walk in two dimensions with borders.

Figure 6 :

 6 Figure 6: transition matrix of the chain Xi = (Li, Ui)

Figure 7 :

 7 Figure7: transition matrix of the chain min{(Xi -Yi) mod k, (Yi -Xi) mod k}. The cases when k is even (left) and k is odd (right) are different. However, they both correspond to the transition matrix A folded in two.

  Appendix A. Proof of Theorem 3.1

(( 1

 1 p i t n ) k e -νpi(tn+ x pn ) ≤ n i=1 (p i t n ) k e -νpitn e -νx = e -νx .Moreover, for x ∈ [0; p n t n /2], we have:f (p i (t n -x/p n )) = a(p i (t n -x/p n ) k )e -νpi(tn-x/pn) (1 + (p i (t n -x/p n ))) ≥ a(p i t n ) k e -νpitn e νx 2 -k (1 + (p i (t n -x/p n ))), which implies that n i=1 f (p i (t n -x/p n )) ≥ e νx 2 -k (1 + εn (x)), where ε(x) is such that lim n→∞ sup x∈[0,tnpn/2] |ε n (x)| = 0. By using that log(1 -x) ≤ -x, this implies that g n (-x) = n i=1 -f (p i (t n -x/p n ))) ≤ exp(-n i=1 f (p i (t n -x/p n )))≤ exp(-e νx [1 + εn (x)])

( 1 -

 1 with lim n→∞ sup x>0 |ε n (x)| = 0. Recall thatg n (x) = P Tn ≤ t n + x/p n = n i=1 f (p i (t n + x/p n )))is increasing in x. Thus, by letting e n = max(ε n , sup x>0 |ε n (x)| , sup x∈[0,tnpn/2] |ε n (x)|), we have lim n→∞ e n = 0. For any A > 0 and any m ∈ {1, 2 . . . }, we have: E [p n ( Tn -t n )] m 1 pt( Tn-tn)≥A =

E p n Tn -t n m 1

 1 {pn( Tn-tn)≤-A} =

E

  ( Tn ) = E E ( Tn ) | T n = E [T n (T n + 1) . . . (T n + -1)] . In particular, E [p n (T n -t n )] = E p n ( Tn -t n ) → γ. Let m ∈ {1, 2 . . . }, we have: E [p n ( Tn -t n )] m = (p n ) m m =1 m E ( Tn ) (-t n ) m- = (p n ) m m =1 m E [T n (T n + 1) . . . (T n + -1)] (-t n ) m-The previous expression is equal toE [[p n (T n -t n )] m ] plus a sum of terms of order (p n ) m E (T n ) (t n ) m-with ≤ -1. As E [T n ] = t n + γ + o(1), showing that (p n ) m (t n ) m-1 implies that E [p n ( Tn -t n )]m and E [[p n (T n -t n )] m ] have the same limit.

Table 1 :

 1 Coupon collector and non-uniform probabilities: Comparison between the approximation tn + γ/pn and the empirical average of E [Tn] computed over 1000 runs of the simulator. The value ±x indicate the 95% confidence intervals on the mean.

		n = 10		n = 20		n = 50
		Simulation t n + γ pn	Simulation t n + γ pn	Simulation	t n + γ pn
	Unif (k = 5)	29.4 ± 0.2	28.8	71.8 ± 0.5	71.5	224.2 ± 1.2	224.5
	log (k = 1)	35.8 ± 1.0	35.9	88.3 ± 2.0	90.2	275.5 ± 5.0	277.6
	square (k = 1) 247.6 ± 9.3 271.5 1255 ± 39	1346	10590 ± 262 10950
	Unif (k = 5)	89.4 ± 0.4	85.7	199.7 ± 0.7 194.6 569.8 ± 1.8	557.9
	log (k = 5)	116.3 ± 1.8 109.9 257.3 ± 3.2 251.1 720.9 ± 7.8	704.0
	square (k = 5) 922 ± 18	834.5 4209 ± 77	3987	31277 ± 455 30214

  It should be clear that Equation (23) and (24) are uniformly bounded in n by a bound that converges to 0 as A goes to infinity. Moreover (25) is equal to (p n t n ) m

	2m	g n (-	p n t n 2	) ≤	(p n t n ) m 2m	e -νpn tn 2	(1+en) .

m exp(-e νx (1 -e n ))dx (

24

)

+ (p n t n ) m-1 m g n (-p n t n /2)[p n t n -p n t n 2 ]

(25)

Acknowledgment

This project was partially supported by the EU project QUANTICOL 600708.

Moreover, for all , we have:

Last, by definition of t n , we have

. Hence, we have:

where the last inequality comes from the fact that p i-/p i decreases with n (assumption (6)) and that p i t n converges to infinity. Now, let ε > 0 and n such that p i /p n ≥ (1 + ε) if and only if i < nn . We have ( p n- pn ) k e -νtn(p n--pn) ≤ (1 + ε) k e -νtnpnε , which converges to 0 as n goes to infinity. This shows Equation (8) for x ≥ 0. The proof for x ≤ 0 is similar, by inverting most of the signs "≥" and "≤".

Appendix B. Proof of Theorem 3.2

The proof consists in three steps. We first obtain uniform upper and lower bounds on g n (x) := P Tn ≤ t n + x/p n . We then use this bound to show that for all m ∈ {1, 2 . . . }, the sequence [p n ( Tn -t n )] m is uniformly integrable, which shows that the moments of p n ( Tn -t n ) converge to the one of a Gumbel distribution. We then show that the moments p n (T n -t n ) converge to the ones of E p n ( Tn -t n ) .

Recall that, f (t) = at k e -νt (1 + t)(1 + (t)) with lim t→∞ (t) = 0. By definition of t n , this implies 1 =

The proof is similar to the proof of Theorem 3.1. We only provide a sketch of proof. Up to replacing Q i by p i Q i , by assumption [START_REF] Flajolet | Birthday paradox, coupon collectors, caching algorithms and self-organizing search[END_REF], one can assume that the probabilities are uniform: p i = 1/n.