There are $M$ persons in a room, and each one has chosen a random integer in $[1, N]$ (here $M$ much smaller than $N$).
Now I repeat the experience of randomly choosing a number in $[1, N]$ and asking people if I have the same number than the one they have, until I get a collision with someone. Let $Y$ be the random variable "number of attempts to get the first collision".
Note: I won't try a second time with the same number if this number didn't match.
How to get the expected value $E[Y]$, as a function of $M$ and $N$?
Note: people don't have to disclose their number to each other, except if there is a collision (then end of the process anyway). The process could go like this:
"I chose number 7, does anyone have it? No? Let's continue. I chose number 12, does anyone have it? No? Let's continue. I chose number 2, does anyone have it? (Somebody raises its hand). Ok, Y=3."
Example:
$N=365$ bitrthday dates, $M=30$ people in the room.
It is linked to the birthday problem, but not exactly the same: in the birthday problem, everyone says its birthday date, and we check if there is a collision between any pair of people in the room. Here only one person (me) is repeating the task of taking random numbers, and asking if there is a collision between me and one of them.
The probability the process lasts beyond the $k^{th}$ stage is $$\left(\frac{N-k}N\right)^M$$ The probability the process lasts exactly $k$ stages is $$\left(\frac{N-k+1}N\right)^M-\left(\frac{N-k}N\right)^M$$ The average number of stages is $$\sum_{k=1}^N k\left[\left(\frac{N-k+1}N\right)^M-\left(\frac{N-k}N\right)^M\right]=\sum_{k=0}^N\left(\frac{N-k}N\right)^M\\=\frac1{N^M}\sum_{k=1}^Nk^M\approx\frac N{M+1}+\frac12$$