0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\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.