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

 A: 
$$\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.
A: 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}}$$
