Large deviations for missing mass - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T06:27:56Z http://mathoverflow.net/feeds/question/109026 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/109026/large-deviations-for-missing-mass Large deviations for missing mass Aryeh Kontorovich 2012-10-06T22:59:08Z 2012-10-07T11:05:28Z <p>Let $\boldsymbol p=(p_1,p_2,\ldots)$ be a distribution over $\mathbb{N}$ and suppose that $S=(X_1,X_2,\ldots,X_n)$ are sampled iid according to $\boldsymbol p$. Define the indicator variable $\xi_j$ to be $0$ if $j$ occurs in the sample $S$ and $1$ otherwise: $$\xi_j=\boldsymbol{1}_{j\notin S}, \qquad j\in\mathbb{N}.$$ The missing mass is the random variable $$U_n = \sum_{j\in\mathbb{N}} p_j\xi_j.$$</p> <p>Concentration inequalities for $U_n$ are known; what about LDPs? I am particularly interested in $$\lim_{n\to\infty} \frac{1}{n} \log P(U_n > E[U_n] + \epsilon)$$ and $$\lim_{n\to\infty} \frac{1}{n} \log P(U_n &lt; E[U_n] - \epsilon).$$</p> <p>Edit: It is <a href="http://jmlr.csail.mit.edu/papers/v4/mcallester03a.html" rel="nofollow">known</a> that $$P(U_n>E[U_n]+\epsilon) \le e^{-n\epsilon^2}$$ and that $$P(U_n &lt; E[U_n]-\epsilon) \le e^{-1.36n\epsilon^2} .$$</p> <p>The constant 1.36 can be <a href="https://dl.dropbox.com/u/3198145/k-s.pdf" rel="nofollow">improved</a> to 1.92.</p>