Probability that an infinite sequence of i.i.d. integers has a repetition

130 Views Asked by At

Let $X_i$ be a sequence of i.i.d. random variables in $\mathbb N$. According to Hewitt-Savage's 0-1 law, the probability that $X_i$ has a repetition is either $0$ or $1$.

If the $X_i$ have a moment of order $2+\epsilon$, then Borel-Cantelli plus the pigeonhole principle allow us to prove that there exists a repetition almost surely.

Does it still hold without any condition on the distribution of $X_i$ ?

1

There are 1 best solutions below

1
On BEST ANSWER

Yes, sure. Let $p$ be the pmf. For any $x$ with $p(x)>0$, the events $\{X_2 = x\}, \{X_3 = x\}, \dots$ are conditionally independent given $X_1$, so we have by de Morgan $$\begin{align*} P(X_2 = x \cup \dots \cup X_n = x \mid X_1 = x) &= 1 - P(X_2 \ne x \cap \dots \cap X_n \ne x \mid X_1 = x) \\ &= 1 - (1-p(x))^{n-1} \\& \to 1. \end{align*}$$ So conditional on $X_1 = x$, there is almost surely another $X_i$ taking the value $x$. Now using the law of total probability and summing over all $x \in \mathbb{N}$, we find that almost surely there exists $i$ with $X_i = X_1$.

By a variant of this, you can show that almost surely, every $x$ with $p(x) > 0$ is repeated infinitely many times.

Even more generally, allowing for continous distributions, you can say that almost surely, the set $\{X_1, X_2, \dots\}$ is dense in the essential range of $X_i$. In this case, the essential range is a subset of $\mathbb{N}$, hence discrete, so the only dense set is that set itself.