= Expected number of observed categories
{title2=$\mathbb E K_n=\sum_{j=1}^m(1-(1-p_j)^n)$}
In $n$ independent trials with category probabilities $p_1,\ldots,p_m$, let $K_n$ count the distinct categories observed. Write it as the <sum> of <indicator random variables> for the categories' appearances. Category $j$ is absent with <probability> $(1-p_j)^n$, so <linearity of expectation> gives the displayed formula. The appearance indicators need not be independent. For equally likely categories the expression becomes $m(1-(1-1/m)^n)$; uneven probabilities can substantially delay observation of rare categories.
Back to article page
