most recent 30 from http://mathoverflow.net 2013-05-22T19:28:25Z http://mathoverflow.net/feeds/question/60418 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/60418/missing-mass-estimate Aryeh Kontorovich 2011-04-03T08:51:43Z 2011-04-03T18:50:01Z

<p>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.</p> <p>There are some good estimators for the missing mass (the McAllester-Schapire <a href="http://www.cs.princeton.edu/~schapire/uncompress-papers.cgi/good-turing.ps" rel="nofollow">paper</a> on Good-Turing estimators is a particularly nice one). </p> <p>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?</p>