5
$\begingroup$

Fix two arbitrary distinct values from $\{1,\dots,n\}$. Say for concreteness we choose the values $1$ and $2$.

We sample uniformly with replacement from $\{1,\dots,n\}$ in a number of stages. Each stage runs until we either sample the same element twice (a duplicate) within the same stage, or we find both of the two values within the same stage. If the stage ends because we sampled the same element twice we just start again with a new stage.

I would like to know the probability distribution for the number of samples we need to have in total before the two values are found within the same stage.

1 Answers 1

0

The probability generating function for a failed attempt is

\begin{align} \sum_{k=1}^{n-1}k!\frac{\binom nk-\binom{n-2}{k-2}}{n^k}\frac knx^{k+1} &= \sum_{k=1}^{n-1}k!\frac{\binom{n-1}k+\binom{n-2}{k-1}}{n^k}\frac knx^{k+1} \\ &= \sum_{k=2}^n\left((k-1)\frac{(n-1)!}{(n-k)!}+(k-1)^2\frac{(n-2)!}{(n-k)!}\right)\left(\frac xn\right)^k\;, \end{align}

and for a successful attempt,

$ \sum_{k=2}^nk!\frac{\binom{n-2}{k-2}}{n^k}\frac2kx^k=2\sum_{k=2}^n(k-1)\frac{(n-2)!}{(n-k)!}\left(\frac xn\right)^k\;. $

We can have any number of failed attempts and then exactly one successful attempt, so the probability generating function for the total number of samples is

$ \left(1-\sum_{k=2}^n\left((k-1)\frac{(n-1)!}{(n-k)!}+(k-1)^2\frac{(n-2)!}{(n-k)!}\right)\left(\frac xn\right)^k\right)^{-1}2\sum_{k=2}^n(k-1)\frac{(n-2)!}{(n-k)!}\left(\frac xn\right)^k\;. $

Unfortunately I don't see how to simplify this.