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

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.

share|cite|improve this question

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.

share|cite|improve this answer

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.