Anna Ben-Hamou
email: anna.benhamou@univ-paris-diderot.fr

Stephane Boucheron
email: stephane.boucheron@univ-paris-diderot.fr

Mesrob I Ohannessian
email: mesrob@gmail.com

Stéphane Boucheron

Keywords: Concentration, regular variation, occupancy, missing mass, rare species

Concentration inequalities in the infinite urn scheme for occupancy counts and the missing mass, with applications

Introduction

From the 20th century to the 21st, various disciplines have tried to infer something about scarcely observed events: zoologists about species, cryptologists about cyphers, linguists about vocabularies, and data scientists about almost everything. These problems are all about 'small data' within possibly much bigger data. Can we make such inference?

Problem setting

To move into a concrete setting, let U 1 , U 2 , • • • , U n be i.i.d. observations from a fixed but unknown distribution (p j ) ∞ j=1 over a discrete set of symbols N * = N \ {0}. We consider each j in N * as a discrete symbol devoid of numerical significance. The terminology of 'infinite urn scheme' comes from the analogy to n independent throws of balls over an infinity of urns, p j being the probability of a ball falling into urn j, at any i-th throw. We alternatively adhere to the symbols or the urns perspective, based on which carries the intuition best. Species, cyphers, and vocabularies all being discrete, are well modeled as such. The sample size n may be fixed in advance; we call this the binomial setting. It may be randomly set by the duration of an experiment; this gives rise to the Poisson setting. More precisely, in the latter case we write it as N , a Poisson random variable independent of (U i ) and with expectation t. We index all Poisson-setting quantities by t and write them with functional notations, instead of subscripts used for the fixed-n scheme.

For each j, n ∈ N * , let X n,j = n i=1 I {Ui=j} be the number of times symbol j occurs in a sample of size n, and X j (t) = N (t) i=1 I {Ui=j} the Poisson version . In questions of underrepresented data, the central objects are sets of symbols that are repeated a small number r of times. The central quantities are the occupancy counts K n,r [respectively K r (t) for the Poisson setting], defined as the number of symbols that appear exactly r times in a sample of size n:

K n,r = |{j, X n,j = r}| = ∞ j=1 I {Xn,j =r} .
The collection (K n,r ) r≥1 [resp. (K r (t)) r≥1 ] has been given many names, such as the "profile" (in information theory [START_REF] Orlitsky | Universal compression of memoryless sources over unknown alphabets[END_REF]) or the "fingerprint" (in theoretical computer science [Batu et al., 2001, Valiant and[START_REF] Valiant | Estimating the unseen: an N/Log(N)-sample estimator for entropy and support size, shown optimal via new CLTs[END_REF]) of the probability distribution (p j ) j∈N . Here we refer to them by occupancy counts individually, and occupancy process all together.

The occupancy counts then combine to yield the cumulated occupancy counts K n,r [respectively K r (t)] and the total number of distinct symbols in the sample, or the total number of occupied urns, often called the coverage and denoted by K n [respectively K(t)]:

K n,r = |{j, X n,j ≥ r}| = ∞ j=1 I {Xn,j ≥r} = s≥r K n,s , and
K n = |{j, X n,j > 0}| = ∞ j=1 I {Xn,j >0} = r≥1 K n,r .
In addition to the occupancy numbers and the number of distinct symbols, we also address the rare (or small-count) probabilities M n,r [respectively M r (t)],

imsart-generic ver. 2014/07/30 file: main-arxiv.tex date: December 30, 2014 defined as the probability mass corresponding to all symbols that appear exactly r times:

M n,r = P({j, X n,j = r}) = ∞ j=1 p j I {Xn,j =r} .

In particular, we focus on M n,0 = ∞ j=1 p j I {Xn,j =0} , which is called the missing mass, and which corresponds to the probability of all the unseen symbols.

Explicit formulas for the moments of the occupancy counts and masses can be derived in the binomial and Poisson settings. The occupancy counts' expectations are given by

EK n = ∞ j=1 (1 -(1 -p j ) n ) EK(t) = ∞ j=1
(1 -e -npj )

EK n,r = ∞ j=1 n r p r j (1 -p j ) n-r EK r (t) = ∞ j=1 e -npj (np j ) r r! EM n,r = ∞ j=1 n r p r+1 j (1 -p j ) n-r EM r (t) = ∞ j=1
e -npj p j (np j ) r r! .

Formulas for higher moments can also be computed explicitly but their expression, especially in the binomial setting where a lot of dependencies are involved, often has an impractical form. This classical occupancy setting naturally models a host of different application areas, including computational linguistics, ecology, and biology. Urns may represent species, and we are interested in the number of distinct species observed in a sample (the ecological diversity) or in the probability of the unobserved species. In linguistics, urns may represent words. In both of these applications, the independence assumption of the random variables {U i } i=1...n may seem unrealistic. For instance in a sentence, the probability of appearance of a word strongly depends on the previous words, both for grammatical and semantic reasons. Likewise, the nucleotides in a DNA sequence do not form an i.i.d. sample. In n-gram models, independence is only conditional and the observations are assumed to satisfy a Markovian hypothesis: the probability of occurrence of a word depends on the n -1 previous words. But the i.i.d. case, although very simple, yields results that are interesting in themselves, and upon which a more sophisticated framework may be built.

Many practical questions may now be formulated in this setting. If we double the duration of a first experiment, how many yet unobserved specimens would we find (how does K 2n,r compare to K n,r [resp. K r (2t) to K r (t)]) [START_REF] Fisher | The relation between the number of species and the number of individuals in a random sample of an animal population[END_REF]? If certain cypher keys have been observed, what is the probability for the next to be different (how does one estimate M n,0 )? For instance, [START_REF] Good | The population frequencies of species and the estimation of population parameters[END_REF] and Turing observed that (n + 1)EM n,0 = EK n+1,1 for all n ≥ 1, and proposed to estimate the missing mass using the Jackknife estimator G n,0 = K n,1 /n (the proportion of symbols seen just once).

imsart-generic ver. 2014/07/30 file: main-arxiv.tex date: December 30, 2014

Contributions

To study the Good-Turing estimator or other quantities that depend significantly on the small-count portion of the observations, we need to understand the occupancy counts well. Our contribution here is to give sharp concentration inequalities with explicit and reasonable constants, for K n , K n,r , and M n,0 [resp. K(t), K r (t), M 0 (t)]. We give distribution-free results, and then exhibit a vast domain where these results are tight, namely the domain of distributions with a heavier tail than the geometric. In this domain, the non-asymptotic exponential concentration properties that we establish are sharp in the sense that the exponents are order-optimal, precisely capturing the scale of the variance. For this reason, we dedicate a portion of the paper to establishing bounds on various variances.

Organization

The paper is organized as follows. In Section 2, we present our terminology and give a concise summary of the results. In Section 3 we present our variance bounds and concentration results for the occupancy counts and the missing mass in great generality. In Section 4 we specialize these results to regularly varying distributions, the aforementioned domain of distributions where concentration can be characterized tightly. We then elaborate on some applications in Section 5, and conclude with a discussion of the results and possible extensions in Section 6. We group all proofs in the end, in Section 7.

Summary of results

Terminology

Our concentration results mostly take the form of bounds on the log-Laplace transform. Our terminology follows closely [START_REF] Boucheron | Concentration inequalities[END_REF]. We say that the random variable Z is sub-Gaussian on the right tail (resp. on the left tail) with variance factor v if, for all λ ≥ 0 (resp. λ ≤ 0),

log Ee λ(Z-EZ) ≤ vλ 2 2 . (2.1)
We say that a random variable

Z is sub-Poisson with variance factor v if, for all λ ∈ R, log Ee λ(Z-EZ) ≤ vφ(λ) , (2.2) with φ : λ → e λ -λ -1.
We say that a random variable Z is sub-gamma on the right tail with variance factor v and scale parameter c if

log Ee λ(X-EX) ≤ λ 2 v 2(1 -cλ)
for every λ such that 0 ≤ λ ≤ 1/c .

(2.3) The random variable Z is sub-gamma on the left tail with variance factor v and scale parameter c, if -Z is sub-gamma on the right tail with variance factor v and scale parameter c. If Z is sub-Poisson with variance factor v, then it is sub-Gaussian on the left tail with variance factor v, and sub-gamma on the right tail with variance factor v and scale parameter 1/3. These log-Laplace upper bounds then imply exponential tail bounds: Inequality (2.3) results in a Bernstein-type inequality for the right tail, that is, for s > 0 our inequalities have the form:

P{Z > E[Z] + √ 2vs + cs} ≤ e -s ,
while Inequality (2.1) for all λ ≤ 0 entails

P{Z < E[Z] - √ 2vs} ≤ e -s .
We present such results first without making distributional assumptions, beyond the structure of those quantities themselves. These concentrations then specialize in various settings, such as that of regular variation.

Main results

We proceed by giving a coarse description of our main results. In the Poisson setting, for each r ≥ 1, (I{X j (t) = r}) j≥1 are independent, hence K r (t) is a sum of independent Bernoulli random variables, and it is not too surprising that it satisfies sub-Poisson, also known as Bennett, inequalities. For λ ∈ R, we have:

log Ee λ(Kr(t)-EKr(t)) ≤ var(K r (t))φ(λ) ≤ E[K r (t)]φ(λ) .
The proofs are elementary and are based on the careful application of Efron-Stein-Steele inequalities and the entropy method [START_REF] Boucheron | Concentration inequalities[END_REF].

As for the binomial setting, the summands are not independent but we can use negative association arguments [START_REF] Dubhashi | Balls and bins: A study in negative dependence[END_REF]] (see Section 7) to obtain Bennett inequalities for the cumulated occupancy counts K n,r . These hold either with the Jackknife variance proxy given by the Efron-Stein inequality, rEK n,r or with the variance proxy stemming from the negative correlation of the summands, EK n,r . Letting v n,r = min(rEK n,r , EK n,r ), we have, for all λ ∈ R:

log Ee λ(Kn,r-EKn,r) ≤ v n,r φ(λ) .

This in turn implies a concentration inequality for K n,r . Letting

v n,r = 2 min ((rEK n,r ) ∨ ((r + 1)EK n,r+1 )), EK n,r ) ,
we have, for all s ≥ 0,

P |K n,r -EK n,r | ≥ 4v n,r s + 2s/3 ≤ 4e -s .
imsart-generic ver. 2014/07/30 file: main-arxiv.tex date: December 30, 2014

We obtain distribution-free bounds on the log-Laplace transform of M n,0 , which result in sub-Gaussian concentration on the left tail, sub-gamma concentration on the right tail with scale proxy 1/n. More precisely, letting v

- n = 2EK 2 (n)/n 2 and v + n = 2EK 2 (n)/n 2 , we show that, for all λ ≤ 0, log Ee λ(Mn,0-EMn,0) ≤ v - n λ 2 2 ,
and, for all λ ≥ 0, log Ee λ(Mn,0-EMn,0

) ≤ v + n λ 2 2(1 -λ/n) .
Indeed, these results are distribution-free. But though the variance factor v - n is a sharp bound for the variance of the missing mass, v + n may be much bigger. This leads us to look for distribution-specific conditions ensuring that v + n captures the right order for the variance, such as by using a tail asymptotic stability condition as in extreme value theory. [START_REF] Karlin | Central limit theorems for certain infinite urn schemes[END_REF] pioneered such a condition by assuming that the function ν : (0, 1] → N, defined by ν(x) = |{j ∈ N * , p j ≥ x}| satisfies a regular variation assumption, namely ν(1/n) ∼ n α (n) near +∞, with α ∈ (0, 1] [see also Gnedin et al., 2007, Ohannessian and[START_REF] Ohannessian | Rare probability estimation under regularly varying heavy tails. In colt 2012[END_REF]. Here is a slowly varying function at ∞, i.e. for all x, (τ x)/ (τ ) → 1 as τ → ∞. This condition allows us to compare the asymptotics of the various occupancy scores. In particular, in this framework EK 2 (n) and EK 2 (n) have the same order of growth, and, divided by n 2 they both are of the same order as the variance of the missing mass. Hence, the regular variation provides a framework in which our concentration inequalities are order-optimal.

To handle the case α = 0, we move from Karamata to de Haan theory, and take ν to have an extended regular variation property, with the additional assumption that EK 1 (n) tends to +∞. This domain corresponds to light-tailed distributions which are still heavier than the geometric. In this case, we manage to show the sub-gamma concentration of the missing mass only for n large enough, that is, that there exists n 0 such that for all n ≥ n 0 , for λ > 0, we have log Ee λ(Mn,0-EMn,0) ≤ (v n λ 2 )/2(1 -λ/n), with v n VarM n,0 .

Back to our examples of applications, considerable insight may be gained from these concentration results. For instance, heavy tails lead to multiplicative concentration for M n,0 and the consistency of the Good-Turing estimator:

Gn,0 Mn,0 p -→ 1. Generally, new estimators can be derived and shown to be consistent in a unified framework, once one is able to estimate α consistently. For instance, when ν(1/.) is regularly varying with index α, α = K n,1 /K n is a consistent estimator of α. Then, to estimate the number of new species in a sample twice the size of the original, we immediately get that K 2n = K n + 2 α -1 α K n,1 is a consistent estimator of K 2n . This methodology is very similar to extreme value theory [START_REF] Beirlant | Statistics of extremes: theory and applications[END_REF]: harnessing limiting expressions and tail parameter estimation. These results strengthen and extend the contribution of [START_REF] Ohannessian | Rare probability estimation under regularly varying heavy tails. In colt 2012[END_REF], which is restricted to power-laws and implicit constants imsart-generic ver. 2014/07/30 file: main-arxiv.tex date: December 30, 2014 in the inequalities. Beyond consistency results, we also obtain confidence intervals for the Good-Turing estimator in the Poisson setting, using empirical quantities.

Historical notes and related work

There exists a vast literature on the occupancy scheme, as formulated here and in many other variations. The most studied problems are the asymptotic behavior of K n and K n,r . This is done often in a finite context, or a scaling model where probabilities remain mostly uniform. Of particular relevance to this paper, we mention the work of [START_REF] Karlin | Central limit theorems for certain infinite urn schemes[END_REF], who built on earlier work by [START_REF] Bahadur | On the number of distinct values in a large sample from an infinite discrete distribution[END_REF], credited as one of the first to study the infinite occupancy scheme. Karlin's main results were to establish central limit theorems in an infinite setting, under a condition of regular variation. He also derived strong laws of large numbers. [START_REF] Gnedin | Notes on the occupancy problem with infinitely many boxes: general asymptotics and power laws[END_REF] present a general review of these earlier results, as well as more contemporary work on this problem. The focus continues to be central limit theorems, or generally asymptotic results. For example the work of [START_REF] Hwang | Local limit theorems for finite and infinite urn models[END_REF] (effectively) provides a local limit theorem for K n provided that the variance tends to infinity. Somewhat less asymptotic results have also been proposed, in the form of normal approximations, such as in the work of [START_REF] Barbour | Small counts in the infinite occupancy scheme[END_REF].

Besides occupancy counts analysis, a distinct literature investigates the number of species and missing mass problems. These originated in the works of [START_REF] Fisher | The relation between the number of species and the number of individuals in a random sample of an animal population[END_REF], [START_REF] Good | The population frequencies of species and the estimation of population parameters[END_REF], and [START_REF] Good | The number of new species, and the increase in population coverage, when a sample is increased[END_REF], and generated a long line of research to this day [START_REF] Bunge | Estimating the number of species: a review[END_REF]. Here, instead of characterizing the asymptotic behavior of these quantities, one is interested in estimating K λn -K n for a λ > 1, that is the number of discoveries when the sample size is multiplied by λ, or estimating M n,0 : estimators are proposed, and then their statistical properties are studied. One recently studied property by [START_REF] Mcallester | On the convergence rate of Good-Turing estimators[END_REF] and [START_REF] Mcallester | Concentration inequalities for the missing mass and for histogram rule error[END_REF], is that of concentration, which sets itself apart from the CLT-type results in that it is non-asymptotic in nature. Based on this, [START_REF] Ohannessian | Rare probability estimation under regularly varying heavy tails. In colt 2012[END_REF] showed that in the regular variation setting of Karlin, one could show multiplicative concentration, and establish strong consistency results. Conversely, characterizing various aspects of concentration allows one to systematically design new estimators. For example, this was illustrated in [START_REF] Ohannessian | Rare probability estimation under regularly varying heavy tails. In colt 2012[END_REF] for the estimation of rare probabilities, to both justify and extend Good's [START_REF] Good | The population frequencies of species and the estimation of population parameters[END_REF] work that remains relevant in some of the aforementioned applications, especially computational linguistics.

Concentration

Occupancy counts

Variance bounds

In order to understand the fluctuations of occupancy counts K n , K(t), K n,r , K r (t), we start by reviewing and stating variance bounds. We start with the Poisson setting where occupancy counts are sums of independent Bernoulli random variables with possibly different success probabilities, and thus variance computations are straightforward. Exact expressions may be derived [see for example Gnedin et al., 2007, Equation (4)], but ingenuity may be used to derive more tractable and tight bounds. We start by stating a well-known connection between the variance of the number of occupied urns and the expected number of singletons [START_REF] Gnedin | Notes on the occupancy problem with infinitely many boxes: general asymptotics and power laws[END_REF][START_REF] Karlin | Central limit theorems for certain infinite urn schemes[END_REF]. In the binomial setting, similar bounds can be derived using the Efron-Stein-Steele inequalities [see Boucheron et al., 2013, Section 3.1]. Proposition 3.1. In the Poissonized setting,

EK 1 (2t) 2 ≤ Var(K(t)) ≤ EK 1 (t) .
In the binomial setting,

Var(K n ) ≤ E [K n,1 (1 -M n,0 )] ≤ EK n,1 .
The upper bounds in these two propositions parallel each other, but in the binomial setting, we cannot hope to establish lower bounds like EK cn,1 /c ≤ Var(K n ) for some constant c > 0 in full generality. To see this, consider the following example which shows that the variance of K(t) and of K n may differ significantly, and that the variance of K n may be much smaller than the expected value of K n,1 . Example 1. In the so-called birthday paradox scenario, n balls are thrown independently into n 2 urns with uniform probabilities 1/n 2 . In the Poisson setting for time t = n, since we have EK(n) = j (1 -e -npj ) = n 2 (1 -e -1/n ), using an upper and lower Taylor expansion we can obtain the bounds:

n -1 2 ≤ EK(n) ≤ n -1 2 + 1 6n . Since Var(K(n)) = j e -npj (1 -e -npj ) = EK(2n) -EK(n), it follows that: n - 1 6n ≤ Var(K(n)) ≤ n + 1 12n
.

Meanwhile, we have E[K 1 (n)] = j np j e -npj = ne -1/n , which can be bounded similarly:

n -1 ≤ E[K 1 (n)] ≤ n -1 + 1 2n .
imsart-generic ver. 2014/07/30 file: main-arxiv.tex date: December 30, 2014

We can thus see that the Poisson birthday paradox satisfies the spirit of Proposition 3.1, if not its letter (because of being outside of our fixed-p setting). Namely, the Poisson quantities Var(K(n)) and EK 1 (n) are of the same order of magnitude, roughly n.

On the other hand, in the binomial setting, since 1 -

M n,0 = K n /n 2 , Var(K n ) ≤ E [K n,1 (1 -M n,0 )] = E K n,1 K n n 2 ≤ 1 n EK n,1 ≤ 1,
where we have used the same variance bound as in the proof of Proposition 3.1 (Section 7.2.1). While this implies that the upper bound Var(K n ) ≤ EK n,1 is satisfied, it also shows that a lower bound of the kind of

EK cn,1 /c ≤ Var(K n ) is not possible, since similarly to EK 1 (n), we have EK n,1 = j np j (1 -p j ) n = n(1 -1 n 2 ) n ≥ n -1.
Another straightforward bound on Var(K n ) comes from the fact that the Bernoulli variables (I {Xn,j >0} ) j≥1 are negatively correlated. Thus, ignoring the covariance terms, we get

Var(K n ) ≤ ∞ j=1 Var(I {Xn,j >0} ) = ∞ j=1 (1 -p j ) n (1 -(1 -p j ) n ) = EK 2n -EK n .
Let us denote this bound by Var ind (K n ) = EK 2n -EK n , as it is a variance proxy obtained by considering that the summands in K n are independent. One can observe that the expression of Var ind (K n ) is very similar to the variance in the Poissonized setting, Var(K(t)) = EK(2t) -EK(t). It is insightful to compare the true variance, the Poissonized proxy, and the negative correlation proxy, to quantify the price one pays by resorting to the latter two as an approximation for the first. We revisit this in more detail in Section 6.1.

We now investigate the fluctuations of the individual occupancy counts K n,r and K r (t), and that of the cumulative occupancy counts K n,r = j≥r K n,j and K r (t) = j≥r K j (t). Proposition 3.2. In the Poisson setting, for r ≥ 1, t ≥ 0, Var(K r (t)) ≤ min (rEK r (t), EK r (t)) .

In the binomial setting, for r, n ≥ 1,

Var(K n,r ) ≤ min (rEK n,r , EK n,r ) .
For each setting, the first bound follows from Efron-Stein-Steele inequalities, the second from negative correlation. These techniques are presented briefly in Sections 7.1.1 and 7.1.2 respectively. Remark 3.1. Except for r = 1, there is no clear-cut answer as to which of these two bounds is the tightest. In the regular variation scenario with index α ∈]0, 1] as explored in [START_REF] Gnedin | Notes on the occupancy problem with infinitely many boxes: general asymptotics and power laws[END_REF], the two bounds are asymptotically of the same order, indeed,

rEK n,r EK n,r ∼ n→+∞ α ,
imsart-generic ver. 2014/07/30 file: main-arxiv.tex date: December 30, 2014

see Section 4 for more on this. Bounds on Var(K r (t)) can be easily derived as K r (t) is a sum of independent Bernoulli random variables, however, noticing that K n,r = K n,r -K n,r+1 and that K n,r and K n,r+1 are positively correlated, the following bound is immediate. Proposition 3.3. In the Poisson setting, for r ≥ 1, t ≥ 0,

Var(K r (t)) ≤ EK r (t) .
In the binomial setting, for r, n ≥ 1,

Var(K n,r ) ≤ min rEK n,r + (r + 1)EK n,r+1 , EK n,r + EK n,r+1 ≤ 2 min ((rEK n,r ) ∨ ((r + 1)EK n,r+1 )), EK n,r ) .

Concentration inequalities

Concentration inequalities refine variance bounds. These bounds on the logarithmic moment generating functions are indeed Bennett (sub-Poisson) inequalities with the variance upper bounds stated in the preceding section. For K n,r , the next proposition gives a Bernstein inequality where the variance factor is, up to a constant factor, the Efron-Stein upper bound on the variance. Proposition 3.4. Let r ≥ 1, and let v n,r = min(rEK n,r , EK n,r ). Then, for all λ ∈ R, log Ee λ(Kn,r-EKn,r) ≤ v n,r φ(λ) ,

with φ : λ → e λ -λ -1.
It is worth noting that the variance bound EK n,r in this concentration inequality can also be obtained using a variant of Stein's method known as sizedbias coupling [START_REF] Bartroff | Bounded size biased couplings, log concave distributions and concentration of measure for occupancy models[END_REF][START_REF] Chen | Normal approximation by Stein's method[END_REF].

A critical element of the proof of Proposition 3.4 is to use the fact that each K n,r is a sum of negatively associated random variables (Section 7.1.2). This is not the case for K n,r , and thus negative association cannot be invoked directly. To deal with this, we simply use the observation of [START_REF] Ohannessian | Rare probability estimation under regularly varying heavy tails. In colt 2012[END_REF] that since K n,r = K n,r -K n,r+1 , the concentration of K n,r follows from that of those two terms. We can show the following. Proposition 3.5. Let

v n,r = 2 min ((rEK n,r ) ∨ ((r + 1)EK n,r+1 )), EK n,r ) .
Then, for s ≥ 0,

P |K n,r -EK n,r | ≥ 4v n,r s + 2s/3 ≤ 4e -s .

Missing mass

imsart-generic ver. 2014/07/30 file: main-arxiv.tex date: December 30, 2014

Variance bound

Recall that M n,0 = ∞ j=1 p j I {Xn,j =0} = ∞ j=1 p j Y j ,
and we can readily show that the summands are negatively associated weighted Bernoulli random variables (Section 7.1.2). This results in a handy upper bound for the variance of the missing mass. Proposition 3.6. In the Poisson setting,

Var(M 0 (t)) = 2EK 2 (t)/t 2 -EK 2 (2t)/2t 2 ≤ 2EK 2 (t)/t 2 ,
while in the binomial setting,

Var(M n,0 ) ≤ ∞ j=1 p 2 j Var(Y j ) ≤ 2EK 2 (n) n 2 .
Note that whereas the expected value of the missing mass is connected to the number of singletons, its variance may be upper bounded using the number of doubletons (in the Poisson setting). This connection was already pointed out in [START_REF] Good | The population frequencies of species and the estimation of population parameters[END_REF] and [START_REF] Esty | Confidence intervals for the coverage of low coverage samples[END_REF].

Concentration of the left tail

Moving on to the concentration properties of the missing mass, we first note that as a sum of weighted sub-Poisson random variables (following [START_REF] Boucheron | Concentration inequalities[END_REF]), the missing mass is itself a sub-gamma random variable on both tails. It should not come as a surprise that the left tail of M n,0 is sub-Gaussian with the variance factor derived from negative association. This had already been pointed out by [START_REF] Mcallester | On the convergence rate of Good-Turing estimators[END_REF] and [START_REF] Mcallester | Concentration inequalities for the missing mass and for histogram rule error[END_REF]. Proposition 3.7. [START_REF] Mcallester | Concentration inequalities for the missing mass and for histogram rule error[END_REF] In the Poisson setting, the missing mass M 0 (t) is sub-Gaussian on the left tail with variance factor the effective variance Var(M 0 (t)) = ∞ j=1 p 2 j e -tpj (1 -e -tpj ). In the binomial setting, the missing mass M n,0 is sub-Gaussian on the left tail with variance factor

v = ∞ j=1 p 2 j Var(Y j ) or v - n = 2EK 2 (n)/n 2 . For λ ≤ 0, log E e λ(Mn,0-EMn,0) ≤ vλ 2 2 ≤ 2v - n λ 2 2 3.2.

Concentration of the right tail

The following concentration inequalities for the missing mass mostly rely on the observation that, for all λ > 0, This suggests that if we have a uniform control on the expected occupancy scores (EK r (t)) r≥2 , then the missing mass has a sub-gamma right tail, with some more or less accurate variance proxy, and scale factor 1/n.

log E e λ(Mn,0-EMn,0) ≤ ∞ r=2 λ n r EK r (n) . ( 3
The next theorem shows that the missing mass is sub-gamma on the right tail with variance proxy 2EK 2 (n)/n 2 and scale proxy 1/n. Despite its simplicity and its generality, this bound exhibits an intuitively correct scale factor: if there exist symbols with probability of order 1/n, they offer the major contribution to the fluctuations of the missing mass.

Theorem 3.8. In the binomial as well as in the Poisson setting, the missing mass is sub-gamma on the right tail with variance factor v + n = 2EK 2 (n)/n 2 and scale factor 1/n. For λ ≥ 0, log E e λ(Mn,0-EMn,0

) ≤ v + n λ 2 2(1 -λ/n) .
If the sequence (EK r (n)) r≥2 is non-increasing, the missing mass is sub-gamma on the right tail with variance factor v - n = 2EK 2 (n)/n 2 and scale factor 1/n, log E e λ(Mn,0-EMn,0

) ≤ v - n λ 2 2(1 -λ/n) .
Remark 3.2. [START_REF] Mcallester | Concentration inequalities for the missing mass and for histogram rule error[END_REF] and [START_REF] Berend | On the concentration of the missing mass[END_REF] point out that for each Bernoulli random variable

Y j , for all λ ∈ R log Ee λ(Yj -EYj ) ≤ λ 2 4c ls (EY j )
,

where c ls (p) = log(p/(1 -p))/(1 -2p) (or 2 if p = 1/2) is the optimal logarithmic Sobolev constant for Bernoulli random variables with success probability p (this sharp and non-trivial result has been proved independently by a number of people: Hoeffding [1963, Theorem 1, second inequality], Kearns and Saul [1998], [START_REF] Berend | On the concentration of the missing mass[END_REF], [START_REF] Raginsky | Concentration of Measure Inequalities in Information Theory[END_REF]). From this observation, thanks to the negative association of the (Y j ) j≥1 , it follows that the missing mass is sub-Gaussian with variance factor

v = ∞ j=1 p 2 j 2c ls ((1 -p j ) n ) ≤ ∞ j=1 p 2 j 2 log((1 -p j ) -n ) ≤ ∞ j=1 p 2 j 2np j ≤ 1 2n .
This variance factor is usually larger than 2EK 2 (n)/n 2 . In the scenarios discussed in Section 4, (2EK 2 (n)/n 2 )/(1/2n) even tends to 0 as n tends to infinity.

Regular variation

Motivation

Are the variance bounds in the concentration results of Section 3 tight? To see that in some pathological examples this may not be the case, consider the following example (which revisits Example 1).

imsart-generic ver. 2014/07/30 file: main-arxiv.tex date: December 30, 2014

Example 2. We may challenge the tail bounds offered by Proposition 3.7 and Theorem 3.8 in the simplest setting where all N symbols have equal probabilities 1/N . Then the missing mass is 1 -K n /N , its variance is Var(K n )/N 2 . In the birthday paradox setting (N = n 2 ), Var(M n,0 ) ≤ 1/n 4 , and the variance bound

2EK 2 (n)/n 2 is not tight. Indeed, one can verify that EK 2 (n) ≥ 1 2 1 -1 n so that v + n ≥ 1 n 2 -1 n 3 .
However, in what is called the central domain in [START_REF] Kolchin | Random allocations[END_REF], that is when N → ∞ while n/N → t ∈ R + , the tail bounds become relevant. The variance of K n is equivalent to N e -t (1 -e -t ) while its expectation is equivalent to N (1 -e -t ). Note that in this setting all EK r (n) and EK n,r are of the same order of magnitude as

EK n , indeed EK r (n)/EK(n) → e -t t r /(r!(1 -e -t )).
These examples are illustrative although they do not fall in the fixed p regime we are considering in this paper. We use them because they have tractable expressions, and they provide informative diagnostics. To parallel the phenomenon of mismatched variance proxies in our setting, one can simply look at the geometric distribution for a concrete example. If (p k ) k≥1 defines a geometric distribution p k = (1 -q) k-1 q, then EK 2 (n) remains bounded, while EK 2 (n) scales like log n as n tends to infinity.

In particular, we may conjecture that Theorem 3.8 is likely to be sharp when the first terms of the sequence (EK r (n)) r≥2 grow at the same rate as EK(n), or at least as EK 2 (n), which is not the case in the birthday paradox setting of Example 2. We see in what follows that the regular variation framework introduced by [START_REF] Karlin | Central limit theorems for certain infinite urn schemes[END_REF] leads to such asymptotic equivalents. The most useful aspect of these equivalent growth rates is a simple characterization of the variance of various quantities, particularly relative to their expectation. We focus on the right tail of the missing mass, which exhibits the highest sensitivity to this asymptotic behavior, by trying to specialize Theorem 3.8 under regular variation.

Definition

To state the regular variation hypothesis, we first introduce some notation. Following [START_REF] Karlin | Central limit theorems for certain infinite urn schemes[END_REF], [START_REF] Gnedin | Notes on the occupancy problem with infinitely many boxes: general asymptotics and power laws[END_REF] and [START_REF] Ohannessian | Rare probability estimation under regularly varying heavy tails. In colt 2012[END_REF], we consider the counting measure on [0, 1]

ν(dx) = ∞ j=1 δ pj (dx) ,
where δ x is the Dirac mass at x.

This assumption is made on the counting function ν, defined for all x > 0 by

ν(x) = ν[x, 1] = |{j : j ≥ 1, p j ≥ x}| .
Following [START_REF] Karlin | Central limit theorems for certain infinite urn schemes[END_REF], we say that frequencies p j are regularly varying with index α ∈ In what follows, we treat three cases separately: the nominal regular variation case with α ∈ (0, 1) strictly, the fast variation case with α = 1, and the slow variation case with α = 0.

[0, 1], if ν(x) ∼ 0+ x -α (1/x
In the latter case, that is if frequencies p j are regularly varying with index 0, we find that the mere regular variation hypothesis is not sufficient to obtain asymptotic formulas. For this reason, we introduce further control in the form of an extended regular variation hypothesis (given by Definition 1 of Section 4.3).

Remark 4.1. Before we proceed, as further motivation, we note that the regular variation hypothesis is very close to being a necessary condition for exponential concentration. For example, considering inequality (3.1), we see that if the sampling distribution is such that the ratio EK 2 (t)/EK 2 (t) remains bounded, then we are able to capture the right variance proxy. Now, defining the shorthand Φ 2 (t) = EK 2 (t) and Φ 2 (t) = EK 2 (t) following the notation of [START_REF] Gnedin | Notes on the occupancy problem with infinitely many boxes: general asymptotics and power laws[END_REF], we have

Φ 2 (t) = 2Φ 2 (t) t .
Hence, Φ 2 (t)/Φ 2 (t) = 2Φ 2 (t)/tΦ 2 (t), and if instead of boundedness, we further require that this ratio converges to some finite limit, then, by the converse part of Karamata's Theorem [see de Haan and Ferreira, 2006, Theorem B.1.5], we find that Φ 2 (and then Φ 2 ) is regularly varying, which in turn implies that ν(1/t) is regularly varying.

4.1. Case α ∈ (0, 1)

We first consider the case 0 < α < 1. The next theorem states that when the sampling distribution is regularly varying with index α ∈ (0, 1), the variance factors in the Bernstein inequalities of Proposition 3.7 and Theorem 3.8 are of the same order as the variance of the missing mass.

Theorem 4.1. Assume that the counting function ν satisfies the regular variation condition with index α ∈ (0, 1), then the missing mass M n,0 (or M 0 (n)) is sub-Gaussian on the left tail with variance factor v - n = 2EK 2 (n)/n 2 and subgamma on the right tail with variance factor v + n = 2EK 2 (n)/n 2 . The variance factors satisfy

lim n v - n Var(M n,0 ) = 1 1 -2 α-2 , lim n v + n Var(M n,0 ) = 2 α(1 -2 α-2 ) ,
imsart-generic ver. 2014/07/30 file: main-arxiv.tex date: December 30, 2014

and thus

lim n v - n v + n = α 2 .
The second ratio deteriorates when α approaches 0, implying that the variance factor for the right tail gets worse when the distribution has a lighter tail. We do not prove Theorem 4.1 as the asymptotics are a consequence of Karlin's results surveyed in [Gnedin et al., 2007, Ohannessian and[START_REF] Ohannessian | Rare probability estimation under regularly varying heavy tails. In colt 2012[END_REF].

In particular, we need Proposition 3.7, Theorem 3.8, and:

Theorem 4.2. [START_REF] Karlin | Central limit theorems for certain infinite urn schemes[END_REF] If the counting function ν is regularly varying with index α ∈ (0, 1), for all r ≥ 1,

-K n a.s. ∼ EK n ∼ +∞ Γ(1 -α)n α (n) , -K n,r a.s. ∼ EK n,r ∼ +∞ αΓ(r-α) r! n α (n) , -Var(M n,0 ) ∼ αΓ(2 -α)(1 -2 α-2 )n α-2 (n)
and the same hold for the corresponding Poissonized quantities.

Note that all expected occupancy counts are of the same order, and the asymptotic for EK 2 (n) follows directly from the difference between EK(n) and EK 1 (n).

Fast variation, α = 1

We refer to the regular variation regime with α = 1 as fast variation1 . From the perspective of concentration, this represents a relatively "easy" scenario. In a nutshell, this is because the variance of various quantities grows much slower than their expectation.

We first start by noting that Theorem 4.1 continues to hold as is for α = 1. However, the rationale is slightly different. Moreover, the occupancy counts in this case present some singular behaviors which justify treating this case separately. We first note the following asymptotics that asserts that in this case, the number of occupied boxes K n and the number of singletons K n,1 are asymptotically equivalent, and that they dominate all the K n,r , for r ≥ 2. Intuitively, almost all the symbols of the sample are distinct and their probability lies around 1/n, but a significant fraction of them has a probability smaller than 1/n. Theorem 4.3. [START_REF] Karlin | Central limit theorems for certain infinite urn schemes[END_REF]

Assume ν(1/x) = x -1 (x) with ∈ RV 0 (note that tends to 0 at ∞). Define 1 : [1, ∞) → R + by 1 (y) = ∞ y u -1 (u)du .
Then 1 ∈ rv 0 and lim t→∞ 1 (t)/ (t) = ∞ and the following asymptotics hold:

-K n a.s. ∼ EK n ∼ +∞ n 1 (n), -K n,1 a.s. ∼ EK n,1 ∼ +∞ EK n , -K n,r a.s. ∼ EK n,r ∼ +∞ 1 r(r-1) n (n) , r ≥ 2,
and the same hold for the corresponding Poissonized quantities.

We can now see that the expected missing mass scales like EK 1 (n)/n while its variance scales like EK 2 (n)/n 2 . That said, it is not immediately clear that the variance factor 2EK 2 (n)/n 2 is of the same order as Var(M n,0 ). As EK(n) and EK 1 (n) are asymptotically equivalent, Theorem 4.3 is not sufficient to obtain the asymptotics for EK 2 (n). This is given by the next proposition, which is in fact sufficient to prove Theorem 4.1 for both 0 < α < 1 and α = 1.

Proposition 4.4. Assume that the counting function ν satisfies the regular variation condition with index α ∈ (0, 1], then for all r ≥ 2,

K r (n) ∼ +∞ Γ(r -α) (r -1)! ν(1/n) a.s. .
Thus, when α = 1, the cumulated occupancy counts EK r (n), for r ≥ 2, are of the order of n (n), and thus each is dominated by EK(n) and EK 1 (n). In particular, EK 2 (n) is of order n (n) and our variance proxy still captures the right order for the variance of the missing mass.

Remark 4.2. Whereas in the case 0 < α < 1, 2EK(n)/n 2 would also have been a good variance proxy, here when α = 1 we really need to remove the singletons and take 2EK 2 (n)/n 2 to get the right order.

We also note that when α = 1, the missing mass is even more stable. If we let v n denote 2EK 2 (n)/n 2 or 2EK 2 (n)/n 2 , then

√ v n EM n,0 ∼    c(α).n -α/2 √ (n) (n) for 0 < α < 1 , c. n -1/2 √ (n) 1(n)
for α = 1 .

Slow variation, α = 0

The setting where the counting function ν satisfies the regular variation condition with index 0 represents a challenge. We refer to this regime simply as slow variation. Recall that this means that ν(z/n)/ ν(1/n) converges to 1 as n goes to infinity, yet to deal with this case we need to control the speed of this convergence, exemplified by the notion of extended regular variation that was introduced by de Haan [See Bingham et al., 1989, de Haan and[START_REF] De Haan | Extreme value theory[END_REF]].

As we illustrate in the end of this section, one may face rather irregular behavior without such a hypothesis.

R + such that for all x > 0 lim τ →∞ (τ x) -(τ ) a(τ ) → τ →∞ log(x) .
The function a(•) is called an auxiliary function. When a function has the extended slow variation property with auxiliary function a, we denote it by ∈ Π a .

Note that the auxiliary function is always slowly varying and satisfies lim τ →∞ (τ )/a(τ ) = ∞, that is it grows slower than the original function. Furthermore, any two possible auxiliary functions are asymptotically equivalent, that is if a 1 and a 2 are both auxiliary functions for , then lim t→∞ a 1 (t)/a 2 (t) = 1.

The notion of extended slow variation and the auxiliary function give us the aforementioned control needed to treat the α = 0 case on the same footing as the 0 < α < 1 case. In particular, in what follows in this section we assume that ν(1/.) ∈ Π a , with the additional requirement that the auxiliary function a tends to +∞.

Remark 4.3. This domain corresponds to light-tailed distributions just above the geometric distribution (the upper-exponential part of Gumbel's domain). For the geometric distribution with frequencies p j = (1 -q)q k-1 , j = 1, 2, . . . , the counting function satisfies ν(1/n) ∼ ∞ log 1/q (n) ∈ RV 0 , but the auxiliary function a(n) = log(1/q) does not tend to infinity. Frequencies of the form p j = cq √ j on the other hand do fit this framework.

Theorem 4.5. [START_REF] Gnedin | Notes on the occupancy problem with infinitely many boxes: general asymptotics and power laws[END_REF] Assume that defined by (t) = ν(1/t) is in Π a where a is slowly varying and tends to infinity. The following asymptotics hold for each r ≥ n

-K n P ∼ EK n ∼ +∞ (n) -K n,r P ∼ EK n,r ∼ +∞ a(n) r -K n,r P ∼ EK n,r ∼ +∞ (n) -M n,r P ∼ EM n,r ∼ +∞ a(n) n .
and the same equivalents hold for the corresponding Poissonized quantities.

Remark 4.4. In this case, the expectations (EK n,r ) r≥1 are of the same order but are much smaller than EK n , and the variables K n and K n,s are all almost surely equivalent to (n). It is also remarkable that all the expected masses (EM n,r ) r≥1 are equivalent.

As EK 2 (n) ∼ EK(n) ∼ (n), whereas the variance of the missing mass is of order a(n)/n 2 , upper bounding EK r (n), r ≥ 2 by EK 2 (n), is no longer sufficient to capture the right order for the variance. However, exploiting more carefully the regular variation hypothesis, we manage to get a uniform control over the EK r (n), which is valid for large enough n.

imsart-generic ver. 2014/07/30 file: main-arxiv.tex date: December 30, 2014 Theorem 4.6. Assume that defined by (x) = ν(1/x) is in Π a where the slowly varying function a tends to infinity, then

1. letting v n = 12a(n)/n 2 , v n Var(M n,0 ) ∼ 3a(n) 4n 2
2. there exists n 0 ∈ N that depends on ν such that for all n > n 0 , for all λ > 0, log E e λ(Mn,0-EMn,0) ≤

v n λ 2 2(1 -λ/n) .
For all s ≥ 0, n ≥ n 0 ,

P M n,0 ≥ EM n,0 + √ 2v n s + s n ≤ e -s .
The same results hold for M 0 (t).

Too slow variation

We conclude this section by motivating why it is crucial to have a heavy-enough tail in order to obtain meaningful concentration. For example, even under regular variation when α = 0, but ν is not in a de Haan class Π a with a(n) → ∞, the behavior of the occupancy counts and their moments may be quite irregular.

In this section, we collect some observations on those light-tailed distributions.

We start with the geometric distribution which represents in many respects a borderline case. The geometric case is an example of slow variation: ν(1/•) ∈ RV 0 . Indeed, with p k = (1 -q) k-1 q, 0 < q < 1, we have

ν(x) = +∞ k=1 I {p k ≥x} = |k ∈ N * , (1 -q) k-1 q ≥ x| = 1 + log(x/q) log(1 -q) ,
and thus ν(x) ∼ x→0

(1/x), with slowly varying.

In this case, Var(K(n)) = EK(2n) -EK(n) → log(2) log(1/1-q) . Proposition 4.7. When the sampling distribution is geometric with parameter q ∈ (0, 1), letting M n = max(X 1 , . . . , X n ),

EM n ≥ EK n ≥ EM n - 1 -q q 2 .
imsart-generic ver. 2014/07/30 file: main-arxiv.tex date: December 30, 2014

In the case of geometric frequencies, the missing mass can fluctuate widely with respect to its expectation, and one cannot expect to obtain sub-gamma concentration with both the correct variance proxy and scale factor 1/n. Indeed, intuitively, the symbol which primarily contributes to the missing mass' fluctuations, is the quantile of order 1 -1/n. With F (k) = k j=1 p j , and F ← the generalized inverse of F ,

j * = F ← (1 -1/n) = inf{j ≥ 1, F (j) ≥ 1 -1/n} = inf{j ≥ 1, k>j p k ≤ 1/n} .
Omitting the slowly varying functions, when ν(1/•) ∈ RV α , 0 < α < 1, j * is of order n α 1-α and p j * is of order n -1 1-α . The closer to 1 is α, the smaller the probability of j * . When α goes to 0, this probability becomes 1/n. With geometric frequencies, j * is log(n) log(1/1-q) and p j * is q n(1-q) . Hence, around the quantile of order 1 -1/n, there are symbols which may contribute significantly to the missing mass' fluctuations.

Another interesting case consists of distributions which are very light-tailed, in the sense that p k+1 p k → 0 when k → ∞. An example of these is the Poisson distribution P(λ), for which p k = 0, then there exists a sequence of integers (u n ) n∈N such that

p k+1 p k = λ k -→ k→+∞ 0 .
lim n→∞ P M n,0 ∈ {F (u n ), F (u n + 1)} = 1 ,
where F (k) = j>k p j .

Applications

Estimating the regular variation index

When working in the regular variation setting, the most basic estimation task is to estimate the regular variation index α. We already mentioned in Section 2 the fact that, when ν ∈ rv α , α ∈ (0, 1), the ratio K n,1 /K n provides a consistent estimate of α. This is actually only one among a family of estimators of α that one may construct. The next result shows this, and is a direct consequence of Proposition 4.4. Proposition 5.1. If ν ∈ rv α , α ∈]0, 1], then for all r ≥ 1 rK n,r K n,r is a strongly consistent estimator of α.

imsart-generic ver. 2014/07/30 file: main-arxiv.tex date: December 30, 2014 Thus, writing k n = max {r, K n,r > 0}, at time n, we can have up to k n nontrivial estimators of α.

Estimating the missing mass

The Good-Turing estimation problem [START_REF] Good | The population frequencies of species and the estimation of population parameters[END_REF] is that of estimating M n,r from the observation (X 1 , X 2 , • • • , X n ). For large scores r, designing estimators for M n,r is straightforward, we assume that the empirical distribution mimics the sampling distribution, and that the empirical probabilities rKn,r n are likely to be good estimators. The question is more delicate for rare events. In particular, for r = 0, it may be a bad idea to assume that there is no missing mass M n,0 = 0, that is to assign a zero probability to the symbols that do not appear in the sample. Various "smoothing" techniques were developed, in order to adjust the maximum likelihood estimator and obtain more accurate probabilities.

Good-Turing estimators attempt to estimate (M n,r ) r from (K n,r ) r for all r. They are defined as

G n,r = (r + 1)K n,r+1 n •
The rationale for this choice comes from the following observations.

EG n,0 = E [K n,1 ] n = EM n-1,0 = EM n,0 + EM n,1 n , (5.1)
and

EG n,r = (r + 1)EK n,r+1 n = EM n-1,r .
(5.2)

In the Poisson setting, there is no bias: EG r (t) = (r + 1) EKr+1(t) t = EM r (t). Here, we primarily focus on the estimation of the missing masses M n,0 and M 0 (t), though most of the methodology extends also to r > 0, with the appropriate concentration results. From (5.1) and (5.2), Good-Turing estimators look like slightly biased estimators of the relevant masses. In particular, the bias EG n,0 -EM n,0 is always positive but smaller than 1/n. It is however far from obvious to determine scenarios where these estimators are consistent and where meaningful confidence regions can be constructed.

When trying to estimate the missing mass M n,0 or EM n,0 , consistency needs to be redefined since the estimand is not a fixed parameter of interest but a random quantity whose expectation further depends on n. Additive consistency, that is bounds on M n,0 -M n,0 is not a satisfactory notion, because, as M n,0 tends to 0, the trivial constant estimator 0 would be universally asymptotically consistent. Relative consistency, that is control on ( M n,0 -M n,0 )/M n,0 looks like a much more reasonable notion. It is however much harder to establish.

In order to establish relative consistency of a missing mass estimator, we have to check that E[ M n,0 -M n,0 ] is not too large with respect to EM n,0 , and that both M n,0 and M n,0 are concentrated around their mean values.

As shown in [START_REF] Ohannessian | Rare probability estimation under regularly varying heavy tails. In colt 2012[END_REF], the Good-Turing estimator of the missing mass is not universally consistent in this sense. This occurs principally in very light tails, such as those described in Section 4.3.1.

imsart-generic ver. 2014/07/30 file: main-arxiv.tex date: December 30, 2014 Proposition 5.2. [START_REF] Ohannessian | Rare probability estimation under regularly varying heavy tails. In colt 2012[END_REF] When the sampling distribution is geometric with small enough q ∈ (0, 1), there exists η > 0, and a subsequence n i such that for i large enough, G ni,0 /M ni,0 = 0 with probability no less than η.

On the other hand, the concentration result of Corollary 4.1 entails a law of large numbers for M n,0 (by a direct application of the Borel-Cantelli lemma), which in turns entails the strong multiplicative consistency of the Good-Turing estimate.

Corollary 5.3. We have the following two regimes of consistency for the Good-Turing estimator of the missing mass.

(i) If the counting function ν is such that EK n,2 /EK n,1 remains bounded and EK n,1 → +∞ (in particular, when ν is regularly varying with index α ∈ (0, 1] or α = 0 and ν ∈ Π a with a → ∞),

M n,0

EM n,0

P -→ 1 ,
and the Good-Turing estimator of M n,0 defined by G n,0 = K n,1 /n, is multiplicatively consistent in probability:

G n,0 M n,0 P -→ 1 .
(ii) If furthermore EK n,2 /EK n,1 remains bounded and if, for all c > 0, ∞ n=0 exp(-cEK n,1 ) < ∞ (in particular, when ν is regularly varying with index α ∈ (0, 1]), then these two convergences occur almost surely.

Consistency is a desirable property, but the concentration inequalities provide us with more power, in particular in terms of giving confidence intervals that are asymptotically tight. For brevity, we focus here on the Poisson setting to derive concentration inequalities which in turn yield confidence intervals. A similar, but somewhat more tedious, methodology yields confidence intervals in the binomial setting as well.

Concentration inequalities for

G 0 (t) -M 0 (t)
In the Poisson setting, the analysis of the Good-Turing estimator is illuminating. As noted in earlier, the first pleasant observation is that the Good-Turing estimator is an unbiased estimator of the missing mass. Second, the variance of G 0 (t) -M 0 (t) is simply related to occupancy counts:

Var(G 0 (t) -M 0 (t)) = 1 t 2 (EK 1 (t) + 2EK 2 (t)) .
(5.3) Third, simple yet often tight concentration inequalities can be obtained for G 0 (t) -M 0 (t).

imsart-generic ver. 2014/07/30 file: main-arxiv.tex date: December 30, 2014

Proposition 5.4. The random variable G 0 (t) -M 0 (t) is sub-gamma on the right tail with variance factor Var(G 0 (t)-M 0 (t)) and scale factor 1/t, and sub-gamma on the left tail with variance factor 3EK(t)/t 2 and scale factor 1/t. For all λ ≥ 0, (i) log Ee λ(G0(t)-M0(t)) ≤ Var(G 0 (t) -M 0 (t))t 2 φ λ t , and (ii) log Ee λ(M0(t)-G0(t)) ≤ 3EK(t) 2t 2 λ 2 1-λ/t . We are now in a position to build confidence intervals for the missing mass.

Proposition 5.5. With probability larger than 1 -4δ, the following hold

M 0 (t) ≤ G 0 (t) + 1 t 6K(t) log 1 δ + 5 log 1 δ . M 0 (t) ≥ G 0 (t) - 1 t 2(K 1 (t) + 2K 2 (t)) log 1 δ + 4 log 1 δ .
To see that these confidence bounds are asymptotically tight, consider the following central limit theorem. A similar results can be paralleled in the binomial setting.

Proposition 5.6. If the counting function ν is regularly varying with index α ∈ (0, 1], the following central limit theorem holds for the ratio G 0 (t)/M 0 (t):

EK 1 (t) EK 1 (t) + 2EK 2 (t) G 0 (t) M 0 (t)
-1 N (0, 1) .

Remark 5.1. Note that when α = 1, this convergence occurs faster: the speed is of order n 1 (n) instead of n α (n).

Estimating the number of species

Fisher's number of species problem [START_REF] Fisher | The relation between the number of species and the number of individuals in a random sample of an animal population[END_REF] consists of estimating K (1+τ )n -K n for τ > 0, the number of distinct new species one would observe if the data collection runs for an additional fraction τ of time. This was posed primarily within the Poisson model in the original paper [START_REF] Fisher | The relation between the number of species and the number of individuals in a random sample of an animal population[END_REF] and later by [START_REF] Efron | Estimating the number of unseen species: How many words did Shakespeare know?[END_REF], but the same question may also be asked in the binomial model. The following estimates come from straightforward computations on the asymptotics given in Theorems 4.2, 4.3 and 4.5.

Proposition 5.7. If the counting function ν is regularly varying with index α ∈ (0, 1], letting α be any of the estimates rK n,r /K n,r of α from Proposition 5.1, then any of the following quantities

(τ α -1)K n , τ α -1 α K n,1 , and r k=2 k k -1 -α τ α -1 α K n,r , r ≥ 2 ,
imsart-generic ver. 2014/07/30 file: main-arxiv.tex date: December 30, 2014 is a strongly consistent estimate of K τ n -K n , the number of newly discovered species when the sample size is multiplied by τ . If the counting function ν is in Π a , with a(n) → +∞, then, for each r ≥ 1, log(τ )rK n,r is an estimate of K τ n -K n , consistent in probability.

Discussion

To conclude the paper, we review our results in a larger context, and propose some connections, extensions, and open problems.

The cost of Poissonization and negative correlation

Resorting to Poissonization or negative correlation may have a price. It may lead to variance overestimates. [Gnedin et al., 2007, Lemma 1] asserts that for some constant c

|Var(K(n)) -Var(K n )| ≤ c n max 1, EK 1 (n) 2
This bound conveys a mixed message. As EK 1 (n)/n tends to 0, it asserts that

|Var(K(n)) -Var(K n )| /EK 1 (n)
tends to 0. But there exist scenarios where EK 1 (n) 2 /n tends to infinity. It is shown in [START_REF] Gnedin | Notes on the occupancy problem with infinitely many boxes: general asymptotics and power laws[END_REF] that EK 1 (n) 2 /(nVar(K(n))) tends to 0, so that, as soon as nVar(K(n)) tends to infinity (which might not always be the case), the two variances Var(K n ) and Var(K(n)) are asymptotically equivalent.

It would be interesting to find the necessary and sufficient conditions under which there is equivalence. Though these aren't generally known, it is instructive to compare Var(K(n)), Var(K n ) and Var ind (K n ) the variance upper bound obtained from negative correlation by bounding their differences. For instance, one can show that for any sampling distribution we have:

EK 2 (2n) n ≤ Var(K(n)) -Var ind (K n ) ≤ 2EK 2 (n) n , and
0 ≤ Var ind (K n ) -Var(K n ) ≤ (EK n,1 ) 2 n - EK 2n,2 2n -1 .
These bounds are insightful but, without any further assumptions on the sampling distribution, they are not sufficient to prove asymptotic equivalence.

imsart-generic ver. 2014/07/30 file: main-arxiv.tex date: December 30, 2014

Extensions of regular variation

The regular variation hypothesis is an elegant framework, allowing one to derive, thanks to Karamata and Tauberian Theorems, simple and comprehensible equivalents for various moments. As we have seen, it comes very close to being a necessary condition for exponential concentration. It may however seem too stringent. Without getting too specific about it, let us mention that other less demanding hypotheses also yield the asymptotic relative orders that work in favor of the concentration of the missing mass. For instance, referring back to Remark 4.1, one could ask instead that:

0 < lim inf t→∞ Φ 2 (t) Φ 2 (t) ≤ lim sup t→∞ Φ 2 (t) Φ 2 (t) < ∞ . Recalling that Φ 2 (t) = 2Φ2(t) t
, and applying Corollary 2.6.2. of [START_REF] Bingham | Regular variation[END_REF], one obtains that Φ 2 is in the class OR of O-regularly varying functions and Φ 2 is in the class ER of extended regularly varying functions, that is, for

all λ ≥ 1 0 < lim inf t→∞ Φ 2 (λt) Φ 2 (t) ≤ lim sup t→∞ Φ 2 (λt) Φ 2 (t) < ∞ , and
λ d ≤ lim inf t→∞ Φ 2 (λt) Φ 2 (t) ≤ lim sup t→∞ Φ 2 (λt) Φ 2 (t) ≤ λ c ,
for some constants c and d. Observe that this result, which is the equivalent of Karamata's Theorem, differs from the regular variation setting, in the sense that the control on the derivative Φ 2 is looser than the one on Φ 2 , whereas, in Karamata Theorem, both the function and its derivative inherit the regular variation property. We can in turn show that Φ(t) = EK(t) is in the class OR and, by Theorem 2.10.2 of [START_REF] Bingham | Regular variation[END_REF], this is equivalent to ν(1/•) ∈ OR, as Φ is the Laplace-Stieltjes transform of ν.

Random measures

As noted by [START_REF] Gnedin | Notes on the occupancy problem with infinitely many boxes: general asymptotics and power laws[END_REF], the asymptotics for the moments of the occupancy counts in the regular variation setting is still valid when the frequencies (p j ) j≥1 are random, in which case the measure ν is defined by

E   ∞ j=1 f (p j )   = 1 0 f (x)ν(dx) ,
for all functions f ≥ 0. We can also define the measure ν 1 by

E   ∞ j=1 p j f (p j )   = 1 0 f (x)ν 1 (dx) ,
imsart-generic ver. 2014/07/30 file: main-arxiv.tex date: December 30, 2014 for all functions f ≥ 0. This measure corresponds to the distribution of the frequency of the first discovered symbol.

For instance, when (p j ) j≥1 are Poisson-Dirichlet(α,0) with 0 < α < 1, the measure ν 1 (dx) is the size-biased distribution of PD(α, 0), that is Beta B(1α, α) [see [START_REF] Pitman | The two-parameter Poisson-Dirichlet distribution derived from a stable subordinator[END_REF]]. Thus we have:

ν 1 [0, x] = 1 B(1 -α, α) x 0 t -α (1 -t) α-1 dt ∼ x→0 x 1-α (1 -α)B(1 -α, α)
and, by [Proposition 13 [START_REF] Gnedin | Notes on the occupancy problem with infinitely many boxes: general asymptotics and power laws[END_REF], this is equivalent to

ν(x) ∼ x→0 1 αB(1 -α, α) x -α .
Thus, denoting by N (x) the random number of frequencies p j which are larger than x, the expectation ν(x) = EN (x) is regularly varying. One can also show that the mass-partition mechanism of the distribution PD(α, 0) almost surely generates N (x) to be regularly varying. To see this,refer to [Proposition 10 Pitman and Yor, 1997] or to [Proposition 2.6 Bertoin, 2006] which assert that the limit L := lim n→∞ np α n exists almost surely. This is equivalent to

N (x) ∼ x→0 x -α L a.s. .
The PD(α, 0) distribution can be generated through a Poisson process with intensity measure ν([x, ∞]) = cx -α . Without entering into further detail, let us mention that similar almost sure results hold even when the intensity measure ν is not a strict power, but satisfies the property

ν([x, ∞]) ∼ x→0 x -α (x) ,
with slowly varying, [Section 6 [START_REF] Gnedin | Regeneration in random combinatorial structures[END_REF]. Working with a regular variation hypothesis thus gives us more flexibility than assuming specific Bayesian priors.

Proofs

Fundamental techniques

Efron-Stein-Steele inequalities

Our variance bounds mostly follow from the Efron-Stein-Steele Inequality [START_REF] Efron | The jackknife estimate of variance[END_REF], which states that when a random variable is expressed as a function of many independent random variables, its variance can be controlled by the sum of the local fluctuations.

imsart-generic ver. 2014/07/30 file: main-arxiv.tex date: December 30, 2014 Theorem 7.1. Let X be some set, (X 1 , X 2 , • • • , X n ) be independent random variables taking values in X , f : X n → R be a measurable function of n variables, and

Z = f (X 1 , X 2 , • • • , X n ). For all i ∈ {1, • • • , n}, let X (i) = (X 1 , • • • , X i-1 , X i+1 , • • • , X n ) and E (i) Z = E[Z|X (i) ]. Then, letting v = n i=1 E[(Z -E (i) Z) 2 ], Var[Z] ≤ v . If X 1 , • • • , X n are independent copies of X 1 , • • • , X n , then letting Z i = f (X 1 , • • • , X i-1 , X i , X i+1 , • • • , X n ), v = n i=1 E[(Z -Z i ) 2 + ] ≤ n i=1 E[(Z -Z i ) 2 ] ,
where the random variables Z i are arbitrary X (i) -measurable and square-integrable random variables.

Negative association

The random variables K n , K n,r , and M n,r are sums or weighted sums of Bernoulli random variables. These summands depends on the scores (X n,j ) j≥1 and therefore are not independent. Transforming the fixed-n binomial setting into a continuous time Poisson setting is one way to circumvent this problem. This is the Poissonization method. In this setting, the score variables (X j (n)) j≥1 are independent Poisson variables with respective means np j . Results valid for the Poisson setting can then be transferred to the fixed-n setting, up to approximation costs. For instance, [START_REF] Gnedin | Notes on the occupancy problem with infinitely many boxes: general asymptotics and power laws[END_REF] (Lemma 1) provide bounds on the discrepancy between expectations and variances in the two settings. (See also our discussion in Section 6.1).

Another approach to deal with the dependence is to invoke the notion of negative association, which provides a systematic comparison between moments of certain monotonic functions of the occupancy scores. In the bins and balls setting, this approach is mostly used to obtain bounds on the logarithmic moment generating function, and thus exponential concentration for the occupancy counts [see [START_REF] Dubhashi | Balls and bins: A study in negative dependence[END_REF][START_REF] Shao | A comparison theorem on moment inequalities between negatively associated and independent random variables[END_REF][START_REF] Mcallester | On the convergence rate of Good-Turing estimators[END_REF][START_REF] Ohannessian | Rare probability estimation under regularly varying heavy tails. In colt 2012[END_REF]. We use this notion throughout the proofs, and therefore present it here formally.

Definition 2 (negative association). Real-valued random variables Z 1 , . . . , Z K are said to be negatively associated if, for any two disjoint subsets A and B of {1, . . . , K}, and any two real-valued functions f : R |A| → R and g : R |B| → R that are both either coordinate-wise non-increasing or coordinate-wise nondecreasing, we have:

E [f (Z A ).g(Z B )] ≤ E [f (Z A )] .E [g(Z B )] .
imsart-generic ver. 2014/07/30 file: main-arxiv.tex date: December 30, 2014

In particular, as far as concentration properties are concerned, sums of negatively associated variables can only do better than sums of independent variables.

Theorem 7.2. [START_REF] Dubhashi | Balls and bins: A study in negative dependence[END_REF]] For each n ∈ N, the occupancy scores (X n,j ) j≥1 are negatively associated.

As any monotonic functions of negatively associated variables are also negatively associated, the variables (I {Xn,j >0} ) j≥1 (respectively (I {Xn,j =0} ) j≥1 ) are negatively associated as increasing (respectively decreasing) functions of (X n,j ) j≥1 . This is of pivotal importance for our proofs of concentration results for K n and M n,0 . For r ≥ 1, the variables (I {Xn,j =r} ) j≥1 appearing in K n,r are not negatively associated. However, following [START_REF] Ohannessian | Rare probability estimation under regularly varying heavy tails. In colt 2012[END_REF], one way to deal with this problem is to observe that

K n,r = K n,r -K n,r+1 ,
recalling that K n,r = ∞ j=1 I {Xn,j ≥r} is the number of urns that contain at least r balls and that the Bernoulli variables appearing in K n,r are negatively associated.

Potter's inequalities and its variants

One useful result from regular variation theory is provided by Potter's inequality [See Bingham et al., 1989, de Haan and[START_REF] De Haan | Extreme value theory[END_REF], for proofs and refinements].

Theorem 7.3. (Potter-Drees inequalities.) (i) If f ∈ rv γ , then for all δ > 0, there exists t 0 = t 0 (δ), such that for all t, x : min(t, tx) > t 0 ,

(1 -δ)x γ min x δ , x -δ ≤ f (tx) f (t) ≤ (1 + δ)x γ max x δ , x -δ
(ii) If ∈ Π a , then for all δ 1 , δ 2 , there exists t 0 such that for all t ≥ t 0 , for all x ≥ 1, This entails

(1 -δ 2 ) 1 -x δ1 δ 1 -δ 2 < (tx) -(t) a(t) < (1 + δ 2 ) x δ1 -1 δ 1 + δ 2 . 7.2.
Var(K(t)) = ∞ j=1 e -tpj (1 -e -tpj ) = EK(2t) -EK(t) = 2t t EM 0 (s)ds . Now, as EM 0 (s) is non-increasing, EK 1 (2t) 2 = tEM 0 (2t) ≤ Var(K(t)) ≤ tEM 0 (t) = EK 1 (t) .
Moving on to the binomial setting, let K i n denote the number of occupied urns when the i th ball is replaced by an independent copy. Then

Var(K n ) ≤ E n i=1 (K n -K i n ) 2 + ,
where (K n -K i n ) + denotes the positive part. Now, K n -K i n is positive if and only if ball i is moved from a singleton into in a non-empty urn. Thus Var(

K n ) ≤ E [K n,1 (1 -M n,0 )].
Proof of Proposition 3.2. The bound rEK n,r follows from the Efron-Stein inequality: denoting by K (i) n,r the number of cells with occupancy score larger than r when ball i is removed, then

K n,r -K (i) n,r = 1 if ball i is in a r-ton 0 otherwise.
And thus, we get

n i=1 (K n,r -K (i) n,r ) 2 = rK n,r .
The second bound follows from the negative association of the variables (I {Xn,j ≥r} ) j (negative correlation is actually sufficient):

Var   ∞ j=1 I {Xn,j ≥r}   ≤ ∞ j=1
Var(I {Xn,j ≥r} ) ≤ EK n,r .

Concentration inequalities for occupancy counts

Proof of Proposition 3.4. Let X n,j denote the occupancy score of cell j, j ∈ N, then

K n,r = ∞ j=1 I {Xn,j ≥r} .
imsart-generic ver. 2014/07/30 file: main-arxiv.tex date: December 30, 2014

As observed in [START_REF] Ohannessian | Rare probability estimation under regularly varying heavy tails. In colt 2012[END_REF], K n,r is a sum of negatively associated Bernoulli random variables. Moreover, the Efron-Stein inequality implies that for each j ∈ N, Var(I {Xn,j ≥r} ) ≤ rEI {Xn,j =r} .

Thus we have log Ee λ(Kn,r-EKn,r) ≤ ∞ j=1 log Ee λ(I {X n,j ≥r} -EI {X n,j ≥r} )

≤ ∞ j=1
Var(I {Xn,j ≥r} )φ(λ)

≤ φ(λ) ∞ j=1 rEI {Xn,j =r} = φ(λ)rEK n,r ,
where the first inequality comes from negative association, the second inequality is Bennett's inequality for Bernoulli random variables, and the last inequality comes from the Efron-Stein inequality. The other bound comes from the fact that Var(I {Xn,j ≥r} ) ≤ EI {Xn,j ≥r} .

Proof of Proposition 3.5.

As K n,r = K n,r -K n,r+1 , {K n,r ≥ EK n,r + x} ⊆ K n,r ≥ EK n,r + x 2 ∪ K n,r+1 ≤ EK n,r+1 - x 2 .
By Proposition 3.4, Bernstein inequalities hold for both K n,r and K n,r+1 , with variance proxies ErK n,r (or EK n,r ) and (r + 1)K n,r+1 (or EK n,r+1 ≤ EK n,r ) respectively. Hence,

P {K n,r ≥ EK n,r + x} ≤ exp - x 2 /4 2(rEK n,r + x/6) + exp - x 2 /4 2((r + 1)EK n,r+1 ) ≤ 2 exp - x 2 /4 2((rEK n,r ) ∨ ((r + 1)K n,r+1 ) + x/6) .
The same reasoning works for the alternative variance proxies and for the left tails.

(t)) = ∞ j=1 p 2 j e -tpj 1 -e -tpj ≤ ∞ j=1 p 2 j e -tpj = 2 t 2 EK 2 (t) .
imsart-generic ver. 2014/07/30 file: main-arxiv.tex date: December 30, 2014

In the binomial setting, by negative correlation,

Var(M n,0 ) ≤ ∞ j=1 p 2 j (1 -(1 -p j ) n ) (1 -p j ) n ≤ ∞ j=1 p 2 j e -npj = 2 n 2 EK 2 (n) .

Concentration inequalities for the missing mass

Proof of Proposition 3.7. For all λ ∈ R,

log E e λ(Mn,0-EMn,0) = log E e λ ∞ j=1 pj (Yj -EYj ) ≤ ∞ j=1 log E e λpj (Yj -E[Yj ]) ≤ ∞ j=1 (1 -p j ) n (1 -(1 -p j ) n )φ(λp j ) ,
where the first inequality comes from negative association, and the second is Bennett's inequality for Bernoulli random variables.

Noting that lim λ→0-φ(λ)/λ 2 = lim λ→0+ φ(λ)/λ 2 = 1/2, the function λ → φ(λ)/λ 2 has a continuous increasing extension on R. Hence, for λ ≤ 0, we have φ(λ) ≤ λ 2 /2.

Thus, for λ < 0, log E e λ(Mn,0-EMn,0)

≤ ∞ j=1 p 2 j (1 -p j ) n (1 -(1 -p j ) n ) λ 2 2 = ∞ j=1 p 2 j Var[Y j ] λ 2 2 . Recall that ∞ j=1 p 2 j Var[Y j ] ≤ 2EK 2 (n)/n 2 (Proposition 3.6
). Proof of Theorem 3.8. From the beginning of the proof of Proposition 3.7, that is, thanks to negative association and to the fact that each Bernoulli random variable satisfies a Bennett inequality, log E e λ(Mn,0-EMn,0) ≤ ∞ j=1 e -npj φ(λp j ) . Now, using the power series expansion of φ,

∞ j=1 e -npj φ(λp j ) = ∞ j=1 e -npj ∞ r=2 (λp j ) r r! = ∞ r=2 λ n r ∞ j=1 e -npj (np j ) r r! .
imsart-generic ver. 2014/07/30 file: main-arxiv.tex date: December 30, 2014

We recognize that for each r,

∞ j=1 e -npj (npj ) r r! = EK r (n) and that for each r ≥ 2, EK r (n) ≤ EK 2 (n), ∞ j=1 e -npj φ(λp j ) = ∞ r=2 λ n r EK r (n) ≤ EK 2 (n) ∞ r=2 λ n r = λ 2 EK 2 (n)/n 2 1 -λ/n ,
which concludes the proof.

Regular variation

Proof of Proposition 4.4. By monotonicity of K n,r , we have the following strong law for any sampling distribution [START_REF] Gnedin | Notes on the occupancy problem with infinitely many boxes: general asymptotics and power laws[END_REF], the discussion after Proposition 2]. Recall that X j (n) ∼ P(np j ) and that, if

K n,r = ∞ s=r K n,s ∼ +∞ ∞ s=r EK s (n) a.s. , [see
Y ∼ P(λ), then P [Y ≤ k] = Γ(k+1,λ) k!
, where Γ(z, x) = +∞ x e -t t z-1 dt is the incomplete Gamma function. Hence

∞ s=r EK s (n) = ∞ j=1 P [X j (n) ≥ r] = ∞ j=1 1 (r -1)! npj 0 e -t t r-1 dt = 1 (r -1)! 1 0 nx 0 e -t t r-1 dt • ν(dx) = 1 (r -1)! 1 0 ne -nx (nx) r-1 ν(x)dx = 1 (r -1)! +∞ 0 e -z z r-1 ν(z/n)dz ∼ +∞ ν(1/n) (r -1)! Γ(r -α) .
In particular, Proof of Theorem 4.6. Recall the beginning of the proof of Theorem 3.8:

K n,
log E e λ(Mn,0-EMn,0) ≤

∞ r=2 λ n r EK r (n).
Now, bounding each EK r (n) by EK 2 (n) is not sufficient to get the right order for the variance: EK 2 (n) is of order (n) whereas VarM n,0 is of order a(n)/n 2 .

We explore more carefully the structure of EK r (n) and show that these quantities are uniformly (in r) bounded by a function of order a(n) for large enough n, that is, that there exists n * ∈ N and C ∈ R + such that for all n ≥ n * , for all r ≥ 1, EK r (n) ≤ Ca(n).

Before going into the proof, we observe that for r ≥ n/a(n), the result is true. Indeed, from the identity ∞ r=1 rEK r (n) = n, we deduce that rEK r (n) ≤ n, so that for r ≥ n/a(n), EK r (n) ≤ a(n). Thus we assume that r ≤ n/a(n).

First, we easily deal with the contribution to EK r (n) of the symbols with probability less than 1/n. Indeed

I r 1 := 1/n 0 e -nx (nx) r r! ν(dx) ≤ 1/n 0 e -nx (nx) 2 2! ν(dx) ≤ EK 2 (n) .
As EK 2 (n) ∼ a(n)/2, for all δ 0 , there exists n 0 such that for all n ≥ n 0 , for all r ≥ 1, I r 1 ≤ (1 + δ 0 )/2. For the the contribution of the symbols with probability larger than 1/n, integration by part and change of variable yield:

I r 2 := 1 1/n e -nx (nx) r r! ν(dx) = e -nx (nx) r r! (-ν(x)) 1 1/n + 1 1/n e -nx n r r! (rx r-1 -nx r ) ν(x)dx = ν(1/n)e -1 r! + ∞ 1 e -z z r-1 (r -1)! - z r r! ν(z/n)dz .
As ∞ 1 e -z z r-1 (r-1)! -z r r! dz = -P[P(1) = r] = -e -1 /r!, we can rearrange the previous expression:

I r 2 = a(n) ∞ 1 e -z z r-1 (r -1)! - z r r! ν(z/n) -ν(1/n) a(n) dz .
Notice that when z ∈ [1, r], the integrand is negative, so we simply ignore this part of the integral and restrict ourselves to

I r 3 := ∞ r e -z z r r! - z r-1 (r -1)! ν(1/n) -ν(z/n) a(n) dz ,
which we try to bound by a constant term for n greater than some integer that does not depend on r.

imsart-generic ver. 2014/07/30 file: main-arxiv.tex date: December 30, 2014

The main ingredient of our proof is the next version of the Potter-Drees Inequality (see Theorem 7.3 in Section 7. 1.3 and [de Haan and Ferreira, 2006, point 4 of Corollary B.2.15]): for ∈ Π a , for arbitrary δ 1 , δ 2 , there exists t 0 such that for all t ≥ t 0 , and for all x ≤ 1 with tx ≥ t 0 ,

(1 -δ 2 ) 1 -x -δ1 δ 1 -δ 2 < (t) -(tx) a(t) < (1 + δ 2 ) x -δ1 -1 δ 1 + δ 2 .
Thus, for arbitrary δ 1 , δ 2 , there exists n 1 such that, for all n ≥ n 1 , for all

z ∈ [1, n/n 1 ], ν(1/n) -ν(z/n) a(n) ≤ (1 + δ 2 ) z δ1 -1 δ 1 + δ 2 .
As r ≤ n/a(n), taking, if necessary, n large enough so that a(n) ≥ n 1 , we have r ≤ n/n 1 and

I r 3 ≤ n/n1 r e -z z r r! - z r-1 (r -1)! (1 + δ 2 ) z δ1 -1 δ 1 + δ 2 dz + ∞ n/n1 e -z z r r! - z r-1 (r -1)! ν(1/n) -ν(z/n) a(n) dz =: I r 4 + I r 5 , with I r 4 ≤ δ 2 + 1 + δ 2 δ 1 ∞ r e -z z r+δ1 r! - z r r! + z r-1 (r -1)! - z r-1+δ1 (r -1)! dz ≤ δ 2 + 1 + δ 2 δ 1 ∞ r
e -z z r+δ1 r! -z r-1+δ1 (r -1)! dz = δ 2 + 1 + δ 2 δ 1 Γ(r + 1 + δ 1 , r) Γ(r + 1) -Γ(r + δ 1 , r) Γ(r) ,

where Γ(a, x) = ∞ x e -t t a-1 dt is the incomplete Gamma function. Using the fact that Γ(a, x) = (a -1)Γ(a -1, x) + x a-1 e -x , we have I r 4 ≤ δ 2 + 1 + δ 2 δ 1 Γ(r + 1) Γ(r + 1 + δ 1 , r) -(r + δ 1 )Γ(r + δ 1 , r) + δ 1 Γ(r + δ 1 , r)

= δ 2 + 1 + δ 2 δ 1
r r+δ1 e -r r! + δ 1 Γ(r + δ 1 , r) Γ(r + 1) .

By Stirling's inequality, for all r, r r+δ1 e -r r! ≤ r δ1 (2πr) -1/2 . Thus, taking s δ 1 = 1/4, the right-hand term is uniformly bounded by 1. And e -z z r r! -z r-1 (r -1)! dz = ν(1/n) a(n) e -n/n1 (n/n 1 ) r r! ≤ ν(1/n) a(n) e -n/n1 (n/n 1 ) n/n1 n/n 1 ! .

By Stirling's inequality, this bound is smaller than ν(1/n) a(n) (2π(n/n 1 )) -1/2 , which tends to 0 as n → ∞. Thus there exists n 2 such that for all n ≥ n 2 , and all r ≤ n/n 1 , I r 5 ≤ δ 2 . In the end, we get that for all δ 0 ≥ 0, δ 1 with 0 ≤ δ 1 ≤ 1/4, and δ 2 ≥ 0, there exists n * = max(n 0 , n 1 , n 2 ) such that for all n ≥ n * , for all r ≥ 1,

EK r (n) ≤ a(n) 1 + δ 0 2 + δ 2 + 1 + δ 2 δ 1 (1 + δ 1 ) + δ 2 .
Taking for instance δ 1 = 1/4 and δ 0 = δ 2 = 1/15, we have that for large enough n and for all r ≥ 1, EK r (n) ≤ 6a(n) , and log E e λ(Mn,0-EMn,0) ≤ 12a(n)

n 2 • λ 2 2(1 -λ/n) .
Proof of Proposition 4.8. Under the condition of the Proposition 4.8, from [START_REF] Grübel | Gaps in discrete random samples[END_REF], with probability tending to 1, the sample is gap-free, hence the missing mass is F (max(X 1 , . . . , X n )).

The condition of the Proposition implies the condition described in [START_REF] Anderson | Extreme value theory for a class of discrete distributions with applications to some stochastic processes[END_REF], i.e. lim n→+∞ F (n+1) F (n) = 0, to ensure the existence of a sequence of integers (u n ) n∈N such that lim n→∞ P {max(X 1 , . . . , X n ) ∈ {u n , u n + 1}} = 1 .

Applications

Proof of Corollary 5.3. Let us assume that EK n,1 → ∞. Using the fact that 0 ≤ EG n,0 -EM n,0 ≤ 1/n, we notice that as soon as EK n,1 → ∞, EG n,0 ∼ +∞ EM n,0 . Now by Chebyshev Inequality,

P

M n,0

EM n,0 If EK n,2 /EK n,1 remains bounded, this becomes smaller than c 1 exp -c 2 2 EK n,1 . Hence, if exp(-cEK n,1 ) is summable for all c > 0, we can apply the Borel-Cantelli lemma and obtain the almost sure convergence of M n,0 /EM n,0 to 1. Moreover, by Proposition 3.5,

-1 > ≤ Var(M n,0 ) 2 (EM n,0 ) 2 ≤ 2EK 2 (n) 2 n 2 (EM
P K n,1 EK n,1 -1 > ≤ 4 exp - 2 (EK n,1 ) 2
2(4(EK n,1 ∨ 2EK n,2 ) + 2/3) , which shows that under these assumptions K n,1 /EK n,1 also tends to 1 almost surely.

Proof of Proposition 5.4. The random variable G 0 (t) -M 0 (t) is a sum of independent, centered and bounded random variables, namely

G 0 (t) -M 0 (t) = 1 t ∞ j=1
I Xj (t)=1 -tp j I Xj (t)=0 .

Bound (i) follows immediately from the observation that each I Xj (t)=1tp j I Xj (t)=0 satisfies a Bennett inequality, log Ee λ(G0(t)-M0(t)) ≤ ∞ j=1 Var(I Xj (t)=1 -tp j I Xj (t)=0 )φ λ t

= Var(G 0 (t) -M 0 (t))t 2 φ λ t .

Bound (ii) follows from the observation that each I Xj (t)=0 - We may now invoke concentration inequalities for K 1 (t) + 2K 2 (t) and K(t).

Indeed, with probability greater than 1 -δ, K(t) ≥ EK(t) -2EK(t) log 1 δ which entails EK(t) ≤ K(t) + log 1 δ 2 + log 1 δ 2 . We have 2K 2 (t) + K 1 (t) ≥ 2EK 2 (t) + EK 1 (t) -4(2EK 2 (t) + EK 1 (t)) log 1 δ with probability greater than 1 -δ, which entails 2EK 2 (t) + EK 1 (t) ≤ (2K 2 (t) + K 1 (t)) + log 1 δ + log 1 δ , which concludes the proof.

Proof of Proposition 5.6. The covariance matrix Cov(t) of (G 0 (t), M 0 (t)) can be written in terms of the expected occupancy counts as

Cov(t) = 1 t 2 EK 1 (t) 0 0 2EK 2 (t) - EK 2 (2t) 2t 2
1 1 1 1 .

From [START_REF] Karlin | Central limit theorems for certain infinite urn schemes[END_REF], we have Cov(t) -1/2 G 0 (t) -EG 0 (t) M 0 (t) -EM 0 (t) N (0, I 2 ) , imsart-generic ver. 2014/07/30 file: main-arxiv.tex date: December 30, 2014

where I 2 is the identity matrix, which can be rewritten as Σ(t) -1/2 G0(t)

EG0(t) -1 M O (t) EM0(t) -1 N (0, I 2 ) ,
with Σ(t) = (EG 0 (t)) -2 Cov(t).

The delta method applied to the function (x 1 , x 2 ) → x 1 /x 2 yields

(1 -1)Σ(t) 1 -1

-1/2
G 0 (t) M 0 (t) -1 N (0, 1) ,

and

(1 -1)Σ(t) 1 -1

-1/2 = EK 1 (t)
EK 1 (t) + 2EK 2 (t)

, which concludes the proof.

Remark 7.1. The proof for the binomial setting is very similar, the only difficulty being that EG n,0 and EM n,0 are no longer equal. However, the bias becomes negligible with respect to the fluctuations, that is, for v n = n α (n) or n 1 (n)

v n EG n,0 EM n,0 -1 → n→∞ 0 .

  Definition 1. A measurable function : R + → R + has the extended slow variation property, if there exists a non-negative measurable function a : R + →

imsart-generic ver. 2014/07/30 file: main-arxiv.tex date: December 30, 2014

  r ∼

	+∞	rK n,r α	a.s. .

imsart-generic ver. 2014/07/30 file: main-arxiv.tex date: December 30, 2014

  n,0 ) 2 ∼ 2(EK n,2 + o(1)) 2 (EK n,1 ) 2 , imsart-generic ver. 2014/07/30 file: main-arxiv.tex date: December 30, 2014where we used that|EK 2 (n) -EK n,2 | → 0 [see Lemma 1[START_REF] Gnedin | Notes on the occupancy problem with infinitely many boxes: general asymptotics and power laws[END_REF].On the other hand,EK n,1 + 2EK n,2 2 (EK n,1 ) 2 ,showing that if, furthermore, EK n,2 /EK n,1 remains bounded, the ratios M n,0 /EM n,0 , G n,0 /EG n,0 and thus M n,0 /G n,0 converge to 1 in probability. To get almost sure convergence, we use Theorem 3.8 to get that whenEK n,1 → ∞, (n)/n 2 + EM n,0 /n) = 2 exp -2 (EK n,1 + o(EK n,1 )) 22(2EK n,2 + EK n,1 + o(EK n,1 )) .

		P	K n,1 EK n,1	-1 >	≤	Var(K n,1 ) 2 (EK n,1 ) 2 ≤
	P	M n,0 EM n,0	-1 >	≤ 2 exp -	2(2EK 2	2 (EM n,0 ) 2

  1 tpj I Xj (t)=1 satimsart-generic ver. 2014/07/30 file: main-arxiv.tex date: December 30, 2014

	isfies a Bennett inequality,
		log Ee λ(M0(t)-G0(t)) ≤	∞ j=1	Var I Xj (t)=0 -	1 tp j	I Xj (t)=1 φ (λp j )
		=	∞ j=1		1 +	1 tp j	e -tpj φ(λp j )
		=	r≥2		λ t		r ∞ j=1	1 +	1 tp j	e -tpj (tp j ) r r!
		=	r≥2		λ t		r	EK r (t) +	1 r	EK r-1 (t)
		≤	r≥2		λ t		r 3EK(t) 2	,
	which concludes the proof.
	Proof of Proposition 5.5. With probability greater than 1 -2δ, by Proposition
	5.4,
		G 0 (t) -M 0 (t) ≤	1 t	2(EK 1 (t) + 2EK 2 (t)) log	1 δ	+	log 1 δ 3t
	and	G 0 (t) -M 0 (t)) ≥ -	1 t	6EK(t) log	1 δ	-	log 1 δ t	.

imsart-generic ver. 2014/07/30 file: main-arxiv.tex date: December 30, 2014

This is also referred to sometimes as rapid variation, as in[START_REF] Gnedin | Notes on the occupancy problem with infinitely many boxes: general asymptotics and power laws[END_REF], but we avoid that terminology as it also has a different connotation in the regular variation literature.imsart-generic ver.

2014/07/30 file: main-arxiv.tex date: December 30, 2014


Giacomo Rodeghiero

Ping-Ping Ding

Yu Zhong

Marc Lambert

Dominique Lesselier

Low-high inspection of composite multi-layers and MUSIC-type electromagnetic imaging

Non Destructive Testing-Evaluation (NdT-E) of complex multi-layer composite panels for problems of quality, viability, safety and availability of complex systems involving manufactured parts (in aeronautics and in automotive industry, as a good example) is becoming an interesting and challenging task nowadays.

From eddy-currents to microwaves, there is the need to make available modeling and imaging procedures

that will be robust, fast, accurate and useful to potential end-users: this requires a sound description of the panels. At a first level of modeling, these aforementioned panels can be considered as a succession of planar slabs which are laying one over the other; each slab is usually formed by a bundle of fibers, whose orientation is parallel with the interfaces and usually it is differing from one to the next. Those fibers may exhibit either electromagnetic isotropy or anisotropy: in the isotropic case, the material parameters are described by scalar space-dependent (and frequency-dependent in most cases) quantities while the anisotropic case leads to tensor quantities. From a modeling perspective at an enough large scale (compared to the local wavelength in propagative case or to the skin depth in diffusive case), the assumption leads to consider a given slab as homogeneous, i.e., its electromagnetic parameters tensor is locally averaged.

Based on [START_REF] Zhong | Electromagnetic response of anisotropic laminates to distributed sources[END_REF][START_REF] Rodeghiero | calculation of electromagnetic scattering in anisotropic multilayers and its inverse problem[END_REF], it is proposed herein a method to compute in an effective fashion the dyadic Green's functions (DGF) for such structures within the framework of contrast-source integral equations.

Damages or disorders, which those composite may suffer from, are of many kinds: voids, fluid-filled cavities, delaminations, etc., with obvious consequences on their electromagnetic and geometric parameters.

That is, the task of making available to end-users some images of the possibly damaged parts. The MUSICtype (MUltiple SIgnal Classification) algorithm [START_REF] Ammari | MUSIC-type electromagnetic imaging of a collection of small three-dimensional inclusions[END_REF] is a good candidate to find the position of small defects.