Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 7 down vote accepted

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

share|cite|improve this answer
(+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) \>. $$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.