# Why can strong law of large numbers be applied in this question?

Let $(X_n)_{n\in\mathbb{N}}$ be i.i.d. random variables taking values in the set of natural number $\mathbb{N}$. Assume that $\mathbb{P}(X_1=i)=p_i>0$ for $i\in\mathbb{N}$. Let $D_n$ denote the carinality of the set $\{X_1,X_2,...,X_n\}$. Prove $(i)$, $D_n\rightarrow\infty$ a.s.; $(ii)$, $D_n/n\rightarrow 0$ in probability. Can one strengthen $(ii)$ to a.s. convergence?

$\left\{ D_{n}\rightarrow\infty\right\} ^{c}=\bigcup_{k=1}^{\infty}\bigcap_{n=1}^{\infty}\left\{ X_{n}\leq k\right\}$ so that $P\left(\left\{ D_{n}\rightarrow\infty\right\} ^{c}\right)\leq\sum_{k=1}^{\infty}P\left(\bigcap_{n=1}^{\infty}\left\{ X_{n}\leq k\right\} \right)$.

For a fixed $k$ we find $P\left(\bigcap_{n=1}^{\infty}\left\{ X_{n}\leq k\right\} \right)\leq P\left(\bigcap_{n=1}^{m}\left\{ X_{n}\leq k\right\} \right)=\left(p_{1}+\cdots+p_{k}\right)^{m}$ for any $m$.

Here $p_{1}+\cdots+p_{k}<1$ so $m\rightarrow\infty$ makes clear that $P\left(\bigcap_{n=1}^{\infty}\left\{ X_{n}\leq k\right\} \right)=0$.

Actually the second convergence can be almost surely

Fix $\epsilon >0$. Let $\tau$ be the first moment when the total probability of elements in $D_n$ is greater than $1 - \frac{\epsilon}{2}$. By the fact that every element will eventually fall into $D_n$, we know $\tau$ is finite almost surely. To strictly prove it, begin with the element with biggest probability, then that with second biggest probability etc.

By the strong law of large number $\limsup\dfrac{D_n - D_\tau}{n - \tau} < \dfrac{\epsilon}{2}$, since after $\tau$, for each step the probability that $D_n$ increase by 1 is less than $\dfrac{\epsilon}{2}$

The above limit is also limsup of $\dfrac{D_n}{n}$.

My question: Why strong law of large number can be applied to $\limsup\dfrac{D_n - D_\tau}{n - \tau} < \dfrac{\epsilon}{2}$?? I don't understand.

For every $n$, consider the random set $Y_n=\mathbb N\setminus\{X_k\mid k\leqslant n\}$, then $Y_{\tau+k-1}\subseteq Y_{\tau}$ for every $k\geqslant1$, hence, for every $n\geqslant\tau$, $$D_n-D_\tau=\sum_{k=1}^{n-\tau}\mathbf 1_{X_{\tau+k}\in Y_{\tau+k-1}}\leqslant\sum_{k=1}^{n-\tau}U_k^\tau,\qquad U_k^\tau=\mathbf 1_{X_{\tau+k}\in Y_\tau}.$$ Conditionally on $Y_\tau$, the sequence $$\left(U_k^\tau\right)_{k\geqslant1}$$ is i.i.d. Bernoulli with probability of success $p(Y_\tau)$ where, for every $B\subseteq\mathbb N$, $p(B)=\sum\limits_{i\in B}p_i$. Thus, by the strong law of large numbers conditionally on $Y_\tau$, one has, almost surely, $$\limsup_{n\to\infty}\frac{D_n-D_\tau}{n-\tau}\leqslant\lim_{n\to\infty}\frac1{n-\tau}\sum_{k=1}^{n-\tau}U^\tau_k=\lim_{n\to\infty}\frac1n\sum_{k=1}^{n-\tau}U^\tau_k=p(Y_\tau).$$ Finally, note that, by definition of $\tau$, $p(Y_\tau)\leqslant\frac12\epsilon$.