3
$\begingroup$

Assume $n$ people choose a number between $1$ and $k$ uniformly at random, simultaneously. What is the probability that any two of the $n$ people get the same number?

I tried: The probability that two people choose the same number is $\frac1k$. There are $\binom{n}{2}$ different pairs. How to proceed from this?

Thanks.

$\endgroup$
  • $\begingroup$ Archi duplicate. $\endgroup$ – Did Sep 30 '13 at 6:00
  • $\begingroup$ You can search for birthday on this site, and see birthday problem in Wikipedia $\endgroup$ – Ross Millikan Apr 22 '14 at 20:07
9
$\begingroup$

There are $k$ choices and $n$ people.

  • First person will choose a random number.
  • Second person will choose a random number and will have $1\over k$ probability to choose the number chosen by others.
  • Third person will have $2\over k$ probability.
  • $n$-th person will have ${n-1} \over k$ probability.

Geting the probability that way will be way too hard, let's get the probability of not having two identical choices:

  • First person will choose a random number (and have $k \over k$ probability).
  • Second person will choose a random number and have $k-1 \over k$ to choose the number not chosen by others.
  • Third person will have $k-2 \over k$ probability.
  • $n$-th person will have $k-n+1 \over k$ probability.

Probability ($p$) is then: $$ p=1-{{k(k-1)(k-2)(k-3)...(k-n+3)(k-n+2)(k-n+1)} \over {k^n}}=1-{k! \over {k^n(k-n)! }} $$

$\endgroup$
  • $\begingroup$ What about n > k? $\endgroup$ – mgiordi Nov 30 '18 at 15:01
2
$\begingroup$

Hint: find the probability that all the numbers are distinct.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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