Large deviations for missing mass

2012-10-06T22:59:08Z

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. $$

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 < E[U_n] - \epsilon). $$

Edit: It is known that $$ P(U_n>E[U_n]+\epsilon) \le e^{-n\epsilon^2}$$ and that $$ P(U_n < E[U_n]-\epsilon) \le e^{-1.36n\epsilon^2} .$$

The constant 1.36 can be improved to 1.92.

Large deviations for missing mass - MathOverflow

Large deviations for missing mass