5
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ It can't, at least not for every $i$: consider a uniform distribution on $\{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
    Commented Apr 3, 2011 at 15:56
  • $\begingroup$ A small style comment: when you put a link, you should replace the number (1 in the above) with a relevant word (e.g. "paper" in this case). $\endgroup$
    – Ori Gurel-Gurevich
    Commented Apr 3, 2011 at 15:58
  • $\begingroup$ Let $m=m_i$ be the missing mass for a given distribution, and $u=u_i$ the missing mass for the uniform distribution. It may be that $u_i$ stochastically dominates $m_i-\eps$, or possibly $m_{i'}-\eps$ for some $\eps$ tending to $0$ and $i'\leq i$ but not much smaller. $\endgroup$
    – Omer
    Commented Apr 4, 2011 at 0:02
  • $\begingroup$ Actually, it appears that the uniform distribution is not extremal at all! The real extremal distribution, it seems, is the one taking on 2 values: $p$ and $(1-p)/(|S|-1)$. Developing... [unless someone already knows the answer, of course!] $\endgroup$
    – Aryeh Kontorovich
    Commented Apr 4, 2011 at 21:08

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .