Is there a closed-form inverse of the Birthday Problem equation over the interval $1 < k < n + 1$?

Question

The Birthday Problem deals with the probability that, in a set of $k$ randomly-chosen people, at least two will share a birthday. It can be generalized to similar questions of a match with any pair out of $k$ choices with $n$ possibilities for the value-to-be-matched with the function

$$ P_{n}(k) = 1 - \frac{Γ(n + 1)}{Γ(n + 1 - k) × n^k} $$

where $Γ(x + 1)$ is the Gamma function shifted by one unit so it is equal to $x!$ for positive $x$.

In the original shared-birthday context, $n = 365$ (or $365.25$ or $366$, depending on how you deal with leap years), making the function $P_{365}(k) = 1 - \frac{Γ(365 + 1)}{Γ(365 + 1 - k) × 365^k}$. Plugging in values for $k$ lets you find that, for example, you only need a group of 23 randomly-chosen people to have a greater than 50% chance that at least two of them will share a birthday ($P_{365}(23) ≈ 50.73$%, or $P_{366}(23) ≈ 50.63$%).

My question is: is there a closed-form expression for an inverse function $k_{n}(P)$ that gives the number of randomly-chosen people needed for a given probability of a matching pair?

The function $P_{n}(k)$ fails the horizontal line test when looking at its entire domain, but if we restrict our view to the interval $1 < k < n + 1$ it passes. There are other functions that fail the horizontal line test over their full domain but which still have useful inverses, like the trig functions, so I'm hoping something similar can be constructed for this probability function.

Answer 1

As Тyma Gaidash commented, there is unlikely to be a closed form expression for the inverse of your expression, but there are reasonable approximations.

Your Wikipedia link says the equivalent of $$P_{n}(k) \approx 1-e^{k(k-1)/(2n)}$$ where $k$ is the number of people, $n=365$ is the number of days in a year, and $P_{n}(k)$ is the probability of at least one shared birthday. Solving this for $k$ (not necessarily an integer for given $n$ and $P_{n}(k)=p$) would suggest an approximation with the equivalent of $$ k \approx \tfrac{1}{2} + \sqrt{\tfrac{1}{4} - 2 n \log_e(1-p) }.$$

For illustrative values of $p$, estimating $k$ and then applying your expression to see the associated $p$, you would get

  p         k approx     implied p
  0.01      3.254405     0.01002512
  0.1       9.284257     0.10076962
  0.2      13.272815     0.20211667
  0.3      16.643813     0.30375442
  0.4      19.817161     0.40552901
  0.5      22.999943     0.50729545
  0.6      26.367784     0.60887877
  0.7      30.150466     0.71002659
  0.8      34.780310     0.81030374
  0.9      41.501672     0.90873600
  0.99     58.482965     0.99233016

so not too far away, but we can do better.

The error in that approximation for $k$ is not far from $\frac13\log_e(1-p)$ for moderate values of $p$ so we could refine the approximation to something like $$ k \approx \tfrac{1}{2} + \sqrt{\tfrac{1}{4} - 2 n \log_e(1-p) }+\tfrac13\log_e(1-p).$$ This would then give

  p         k approx     implied p
  0.01      3.251055     0.01000001
  0.1       9.249137     0.10000152
  0.2      13.198433     0.20000615
  0.3      16.524922     0.30001387
  0.4      19.646886     0.40002454
  0.5      22.768894     0.50003789
  0.6      26.062353     0.60005330
  0.7      29.749142     0.70006948
  0.8      34.243831     0.80008346
  0.9      40.734144     0.90008642
  0.99     56.947908     0.99003559

and it would be possible to improve this further.