Large deviations for missing mass

Question

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.

Answer 1

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.

Answer 2

At first I had thought that one could apply Ellis' theorem, [E:1984], which states that for a sequence, $U_n$, of random vectors in $\mathbb R^d$,

if

$\lim_{n\rightarrow \infty} \frac{1}{n} \log \mathbb E[\exp(n \alpha X_n)] = \Lambda(\alpha)$ exists and is convex for $\alpha$ in an open ball about $0$

then

[1] $\quad\liminf_{n\rightarrow \infty} \frac{1}{n}\log\mathbb P(X_n \in G) \geq -\inf_{x \in G}\Lambda^{\star}(x)$ for $G$ open

[2] $\quad\limsup_{n\rightarrow \infty} \frac{1}{n}\log\mathbb P(X_n \in F) \leq -\inf_{x \in F}\Lambda^{\star}(x)$ for $F$ closed

and for convex sets, $C$, the limit exists

[3] $\quad\lim_{n\rightarrow \infty} \frac{1}{n}\log\mathbb P(X_n \in C) = -\inf_{x \in C}\Lambda^{\star}(x)$ for $C$ convex

Here, $\Lambda^{\star}$ is the Legendre-Frenchel transform of $\Lambda$ :

[4] $\quad\Lambda^{\star}(x) = x \,\alpha_x - \Lambda(\alpha_x)$, where $\alpha_x$ is the solution in $\alpha$ to

[5] $\quad\frac{d}{d\alpha}\Lambda(\alpha) = x, \quad \alpha_x = (\Lambda')^{-1}(x)$

In one dimension, any interval on the line (half line) is a convex set and therefore the limit exists. The infemum is given by the "dominating point" which is the point closest to the mean. In this case, which covers the inequalities requested,

[6] $\quad\lim_{n\rightarrow \infty} \frac{1}{n}\log\mathbb P(X_n > \mu + \epsilon) = -\Lambda^{\star}(\mu + \epsilon)$

[7] $\quad\lim_{n\rightarrow \infty} \frac{1}{n}\log\mathbb P(X_n < \mu - \epsilon) = -\Lambda^{\star}(\mu - \epsilon)$

Expanding $\Lambda^{\star}(\bar \xi + \epsilon)$ about $\epsilon=0$, using the inverse function theorem in [5] to calculate derivatives in [4], we have to second order for the general case,

$\Lambda^{\star}(\mu + \epsilon) = \Lambda^{\star}(\mu - \epsilon) = \frac{1}{2\,\Lambda''(0)} \,\epsilon^2$

Now in the particular case at hand, consider $\mathcal I = 2^{\mathbb N}$, and allowing abuse of notation whereby a subset of naturals is identified with its corresponding increasing sequence,

let $\mathcal J_n = \{ \;\vec j \in \mathcal I\,: | \mathbb N \setminus \vec j | \leq n \}$

Intuitively, $U_n$ takes values

$U_n = \sum_{\ell=1}^{\infty} p_{j_{\ell}}\quad$ with probability $\quad(1 - \sum_{\ell=1}^{\infty} p_{j_{\ell}})^n\qquad$ for $\;\vec j \in \mathcal J_n$

but since the cardinality of $\mathcal I$ and hence, also of $\mathcal J_n$, is $\aleph_1$ then intuition must be excercised with care. If there is a limiting random variable