Missing mass estimate - MathOverflow 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 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>