Let $S$ be a finite set with probability distribution $P$. Define the random variable $m_i$ to be the "missing mass" after seeing $i$ iid samples from $S$ under $P$. That is, $m_i$ is the total mass under $P$ of all the points unobserved in the first $i$ samples.

There are some good estimators for the missing mass (the McAllester-Schapire paper on Good-Turing estimators is a particularly nice one).

I looking for a pointer to a result along the following lines: the uniform distribution is "extremal" or "worst-case" for this problem. It's easy to see that it maximizes the expectation of $m_i$, but I think something stronger should be true. Perhaps the uniform distribution maximizes $m_i$ in the stochastic-dominance sense?

`$\{0,1\}$`

vs. a biased one $P(X=0)=1/3$. Then the former has $P(m_1=1/2)=1$ while the latter will have $P(m_1=2/3)=1/3$. $\endgroup$ – Ori Gurel-Gurevich Apr 3 '11 at 15:56