Keywords: subgroups of free groups, finite group presentations, statistical properties, Stallings graphs, partial injections, malnormality MSC: 20E05, 05A15, 20F69

The usual way to investigate the statistical properties of finitely generated subgroups of free groups, and of finite presentations of groups, is based on the so-called word-based distribution: subgroups are generated (finite presentations are determined) by randomly chosen k-tuples of reduced words, whose maximal length is allowed to tend to infinity. In this paper we adopt a different, though equally natural point of view: we investigate the statistical properties of the same objects, but with respect to the so-called graph-based distribution, recently introduced by Bassino, Nicaud and Weil. Here, subgroups (and finite presentations) are determined by randomly chosen Stallings graphs whose number of vertices tends to infinity.

Our results show that these two distributions behave quite differently from each other, shedding a new light on which properties of finitely generated subgroups can be considered frequent or rare. For example, we show that malnormal subgroups of a free group are negligible in the graphbased distribution, while they are exponentially generic in the word-based distribution. Quite surprisingly, a random finite presentation generically presents the trivial group in this new distribution, while in the classical one it is known to generically present an infinite hyperbolic group.

Introduction

Statistical properties of elements and subgroups of free groups have evoked much interest in recent years, especially after Gromov's famous claim [14, 0.2.A] that "most" groups were hyperbolic, which led to precise statements and proofs by Ol'shanskiȋ [START_REF] Yu | Ol ′ shanskiȋ. Almost every group is hyperbolic[END_REF] and by Champetier [START_REF] Champetier | Propriétés génériques des groupes de présentation finie[END_REF][START_REF] Champetier | Propriétés statistiques des groupes de présentation finie[END_REF]. Shortly thereafter, Ol'shanskiȋ and Arzhantseva [START_REF] Goulnara | Ol ′ shanskiȋ. Generality of the class of groups in which subgroups with a lesser number of generators are free[END_REF][START_REF] Goulnara | A property of subgroups of infinite index in a free group[END_REF] pursued the study of the statistical properties of finite presentations of groups, that is, largely, of finitely generated normal subgroups of free groups. We refer the reader to the survey by Ollivier [START_REF] Ollivier | A January 2005 invitation to random groups[END_REF] for more details.

This interest encountered another historical trend in combinatorial group theory, namely the consideration of algorithmic problems, which leads naturally to an interest in the evaluation of the complexity of these algorithms (e.g. [START_REF] Birget | PSPACEcomplete problems for subgroups of free groups and inverse finite automata[END_REF][START_REF] Margolis | Closed subgroups in pro-V topologies and the extension problem for inverse automata[END_REF][START_REF] Roig | On the complexity of the Whitehead minimization problem[END_REF]) and in enumeration problems.

The search for innovative group-based cryptographic systems (see [START_REF] Myasnikov | Group-based cryptography[END_REF] for instance) only reinforced the study of complexity questions, and focused it on the investigation of the statistical properties of finitely generated subgroups of free groups, notably via the notion of generic complexity (see [START_REF] Kapovich | Generic properties of Whitehead's algorithm and isomorphism rigidity of random one-relator groups[END_REF][START_REF] Jitsukawa | Malnormal subgroups of free groups[END_REF]).

The usual method to approach statistical properties is to enumerate the objects under consideration, or more precisely, representatives for these objects, in a stratified way. For instance, if we wish to investigate k-generated subgroups of F r (resp. finitely presented groups with r generators and k relators), we proceed by enumerating lists of k-tuples of generators (resp. relators) over a fixed alphabet of r letters, so that at level n one has enumerated all such ktuples whose elements have length at most n. In the situation we will consider, there are only finitely many objects of a given level n and it makes sense to ask what proportion of level n objects satisfy a given property. This gives us a number p n between 0 and 1 for each n, associated to the given property and one can ask whether this sequence has a well defined limit. If the limit exists and is equal to 1, we would say that the property is generic, and take this to mean that most objects satisfy the property. At the other extreme, if the limit of the p n equals 0, we would say that the property in question is negligible and conclude that it is rarely encountered amongst our objects.

A crucial observation, which is well worth mentioning in view of the intuitive weight carried by expressions such as most objects or rarely encountered, is that genericity and negligibility depend essentially on the choice of the stratification: different stratifications of the same objects, say finitely generated subgroups of free groups, will bring to light different insights on the statistical behavior of these objects. Concretely, different properties will appear to be generic or negligible.

Up to recently (namely the publication of [START_REF] Bassino | Random generation of finitely generated subgroups of a free group[END_REF]), the literature was unanimous in adopting the representation of finitely generated subgroups of free groups by k-tuples of generators, stratified by their maximal length -which we call the word-based distribution.

It is the purpose of this paper to question this unanimity. The basic idea is that there exists another very natural representation of finitely generated subgroups of free groups, by their Stallings graph ( [START_REF] Stallings | Topology of finite graphs[END_REF], see Section 2.1). Stratifying finitely generated subgroups by the size (number of vertices) of their Stallings graph -what we call the graph-based distribution -indeed sheds a different light on which properties of subgroups are frequent or rare. One of our main results is that malnormality and purity, which are generic in the word-based distribution, are negligible in the graph-based distribution (Section 4).

We also exhibit a property of finitely generated subgroups of F r that is negligible in the word-based distribution and that has a non-zero, non-one asymptotic probability (namely e -r ) in the graph-based distribution (Section 5).

Finally we explore the possibility of using the graph-based distribution to discuss the statistical properties of finitely presented groups. The results there are disappointing: it turns out that finitely presented groups are generically trivial in this distribution -quite differently from the word-based distribution in which they are known to be generically infinite and hyperbolic (Section 6).

Sections 2 and 3 are devoted to preliminaries on genericity and to a review of the main features of the word-based and the graph-based distributions for finitely generated subgroups of free groups.

Preliminaries

Here we summarize standard facts about the Stallings graphs of subgroups (in Section 2.1) and we review the notions of generic and negligible properties.

Throughout the paper, A denotes an alphabet, that is, a finite non-empty set and F (A) denotes the free group over A. The elements of F (A) are represented by the reduced words written using letters from A and their formal inverses {a -1 | a ∈ A}. If r ≥ 1, we often use the notation F r instead of F (A), to indicate that A consists of r letters. Throughout the paper, we will in fact assume that r ≥ 2.

We denote by [n] (n ≥ 1) the set {1, . . . , n}.

Subgroup graph representation

Each finitely generated subgroup of F (A) can be represented uniquely by a finite graph of a particular type, by means of the technique known as Stallings foldings [START_REF] Stallings | Topology of finite graphs[END_REF]. This representation has been used by many authors, frequently using combinatorial, graph-theoretic notations that slightly differ from those used by Stallings. It is this formalism that we also use, which can also be found in [START_REF] Weil | Computing closures of finitely generated subgroups of the free group[END_REF][START_REF] Kapovich | Stallings foldings and subgroups of free groups[END_REF][START_REF] Nicholas | A fast algorithm for Stallings' folding process[END_REF][START_REF] Miasnikov | Algebraic extensions in free groups[END_REF]. The procedure of Stallings foldings is informally described at the end of this section. An A-graph is defined to be a pair Γ = (V,

E) with E ⊆ V × A × V , such that • if (u, a, v), (u, a, v ′ ) ∈ E, then v = v ′ ; • if (u, a, v), (u ′ , a, v) ∈ E, then u = u ′ .
The elements of V are called the vertices of Γ and the elements of E are its edges. We say that Γ is connected if the underlying undirected graph is connected. If v ∈ V , we say that v is a leaf if v occurs at most once in (the list of triples defining) E and we say that Γ is v-trim if no vertex w = v is a leaf. Finally we say that the pair (Γ, v) is admissible if Γ is a finite, v-trim and connected A-graph. Then it is known (see [START_REF] Stallings | Topology of finite graphs[END_REF][START_REF] Weil | Computing closures of finitely generated subgroups of the free group[END_REF][START_REF] Kapovich | Stallings foldings and subgroups of free groups[END_REF][START_REF] Miasnikov | Algebraic extensions in free groups[END_REF]) that:

• Stallings associated with each finitely generated subgroup H of F (A) a unique admissible pair of the form (Γ, 1), which we call the graphical representation or the Stallings graph of H and write Γ(H);

• every admissible pair (Γ, 1) is the graphical representation of a unique finitely generated subgroup of F (A);

• if (Γ, 1) is the graphical representation of H and u is a reduced word, then u ∈ H if and only if u labels a loop at 1 in Γ (by convention, an edge (u, a, v) can be read from u to v with label a, or from v to u with label a -1 );

• if (Γ, 1) is the graphical representation of H, then rank(H) = |E|-|V |+1;

• finitely generated subgroups H and K are conjugates if and only if the cyclic cores of Γ(H) and Γ(K) (obtained by repeatedly deleting leaves and the edges they are adjacent to) are equal.

We informally remind the readers of the computation of the graphical representation of a subgroup generated by a subset B = {u 1 , . . . , u k }. It consists in building an (A ⊔ A -1 )-graph, changing it into a A-graph, then reducing it using foldings. First build a vertex 1. Then, for every word u of length n in B, build a loop with label u from 1 to 1, adding n -1 vertices. Change every edge (u, a -1 , v) labeled by a letter of A -1 into an edge (v, a, u). Then iteratively identify the vertices v and w whenever there exists a vertex u and a letter a ∈ A such that either both (u, a, v) and (u, a, w) or both (v, a, u) and (w, a, u) are edges in the graph (the corresponding two edges are folded, in Stallings' terminology).

The resulting graph Γ is such that (Γ, 1) is admissible and, very much like in the (1-dimensional) reduction of words, it does not depend on the order used to perform the foldings.

Negligibility and genericity

Let S be a countable set, the disjoint union of finite sets S n (n ≥ 0), and let B n = i≤n S i . Typically in this paper, S will be the set of Stallings graphs, of partial injections, of reduced words or of k-tuples of reduced words, and S n will be the set of elements of S of size n. A subset X of S is negligible (resp. generic) if the probability for an element of B n to be in X, tends to 0 (resp. to 1) when n tends to infinity; that is, if lim n |X∩Bn| |Bn| = 0 (resp. = 1). Naturally, the negligibility or the genericity of a subset X of S depends on the layering of S into the S n . In particular, if X and its complement are both infinite, then an appropriate partition of S into finite subsets S n will make X negligible, another will make it generic, and indeed, another will be such that lim n |X∩Bn| |Bn| = p for any fixed 0 < p < 1. Thus, any discussion of negligibility or genericity must clearly specify the distribution that is considered, that is, the choice of the partition (S n ) n .

Rate of convergence

In general, we may be interested in the speed of convergence of |X∩Bn| |Bn| -towards 0 if X is negligible and towards 1 if it is generic. One reason is that a higher speed of convergence indicates a higher rate of confidence that a randomly chosen element of S of size n will miss X if X is negligible, or will be in X if X is generic, even for moderately large values of n.

If a class F of functions tending to 0 is closed under max (of two elements), we say that a subset

X is F-negligible if |X∩Bn| |Bn| = O(f (n)) for some f ∈ F.
We also say that X is F-generic if the complement of X is F-negligible. Note that F-negligible (resp. F-generic) sets are closed under finite unions and intersections.

Much of the literature is concerned with exponential negligibility or genericity, namely F-negligibility or genericity where F is the class of functions e -cn (c > 0).

Balls versus spheres

The definition of negligibility and genericity above is given in terms of the balls B n : the sets of elements of size at most n. It is sometimes more expedient to reason in terms of the proportion of elements of X in the spheres S n : let us say, within the ambit of this section, that a set X is S-negligible (resp. S-generic) if the ratio |X∩Sn| |Sn| tends to 0 (resp. 1). The definition of F-S-negligibility or F-S-genericity is analogous. We verify in this section that (exponential) Snegligibility implies (exponential) negligibility. The same holds of course for genericity.

Proposition 2.1 An S-negligible (resp. S-generic) set is also negligible (resp. generic).

If the structures under consideration grow fast enough, so that lim Bn B 2n = 0, then the same result holds for exponential negligibility and genericity.

The proof of this statement relies on the following technical lemma. Lemma 2.2 Let (a n ) and (b n ) be increasing sequences of positive real numbers.

(1) (Stolz-Cesàro theorem) If lim b n = ∞ and lim a n+1 -an b n+1 -bn = 0, then lim an bn = 0.

(2) If ( bn b 2n ) and ( a n+1 -an b n+1 -bn ) converge to 0 exponentially fast and if a n ≤ b n for each n, then ( an bn ) converges to 0 exponentially fast as well.

Proof.

(1) Since lim a n+1 -an b n+1 -bn = 0, for each ε > 0, there exists n 0 such that a n+1 -a n ≤ ε(b n+1 -b n ) for all n ≥ n 0 . Summing these inequalities for all integers between n -1 and n 0 , we find that a n -a n 0 ≤ ε(b n -b n 0 ) for all n > n 0 . Dividing by b n and using the fact that lim b n = ∞, we conclude that an bn < 2ε for all large enough n.

(2) Our hypothesis is now that there exists c > 0 such that a n+1 -a n ≤ e -cn (b n+1 -b n ) for all n ≥ n 0 . Summing these inequalities for the integers between n and 2n -1, we find that a 2n -a n ≤ e -cn (b 2n -b n ) for all n ≥ n 0 . We now divide both sides by b 2n and use the fact that an b 2n ≤ bn b 2n and that this sequence converges to 0 exponentially fast to conclude that ( a 2n b 2n ) n converges to 0 exponentially fast. Summing instead for the integers between n and 2n and dividing by b 2n+1 shows that ( a 2n+1 b 2n+1 ) n converges to 0 exponentially fast as well.

⊓ ⊔

Proof of Proposition 2.1. Let X ⊆ S, a n = |X ∩ B n | and b n = |B n |. Then a n -a n-1 = |X ∩ S n | and b n -b n-1 = |S n |.
The statement on (exponential) negligibility now follows directly from Lemma 2.2. The statement on genericity follows as well, since generic sets are the complements of negligible sets. ⊓ ⊔

The word-based and the graph-based distributions

In order to discuss the distribution of finitely generated subgroups of F r , we need to fix a representation of these subgroups by means of discrete structures.

In this paper we consider two such structures: a subgroup can be given by a tuple of generators (reduced words in F r ), or by its Stallings graph (Section 2.1).

In the first case, the size of the representation is the pair (k, n) where k is the number of generators and n their maximal length -or n if k is fixed; in the second case, the size of the representation is the number n of vertices of the Stallings graph. In either case, there are only finitely many subgroups of each size.

We first review the literature on the word-based and the graph-based distributions (Sections 3.1 and 3.2), and then start the discussion of negligible or generic properties of subgroups (Section 3.3).

The word-based distribution

The distribution usually found in the literature (e.g. [START_REF] Kapovich | Generic properties of Whitehead's algorithm and isomorphism rigidity of random one-relator groups[END_REF][START_REF] Jitsukawa | Malnormal subgroups of free groups[END_REF][START_REF] Kapovich | Genericcase complexity, decision problems in group theory, and random walks[END_REF]) is in fact a distribution on the k-tuples h = (h 1 , . . . , h k ) of reduced words of length at most n, where k is fixed and n is allowed to grow to infinity; one then considers the subgroup H generated by h. We call this distribution word-based.

Let us first record three elementary facts, which can also be found in [START_REF] Jitsukawa | Malnormal subgroups of free groups[END_REF] 1 . We denote by R n the set of reduced words of length at most n.

Fact 3.1 |R n | = r r -1 (2r -1) n 1 - 1 r(2r -1) n . ⊓ ⊔
Proof. The number of reduced words of length i ≥ 1 is 2r(2r -1) i-1 , so the cardinality of R n is

|R n | = 1 + n i=1 2r(2r -1) i-1 = 1 + 2r (2r -1) n -1 2r -2 = 1 + r r -1 ((2r -1) n -1) = r r -1 (2r -1) n 1 - 1 r(2r -1) n . ⊓ ⊔ Fact 3.2 Let 0 < α < 1.
Exponentially generically, a reduced word in R n has length greater than αn.

⊓ ⊔

Proof. The proportion of words in R n , of length less than or equal to αn, is

|R ⌊αn⌋ | |R n | = r r-1 (2r -1) ⌊αn⌋ (1 + o(1)) r r-1 (2r -1) n (1 + o(1)) = (2r -1) ⌊αn⌋-n (1 + o(1)) ≤ (2r -1) (α-1)n (1 + o(1)).
Since α -1 < 0, it converges to 0 exponentially fast.

⊓ ⊔

Let h = (h 1 , . . . , h k ) be a tuple of reduced words and let µ > 0 such that min |h i | > 2⌈µ⌉. We denote by Pref µ ( h) the set of prefixes of length at most ⌈µ⌉ of the h i and h -1 i .

Fact 3.3 Let 0 < λ < 1 2 .
Exponentially generically, a k-tuple (h 1 , . . . , h k ) of elements of R n , is such that min |h i | > 2⌈λn⌉ and the prefixes of the h i and h -1 i of length ⌈λn⌉ are pairwise distinct.

⊓ ⊔

Proof. The complement in R k n of the set of k-tuples described in the statement is the union of the set Y of k-tuples h where min |h i | ≤ 2⌈λn⌉, and of the set Z of k-tuples where min |h i | > 2⌈λn⌉ and the set of prefixes of length ⌈λn⌉ of the h i and h -1 i has at most 2k -1 elements. Since 2λ < 1, the set Y is exponentially negligible by Fact 3.2 and we now concentrate on Z.

For each integer 2⌈λn⌉ < m ≤ n, let Z m be the set of k-tuples in Z, such that min

|h i | = m. Then |Z m | ≤ (2r(2r -1) ⌈λn⌉-1 ) 2k-1 k(2k -1) (2r -1) k(m-2⌈λn⌉) ≤ (2r) 2k-1 k(2k -1) (2r -1) k(m-2)-⌈λn⌉+1 .
Summing these inequalities for all 2⌈λn⌉ < m ≤ n, we find

|Z| ≤ (2r) 2k-1 k(2k -1) (2r -1) k(n-1)-⌈λn⌉+1 .
As a result, the proportion of k-tuples in Z is at most

(2r) 2k-1 k(2k -1) (2r -1) k(n-1)-⌈λn⌉+1 r k (r-1) k (2r -1) kn (1 + o(1)) ≤ C (2r -1) -λn (1 + o(1))
for some constant C depending only on k and r. Thus, this proportion converges to 0 exponentially fast. ⊓ ⊔ Remark 3.4 The small cancellation property, a closely related statement relative to common factors located anywhere in the words h i and h -1 i (not just at their extremities), is discussed in Lemma 4.5, in a variant of Arzhantseva and Ol'shanskiȋ's result on cyclic words [2, Lemma 3].

⊓ ⊔ Let 0 < α < 1 and 0 < λ < α 2 , and for each n, let Y α,λ,n,k be the set of k-tuples h = (h 1 , . . . , h k ) ∈ R k n such that min |h i | > αn and the prefixes of the h i and h -1 i of length ⌈λn⌉ are pairwise distinct. Facts 3.2 and 3.3 show that the proportion of elements of R k n in Y α,λ,n,k converges to 1 exponentially fast: in the search for exponentially generic properties of subgroups, we can restrict our attention to the tuples in Y α,λ,n,k and to the subgroups they generate.

The following observation is the basis for our exponential genericity proofs, in the context of the word-based distribution.

Fact 3.5 Let α, λ satisfy 0 < 2λ < α < 1. If h ∈ Y α,λ,n,k and H = h ,

then Γ(H) consists of two parts:

-the vertices at distance at most ⌈λn⌉ from the distinguished vertex and the edges connecting them: this forms a tree with vertex set Pref λn ( h), and edges u → a ua if a ∈ A and u, ua ∈ Pref λn ( h); this tree, which we call the central part of Γ(H), has 2k leaves;

-and for each 1 ≤ i ≤ k, where h i = p i m i s i and |p i | = |s i | = ⌈λn⌉, a path labeled m i from the vertex p i to the vertex s -1 i (both are in the central part); we call these paths the outer loops.

⊓ ⊔

This leads to the following results. Propositions 3.6 and 3.8 first appeared in a paper by Jitsukawa [START_REF] Jitsukawa | Malnormal subgroups of free groups[END_REF]. They are direct consequences of earlier analogous results (counting cyclic words instead of words) due to Arzhantseva and Ol'shanskiȋ [2, Lemma 3]. Proposition 3.6 Exponentially generically, a k-tuple of elements of R n generates a subgroup of rank k.

Proof. Let α, λ satisfy 0 < 2λ < α < 1. As observed above, it suffices to show that if h ∈ Y α,λ,n,k , then H = h has rank k. In that case, using Fact 3.5, we find that Γ(H) is formed of a central part and k outer loops.

The central part is a tree and like all trees, the number of its edges is 1 less than the number of its vertices. With the notation of Fact 3.5, the number of additional vertices (resp. edges) in the outer loops is i (|m i | -1) (resp. Proof. Since the first k components of a (k + k ′ )-tuple of elements of R n are independent from the k ′ last components, and since such a (k + k ′ )-tuple exponentially generically generates a subgroup of rank k + k ′ (Proposition 3.6), we find that a k-tuple and an k ′ -tuple of elements of R n exponentially generically generate their free product. This in turn implies the other properties. ⊓ ⊔ Proposition 3.7 shows that two k-tuples of elements of R n exponentially generically generate distinct subgroups. Proposition 3.8 is a little more precise.

i |m i |).
Proposition 3.8 Let α, λ satisfy 0 < 2λ < α < 1. The k-tuples h and h ′ in Y α,λ,n,k generate distinct subgroups, unless h ′ = (h ε 1 σ(1) , . . . , h ε k σ(k) ) for some permutation σ of [k] and for ε 1 , . . . , ε k ∈ {-1, +1}.
Proof. If h = h ′ , then the graphs Γ h and Γ h ′ are equal. In particular, their central parts, formed by the vertices at distance at most ⌈λn⌉ from the distinguished vertex, coincide. Fact 3.5 shows that if h ∈ Y α,λ,n,k , then Γ h completely determines all the k-tuples h ′ ∈ Y α,λ,n,k such that Γ h ′ = Γ h , and that they coincide with h up to the order of the elements and the direction in which the outer loops are read.

⊓ ⊔ Proposition 3.8 shows that, if we consider the class S α,λ,n,k of subgroups generated by k-tuples in Y α,λ,n,k , then each subgroup occurs the same number of times, namely 2 k k!. Randomly choosing a k-tuple in Y α,λ,n,k yields therefore a random subgroup in S α,λ,n,k , and the proportion of these subgroups among all subgroups generated by a k-tuple of words of length at most n tends to 1 exponentially fast.

The graph-based distribution

The uniform distribution on the set of size n Stallings graphs was analyzed by Bassino, Nicaud and Weil [START_REF] Bassino | Random generation of finitely generated subgroups of a free group[END_REF]. Here we summarize the principles of this distribution and the features which will be used in this paper.

We already noted that in Stallings graphs, each letter labels a partial injection on the vertex set: in fact, a Stallings graph can be viewed as a collection (f a ) a∈A of partial injections on an n-element set, with a distinguished vertex, and such that the resulting graph (with an a-labeled edge from i to j if and only if j = f a (i)) is connected and has no vertex of degree 1, except perhaps the distinguished vertex. We may even assume that the n-element set in question is [n] = {1, . . . , n}, with 1 as the distinguished vertex, see [3, Section 1.2] for a precise justification. In particular, the automorphism group of an admissible pair (Γ, 1) is always trivial.

One shows [3, Corollary 2.7] that the probability that an A-tuple (f a ) a∈A of partial injections on [n] induces a Stallings graph tends to 1 as n tends to infinity, and the problem of randomly generating a Stallings graph then reduces (via an efficient rejection algorithm, see [START_REF] Bassino | Random generation of finitely generated subgroups of a free group[END_REF]Section 3]) to the problem of efficiently generating a random partial injection on [n]. This view of a Stallings graph as an A-tuple of partial injections on [n] is central in our analysis.

The maximal orbits of a partial injection f (equivalently: the connected components of the function graph of f ) can be of two kinds: cycles -where each element is both in the domain and in the range of f -and sequences. The size of each of these components is defined to be the number of vertices which they contain. It is this combinatorial view of partial injections -as a disjoint union of cycles and sequences -, which is at the heart of the random generation algorithm, obtained using the so-called recursive method [START_REF] Nijenhuis | Combinatorial algorithms[END_REF][START_REF] Flajolet | A calculus for the random generation of labelled combinatorial structures[END_REF].

The distribution of sizes of components is studied in [3, Section 3], as well as the distribution of cycles vs. sequences among size k components. The random generation algorithm consists in drawing a size of component, say k, according to the relevant distribution; then drawing whether this size k component is a cycle or a sequence; and finally drawing a partial injection on the remaining n -k elements [START_REF] Bassino | Random generation of finitely generated subgroups of a free group[END_REF]Section 3.1]. This results in a partial injection on an nelement set, and we need only add a random numbering (1 through n) of the elements of that set.

However complex the method may seem, it guarantees a uniform distribution among all size n partial injections, it is easy to implement and its average time complexity is linear (in the RAM model; it is O(n 2 log n) under the bit-cost assumption) [3, Section 3.3].

To further discuss partial injections and other combinatorial structures, we use the notion of exponential generating series, written EGS. If S is a class of finite discrete structures such that there are finitely many S-structures of each size, let S n be the number of S-structures of size n. The EGS of S is the formal power series S(z) = n≥0

I(z) = 1 1 -z exp z 1 -z and I n n! = e -1 2 2 √ π e 2 √ n n -1 4 (1 + o(1)).
This result is obtained by means of deep theorems from analytic combinatorics. The same methods can be used to study the asymptotic behavior of particular parameters, such as the number of sequences of a partial injection. This parameter is directly connected with the number of edges in the Stallings graph formed by the partial injections f a (a ∈ A), which leads to the following result [ The expected rank of a randomly chosen size n subgroup of F r is asymptotically equivalent to (r -1)n -r √ n + 1.

Negligible and generic properties of subgroups

Thus, in the discussion of statistical properties of finitely generated subgroups of a (fixed) free group F r , we have two distributions at our disposal. One, the word-based distribution, is governed by two parameters: the number of generators and their maximum length, the former fixed and the latter allowed to tend to infinity. The other, the graph-based distribution, is governed by a single parameter: the size of the Stallings graph. We first observe that our discussion of the graph-based distribution (as well as the results in [START_REF] Bassino | Random generation of finitely generated subgroups of a free group[END_REF]) is in terms of spheres rather than balls: as we saw in the Section 2.2.2, the (exponential) negligibility or genericity results obtained in that setting are sufficient. In contrast, the existing literature on the wordbased distribution is in terms of balls, as is our description in Section 3.1 above.

The graph-based as well as the word-based distribution allow the discussion of properties of subgroups (of subgroups of a fixed rank k in the word-based case). There is of course no reason why a property that is generic or negligible in one distribution should have the same frequency in the other.

Our two distributions are indeed very different. How different is illustrated in Figure 1, which shows a "random" size 200 Stallings graph and the Stallings graph of the subgroup of F 2 generated by a "random" 5-tuple of words of length at most 40 (which has close to 200 vertices). This figure provides the intuition to exhibit properties of subgroups that are negligible in one distribution and generic in the other.

It is not difficult to come up with such properties. It is the case, for instance, of the property to have rank ℓ, for a fixed integer ℓ ≥ 1. In the graph-based distribution, this property is negligible as a consequence of Proposition 3.10 (see [START_REF] Bassino | Random generation of finitely generated subgroups of a free group[END_REF]Corollary 4.2]). In contrast, it is exponentially generic in the word-based distribution of ℓ-generated subgroups, see Proposition 3.6. For the same reason, it is exponentially negligible in the word-based distribution of k-generated subgroups with k = ℓ.

The properties of malnormality and purity, discussed in Section 4, provide more complex examples of this sort.

Malnormal and pure subgroups

Malnormality and purity are two important properties of subgroups. A subgroup H is pure if x n ∈ H and n = 0 implies x ∈ H. A pure subgroup is also called closed under radicals or isolated.

The subgroup H is malnormal if H ∩ H g = 1 for every g ∈ H. Malnormal subgroups play an important role in the study of amalgamated products (e.g. [START_REF] Karrass | The free product of two groups with a malnormal amalgamated subgroup[END_REF][START_REF] Bleiler | The free product of groups with amalgamated subgroup malnormal in a single factor[END_REF]) and in the characterization of their hyperbolicity [START_REF] Kharlampovich | Hyperbolic groups and free constructions[END_REF]. The following is elementary from the definition. Note that the converse statement does not hold: a, bab -1 is pure, yet not malnormal.

Both malnormality and purity have nice graphical characterizations, which imply that these properties are decidable for finitely generated subgroups of free groups. The result on malnormality is due to Kapovich and Myasnikov [START_REF] Kapovich | Stallings foldings and subgroups of free groups[END_REF] (following a decidability result in [START_REF] Baumslag | Malnormality is decidable in free groups[END_REF]), that on purity is due to Birget, Margolis, Meakin and Weil [START_REF] Birget | PSPACEcomplete problems for subgroups of free groups and inverse finite automata[END_REF]. Proposition 4.2 Let (Γ, 1) be the graphical representation of a subgroup H.

(1) H is non-malnormal if and only if there exists a non-trival reduced word u and distinct vertices x = y in Γ such that u labels loops at x and at y.

(2) H is non-pure if and only if there exists a non-trival reduced word u, an integer n ≥ 2 and a vertex x in Γ such that u n labels a loop at x but u does not.

4.1 Genericity in the word-based distribution. . . In view of Lemma 4.1, we also have the following result. We now proceed to prove Theorem 4.3. The proof relies on the two following lemmas, which provide an analogue of a small cancellation property for tuples of reduced words. These lemmas constitute a variant of the results of Gromov [14, 0.2.A] for tuples of cyclic words, proved also by Champetier [START_REF] Champetier | Propriétés génériques des groupes de présentation finie[END_REF][START_REF] Champetier | Propriétés statistiques des groupes de présentation finie[END_REF] and by Arzhantseva and Ol'shanskiȋ [2, Lemma 3]. Lemma 4.5 Let 0 < β < 1. The proportion of k-tuples h of reduced words in F r of length at most n, such that one of the h i contains two distinct occurrences of factors v and w of length at least βn, with v = w or v = w -1 , converges to 0 exponentially fast. Lemma 4.6 Let 0 < β < 1. The proportion of k-tuples h of reduced words of length at most n, such that a word v of length at least βn has an occurrence in one of the h i and v or v -1 has an occurrence in h j for some j = i, converges to 0 exponentially fast.

We can now prove Theorem 4.3.

Proof of Theorem 4.3. Let 0 < α < 1 and 0 < λ < α 4 . Let h = (h 1 , . . . , h k ). Exponentially generically, we have min |h i | > αn and the prefixes of length ⌈λn⌉ of the h i and h -1 i are pairwise distinct (Facts 3.2 and 3.3). In addition, exponentially generically, no word of length at least α-4λ

2 n has distinct occurrences as a factor of the h i and the h -1 i (Lemmas 4.5 and 4.6).

Let us now assume that h satisfies all these properties. Then Γ = Γ( h ) is composed of a central part, which is a tree containing the distinguished vertex and all the vertices corresponding to the prefixes of the h i and h -1 i of length up to ⌈λn⌉, and of outer loops whose labels are factors of the h i (or the h -1 i , depending on the direction in which they are read), see Fact 3.5.

Any loop in Γ must visit the central part of Γ at least once, and run along at least one of the outer loops. Let us now assume that a word u labels two distinct loops in Γ. Up to conjugation of u, we can assume that the base point of the first loop is in the central part of Γ. Then u has a factor v of length ⌈αn⌉ -2⌈λn⌉, which is a factor of some h i or h -1 i . The other occurrence of a loop labeled u reveals another path in Γ labeled v. This path may not be entirely in an outer loop, but if it is not, then it visits the central part of Γ only once, so it has a factor v ′ of length at least α-4λ

2 n in an outer loop, and hence in one of the h i or h -1 i . This word v ′ has distinct occurrences as a factor of the h i and the h -1 i , a contradiction. ⊓ ⊔

. . . and negligibility in the graph-based distribution

In contrast, we show that malnormality and purity are negligible in the graphbased distribution.

Theorem 4.7 The probability that a random subgroup of size n is pure is

O(n -r 2 ).
By Lemma 4.1, this implies the following Corollary 4.8 The probability that a random subgroup of size n is malnormal is O(n -r 2 ).

To prove Theorem 4.7, we observe that if H is a finitely generated subgroup of F r and a cycle of length at least 2 in Γ(H) is labeled by a power of some letter a, then H is not pure (Proposition 4.2). Therefore, if a subgroup is pure, then the partial injection determined by each letter in A has only sequences and length 1 cycles.

Thus Theorem 4.7 follows directly from the following proposition.

Proposition 4.9 The probability that a size n partial injection has no cycle of length greater than or equal to 2 is asymptotically equivalent to e √ n .

Our proof of Proposition 4.9 uses Hayman's theorem, discussed in Section 4.2.1 below. Remark 4.10 There are many more reasons for a subgroup to fail to be pure, than those considered here. In terms of Proposition 4.2, we have considered only the words u that are equal to a letter of the alphabet. As a result, the probability of purity and that of malnormality are likely to be much smaller than the upper bounds given above. The open question here is whether purity and normality are exponentially negligible with respect to the graph-based distribution.

⊓ ⊔

H-admissible functions and Hayman's theorem

Hayman's theorem on the asymptotic behavior of the coefficients of certain power series requires a technical hypothesis called H-admissibility. Here we give only the technical definition and statement we will use, and we refer the readers to [START_REF] Flajolet | Analytic combinatorics[END_REF]Chapter VIII] for further details on this theorem and on saddlepoint asymptotics in general. Let f (z) be a function of the form f (z) = e h(z) that is analytic at the origin, with radius of convergence ρ. We denote by [z n ]f (z) the coefficient of z n in the power series development of f at the origin. Let

a(r) = rh ′ (r) and b(r) = r 2 h ′′ (r) + rh ′ (r).
The function f (z) is said to be H-admissible if there exists a function δ : ]0, ρ[-→ ]0, π[ such that the following three conditions hold:

(H1) lim r→ρ b(r) = +∞.

(H2) Uniformly for |θ| ≤ δ(r)

f (re iθ ) ∼ f (r)e iθa(r)-1 2 θ 2 b(r) when r tends to ρ. [That is, f (re iθ ) = f (r)e iθa(r)-1 2 θ 2 b(r) (1 + γ(r, θ)) with |γ(r, θ)| ≤ γ(
ζ f ′ (ζ) f (ζ) = n. Then [z n ]f (z) = f (ζ) ζ n 2πb(ζ) (1 + o(1)) .
where b(z) = z 2 h ′′ (z) + zh ′ (z).

Proof of Proposition 4.9

Let K be the set of partial injections in which all the cycles have length 1 and let J the set of partial injections without any cycles (a subset of K). The elements of J are known as fragmented permutations, see [START_REF] Flajolet | Analytic combinatorics[END_REF]Section II.4.2]. Let K n and J n be the number of size n elements of K and J , and let K(z) and J(z) be the corresponding EGS. We want to show that Kn In is equivalent to

e √ n .
The series J(z) is studied in detail in [11, Example VIII.7, Proposition VIII.4]. There, it is shown in particular that J(z) is H-admissible and that

J(z) = exp z 1 -z and J n n! = e -1 2 2 √ π e 2 √ n n -3 4 (1 + o(1)). (1)
A partial injection in K consists of a set of length 1 cycles and a fragmented permutation. It follows that

K n = n k=0 n! k!(n -k)! J k , so that K(z) = ∞ n=0 K n n! z n = ∞ n=0 1 n! z n ∞ n=0 J n n! z n = e z J(z) = exp z + z 1 -z .
Now e z is H-admissible: this can be verified directly, or by application of [START_REF] Flajolet | Analytic combinatorics[END_REF]Theorem VIII.5]. We already noted that J(z) is H-admissible, and hence K(z) is H-admissible as well, as the product of two H-admissible functions ([11, Theorem VIII.5] again). The saddle-point equation

z K ′ (z) K(z) = n (see Section 4.2.1) is z(2 -2z + z 2 ) (1 -z) 2 = n,
i.e. z 3 -(n + 2)z 2 + 2(n + 1)z -n = 0.

Let P n (z) be the polynomial on the left hand side of this last equation. Examining the sign of the derivative of P n (z) on the interval [0, 1] and the values of P n at 0 and 1, we find that P n has a unique zero between 0 and 1, say ζ n . Moreover

ζ n = 1 - 1 √ n + 1 2n + O 1 n √ n . (2)
This asymptotic development can be obtained using maple, based on the application of the Cardan method to this degree 3 polynomial. We can also observe the following. Let Q n (z) be the polynomial defined by the identity

P n (1 -z) = 1 -z + (1 -n)z 2 -z 3 = Q n (z) -z 3 .
The zero of Q n (z) in the interval [0, 1] is

α n = √ 4n -3 -1 2(n -1) = 1 √ n - 1 2n + O(n -3 2 )
and if

β n = 1-α n , we have P n (β n ) = -α 3 n , which is negative for n large enough. Now let γ n = 1 -1 √ n + 1 2n . Then P n (γ n ) = 5 4n + O(n -3 2 ),
which is positive for n large enough. It follows that β n < ζ n < γ n , justifying the development in [START_REF] Goulnara | Ol ′ shanskiȋ. Generality of the class of groups in which subgroups with a lesser number of generators are free[END_REF]. With the notation of Section 4.2.1, we also have

b(z) = z 2 d 2 dz 2 log K(z) + z d dz log K(z) = z(2 -2z + 3z 2 -z 3 ) (1 -z) 3 , so that b(ζ n ) = 2n 3/2 + O(n).
Then we have

log ζ n n = n log 1 - 1 √ n + 1 2n + O 1 n √ n = - √ n + O 1 √ n and K(ζ n ) = exp ζ n + ζ n 1 -ζ n ∼ e 1 2 e √ n .
By Theorem 4.11, we now have

[z n ]K(z) ∼ K(ζ n ) ζ n n 2πb(ζ n ) ∼ e √ n e 1 2 e √ n 1 2 √ πn 3/4 ∼ e 1 2 2 √ π n -3/4 e 2 √ n . Proposition 4.9 follows since [z n ]I(z) ∼ e -1 2 2
√ π e 2 √ n n -1/4 (Proposition 3.9) and hence, Kn In ∼ e √ n .

A remark on the Hanna Neumann conjecture

The Hanna Neumann Conjecture (HNC), recently established by Mineyev [START_REF] Mineyev | Submultiplicativity and the Hanna Neumann conjecture[END_REF] after several decades of partial results, deals with the rank of the intersection of finitely generated subgroups of free groups (see also [START_REF] Mineyev | Groups, graphs, and the Hanna Neumann Conjecture[END_REF] for an alternative proof, purely in terms of groups and graphs). For convenience, let the reduced rank of a subgroup H, written rk(H), be equal to rk(H) = max(0, rank(H) -1).

Mineyev's theorem states that, if H and K are finitely generated subgroups of F , then rk(H ∩ K) ≤ rk(H) rk(K), as conjectured by Hanna Neumann. It also shows the stronger inequality conjectured by Burns [START_REF] Robert | On finitely generated subgroups of free products[END_REF], formerly known as the strengthened Hanna Neumann conjecture (SHNC):

rk(H ∩ K g ) ≤ rk(H) rk(K),
where the sum runs over all subsets KgH (in K\F/H) such that H ∩ K g = 1 and K g = g -1 Kg.

We discuss here how our results show that the cases where this inequality is non-trivial are rare, in the sense that rk(H ∩ K) and rk(H ∩ K g ) are generically equal to zero.

It was observed, initially by Stallings [START_REF] Stallings | Topology of finite graphs[END_REF] and Gersten [START_REF] Stephen | Intersections of finitely generated subgroups of free groups and resolutions of graphs[END_REF], that HNC and SHNC have natural interpretations in terms of Stallings graphs. If Γ is an Alabeled graph, let us denote by χ(Γ) the difference between the number of edges and the number of vertices of Γ: thus rk(H) = χ(Γ(H)). Let ∆(H, K) be the graph obtained from Γ(H) and Γ(K) as follows: the vertices of ∆(H, K) are the pairs (u, v) such that u is a vertex of Γ(H) and v is a vertex of Γ(K); and the edges of ∆(H, K) are the triples ((u, v), a, (u ′ , v ′ )) such that (u, a, u ′ ) is an edge of Γ(H) and (v, a, v ′ ) is an edge of Γ(K).

Let ∆ 1 be the connected component of ∆(H, K) containing (1, 1) (where 1 denotes the origin of Γ(H) and of Γ(K)), and let ∆ 2 be the union of the connected components of ∆(H, K) which are not trees. Then HNC holds for H and K if and only if χ(∆ 1 ) ≤ rk(H) rk(K), and SHNC holds for H and K if and only if χ(∆ 2 ) ≤ rk(H) rk(K).

Now observe (as in Proposition 3.7) that a randomly chosen (k + ℓ)-tuple of elements of R n is composed of the juxtaposition of a randomly chosen k-tuple and a randomly chosen ℓ-tuple. Exponentially generically, such a k-tuple h and ℓ-tuple h ′ generate subgroups with trivial intersection: in particular, HNC holds exponentially generically in the word-based distribution.

In fact, with the same ideas as in the proof of Theorem 4.3, exponentially generically, there is no loop in Γ( h ) with an occurrence as a loop in Γ( h ′ ). Therefore SHNC holds exponentially generically.

As mentioned above, both HNC and SHNC are now known to hold, but it seems interesting to point out that exponentially generically, they hold for trivial reasons.

An intermediate property

In this section, we discuss an intermediate property of subgroups, that is a property such that the proportion of subgroups of size n with this property has a limit which is neither 0 nor 1 (respectively the negligible and the generic cases).

Theorem 5.1 The probability that a random size n subgroup of F r intersects trivially the conjugacy classes of the generators tends to e -r when n tends to infinity.

The discussion of this property is included here because we do not know many examples of such intermediate properties. Unfortunately, the property in question is geometric in the sense that it depends on the combinatorial parameters of the Stallings graph of the subgroup, and is not preserved under the automorphisms of F r . It would be interesting to exhibit such a property that would be algebraic (preserved under automorphisms). One might think for instance of the property of avoiding the conjugacy classes of all the elements of some basis of F r , or the property of avoiding all primitive words. Remark 5.2 The property described in Theorem 5.1 is exponentially negligible in the word-based distribution. Indeed, if h is a k-tuple of reduced words of length at most n, then Γ( h ) has exponentially generically k loops of length at least n 2 and no loop of length 1 (see the discussion in Section 3.1 with α = 3 4 and λ = 1 8 ).

⊓ ⊔

The rest of this section is devoted to the proof of Theorem 5.1. It is easily verified that a subgroup H contains a conjugate of letter a ∈ A if and only if a labels a loop at some vertex of Γ(H), that is, if and only if the corresponding partial injection has some fixpoint. Since the drawing of the partial injections corresponding to the different letters is independent, the theorem follows directly from the following proposition.

Proposition 5. [START_REF] Bassino | Random generation of finitely generated subgroups of a free group[END_REF] The probability that a size n partial injection has no fixpoint tends to 1 e when n tends to infinity.

Remark 5.4 Note that 1 e is also the limit of the probability that a size n permutation has no fixpoint (a so-called derangement, see [START_REF] Comtet | Advanced combinatorics[END_REF]).

⊓ ⊔

Our proof of Proposition 5.3 again uses Hayman's theorem (Section 4.2.1). We also need the following technical result. Proposition 5.5 Let f 0 (z) be an H-admissible function with radius of convergence ρ < ∞. Then f (z) = e -z f 0 (z) is H-admissible as well.

Proof. Since f 0 is analytic at the origin, it is clear that f (z) is analytic at the origin as well, with a radius of convergence equal to that of f 0 (z).

Let h(z) be such that f (z) = e h(z) . If h(z) = h 0 (z) -z, then we have f 0 (z) = e h 0 (z) .

Let a 0 (t) = th ′ 0 (t), a(t) = th ′ (t), b 0 (t) = t 2 h ′′ 0 (t) + a 0 (t) and b(t) = t 2 h ′′ (t) + a(t). Then a(t) = a 0 (t) -t and b(t) = b 0 (t) -t.

It is immediate that lim t→ρ b(t) = +∞ since this limit holds for b 0 . That is, Condition (H1) holds.

We now verify Condition (H2). Let δ(t) be a positive function such that lim t→ρ δ(t) = 0; and such that, uniformly for |θ| ≤ δ(t), and as t tends to ρ,

h 0 (te iθ ) = h 0 (t) + iθa 0 (t) - 1 2 θ 2 b 0 (t) + o(1). Then h(te iθ ) = h 0 (te iθ ) -te iθ = h 0 (t) + iθa 0 (t) - 1 2 θ 2 b 0 (t) + o(1) -te iθ = h(t) + iθa(t) - 1 2 θ 2 b(t) + o(1) -te iθ + t + tiθ - 1 2 tθ 2 .
We now observe that, if |θ| ≤ δ(t) and as t tends to ρ, then |tiθ| ≤ tδ(t) = o(1) and similarly, 1 2 tθ 2 = o(1). Finally,

|t(1 -e iθ )| = t (1 -cos θ) 2 + sin 2 θ = t 2(1 -cos θ) ≤ t|θ| ≤ tδ(t) = o(1).
Thus h(te iθ ) = h(t) + iθa(t) -1 2 θ 2 b(t) + o(1) uniformly for |θ| ≤ δ(t), which concludes the verification of (H2).

Finally, we want to show that

f (te iθ ) √ b(t) f (t)
tends to 0 when t tends to ρ, uniformly for δ(t) ≤ |θ| ≤ π. We have

f (te iθ ) b(t) f (t) = f 0 (te iθ )e -te iθ b(t) f 0 (t)e -t = f 0 (te iθ ) b 0 (t) f 0 (t) e t(1-e iθ ) 1 - t b 0 (t)
.

Since f 0 is H-admissible, uniformly for δ(t) ≤ |θ| ≤ π and as t tends to ρ,

f 0 (te iθ ) b 0 (t) f 0 (t) = o(1).
Moreover, 1 -t b 0 (t) = 1 + o(1) since lim t→ρ b 0 (t) = +∞. Finally, when 0 < t < ρ, |e t(1-e iθ ) | = e t(1-cos θ) ≤ e 2ρ . This suffices to conclude that (H3) holds, and hence that f (z) is H-admissible.

⊓ ⊔

Proof of Proposition 5.3. Let L be the set of partial injections without fixpoints (i.e., without size 1 cycles), let L n be the number of size n elements of L and let L(z) be the corresponding EGS. We want to show that L n = 1 e I n (1 + o(1)). The EGS L(z) is computed using the standard calculus of enumeration of labeled structures (displayed in [START_REF] Flajolet | Analytic combinatorics[END_REF]), which was already used to compute I(z) in [START_REF] Bassino | Random generation of finitely generated subgroups of a free group[END_REF]: since the EGS of cycles is log( 11-z ), the EGS of cycles of size at least 2 is log( 11-z ) -z and the EGS of non-empty sequences is z 1-z , we have

L(z) = exp log( 1 1 -z ) -z + z 1 -z = 1 1 -z exp z 2 1 -z = I(z)e -z .
We already know that I(z) is H-admissible [3, Lemma 2.8] and Proposition 5.5 shows that L(z) is H-admissible as well.

The saddlepoint is the solution

ζ n in the open interval ]0, 1[) of the equa- tion z L ′ (z)
L(z) = n. An elementary computation shows that we need to solve the equation

z 3 + (n -1)z 2 -(2n + 1)z + n = 0, i.e., (z + n + 1)(1 -z) 2 -1 = 0.
Letting z = 0 and z = 1 in this equation shows that there is a solution in the interval (0, 1); moreover, one verifies easily that (z + n + 1)(1 -z) 2 -1 is monotonous on (0, 1), and hence our equation has exactly one solution in that interval, say, ζ n . From 0 < ζ n < 1, we deduce that

1 n+2 < (1 -ζ n ) 2 < 1 n+1
, and hence 1 -

1 n+1 < ζ n < 1 - 1 n+2 . In particular, ζ n = 1 -1 √ n + O 1 n √ n .
It now follows from Theorem 4.11 that

[z n ]L(z) = L(ζ n ) ζ n n 2πb(ζ n ) (1 + o(1)).
In view of the proof of Proposition 5.5, b(t) = b 0 (t) -t, where b 0 is the corresponding function for the H-admissible function I(z). Using [3, Equation (7), p. 392], we find that b 0 (t) = 2t (1-t) 3 , and hence b(t) = t(1+3t-3t 2 +t 3 )

(1-t) 3 . Elementary computations show that

b(ζ n ) = 2n 3 2 1 + O 1 √ n and 1 2πb(ζ n ) = n -3 4 2 √ π 1 + O 1 √ n . Moreover, ζ -n n = exp -n log 1 - 1 √ n + O 1 n √ n = exp √ n + 1 2 + O 1 √ n . Finally, L(ζ n ) = √ n exp √ n -2 + O 1 √ n 1 + O 1 n .
At last we have:

[z n ]L(z) = e -3 2 2 √ π n -1 4 e 2 √ n 1 + O 1 √ n .
Comparing with the estimate of [z n ]I(z) in Proposition 3.9, we find the announced result, namely

L n I n = [z n ]L(z) [z n ]I(z) = 1 e (1 + o(1)).
⊓ ⊔

Finitely presented groups

One of the motivations for the study of subgroup distributions has been the investigation of the statistical properties of finitely presented groups, see [START_REF] Gromov | Hyperbolic groups[END_REF][START_REF] Champetier | Propriétés génériques des groupes de présentation finie[END_REF][START_REF] Champetier | Propriétés statistiques des groupes de présentation finie[END_REF][START_REF] Yu | Ol ′ shanskiȋ. Almost every group is hyperbolic[END_REF][START_REF] Goulnara | Ol ′ shanskiȋ. Generality of the class of groups in which subgroups with a lesser number of generators are free[END_REF][START_REF] Goulnara | A property of subgroups of infinite index in a free group[END_REF]. Strictly speaking, this would require a notion of distribution of these groups, so that one would make a list of non-isomorphic groups and investigate the frequency of groups with certain properties within that list. No such notion is available, as far as the authors are aware and current literature operates rather with a notion of distribution of finite presentations.

Recall that a finite presentation is a pair (A, R), where A is a finite set (the alphabet of generators) and R is a tuple of elements of F (A) (the relators). The resulting finitely presented group G, written G = A | R , is the quotient G = F (A)/N (R), where N (R) is the normal subgroup generated by R. The usual approach of statistical properties of finitely presented groups is based on the uniform distribution on k-tuples of reduced (or cyclically reduced) words of length at most n.

Of course, different presentations may yield the same group, even if the alphabet of generators is fixed. We are not aware of an analogue of Proposition 3.8 above, which would state, say, that the distribution of finitely presented groups with k relators of length at most n resulting from the uniform distribution on k-tuples of reduced (or cyclically reduced) words of length at most n, is uniform, at least on a generic subset of k-tuples. However, partial results exist in this direction for one-relator groups (Kapovich, Schupp and Shpilrain [START_REF] Kapovich | Generic properties of Whitehead's algorithm and isomorphism rigidity of random one-relator groups[END_REF], Sapir and Spakulova [START_REF] Sapir | Residual properties of 1-relator groups[END_REF][START_REF] Sapir | Almost all one-relator groups with at least three generators are residually finite[END_REF]).

In this section, we want to discuss an idea that may seem reasonable in this context, but which turns out to be disappointing. If H is the subgroup generated by the tuple of relators R, then N (R) = N (H), so the group G = A | R is also specified by the pair A | H . Thus, instead of looking at the normal closure of a finite set of elements, we look at the normal closure of a finitely generated subgroup. Now, clearly, if one generates a list of subgroups H by listing k-tuples of generators (the word-based distribution discussed earlier in this article), then the distribution of groups produced by this process will be the same as if one were working with presentations.

The idea we wish to explore is to generate the subgroup H via its Stallings graph, that is, to use the graph-based distribution of subgroups. Precisely, we may present groups via pairs, A | Γ where A is an alphabet and Γ is a Stallings graph. This is a priori a more compact representation of the group (more compact in bit size, less convenient to L A T E X). 2 More importantly, as we have seen that the graph-based distribution of subgroups is different from the word-based distribution, we may anticipate a different distribution of finitely presented groups as well, which would give us different insights on finitely presented groups. Now an interesting feature of the statistical study of group presentations by tuples of relators is that the groups produced are generically non-trivial, and in fact infinite. More strongly, if A and k are fixed and if the maximal length n of the relators in the k-tuple R tends to infinity, then generically G = A | R is such that every subgroup generated by |A| -1 elements is free [START_REF] Goulnara | Ol ′ shanskiȋ. Generality of the class of groups in which subgroups with a lesser number of generators are free[END_REF]. It is also known that G is generically hyperbolic (Ol'shanskiȋ [START_REF] Yu | Ol ′ shanskiȋ. Almost every group is hyperbolic[END_REF] and Champetier [START_REF] Champetier | Propriétés génériques des groupes de présentation finie[END_REF][START_REF] Champetier | Propriétés statistiques des groupes de présentation finie[END_REF], proving a statement of Gromov [START_REF] Gromov | Hyperbolic groups[END_REF]).

In sharp contrast, and somewhat disappointingly, generically, a finitely presented group of the form A | Γ is trivial. Theorem 6.1 Generically, the finitely presented group A | Γ is trivial. In other words, generically, the normal closure of a randomly chosen subgroup of F r of size n, is F r itself.

The rest of Section 6 is devoted to the proof of Theorem 6.1. We note that if the lengths of the cycles of the partial injection induced by letter a in Γ(H) are relatively prime, then a belongs to the normal subgroup N (H), and hence a = 1 in G = A | H . Thus it suffices to prove the following proposition. Proposition 6.2 Generically, the lengths of the cycles of a size n partial injection are relatively prime. Remark 6.3 Our proof that A | H is generically trivial relies on a rather rough upper bound: we show that generically with probability 1 -O(n -1 6 ), each letter a is a product of conjugates of powers of a in H. We do not know whether A | H is exponentially generically trivial. See Remark 4.10 for a similar situation.

⊓ ⊔

The permutation case

We start with the case of permutations, which is interesting in and of itself.

Observe that if the lengths of the orbits of a permutation are not relatively prime, then these lengths have a common prime divisor p, which is in particular a divisor of n. Let P (p) n be the set of size n permutations in which all the orbits have size a multiple of p. Lemma 6.4 Let ≥ 2 and let p be a prime divisor of n.Then

|P (p) n | ≤ 2n! n 1 p -1
Proof. We fix p, so n is of the form n = mp and we proceed by induction on m. If m = 1, that is, p = n, then |P

n | is the number of size n cycles, namely (n -1)!. We now assume that m > 1.

We enumerate the elements of

P (p)
n in terms of the size kp of the orbit of 1: to determine such a permutation, one needs to select the other kp-1 elements of that orbit, select a cycle on these kp elements, and select a permutation on the remaining elements, that is, an element of P

Proof of Proposition 6.2

Isolating the cycles in a size n partial injection, reveals a permutation (on a subset X of [n]) and a fragmented permutation (i.e., a cycle-less partial injection) on the complement of X.

The EGS J(z) = n Jn n! z n of fragmented permutations was discussed in Section 4.2, where we noted in particular that J(z) = exp z 1-z . us add the following observation. Lemma 6. [START_REF] Bleiler | The free product of groups with amalgamated subgroup malnormal in a single factor[END_REF] The sequence (J n /n!) n>0 is increasing.

Proof. Let M n = Jn n! , so that J(z) = n≥0 M n z n . The equalities d dz J(z) = ⊓ ⊔ Specifying a size n partial injection whose permutation part (the union of the cycles) has size k, amounts to choosing k elements, choosing a permutation on these k elements, and choosing a fragmented permutation on the remaining n -k elements: the number of such partial injections is

n k k!J n-k = n! J n-k (n -k)! ;
and the number of those in which the sizes of the cycles have a non-trivial gcd is at most equal to

2n! J n-k (n -k)! 1 √ k + log 3 k k 2 3
by Proposition 6.5. Moreover, summing the numbers of partial injections with permutation part of size k, we get

I n = n k=0 n! J n-k (n -k)! .
We use these observations to show the following facts, which together suffice to establish Proposition 6.2. Fact 6.7 The proportion of size n partial injections whose permutation part has size less than n Thus the proportion of these partial injections is at most 4n -1 6 . ⊓ ⊔

Proposition 3 . 7

 37 Therefore, in Γ(H), we have |E| -|V | + 1 = k and hence rank(H) = k (see Section 2.1).⊓ ⊔ Exponentially generically, a k-tuple h and an k ′ -tuple h ′ of elements of R n generate subgroups that are distinct, have trivial intersection, and are such that h, h ′ = h * h ′ .

  Sn n! z n . Let I(z) = n≥0 In n! z n be the EGS of partial injections. Bassino, Nicaud and Weil show the following [3, Section 2.1 and Proposition 2.10]. Proposition 3.9 The EGS I(z) of partial injections satisfies the following

3 ,

 3 Lemma 2.11 and Corollary 4.1]. Proposition 3.10 The expected number of sequences in a randomly chosen partial injection of size n is asymptotically equivalent to √ n.

Figure 1 :

 1 Figure 1: The Stallings graphs of two randomly generated subgroups of F 2 . On the left, a subgroup generated by a random 5-tuple of words of length at most 40. On the right, a random Stallings graph of size 200. Only the shape of the graphs is depicted, vertices and edge labels and directions are not represented. The pictures have been generated by neato. Note that the scale (average distance between two vertices) is not the same on the two pictures.

Lemma 4 . 1

 41 If a subgroup is malnormal, then it is pure.

Corollary 4 . 4

 44 Purity is exponentially generic in the word-based distribution.

  r) when |θ| ≤ δ(r) and lim r→ρ γ(r) = 0.] (H3) and uniformly for δ(r) ≤ |θ| ≤ π f (re iθ ) b(r) = o(f (r)) when r tends to ρ. Hayman's theorem [11, Theorem VIII.4] states the following. Theorem 4.11 Let f (z) = e h(z) be a H-admissible function with radius of convergence ρ and ζ = ζ(n) be the unique solution in the interval ]0, ρ[ of the saddlepoint equation

Since the map x → x 1 p - 1 1 p - 1 ≤ j+1 j x 1 p 1 p -j 1 p

 1111111 Isolating the term j = 0 and using the induction hypothesis, it follows that|P (p)n | ≤ (nis non-increasing on positive reals, we have (j + 1) -1 dx = p((j + 1) ).

1 ( 1

 11 -z) 2 J(z), and hence (1 -z) 2 d dz J(z) = J(z), yield the following recurrence relation, for all n ≥ 2:(n + 1)M n+1 = (2n + 1)M n -(n -1)M n-1 .It follows that, for all n ≥ 2,(n + 1)(M n+1 -M n ) = nM n -(n -1)M n-1 = n(M n -M n-1 ) + M n-1 .The result follows by induction since M 1 = 1 and M 2 = 3 2 (see for instance[START_REF] Flajolet | Analytic combinatorics[END_REF] Section II.4.2]).

1 3Fact 6 . 8 1 3 2 √ 1 3

 168121 is O(n -1 6 ).⊓ ⊔ The proportion of size n partial injections whose permutation part has size greater than n and for which the sizes of the cycles has a non-trivial gcd, is O(n -1 6 ).⊓ ⊔Proof of Fact 6.7. The proportion of size n partial injections whose permutation part has size less than n last inequality holds since Jn In = O(n -1 2 ) (compare the asymptotic equivalents of Jn n! given in Section 4.2.2 and of In n! in Proposition 3.9).⊓ ⊔Proof of Fact 6.8. Here we use Proposition 6.5 and the fact that, for large enough integers, we have 1 k . The number of size n partial injections whose permutation part has size greater than n and for which the sizes of the cycles has a non-trivial gcd, is bounded above by

We choose to reiterate the proofs of these results, because we feel that our presentation exhibits more clearly their combinatorial underpinnings.

It would be more interesting to have a unique, discrete representation of finitely generated normal subgroups, but no such representation seems to be known. And distinct normal subgroups may well lead to isomorphic quotients.

Acknowledgements

We want to thank Nicolas Pouyanne for fruitful discussions on the gcd of the lengths of cycles in a random permutation. We also thank the anonymous referees for their insightful remarks, pointing us to important references and spotting two computational mistakes.

All authors benefitted from the support of the French-Spanish program picasso (project ACI-HF2006-0239). The first and third authors were supported by the ANR (projects blan 07-2 195422 gamma and anr-2010-blan-0204 magnum). The second and fourth authors were supported by MEC (Spain) and the EFRD (EC) through project number MTM2008-01550. The last author was supported by the ESF program AutoMathA and by the ANR (project anr-2010-blan-0202 frec).

Therefore, isolating the term j = 1,

Now we have

Since p ≥ it holds

and hence

which concludes the proof. ⊓ ⊔ Proposition 6.5 The probability that the lengths of the orbits of a size n permutation are not relatively prime is at most equal to 2 √ n + 2n -2 3 log 3 n.

Proof. Let Q n be the set of size n permutations for which the lengths of the orbits are not relatively prime, and let q n = |Qn| n! . As we already observed, a common divisor of the lengths of the orbits of a size n permutation is also a divisor of n. Therefore, if n is prime, then Q n is the set of size n cycles, so |Q n | = (n -1)!, q n = 1 n and we have the desired result. If n is not prime, then every size n permutation in Q n is in P (p) n for some prime divisor p of n. These sets are not pairwise disjoint, but the sum of their cardinalities is an upper bound for |Q n |. For these values of p,

by Lemma 6.4. Separating the case p = 2 from the cases p ≥ 3, we find that

, where D is the number of distinct odd prime divisors of n. Since n ≥ 3 D , we have D ≤ log 3 n and hence

which concludes the proof. ⊓ ⊔


Steffen Grünewälder
email: steffen@cs.ucl.ac.uk

Jean-Yves Audibert
email: audibert@imagine.enpc.fr

Manfred Opper
email: opperm@cs.tu-berlin.de

John Shawe-Taylor

Regret Bounds for Gaussian Process Bandit Problems

Bandit algorithms are concerned with trading exploration with exploitation where a number of options are available but we can only learn their quality by experimenting with them. We consider the scenario in which the reward distribution for arms is modelled by a Gaussian process and there is no noise in the observed reward. Our main result is to bound the regret experienced by algorithms relative to the a posteriori optimal strategy of playing the best arm throughout based on benign assumptions about the covariance function defining the Gaussian process. We further complement these upper bounds with corresponding lower bounds for particular covariance functions demonstrating that in general there is at most a logarithmic looseness in our upper bounds.

INTRODUCTION

Bandit problems have become a topic of extensive research in recent years and many extensions of the classical framework [START_REF] Robbins | Some aspects of the sequential design of experiments[END_REF][START_REF] Gittins | A dynamic allocation index for the discounted multiarmed bandit problem[END_REF][START_REF] Berry | Bandit problems[END_REF][START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF][START_REF] Cesa-Bianchi | Prediction, Learning, and Games[END_REF] have been developed (among many others, [START_REF] Abernethy | Competing in the dark: An efficient algorithm for bandit linear optimization[END_REF][START_REF] Slivkins | Adapting to a changing environment: the brownian restless bandits[END_REF][START_REF] Wang | Algorithms for infinitely many-armed bandits[END_REF][START_REF] Bubeck | Online optimization in X-armed bandits[END_REF]Kleinberg et al., 2008b). A particularly important extension for real world applications is the use of a Gaussian process to model the reward distribution. It allows a canonical treatment of optimization problems with expensive-to-evaluate objective functions for which the expected similarity for different arguments (or parameter settings) are defined through kernels. Recently a number of different algorithms have been developed to tackle this sequential optimization problem with Gaussian process (GP) prior (see Section 2 of [START_REF] Ginsbourger | A Multipoints Criterion for Deterministic Parallel Global Optimization based on Gaussian Processes[END_REF] for an overview of them). The theoretical underpinnings in the form of regret bounds are, however, still missing.

To illustrate the setting, consider the problem of optimizing throughput of mobile phones. In this example, the arms of the bandit would correspond to system settings and the corresponding throughput to the reward. A kernel could be used to model the expected similarity between the rewards of two settings of the mobile. In the Bayesian framework, the kernel encodes our prior belief that the reward as a function of parameter settings is drawn from a GP defined by the given kernel (Figure 1 shows a draw from a GP with a Gaussian kernel). The approach will work well in practice if the GP reward functions are similar to that of the concrete optimisation problem at hand. Due to the flexibility and power of GPs, the approach has sparked considerable interest [START_REF] Schonlau | Computer Experiments and Global Optimization[END_REF][START_REF] Jones | Efficient global optimization of expensive black-box functions[END_REF][START_REF] Jones | A taxonomy of global optimization methods based on response surfaces[END_REF][START_REF] Ginsbourger | Towards gp-based optimization with finite time horizon[END_REF][START_REF] Osborne | Gaussian processes for global optimization[END_REF]. The early works were done in the field of global optimisation. Using stochastic processes for global optimisation has a long tradition. The earliest works date back to [START_REF] Kushner | A new methods of locating the maximum point of an arbitrary multipeak curve in the presence of noise[END_REF]. The use of GPs is relatively new and can be found associated with the name "Kriging" and response surfaces [START_REF] Schonlau | Computer Experiments and Global Optimization[END_REF][START_REF] Jones | Efficient global optimization of expensive black-box functions[END_REF][START_REF] Jones | A taxonomy of global optimization methods based on response surfaces[END_REF]. These works address exploration-exploitation tradeoffs to find the global optimum which is very similar to what Bandit algorithms do. Their motivation for introducing GPs to global optimisation comes from an engineering viewpoint, where the design space (also called the state space) can often be interpolated and extrapolated quite accurately and the GP allows them to "see" obvious trends. Furthermore, it allows them to provide what they call credible stopping rules. The suboptimality of the one-step lookahead policy has been recently exhibited and a multi-step optimal lookahead policy has been proposed [START_REF] Osborne | Gaussian processes for global optimization[END_REF][START_REF] Ginsbourger | Towards gp-based optimization with finite time horizon[END_REF].

While a number of practical algorithms have been developed, there are no theoretical guarantees available on their performance in the form of regret bounds. One of the reason for this lies in the difficulty of deriving regret bounds for the GP setting. Bounding the regret requires to understand the behaviour of the supremum of the reward function for the posterior distribution, that is the distribution of the process knowing the past observations. Furthermore, each kernel induces various type of correlations between the rewards. Dealing with these problems in a generic way is also the target of this work. If we consider again Figure 1, we can ask where is the maximum? How high is it? How close to the maximum are rewards at arms that are ε close to the optimal arm? How consistent are these properties across multiple draws?

The key to dealing with these questions lies in a fundamental work from probability theory. One of the key tools is the celebrated chaining argument with, in particular, the Dudley integral [START_REF] Dudley | The sizes of compact subsets of hilbert space and continuity of gaussian processes[END_REF]. This argument allows us to bound the expected supremum and, from concentration inequalities, with high probability, the supremum for a given GP sample. The interesting property of the Dudley integral is that it breaks the problem of handling the supremum down to understanding the posterior covariance function. The second important idea to make the approach general is the use of Hölder continuity assumptions on the kernel. These assumptions allows to control how the prior (and indirectly the posterior) Gaussian process when we move a short distance away from our current point.

The assumption on the covariance is fulfilled by a majority of kernels (this is typically the case for the Brownian motion, the Brownian bridge, the OrnsteinUhlenbeck process, and the GP associated to the Gaussian kernel) and can be easily verified.

MAIN RESULTS

The first result is the upper bound on the regret for GPs with covariance functions that are Hölder continuous with a coefficient α and a constant L k (details are given in Section 4). Assuming a zero mean Gaussian process prior, we know that after playing T arms in [0, 1] D that the optimal strategy has a regret no bigger than

4 L k log(2T ) (2 T ) α + 15 (α + 3)DL k α(2 T ) α ,
where T := T 1/D . This upper bound is complemented by the following Figure 1: A draw from a Gaussian process on [0, 1] 2 with a Gaussian kernel (σ = 0.1). A draw represents an optimization problem. The optimal arm is the one where the peak is highest.

lower bound on the optimal regret:

κ L k 2 α (2T ) α/D log T ,
where κ > 0 is a universal constant. The lower bound is derived for a specific kernel that fulfills the α-Hölder continuity assumption and matches the upper bound up to a logarithmic factor.

During the reviewing process of this work, another work [START_REF] Srinivas | Gaussian process bandits without regret: An experimental design approach[END_REF] addressing regret bounds in GP optimization has appeared. It provides a different approach linked to optimal empirical design and information gain and studies the cumulative regret. So, both the bounds presented here and theirs are of interest (and cannot really be compared).

BACKGROUND

We start with discussing the classical bandit setting.

In its most basic formulation a finite number of arms (or actions) x 1 , . . . , x K is given. Each arm is associated to a reward distribution characterizing the arm. Successive plays of an arm x i yields a sequence of rewards which are independent and identically distributed according to this unknown distribution (with unknown expectation). The goal is to define a strategy such that a functional called regret is minimised. Typically, the regret measures the expected loss for the strategy compared to playing the arm with the highest expected reward.

In our setting we do not have a finite number of arms but a continuum of arms. Different approaches to the continuum arm space setting have already been proposed [START_REF]The continuum-armed bandit problem[END_REF]; [START_REF] Kleinberg | Nearly tight bounds for the continuumarmed bandit problem[END_REF]

GAUSSIAN PROCESSES

We use a Gaussian process to model the reward distribution. A stochastic process r(x) is Gaussian if and only if for every finite set of indices x 1 , . . . , x n the variable (r(x 1 ), . . . , r(x n )) is a multivariate Gaussian random variable [START_REF] Rasmussen | Gaussian Processes for Machine Learning[END_REF]. A Gaussian process is completely specified by its mean function µ and its covariance function

k(x, y) = Cov[r(x), r(y)].
The covariance function k is symmetric and positive semi-definite.

Metric Entropy Bound for the Expected Supremum

The Dudley integral [START_REF] Dudley | The sizes of compact subsets of hilbert space and continuity of gaussian processes[END_REF] gives a bound on the expected supremum of a Gaussian process. It is defined with respect to the canonical metric d(x, y) = x, x -2 x, y + y, y , where •, • denotes the covariance.

The bound on the expected supremum uses the size of the parameter space X. The size is measured with the packing number N (ε, X), which is the maximal number of points that are all at least ε-distant from each other (in the d(x, y) metric).

The bound on the expected supremum is given in the following theorem (Massart, 2003)[Th. 3.18, p. 74]:

Theorem 3.1 (Metric Entropy Bound) Let (f (x)) x∈X be some centered Gaussian process. Assume that (X, d) is totally bounded and denote by N (ε, X) the ε-packing number of (X, d), for all positive ε.

If log N (ε, X) is integrable at 0, then (f (x)) x∈X admits a version which is almost surely uniformly continuous on (X, d). Moreover, if (f (x)) x∈X is almost surely continuous on (X, d), then E sup x∈X f (x) ≤ 12 σ X 0 log N (ε, X)dε, where σ X = sup x∈X Var f (x) is the supremum of the variance on X.
The important property of the bound is that it transforms the problem of understanding some complex stochastic process into understanding d(x, y) which is a deterministic object that can be studied using analytic methods.

Inequalities

We will need two inequalities for Gaussian, respectively sub-Gaussian random variables. The first can be found in Massart (2003)[Prop. 3.19, p. 77]:

Proposition 3.2 If (f (x)) x∈X is some almost surely continuous Gaussian process on the totally bounded set (X, d) then for every λ ∈ R E[exp(λ(sup f (x) -E[sup f (x)]))] ≤ exp λ 2 σ 2 X 2 , with σ X = sup x∈X Var f (x).
The second is a statement about the supremum of sub-Gaussian random variables and can be found in [START_REF] Devroye | Combinatorial Methods in Density Estimation[END_REF][Lem. 2.2, p. 7]:

Lemma 3.3 Let σ > 0, n ≥ 2 and let Y 1 , .
. . , Y n be real-valued random variables such that for all s > 0 and

1 ≤ i ≤ n, E exp (sY i ) ≤ exp s 2 σ 2 /2 . Then E max i≤n Y i ≤ σ √ 2 log n.

The Posterior Process

The posterior process, i.e. the process conditional on observations, is again a Gaussian process. For a zero mean prior process f the mean µ Z of the posterior process is given by µ

Z (x) = k(x, Z) k(Z, Z) -1 f (Z)
, where we use the short form k(x, Z) := (k(x, Z 1 ), . . . , k(x, Z n )) and k(Z, Z) for the kernel matrix of a vector Z := (Z 1 , . . . , Z n ). The Z's denote the positions of the observations. And the values at these positions are f (Z) = (f (Z 1 ), . . . , f (Z n )) . The covariance of the posterior process is given by x, y := x, y Z := k(x, y) -k(x, Z) k(Z, Z) -1 k(Z, y).

THE BANDIT GAME WITH A GAUSSIAN PROCESS PRIOR

Central to our approach are two Hölder continuity assumptions for the mean and the covariance. The covariance function k and the mean function µ are assumed to satisfy the following mild conditions:

(A1) For some L µ ≥ 0, for any x, y ∈ X, µ(x)-µ(y) ≤ L µ x -y ∞ .
(A2) For some L k ≥ 0 and some α > 0, for any

x, y ∈ X, k(x, x) -k(x, y) ≤ L k x -y α ∞ .
We use the supremum norms as it leads to simpler bounds (compared to the Euclidean norm for instance). However, as X is a finite dimensional space all norms are equivalent, meaning the results apply to arbitrary norms up to an extra constant.

Furthermore, we assume for simplicity that the space of arms is the D-dimensional unit cube X = [0, 1] D .

It is easy to extend the results to cubes of size R.

GAME DEFINITION

The player knows the (prior) distribution of the Gaussian process (he knows the mean function µ and the covariance function k). He also knows the number T of rounds to play. The game is the following.

For t = 1, . . . , T the player chooses xt ∈ X. the player observes r(x t ). At the end of these T rounds, the player receives the reward max r(x 1 ), . . . , r(x T ) .

A common alternative target encountered in the bandit literature is the cumulative reward T t=1 r(x t ). In applications, it is often the case that the 'max' reward is more interesting than the cumulative one. The two problems differ substantially in the sense that there is no cost of exploring in the 'max' reward setting (see [START_REF] Bubeck | Pure exploration in multi-armed bandits problems[END_REF] for an interesting link between the two regret notions).

THE OPTIMAL STRATEGY

It is then natural to define the optimal strategy as the one having the highest expected reward: E max r(x 1 ), . . . , r(x T ) .

It occurs that the optimal strategy is the one obtained by dynamic programming or backward induction [START_REF] Bellman | A problem in the sequential design of experiments[END_REF], which in our finite horizon setting can be viewed as the T -steps lookahead strategy following the terminology of [START_REF] Ross | Applied Probability Models with Optimization Applications[END_REF]: at time t the player chooses r(x t-1 ) .

xt = argmax xt∈X E max xt+1∈X • • • E max x T -1 ∈X E max x T ∈X E max r(x 1 ), . . . , r(x T ) r(x 1 ), . . . , r(x T -1 ) r(x 1 ), . . . , r(x T -2 ) • • • r(x 1 ), . . . ,
(

) 1
The formula is a bit awful, but the idea is simple. If we are at time T , the optimal action xT is argmax

x T ∈X E max r(x 1 ), . . . , r(x T ) r(x 1 ), . . . , r(x T -1 ) ,
which corresponds to a one-step lookahead. From this, we know that at time T -1, if we choose x T -1 , our expected reward knowing the past will be E max

x T ∈X E max r(x 1 ), . . . , r(x T ) r(x 1 ), . . . , r(x T -1 ) r(x 1 ), . . . , r(x T -2 ) .

This leads to the optimal choice for x T -1 defined in (1). Repeated this argument again, we obtain the Tsteps lookahead strategy. This policy is, in spirit, the same as the one proposed in (Osborne et al., 2009, Section 3.2). Our main result is to provide a regret bound for it.

It is important to understand that the distribution of r(x t ) knowing r(x 1 ), . . . , r(x t-1 ) is known: it is the Gaussian posterior. The difficulty of proving results on the algorithm relies on the understanding of the behaviours of the mean and covariance of the Gaussian process conditional to the past observations.

GUARANTEE ON THE PERFORMANCE OF THE OPTIMAL STRATEGY

We call a guarantee on how the optimal strategy works a lower bound on the expected reward E max r(x 1 ), . . . , r(x T ) , or equivalently an upper bound on the expected regret E sup x∈X r(x)max r(x 1 ), . . . , r(x T ) . We need a definition to simplify the notation: T := T 1/D . To establish the bound, we will use the following path.

• define a simpler strategy: we will consider the naive grid strategy. We partition the space of arms X into T D ≤ T many cubes of side length 1/ T and play the center of each of these cubes.

• lower bound the expected reward of this simpler strategy. This last point will rely on the use of concentration inequalities for the supremum of Gaussian and sub-Gaussian processes.

Theorem 4.1 Under Assumptions (A1) and (A2), The optimal strategy satisfies

E sup x∈X r(x) -max r(x 1 ), . . . , r(x T ) ≤ E sup x∈X r(x) -max r(x 1 ), . . . , r(x T ) ≤ 4 L k log(2T ) (2 T ) α + 15 (α + 3)DL k α(2 T ) α + L µ 2 T . Proof. Let i = (i 1 , . . . , i D ) be a D-dimensional index with 1 ≤ i j ≤ T . Let I i = i1-1 T , i1 T × . . . × i D -1 T , i D T
be the i's cube. We have

x i = ( 2i1-1 2 T , . . . , 2i D -1 2 T ) ∈ I i . Introduce the random variables U i = sup x∈I i r(x) -E r(x) r(x i ) V i = sup x∈I i E r(x) r(x i ) -r(x i ) W i = sup x∈I i r(x) -r(x i ) .
We have

E sup x∈X r(x) -max r(x 1 ), . . . , r(x T ) ≤ E max i∈{1,..., T } D W i ≤ E max i∈{1,..., T } D U i + E max i∈{1,..., T } D V i ≤ E max i∈{1,..., T } D U i -E[U i |r(x i )] + E max i∈{1,..., T } D E[U i |r(x i )] + E max i∈{1,..., T } D V i . (2)
Before giving the propositions upper bounding the three terms of the last righthand-side, let us introduce a convenient notation. Define

k(x, y|z) = k(x, y) - k(x, z)k(y, z) k(z, z) 1 k(z,z)>0
= Cov(r(x), r(y)|r(z)),

i.e., k(x, y|z) is the conditional covariance of r(x) and r(y) knowing the value of r(z). Similarly, define d(x, y|z) the posterior distance knowing the value of r(z). We have

d 2 (x, y|z) = k(x, x|z) + k(y, y|z) -2k(x, y|z) = k(x, x) + k(y, y) -2k(x, y) - [k(x, z) -k(y, z)] 2 k(z, z) 1 k(z,z)>0 ≤ d 2 (x, y), (3)
where d(x, y) denotes the prior distance and we used the characteristic function 1 k(z,z)>0 to account for cases where k(z, z) = 0, i.e. for cases where at z no information can be gained as the value is known exactly. This inequality shows that the posterior distance is at most equal to the prior distance, which gives a rough but useful upper bound on the posterior distance.

The ε-covering number is the minimum number of balls of radius ε covering the space. The ε-packing number is known to be smaller than the ε/2-covering number. We will map the problem of covering X in the canonical d(x, y) metric to the problem of covering X in the original metric from X. It is convenient to introduce a function for this. Let

ψ i (β) = sup x,y∈I i x-y ∞≤β d(x, y|x i ) Define σ i = sup x∈I i Var r(x) r(x i ) . We have σ i = sup x∈I i Var r(x) -r(x i ) r(x i ) = sup x∈I i d(x, x i |x i ) ≤ 2L k (2 T ) α ,
where the last inequality uses (3), the decomposition

d 2 (x, x i ) = [k(x, x)-k(x, x i )]+[k(x i , x i )-k(x, x i )] and Assumption (A2). Introduce σ = max i∈{1,..., T } D σ i . We have σ ≤ 2L k (2 T ) α . ( 4
)
Proposition 4.2 For the first term we have that

E max i∈{1,..., T } D U i -E[U i |r(x i )] ≤ 2 L k log(T ) (2 T ) α .
Proof. Using Proposition 3.2 we have for any i ∈ {1, . . . , T } D and λ > 0 that

Ee λ{U i -E[U i |r(x i )]} = E r(x i ) E e λ{U i -E[U i |r(x i )]} r(x i ) ≤ E r(x i ) e λ 2 σ 2 i /2 = e λ 2 σ 2 i /2 ≤ e λ 2 σ 2 X /2 .
We can use now apply Lemma 3.3 and we get that

E max i={1,..., T } D U i -E[U i |r(x i )] ≤ σ 2 log( T D ),
and conclude by using (4).

Proposition 4.3 Under Assumption (A2) we have for the second term that

E max i∈{1,..., T } D E[U i |r(x i )] ≤ 24 (α + 3)DL k log(2) 2α(2 T ) α .
Proof. We use the metric entropy bound to control the E[U i |r(x i )] terms together with the Lipschitz assumption. Our bound will be the same for all i and will be a deterministic quantity. Therefore the outer expectation does not change anything. Let

ψ -1 i (ε) = inf β > 0 : ψ i (β) > ε . Since ψ i is continuous, we have ψ i [ψ -1 i (ε/2)], and in particular, x-y ∞ ≤ ψ -1 i ( ε 2 ) implies d(x, y|x i ) ≤ ε 2 . So a uniform grid of I i of step 2ψ -1 i ( ε 2 ) allows to build a ε 2 -covering net, implying that N (ε, I i ) ≤ 1 2 T ψ -1 i ( ε 2 ) D .
Using Theorem 3.1, we have

E[U i |r(x i )] ≤ 12 √ D σ 0 log 1 2 T ψ -1 i ( ε 2 ) + 1 dε. Since ψ i (β) ≤ √ 2L k β α , we have ψ -1 i ( ε 2 ) ≥ ε 2 √ 2L k 2 α
. By using (4) and the integral computations in Ap-

pendix A with a = α/2, b = (2 √ 2L k ) 2/α 2 T and c = 2L k (2 T ) α , we get σ 0 log 1 2 T ψ -1 i ( ε 2 ) + 1 dε ≤ c 0 log 1 + bε -1/a dε ≤ 2 L k log(2e2 α/2 ) α(2 T ) α .
Proposition 4.4 Under Assumption (A1) and (A2) we have for the third term that

E max i∈{1,..., T } D V i ≤ L µ 2 T + 2 L k log(2T ) (2 T ) α .
Proof. We have

V i = sup x∈I i µ(x) -µ(x i ) + 1 k(x i ,x i )>0 k(x, x i ) k(x i , x i ) -1 [r(x i ) -µ(x i )] .
Let

a i = sup x∈I i k(x,x i ) k(x i ,x i ) -1 1 k(x i ,x i )>0
. We have

V i ≤ sup x∈I i µ(x) -µ(x i ) + a i [µ(x i ) -r(x i )] . a i [µ(x i )-r(x i )
] is a one dimensional Gaussian random variable with mean zero. Now using a property from the moment generating function of a one dimensional Gaussian we find that for any λ ∈ R

Ee λa i [µ(x i )-r(x i )] ≤ e λ 2 a 2 i k(x i ,x i )/2 .
Using again Lemma 3.3, we have

E max i={1,..., T } D V i ≤ max i={1,..., T } D µ(x) -µ(x i ) + 2 log(2 T D ) max i={1,..., T } D a 2 i k(x i , x i ).
The last term can be bounded in the following way

a 2 i k(x i , x i ) ≤ sup x∈I i [k(x, x i ) -k(x i , x i )] 2 k(x i , x i ) 1 k(x i ,x i )>0 ≤ sup x∈I i d 2 (x, x i ) ≤ (A2) 2L k (2 T ) α ,
where the Cauchy-Schwarz inequality was used at the second inequality.

Plugging the results of the three previous propositions into (2) leads to the announced result.

A LOWER BOUND

In this section we present a lower bound to complement the upper bound from Theorem 4.1. On the positive side, this lower bound matches the leading term (in T ) of the upper bound up to a logarithmic factor, and it holds for any dimension D. On the negative side, the bound is obtained by constructing a specific Gaussian process. Therefore, it does not apply to a specific kernel. Yet, it tells us that under our general assumptions a big improvement cannot be gained. where Y 1 , . . . , Y 2T are independent standard normal random variables. For any D ≥ 1, L k ≥ 0, L µ ≥ 0, 0 < α ≤ 1 and T ∈ 1 2 , 2 D 2 , 3 D 2 , . . . , there exists a Gaussian process r defined on [0, 1] D satisfying Assumptions (A1) and (A2) such that

E sup x∈X r(x) -max r(x 1 ), . . . , r(x T ) ≥ κ T L k 2 α (2T ) α/D log T ≥ κ L k 2 α (2T ) α/D log T ,
for some universal constant κ > 0.

Proof. Let m = (2T ) 1/D . By assumption on T , m is an integer. Define h = L k (2m) α . To prove the lower bound, we consider a Gaussian process r(x) = This grid has 2T points. Let s 1 , . . . , s 2T denote these points (the ordering of these points has no importance). Define the function φ by

φ(u) = h (2m) -α -u α ∞ if u ∞ ≤ (2m) -1 0 otherwise
We consider the functions φ i (x) = φ(x -s i ) so that the Gaussian process is simply

r(x) = 2T i=1 φ(x -s i )Y i .
The function φ is continuous and "peaked around zero". Let us check that for any s, t ∈ R D , we have

φ(t) -φ(s) ≤ h t -s α ∞ . ( 5
)
First it is easy to see that we only need to prove this inequality for s and t in the cubic ball B = u ∈ R D : u ∞ ≤ (2m) -1 . Now, since for 0 < α ≤ 1 and any nonnegative numbers a and b we have (a + b) α ≤ a α + b α , for any s and t in B, we obtain

φ(t) -φ(s) ≤ h t α ∞ -s α ∞ ≤ h t ∞ -s ∞ α ≤ h t -s α
∞ , so that (5) holds. We now use (5) to prove that Assumption (A2) is satisfied. We have

k(s, t) = E[r(s)r(t)] = 2T i=1 φ(s -s i )φ(t -s i ) = φ(s -s j )φ(t -s j ),
for j an integer such that t -s j ∈ B. For such a j, from (5), we can also write

k(t, t) -k(s, t) = φ(t -s j ) φ(t -s j ) -φ(s -s j ) ≤ h 2 (2m) -α t -s α ∞ = L k t -s α
∞ . So Assumptions (A1) and (A2) are satisfied (for any L µ ≥ 0, since µ(x) = 0 for any x ∈ [0, 1] D ).

Whatever policy is used, after T observations of the Gaussian process, among the 2T random variables Y 1 , . . . , Y 2T , we know only the values of T of them, and we get absolutely no information on the T remaining ones 1 . Without loss of generality, let us consider that these T values correspond to Y 1 , . . . , Y T . We thus have

E sup x∈X r(x) -max r(x 1 ), . . . , r(x T ) ≥ h(2m) -α E max i=1,...,2T Y i -max i=1,...,T Y i = κ T L k (2m) α log T .
This is the first inequality of the theorem. To obtain the second inequality, we will prove that there is an absolute constant κ > 0 such that κ T > κ for any T ≥ 1. To do this, since κ T is positive for any T ≥ 1, it suffices to prove that there exists u T such that κ T ≥ u T for any large enough T and u T converges to a positive constant when T tends to infinity. Define

a T = 2 log T log(2T ) , M 1 = max i=1,...,T Y i , M 2 = max i=T +1,...,2T Y i , Φ(t) = P(Y 1 > t), and
u T = log T a T + 2 log 2 - √ a T × 1 -P M 1 ≤ a T + 2 log 2 P M 1 ≤ √ a T .
For T ≥ 2, we have

κ T = log T E max(0, M 2 -M 1 ) ≥ log T a T + 2 log 2 - √ a T × P M 2 ≥ a T + 2 log 2; M 1 ≤ √ a T = u T .
To obtain an equivalent on u T when T goes to infinity, we use the well-known bound on tails of the normal distribution (e.g., see Pollard (2002, Appendix D)

): exp(-t 2 2 ) t √ 2π 1 - 1 t 2 ≤ Φ(t) ≤ exp(-t 2 2 ) t √ 2π .
Consequently, we obtain

P M 1 ≤ √ a T = [1 -Φ( √ a T )] T -→ T →∞ exp - 1 √ 4π
and similarly

P M 1 ≤ a T + 2 log 2 -→ T →∞ exp - 1 2 √ 4π .
Finally, elementary computations give

log T a T + 2 log 2 - √ a T -→ T →∞ log 2 √ 2 .
Putting together the three last results, we obtain that u T converges to a positive constant when T goes to infinity, hence there exists κ > 0 such that κ T ≥ κ for any T ≥ 1.

CONCLUSIONS AND FUTURE WORK

The main contribution of the paper has been to our knowledge the first analysis of a new bandit scenario based on a Gaussian process model of the reward function. The results bound the regret (relative to always playing the optimal arm) of particular strategies in the case where there is no noise in the observed reward and the kernel satisfies benign continuity assumptions. We provide lower bounds that show our bounds are in general at most a logarithmic factor away from optimal.

We intend to extend this work to model of rewards incorporating a noise term so that the true reward would not then be directly observed. A more ambitious goal is to develop reward bounds for algorithms that merge the exploration and exploitation phases through for example selecting arms based on an upper confidence bound. It will also be interesting to see if more detail properties of the kernel (other than Hölder continuity) can be incorporated into the analysis to provide tighter bounds for special types of kernel, such as for example specific spectral properties.

We believe that the line of analysis developed here will provide important groundwork for these further studies and will at the same time help to inform improvements in practical Gaussian process bandit algorithms.

A Dudley integral computations

To bound the Dudley integral, we use

  ; Auer et al. (2007); Wang et al. (2008); Bubeck et al. (2008); Klein-berg et al. (2008a) but they do not integrate the Gaussian process assumption. The precise definition of our setting and regret is given in Section 4.

2T

  i=1 φ i (x)Y i , where φ i are real-valued functions with disjoint supports (up to the boundaries) and Y 1 , . . . , Y 2T are i.i.d. centered normal random variables with unit variance. Consider the regular grid on [0, 1] D defined by , . . . , i D ) ∈ {1, . . . , m} D .

  bε -1/a )dε ≤ c log(e2 a+1 ) a . (6) which holds for any a, b and c such that b a = 2c. Indeed, letting ξ = (1 + 2 -1/a ) a , we have c 0 log(1 + bε -1/a )dε ≤ c 0 log ξ a bε -1/a dε

A different viewpoint is to compute explicitly the optimal policy in this setting. It is easy to see that the policy stems down to playing a different grid point at each time step.

Acknowledgements

We would like to thank the European Union for funding through PASCAL 2 and the ARAGORN project. The second author would like to acknowledge the French National Research Agency (ANR) through COSINUS program (project EXPLO-RA, ANR-08-COSI-004).