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](http://jmlr.csail.mit.edu/papers/v4/mcallester03a.html) 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](https://dl.dropboxusercontent.com/u/3198145/k-s-ecp.pdf) to 1.92.



Large deviations for missing mass
Background: this question is motivated by the OP's paper <http://arxiv.org/pdf/1111.2328.pdf>. Amir Dembo and I had answered this question privately to Aryeh a long time ago. I paste the answer here, adapted from email correspondence, in case anybody still needs it. I used the question as a take home exam in a large deviations course already :)


The answer depends on the properties of the $p\_i$'s. For example, trivially if 
the set of non-zero $p\_i$s is finite, the rate function will be infinity except on a finite number of points. So one needs to define the following subset of $[0,1]$:


$A=\{x\in [0,1]: \exists I \mbox{ s.t.} \sum\_{i\in I} p\_i=x\}$


If one assumes that the set $A$ is dense in $[0,1]$, the rate function is $\log(1-x)$, i.e. 


$n^{-1}\log P(U\_n\sim x)\to \log (1-x)$


In general, it will be that on the closure of $A$, and infinity elsewhere.


Here are hints of the derivation:


First we do the case where the support of the vector $p$ is finite. In this case, there are only finitely many values of $U\_n$ that are possible. Each of these values corresponds to a point $x$, and there are only finitely many configurations
for each point $x$ (by configurations I mean values $\xi\_j$). But now, to get one configuration, you have to avoid certain values.


Let me do an example.
If $p\_1=2/3$ and $p\_2,p\_3 =1/6$, and you try to hit $x=2/3$, all $X\_i$ have to avoid $1$ and some $X\_i$ has to hit 2 and another must hit 3. Conditioned on not hitting 1, the probability to 
hit 2,3 is going to 1 with $n$. Then the probability of not hitting 1 is $(1-x)^n$, and so the probability we care about is 
$(1-\delta\_n)(1-x)^n$ where $\delta\_n\to 0$. This gives the statement.


In the general compact support case, one has a combinatorial factor multiplying this, but this combinatorial factor does not depend on $n$. 


Finally, every $p$ can be approximated by a compact support $p$, within total error $\delta$ in the value of $U\_n$. So one gets what are called exponentially good approximations of the 
$U\_n$'s for which you have a LDP. The conclusion is just epsilon-delta argument.


