# 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)$?

-
Probably easier to compute $P(X=x)$ and compute $P(X\geq x)=\sum_{y=x}^{n+1} P(X=y)$ –  Thomas Andrews Jan 1 '13 at 20:19
@ThomasAndrews Not in this case. –  Did Jan 1 '13 at 22:26

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).$$

-
(+1) For a slick alternate argument. –  cardinal Jan 1 '13 at 21:54
Please do not modify the question after answers were posted. Rather, post a new question. –  Did Jan 1 '13 at 22:45

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) \>.$$

-