I'm struggling with the following problem. Let $X_i$ be iid discrete rvs, taking values in $\mathbb{N}$ with arbitrary distribution $\mathrm{P} (X_i = k) = p_k$. Let $Z_n$ be a number of distinct values in $X_1, \ldots, X_n$. I need to find its expectation and variance and compare it to Efron-Stein inequality estimate on variance.

My reasoning is as follows: let $Y_i$ be indicator rv, assuming $1$ if $X_i$ has value different from $X_1, \ldots, X_{i - 1}$. Then

$$ \mathrm{P} (Y_i = 1) = \sum_{i = k}^{\infty} \mathrm{P} (Y_i = 1 | X_i = k) \mathrm{P} (X_i = k) = \\ = \sum_{k = 1}^{\infty} \mathrm{P} (X_1 \neq k, \ldots X_{i - 1} \neq k) \mathrm{P} (X_i = k) = \sum_{k = 1}^{\infty} (1 - p_k)^{i - 1} p_k. $$

Then, since $Z_n = \sum_{i = 1}^n Y_i$:

$$ \mathrm{E} Z_n = \sum_{i = 1}^n \mathrm{E} Y_i = \sum_{i = 1}^n \sum_{k = 1}^{\infty} (1 - p_k)^{i - 1} p_k. $$

So far so good. I checked my calculations with simulations from Poisson distribution - they agree very closely.

Now to variance. Since $Z_n - Z_{n - 1}$ differs at most by one, for function with bounded differences by Efron-Stein inequality we have an estimation on variance:

$$ \mathrm{Var} (Z_n) \leq \frac{n}{4}. $$

But I can't calculate variance analytically to compare it to estimation. Unfortunately, $Y_n$ and $Y_m$ are anti-correlated, so simple sum of separate variances won't do. I tried to calculate covariance, but ended up with rather messy formula. Any ideas how I can get a nice expression for $\mathrm{Var} (Z_n)$?


1 Answer 1


You can rewrite $Z_n$ as $$ Z_n = \sum_{i=1}^\infty I(\{X_1=i\}\cup\ldots\cup\{X_n=i\}) = \sum_{i=1}^\infty\bigl(1-I(X_1\neq i,\ldots,X_n\neq i)\bigr) $$ So $$ \mathbb EZ_n = \sum_{i=1}^\infty\bigl(1-\mathbb P(X_1\neq i,\ldots,X_n\neq i)\bigr) = \sum_{i=1}^\infty\bigl(1-(1-p_i)^n\bigr). $$ In the paper N. S. Zakrevskaya, A. P. Kovalevskii, “One-parameter probabilistic models of text statistics”, Sib. Zh. Ind. Mat., 4:2 (2001), 142–153 (only in Russian) the following inequality is proved, see p.146, Lemma 3: $$ \mathrm{Var}(Z_n)\leq \mathbb EZ_n. $$ The proof is very simple: $$ \mathbb E(Z_n^2) = \sum_{i=1}^\infty\sum_{j=1}^\infty\bigl(1-\mathbb P(X_1\neq i,\ldots, X_n\neq i)-\mathbb P(X_1\neq j,\ldots, X_n\neq j)+\mathbb P(X_1\neq i,\ldots, X_n\neq i,X_1\neq j,\ldots, X_n\neq j)\bigr) $$ $$\tag{1}\label{1} =\sum_{i=1}^\infty\sum_{j=1\\j\neq i}^\infty\bigl(1-(1-p_i)^n-(1-p_j)^n+(1-p_i-p_j)^n\bigr)+\mathbb EZ_n $$ $$ \leq \sum_{i=1}^\infty\sum_{\color{red}{j=1}}^{\color{red}\infty}\bigl(1-(1-p_i)^n-(1-p_j)^n+(1-p_i-p_j\color{red}{+p_ip_j})^n\bigr)+\mathbb EZ_n $$ $$ =\bigl(\mathbb EZ_n\bigr)^2+\mathbb EZ_n. $$ So, $\mathrm{Var}(Z_n)\leq \mathbb EZ_n$. Two pages after in Lemma 6 it is proved that $\mathbb EZ_n =o(n)$ as $n\to\infty$.

You can use the expression for second moment to try to find variance, but I doubt it is possible. Subtracting squared expectation from \eqref{1} we get $$ \mathrm{Var}(Z_n)=\sum_{i=1}^\infty\sum_{j=1\\j\neq i}^\infty\bigl((1-p_i-p_j)^n-(1-p_i)^n(1-p_j)^n\bigr)+\sum_{i=1}^\infty (1-p_i)^n(1-(1-p_i)^n) $$ The first summand is negative, and the second one gives very small results in examples. Say, under geometric distribution $p_i=2^{-i}$, for $n=20$ it equals to $0.98495$. For $p_i=\frac12(\frac23)^i$ and $n=10$ second summand equals to $1.64842$.

  • 1
    $\begingroup$ Brilliant! Just what I was looking for. Thank you. Very interesting paper, by the way. $\endgroup$
    – fanvacoolt
    Nov 17, 2019 at 19:26
  • $\begingroup$ @fanvacoolt, the 2nd author of the above-mentioned paper provides me two extra links. It appears, that the priority belongs to Bahadur, R. R., 1960. On the number of distinct values in a large sample from an infinite discrete distribution. Proceedings of the National Institute of Sciences of India, 26A, Supp. II, 67--75. And also you can find calculations of variance with poissonization trick here: arxiv.org/pdf/math/0609498.pdf $\endgroup$
    – NCh
    Nov 18, 2019 at 11:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .