Let $\{X_n\}_{n=1}^{\infty}$ be a sequence of i.i.d. random variables, whose range is $\mathbb{N}$ (e.g., Geo(1)). Consider now the random sequence $X_1,X_2,X_3,...$
What is the probability that each $k\in\mathbb{N}$ shows up infinitely many times in the sequence? I believe that the somewhat unexpected answer is $1$ (I show why below), but it still seems to me very unintuitive. Can someone please either explain to me the intuition behind it or show me where I'm wrong?
My proof
For every $n,k\in\mathbb{N}$, define the event: $A_n^k:=\{X_n=k\}$. For any $k\in\mathbb{N}$ define: $$A^k:=\bigcap_{n=1}^{\infty}\bigcup_{m=n}^{\infty}A_m^k=(A_n^k\quad i.o.)$$ This is the event of $k$ showing up infinitely many times in the sequence. As the RV's are identically distributed, for any $k\in\mathbb{N}$ we have: $$\sum_{n=1}^{\infty}\mathbb{P}(A_n^k)=\sum_{n=1}^{\infty}\mathbb{P}(A_1^k)=\infty$$ We also know that the RV's are independent, thus so are the sequence of events $\{A_n^k\}_{n=1}^\infty$, hence by the Second Borel-Cantelli Lemma we conclude: $\mathbb{P}(A^k)=1$.
Now notice that the event of each $k\in\mathbb{N}$ showing up infinitely many times in the sequence is exactly $A:=\bigcap_{k=1}^{\infty}A^k$. In particular, $A$ is an intersection of countably many events of probability $1$, hence $\mathbb{P}(A)=1$ as well.
I didn’t notice what is paradoxical here. Your opinion is, in this infinitely long sequence of random variables, there’s some number will just appare finitely many times, just because there’s infinitely many numbers with sufficiently small probability to be chosen by a random variable?
Firstly, the cardinality for $\mathbb N$ numbers to appare $\mathbb N$ times is still $\mathbb N$, this gives a possibility for it to hold.
Secondly, let me use a deterministic analogue (yeah that’s very improper in probability theory). Let $a_n$ be the number of trailing zeros in $n$’s binary representation plus one. That is, $a_n = \nu_2(n) + 1$ if you are ok with the notation in number theory.
The thing is, the frequency for $k$ ($k \in \mathbb Z^+$) to appare in the first $n$ $a_n$’s is approximately $2^{-k}$, when $n$ is sufficiently large for $k$. This is the geometric distribution with parameter $1/2$. Would you deny that in this infinitely long sequence, all numbers have appeared infinitely many times?