Probability of a certain subsequence from a sequence of i.i.d. uniformly distributed discrete random variables. Let $\{x_k\}_{k\in\mathbb{N}}$ be a sequence of i.i.d. random variables with $x_k\sim U_{[[ 1,n]]}$ for all $k\in\mathbb{N}$ where $U_{[[1,n]]}$ is the uniform distribution on the discrete set $[[1,n]]:=\{1,2,\ldots,n\}$. Fix $a\in[[1,n]]$. What is the probability that there is a subsequence $\{x_{k_j}\}_{j\in\mathbb{N}}$ such that $\forall j\in\mathbb{N}$, $x_{k_j} = a\in[[1,n]]$? I think it should be $1$ but I don't know how to show it. References to learn about problems like this are also appreciated.
 A: In order to deal with such questions on a formal level, we need the concepts of "infinite product of sigma algebras", "infinite product of probability measures", and "infinite product of probability spaces". You can read up on this, for example, here: https://jpmccarthymaths.com/2012/01/08/infinite-products-of-probability-spaces/
Assuming all of these concepts, we can proceed as follows.
First, we have
Probability($a$ occurs infinitely often) = $1 -$ Probability($a$ occurs only finitely many times).$\quad\quad$(i)
Moreover
Probability($a$ occurs only finitely many times) = $\sum_{k = 0}^\infty$ Probability($a$ occurs exactly $k$ times),$\quad\quad$(ii)
since the events {$a$ occurs exactly $k$ times } for differente values of $k$ are disjoint.
Let's calculate Probability($a$ occurs exactly $0$ times).
We have
{$a$ occurs exactly $0$ times }$ = \cap_{j=1}^{\infty} ${$a$ does not occur the first $j$ times }.$\quad\quad$(iii)
Also,
{$a$ does not occur the first $j_1$ times } $\supseteq$ {$a$ does not occur the first $j_2$ times }
for $j_1 \leq j_2$.
In other words, the sequence of events on the r.h.s of (iii) is monotonically descending.
From this, we get, using a "well known" property of probability measures (continuity from above, see, for example, here: Properties of Probability Measure),
Probability($a$ occurs exactly $0$ times ) = $\lim_{j\rightarrow\infty}$ Probability($a$ does not occur the first $j$ times ).$\quad\quad$(iv)
Now,
Probability($a$ does not occur the first $j$ times )$ = (\frac{n-1}n)^j$,$\quad\quad$(v)
since the first $j$ terms in the sequence $(x_k)$ are not allowed to be equal to $a$, while the remaining terms can take on any value.
Combining (iv) and (v), we find
Probability($a$ occurs exactly $0$ times ) = $0$.
Next, let's calculate Probability($a$ occurs exactly $2$ times).
We have
{$a$ occurs exactly $2$ times }$ = \cup_{1 \leq j_1 < j_2 < \infty} ${$a$ occurs exactly at positions $j_1$ and $j_2$ },$\quad\quad$(vi)
where the union on the r.h.s is disjoint.
From this, we get
Probability($a$ occurs exactly $2$ times $) = \sum_{1 \leq j_1 < j_2 < \infty} $Probability($a$ occurs exactly at positions $j_1$ and $j_2$ ).$\quad\quad$(vii)
Moreover, for fixed $1 \leq j_1 \leq j_2 < \infty$, we have
{$a$ occurs exactly at positions $j_1$ and $j_2$ } = $\cap_{k = j_2}^\infty$ {$a$ occurs at positions $j_1$ and $j_2$, and maybe at positions after $k$, but not elsewhere},$\quad\quad$(viii)
where the sequence of events on the r.h.s. is monotonically descending for $k \rightarrow \infty$.
Using this, we get as above,
Probability($a$ occurs exactly at positions $j_1$ and $j_2$) $= \lim_{k \geq j_2, k \rightarrow\infty}$ Probability($a$ occurs at positions $j_1$ and $j_2$, and maybe at positions after $k$, but not elsewhere),$\quad\quad$(ix)
and for $k \geq j_2$
Probability($a$ occurs at positions $j_1$ and $j_2$, and maybe at positions after $k$, but not elsewhere) = $(\frac1n)^2(\frac{n-1}n)^{k-2}$.$\quad\quad$(x)
Combining (ix) and (x), we get
Probability($a$ occurs exactly at positions $j_1$ and $j_2$) $=$0$.\quad\quad$(xi)
Now, combining (vii) and (xi), we get
Probability($a$ occurs exactly $2$ times $) = $0$.\quad\quad$(xii)
The cases $k = 1$ and $k \geq 3$ are embarassingly similar to the case $k = 2$.
We find for all $k \in \{0, 1, \ldots \}$
Probability($a$ occurs exactly $k$ times ) = $0$.$\quad\quad$(xiii)
Combining (ii) and (xiii) gives
Probability($a$ occurs only finitely many times) = $0$.$\quad\quad$(xiv)
Combining (i) and (xiv) now gives
Probability($a$ occurs infinitely often) = $1$,
as conjectured.
So we see that once we have the aforementioned concepts of infinite products of sigma algebras etc, the calculations boil down to basic calculus.
If you're not familiar with those infinite products of sigma algebras etc, you should study them. You've seen that they're useful.
