MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
You might wish to describe more precisely the concentration inequalities which are known for $U_n$. – Did Oct 7 '12 at 10:54
The question has been edited to include the known concentration results for $U_n$. – Aryeh Kontorovich Oct 7 '12 at 11:23
up vote 4 down vote accepted

Background: this question is motivated by the OP's paper 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.

share|cite|improve this answer

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


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


[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

share|cite|improve this answer
The second formula for $V_n$ is not equal to the first, defining, one. The second one enumerates the number of times $X_i=j$ while one is interested in whether or not $X_i=j$ for some $i$s. In other words, you use $k$ instead of $\min(k,1)$. – Did Oct 29 '13 at 9:38
Whoops! Thank you for pointing that out! Ok back to the drawing board. I'll modify my post as soon as I have time. – Grant Izmirlian Oct 29 '13 at 14:43
OK. I mentioned the fact at the beginning of your post. – Did Oct 29 '13 at 14:45

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.