Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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,\ldots,n\}$. Let $X$ be a random variable that represents the number of samples until a duplicate is found. So if the samples were $1,6,3,2, 5,1$ then $X=6$. Let $Y$ be a random variable that represents the number of samples before both the values $1$ and $2$ have been found. So in our example $Y=4$.

How does one find the following.

  • The probability $P(X<Y)$ or in other words $P(Y-X > 0)$.
  • The conditional probability $P(X \geq x \,\mid \, X<Y)$.
share|cite|improve this question
up vote 3 down vote accepted

$$\lim_{n\to\infty}n\,\mathbb P(X\gt Y)=2.$$

To show this, note that, for every $x\geqslant2$, the event $[Y\leqslant x,X=x+1]$ corresponds to a sample of size $x$ without duplicate and including $1$ and $2$, and to a duplicate appearing at time $x+1$. Each sample of size $x$ without duplicate and including $1$ and $2$ corresponds bijectively to a sample of size $x-2$ without duplicate and without $1$ and $2$, and to the choice of a position in this sample of size $x-1$ to place $1$, and finally to the choice of a position in this augmented sample to place $2$. And there are $x$ choices for the duplicate at time $x+1$.

Thus, the number of samples corresponding to the event $[Y\leqslant x,X=x+1]$ is $$ (n-2)_{x-2}\cdot(x-1)\cdot x\cdot x. $$ The total number of samples of length $x+1$ is $n^{x+1}$ hence $$ \mathbb P(Y\lt X)=\sum_{x=2}^n\mathbb P(Y\leqslant x,X=x+1)=t_n, $$ with $$ t_n=\sum_{x=2}^n\frac{(x-1)x^2(n-2)_{x-2}}{n^{x+1}}=\frac{(n-2)!}{n^{n+1}}\sum_{y=0}^{n-2}\frac{(n-y-1)(n-y)^2n^y}{y!}, $$ where one uses the change of variable $y=n-x$. Let $N_n$ denote a Poisson random variable with parameter $n$, then $$ t_n=\frac{(n-2)!}{n^{n+1}}\mathrm e^n\mathbb E((n-N_n-1)(n-N_n)^2:n-N_n\geqslant2). $$ The central limit theorem indicates that $n-N_n=\sqrt{n}Z_n$ where $Z_n\to Z$ in distribution, with $Z$ standard normal, hence $$ t_n\sim\frac{(n-2)!}{n^{n+1}}\mathrm e^nn^{3/2}\mathbb E(Z^3:Z\geqslant0). $$ Stirling's formula and the value $\mathbb E(Z^3:Z\geqslant0)=2/\sqrt{2\pi}$ yield the result stated at the beginning of this answer.

Likewise, for each $x\geqslant2$, $$ \mathbb P(X\geqslant x\mid X\lt Y)=\frac{\mathbb P(X\geqslant x,X\lt Y)}{\mathbb P(X\lt Y)}=\frac{\mathbb P(X\geqslant x)-\mathbb P(X\geqslant x,X\gt Y)}{\mathbb P(X\lt Y)}. $$ The denominator is $1-\mathbb P(X\gt Y)=1-t_n$. The numerator involves $\mathbb P(X\geqslant x)$, whose value is known, and $$ \mathbb P(X\geqslant x,X\gt Y)=\sum_{y=x-1}^{n}\mathbb P(Y\leqslant y,X=y+1), $$ and one knows from the first part of this post that $$ \mathbb P(Y\leqslant y,X=y+1)=\frac{(y-1)y^2(n-2)_{y-2}}{n^{y+1}}, $$ hence the value of $\mathbb P(X\geqslant x\mid X\lt Y)$ follows.

share|cite|improve this answer

Let A(i) be the event that i distinct numbers have been sampled, none of them 1 or 2. Let B(i) be the event that i+1 distinct numbers have been sampled, exactly one of them being 1 or 2. (Both of these are for $0 \leq i \leq n-2$.) Also denote the event of obtaining a duplicate be D, and the event of obtaining 1 and 2 be M. When M or D is reached, the process stops, and this must happen after at most n steps. What we want for the first question, "what is $P(X<Y)$?" is the probability that the process ends in M.

The process starts at A(0) and the probabilities of going between these events are $$P(A(i) \to A(i+1)) = (n-i-2)/n$$ $$P(A(i) \to B(i)) = 2/n$$ $$P(A(i) \to D) = i/n$$

$$P(B(i) \to B(i+1)) = (n-i-2)/n$$ $$P(B(i) \to D) = (i+1)/n$$ $$P(B(i) \to M) = (n-i-2)/n$$

Note that the process only gets to M via a B(i) and that comes from B (i-1) or A(i). There are j paths each of length j+1 from A(0) to M: $$A(0) \to B(0) \dots B(j-1) \to M$$ $$A(0) \to A(1) \to B(1) \dots B(j-1) \to M$$ $$\dots$$ $$A(0) \to A(1) \dots A(j-1) \to B(j-1) \to M$$

Each of these paths has the same probability, namely $$2(n-2)(n-3) \dots (n-j) / n^{j+1}$$ so $$P(X=j+1 | X < Y) = 2j(n-2)(n-3) \dots (n-j) / n^{j+1}$$ and $$P(X<Y) = 2 \sum_{i=1}^{n-1} \frac{i(n-2)!}{(n-1-i)!n^{i+1}}$$

share|cite|improve this answer

Your Answer


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