2

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.

flag
You might wish to describe more precisely the concentration inequalities which are known for $U_n$. – Didier Piau Oct 7 at 10:54
The question has been edited to include the known concentration results for $U_n$. – Aryeh Kontorovich Oct 7 at 11:23

Your Answer

Get an OpenID
or

Browse other questions tagged or ask your own question.