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