MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

2 added 313 characters in body

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.

1

# Large deviations for missing mass

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