find and prove probability of P({D1,D2,D3,...}=N)

Question

Let $D_1, D_2,\cdots$ be independent with $D_n\sim Unif\{1,2,\cdots,n\}$. Find and prove tthe probability of $P(\{D_1,D_2,\cdots\}=\mathbb{N})$. I am a bit lost as to how to prove this. My intuition tells it should be 1. Hope someone could help! Thanks!

Answer 1

The probability is indeed $1$.

For any $k \le n$ the probability of the event $$k \notin \{ D_k , \dots , D_n\}$$ is equal to $$\frac{k-1}{k} \cdot \frac{k}{k+1} \cdots \frac{n-1}{n} = \frac{k-1}{n}$$ As $n \to \infty$ this probability tends to $0$.

Hence the event $$k \notin \{ D_k , \dots \}$$ has probability $0$.

This means that $k$ belongs almost certainly to the set $\{ D_n : n \in \Bbb N\}$.

Since $\Bbb N$ is countable, and countable intersection of almost certain events is almost certain, the probability of the event $$\Bbb N \subseteq \{ D_n : n \in \Bbb N\}$$ is $1$.

Answer 2

---

UPDATED ANSWER

---

Thanks to @Crostul (who has revised the answer below) and @TippingOctopus.

Hint: Consider the probability $P(k\notin\{D_1,D_2,\dots,D_n\})$ where $k<n$.

The event that the set $\mathscr{D} = \{D_1,D_2\dots\}$ contains $\mathbb{N}$ is similar to asking whether every element of $\mathbb{N}$ belongs to this set $\mathscr{D}$. The probability that a number $k$ does not belong to the set $\{D_1,D_2\dots,D_n\}$ where $k<n$ is given by $$ P(k\notin\{D_1,D_2,\dots,D_n\}) = P(k\notin\{D_{k},D_{k+1},\dots,D_n\}) = \frac{k-1}{k}\cdot\frac{k}{k+1}\cdot\cdot\cdot\frac{n-1}{n} = \frac{k-1}{n}.$$

Now fix $k$. As $n$ tends to $\infty$, the probability of this number $k$ belonging to the set $\mathscr{D}$ is $$ P(k\in\{D_1,D_2,\dots\}) = 1 - P(k\notin\{D_1,D_2,\dots\}) = \lim_{n\rightarrow\infty} 1-\frac{k-1}{n} = 1.$$

Hence, $P(N\subseteq \mathscr{D}) = 1$ which is your answer.

---

OLD ANSWER

---

Hint: Let $S_n = \{1,2,\dots,n\}$. Consider the following probabilities:

(i) $P(\{D_1,\dots,D_n\} = S_n) =\ ??$

(ii) $P(\{D_1,\dots,D_{n-1}\} = S_n) =\ ??$

Solution. The probability of (i) above is $1/n!$. Taking limit as $n$ tends to infinity, we get the probability as $0$. Thus, $$ P(\{D_1,D_2\dots\} = \mathbb{N}) = \lim_{n\rightarrow\infty} P(\{D_1,\dots,D_n\} = S_n) = \lim_{n\rightarrow\infty} 1/n! = 0.$$ (The probability of (ii) above is $0$ because there is no way of that $n$ occurs above.)

Hope this helps. Do correct me if I am wrong.