CDF related to sampling with replacement Consider a random process where integers are sampled uniformly with replacement from $\{1...n\}$.  Let $X$ be a random variable that represents the number of samples until either a duplicate is found or both the values $1$ and $2$ have been found.  So if the samples where $1,6,3,5,1$ then $X=5$ and if it was $1,6,3,2$ then $X=4$.  
How does one find the cumulative distribution function. That is how does one find $P(X \geq x)$? 
 A: Let $x\geqslant1$. There are $n^x$ samples of length $x$. Amongst these, $(n)_x=\frac{n!}{(n-x)!}$ samples have no duplicate. 
A sample of length $x$ without duplicate where two distinct given results $i$ and $j$ appear is uniquely described by a sample of length $x-2$ without duplicate where neither result $i$ nor result $j$ appear, and the choice of a position amongst $x-1$ where one places result $i$, and the choice of a position amongst $x$ (once result $i$ is placed) where one places result $j$. There are $x(x-1)\cdot(n-2)_{x-2}$ of these samples. 
Thus, the number $S_x$ of samples of length $x$ without duplicate where results $i$ and $j$ do not both appear is
$$
S_x=(n)_{x}-x(x-1)\cdot(n-2)_{x-2},
$$
and, for every $x\geqslant0$,
$$
\mathbb P(X\gt x)=n^{-x}S_x=\frac{n!}{(n-x)!\,n^x}\left(1-\frac{x(x-1)}{n(n-1)}\right).
$$
A: First, note that by the pigeonhole principle, $\renewcommand{\Pr}{\mathbb P}\Pr(X > n) = 0$.
Next let 
$$
A_m := \{\text{no duplicates in first $m$ trials}\}
$$ 
and 
$$
B_{m,i} := \{\text{The value $i$ has been seen in the first $m$ trials}\} \>.
$$ 
Then, by decomposing into disjoint sets and employing symmetry, we have
$$
\Pr(X > m) = \Pr(A_m (B_{m,1}^c \cup B_{m,2}^c)) = \Pr(A_m B_{m,1}^c B_{m,2}^c) + 2 \Pr(A_m B_{m,1} B_{m,2}^c) \>. 
$$
But the second probability on the right-hand side is (again, by symmetry)
$$
\Pr(A_m B_{m,1} B_{m,2}^c) = m \Pr(A_m \cap \{\text{$1$ is in the first position}\} \cap B_{m,2}^c) \>.
$$
These two probabilities are easy to find by simple (combinatorial) arguments.
$$
\Pr(A_m B_{m,1}^c B_{m,2}^c) = \frac{(n-2) (n-3) \cdots (n-m-1)}{n^m}
$$
and
$$
\Pr(A_m \cap \{\text{$1$ is in the first position}\} \cap B_{m,2}^c) = \frac{1 \cdot (n-2) \cdots (n-m)}{n^m} \>.
$$
Thus, for $1 \leq m < n$,
$$
\Pr(X > m) = \frac{(n-2)!\,(n+m-1)}{n^m (n-m-1)!} = \frac{n!}{(n-m)!\, n^m}\left(1 - \frac{m(m-1)}{n(n-1)}\right) \>.
$$
