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

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

Your Answer


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

Browse other questions tagged or ask your own question.