Let $X\_1,X\_2,...$ be i.i.d variables with value in $\mathbb{N}$ (not necessarily finitely supported). Suppose $E(X\_1) < \infty$.


Denote :


$$R\_n = \textbf{Card}\{X\_1,...,X\_n\}$$


I must prove that $E(R\_n) = o(\sqrt{n})$, but do not really know how to proceed. Does anyone have a hint :)? Many thanks !



Estimation of the expected number of sites visited by i.i.d
Denote $p\_k=P(X=k)$. Then $E(R\_n)=\sum\_k P(k\in \{X\_1,\ldots,X\_n\})\leqslant \sum\_k \min(1,np\_k)$. We are given that $\sum kp\_k<\infty$. Fix $\varepsilon>0$. The sum of $\min(1,np\_k)$ over $k<\varepsilon \sqrt{n}$ is of course at most $1+\varepsilon \sqrt{n}$. The sum over $k\geqslant \varepsilon \sqrt{n}$ is at most $$n\sum\_{k\geqslant \varepsilon \sqrt{n}}p\_k\leqslant \frac{\sqrt{n}}{\varepsilon}\sum\_{k\geqslant \varepsilon \sqrt{n}}kp\_k=o(\sqrt{n}).$$
Thus the result.


