Discrete i.i.d random variables $\{X_n\}_{n=1}^{\infty}$,let $R_n=\#\{X_1,X_2,...,X_n\}$ Discrete i.i.d random variables $\{X_n\}_{n=1}^{\infty}$, let $R_n=\#\{X_1,X_2,...,X_n\}$, namely the number of elements in the given set.
Prove: $\lim_{n \to \infty} \frac{R_n}{n} \to 0$ a.s..
I've tried to prove for any $\varepsilon > 0$, that $$\sum_{n=1}^\infty \mathbb{P}\left(\frac{R_n}{n}\geq\varepsilon \right) <\infty$$
If this holds we can get the conclusion by using Borel-Cantelli lemma. But I failed to compute $\mathbb{P}(\frac{R_n}{n}\geq\varepsilon)$. Maybe other methods will work?
 A: Here is another idea without Borel-Cantelli. I hope it makes sense:
Let $E$ be a countable set such that $\Bbb P (X_1\in E) = 1$.
Then for any $A\subseteq E$ we have by the law of large numbers that
$$\frac 1n S_n^A := \frac 1 n \sum_{i=1}^n 1_{\{X_i \in A\}} \overset{n\to\infty}\to \Bbb P(X_1 \in A)$$
almost surely.
Let $\varepsilon >0$. Then there is a finite subset $K\subseteq E$ with $\Bbb P (X_1 \in K)\geq 1-\varepsilon$.
Let $O_n := \{X_1, \ldots , X_n\}$. Then we have
$$R_n = n - \sum_{x\in O_n} \left( S^{\{x\}}_n -1  \right) = n - \sum_{x\in O_n \cap K} \left( S^{\{x\}}_n -1  \right) - \sum_{x\in O_n\cap(E\setminus K)} \left( S^{\{x\}}_n -1  \right)$$
We have
$$\sum_{x\in O_n\cap(E\setminus K)} \left( S^{\{x\}}_n -1  \right) \leq \sum_{x\in O_n\cap(E\setminus K)} S^{\{x\}}_n   \leq \sum_{x\in E\setminus K}  S^{\{x\}}_n \leq S_n^{E\setminus K}$$
Thus
$$\limsup_{n\to\infty} \frac 1 n \sum_{x\in O_n\cap(E\setminus K)} \left( S^{\{x\}}_n -1  \right) \leq \limsup_{n\to\infty} \frac 1 n S_n^{E\setminus K} = \Bbb P (X_1 \in E\setminus K) \leq \varepsilon$$
Further,
$$\Big\vert n - \sum_{x\in O_n \cap K} \left( S^{\{x\}}_n -1  \right) \Big\vert  = n - \sum_{x\in O_n \cap K} \left( S^{\{x\}}_n -1  \right) \leq n - \sum_{x\in K} \left( S^{\{x\}}_n -1  \right) = n - S^{K}_n + \#K$$
Therefore
$$\frac 1 n\Big\vert n - \sum_{x\in O_n \cap K} \left( S^{\{x\}}_n -1  \right) \Big\vert \leq 1 - \frac 1 n S^K_n + \frac {\#K}n \to 1 - \Bbb P (X_1 \in K) \leq \varepsilon$$
By the triangle inequality
$$\limsup_{n\to\infty} \frac 1 n R_n \leq 2 \varepsilon$$ almost surely.
Since this is true for every rational $\varepsilon >0$ it follows that
$$\limsup_{n\to\infty} \frac {R_n}n = 0$$
almost surely.
