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

By Anna Ben-Hamou, Stéphane Boucheron, Mesrob I. Ohannessian. 2014

77 citations recorded by the source corpus.

An infinite urn scheme is defined by a probability mass function $(p_j)_{j\geq 1}$ over positive integers. A random allocation consists of a sample of $N$ independent drawings according to this probability distribution where $N$ may be deterministic or Poisson-distributed. This paper is concerned with occupancy counts, that is with the number of symbols with $r$ or at least $r$ occurrences in the sample, and with the missing mass that is the total probability of all symbols that do not occur in the sample. Without any further assumption on the sampling distribution, these random quantities are shown to satisfy Bernstein-type concentration inequalities. The variance factors in these concentration inequalities are shown to be tight if the sampling distribution satisfies a regular variation property. This regular variation property reads as follows. Let the number of symbols with probability larger than $x$ be $\vec{\nu}(x) = |\{ j \colon p_j \geq x\}|$. In a regularly varying urn scheme, $\vec{\nu}$ satisfies $\lim_{\tau\rightarrow 0} \vec{\nu}(\tau x)/\vec\nu(\tau) = x^{-\alpha}$ for $\alpha \in [0,1]$ and the variance of the number of distinct symbols in a sample tends to infinity as the sample size tends to infinity. Among other applications, these concentration inequalities allow us to derive tight confidence intervals for the Good-Turing estimator of the missing mass.

Subfields: Applied Mathematics, Artificial Intelligence, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/df531915c23d6cec0488172c0cc83137e7165bd7

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

In Artificial Intelligence

In Statistics and Probability

Citations in the corpus

On the sub-Gaussianity of the Beta and Dirichlet distributions (2017, background): “…proxy variance for discrete random variables like the Bernoulli distribution (Buldygin and Moskvichova, 2013; Kearns and Saul, 1998; Berend and Kontorovich, 2013) and the missing mass (McAllester and Schapire, 2000; McAllester and Ortiz, 2003; Berend and Kontorovich, 2013; Ben-Hamou et al., 2017).”
Sub‐Weibull distributions: Generalizing sub‐Gaussian and sub‐Exponential properties to heavier tailed distributions (2019, background): “…transportation and PAC-Bayes inequalities (Boucheron et al., 2013; Raginsky and Sason, 2013; van Handel, 2014; Catoni, 2007), the missing mass problem (Ben-Hamou et al., 2017), bandit problems (Bubeck and Cesa-Bianchi, 2012) and singular values of random matrices (Rudelson and Vershynin, 2010).”