Recently, I encountered an interesting problem with the cardinality of a set generated by a sequence of $i.$$i.$$d$ random variables.
Let $\{\xi_{i}\}$ be an $i.$$i.$$d$ sequence, taking values in positive integers. Assume $P(\{\xi_{1}=i\})=p_{i}$ and all $p_i>0$ with $\sum p_{i}=1$. We denote $D_{n}$ as the number of elements of the set $\{\xi_{1},\xi_{2}...\xi_{n} \}$. Then try to prove $\frac{D_{n}}{n}\to 0$ in probability.
My analysis is as follows.
We can write $D_{n}=1+1_{\xi_{2}\notin \{\xi_{1}\}}+...+1_{\xi_{n}\notin\{\xi_{1},\ \xi_{2}\ ,,,\ \xi_{n-1} \ \ \} }$
I want to estimate $\mathbb{E}(\frac{D_{n}}{n})$ and I can get $\mathbb{E}(D_{n})=\tbinom{n}{1}-\tbinom{n}{2}\sum p^{2}_{i}+\tbinom{n}{3}\sum p^{3}_{i}+...+(-1)^{n-1}\tbinom{n}{n}\sum p^{n}_{i}$. But then, I don't know how to prove $\mathbb{E}(\frac{D_{n}}{n}) \to 0$. Could anyone help me? Thank you.