Birthday problem with known number of collisions

91 Views Asked by At

I find out that the problem I'm trying to solve is related to Birthday problem, specifically to collision counting:

$$c = n - d + d(\frac{d-1}{d})^n$$

In my case, I know the desired number of collisions c and the number of selections n.

My goal is to figure out the formula for d using c and n, so I can express that in my program.

Please guide me how to solve this kind of equations, a link to similar examples would be really helpful.

1

There are 1 best solutions below

0
On BEST ANSWER

For $n \gt 4$ you will not find a general analytic solution, so you are looking at numerical techniques. There are many one dimensional rootfinders out there. Simple bisection is easy to program and as your function is easy to evaluate will probably be fast enough. Write your function as $f(d)=-c + n - d (1-(\frac{d-1}{d})^n)$ and you are trying to find the $d$ where $f(d)=0$ You know that $f(0) \gt 0$ and should be able to check that $f(n) \lt 0$. Then split the interval in half and evaluate $f(\frac n2)$. Replace whichever endpoint has the same sign and continue until the endpoints differ by less than $1$, round to the nearest whole number, and declare victory.