Probability of choosing the same number

Question

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.

Answer 1

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)! }} $$

Answer 2

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