Generalized variation of birthday problem: k-wise collisions for particular person

Question

In a room with n other people what is the expected value of n for k other people to share the same birthday as me?

I know from this very helpful wikipedia article that the probability for $k=1$ can be represented as:

$$q(n;d) = 1 - \left(\frac{d-1}{d}\right)^n$$

where d is some number of equally likely birthdays.

I found approximations for the canonical birthday problem extended to k collisions in this post. I'm looking for a similar generalization but applied to the same birthday as me variation.

I am planning on running some simulations so computability of the solution is a factor. A good approximation will be more than sufficient.

Answer 1

Using standard assumptions (birthdays i.i.d. uniformly across $d$ days), then

• the probability that $k$ out of $n$ other people share your birthday is binomial: $\mathbb P(K=k)={n \choose k}\frac{(d-1)^k}{d^n}$
• the probability at least $k$ share your birthday is $\mathbb P(K\ge k)=\frac{\sum_{i=k}^{n}{n \choose i}(d-1)^i}{d^n} = 1-\frac{\sum_{j=0}^{k-1}{n \choose j}(d-1)^{n-j}}{d^n}$
• which in the case $k=1$ gives $\mathbb P(K\ge 1) = 1-\frac{(d-1)^{n}}{d^n}$, as you already have

The expected number who share your birthday is $\mathbb E[K]=\frac{n}{d}$

If instead $k$ is fixed and you increase $n$ until $k$ matches occur, you have a version of the negative binomial distribution, the sum of $k$ geometric distributions each with expected value $d$, so $\mathbb E[N]=kd$

The Wikipedia article's same birthday as you variant in fact looks at the question of the minimum $n$ where $\mathbb P(K\ge 1)\ge \frac12$, and this would be $n = \Big\lceil\frac{\log(2)}{ \log(d)-\log(d-1)}\Big\rceil$. There is not such a simple calculation for the more general $\mathbb P(K\ge k)\ge \frac12$, but the number rises by close to $d$ each time $k$ increases by $1$. For example with $d=365$, you would get

k  min(n: P(K>=k)>=1/2)  difference

 1         253               
 2         613              360  
 3         976              363
 4        1340              364 
 5        1705              365 
 6        2070              365 
 7        2435              365 
 8        2799              364 
 9        3164              365 
10        3529              365