Combinatoric Birthday Paradox

Question

There is likely a closed form solution for this problem but it's had me puzzled for days. This is about a variant on the classic birthday paradox. To recap, the birthday paradox is where given only 23 students the probability that two have the same birthday is > 0.5.

The variant is this: If each student has two (or K) special days, what is the probability that given N students each student has at least one special day that is unique to them.

I stumbled across this problem while working on a related cryptographic algorithm.

Another way of phrasing this is in terms of a lottery: If a lottery drawing consists of 5 random numbers (with repetition) drawn from a set of 100 numbers, after N drawings what is the probability that each drawing had at least one unique number among it's 5.

Explicitly, given these variables:

$C = $ the size of the set of choices (e.g. 100 for the lottery or 365 for the special days)

$K = $ # of random choices for each event (e.g. 5 for the lottery, 2 for the special days)

$N = $ # of events that have taken place (e.g. lottery drawings, or number of students)

Here is what I'm trying to solve for:

$P(C, K, N) = $ the probability that after N events, where each draws K random items from a set of C items, each event has at least one item that was not drawn in any other event.

Note that $P(C, 1, N)$ provides the solution to the classic birthday paradox.

To be clear, repetition is allowed. That is, a student could have the same special day twice, or the lottery drawing could be (5, 5, 78, 10, 5). In that event, if at least one of those numbers was never seen before, it counts as unique.

The best I've come up with is this:

Given a function, $Q(C, K, N)$ that computes the probability that the $N^{th}$ event has at least one unique value:

We would get these values in the student scenario:

$$ Q(2, 365, 0) = 1 - \frac{0}{365}\frac{0}{365} = 1.00000 $$ $$ Q(2, 365, 1) = 1 - \frac{2}{365}\frac{2}{365} = 0.99996 $$ $$ Q(2, 365, 2) = 1 - \frac{4}{365}\frac{4}{365} = 0.99987 $$

And similarly for the lottery drawing:

$$ Q(5, 100, 0) = 1 - \frac{0}{100}\frac{0}{100} = 1.00000 $$ $$ Q(5, 100, 1) = 1 - \frac{5}{100}\frac{5}{100} = 0.99999 $$ $$ Q(5, 100, 2) = 1 - \frac{10}{100}\frac{10}{100} = 0.99999 $$

This generalizes to:

$$ Q(C, K, N) = 1 - (\frac{N * K}{C})^K $$

If $Q$ computes the probability of any given student having at least one unique day than the probability of N events all having at least one unique day is just multiplying all of the probabilities together:

$$P(C, K, N) = \prod_{n=0}^N 1 - (\frac{n * K}{C})^{K}$$

This looks promising because for the case where $K = 1$, this simplifies to:

$$\prod_{n=0}^N \frac{C - n}{C}$$

which is the formula for the traditional birthday paradox.

The problem is that this proposed formula, beyond $K=1$, isn't actually correct, as verified by a monte-carlo simulation I've been running to compare it against.

I can't seem to wrap my head around what the problem is though. I've tried about a dozen different ways to approach the problem. It seems that there may be no closed form solution, unfortunately.

Answer 1

I think the formula is more like that:

$$ P(C,K,N)= \left(\prod_{n=0}^{N-1}\frac{C-n}{C}\right)\left(\frac{C-N+1}{C}\right)^{(K-1)*N} $$

Intuitively, you have to choose the $N$ draw that will be unique. There are $C$ possibilities among $C$ for the first $C-1$ among $C$ for the second and so on (hence the $\prod_{n=0}^{N-1} \frac{C-n}{C}$).

Ten you have to choose the other draws. You cannot pick the unique one (unless the one the is in the same event as you) hence there is $C-N+1$ choices possible among $C$ and there are $(K-1)*N$ such draw (hence the $\left(\frac{C-N+1}{C}\right)^{(K-1)*N}$).

Answer 2

I'm rewriting this answer completely because I found the error in my previous attempt. As before I'm dealing only with the $K=2$ case (students' special days).

Let $d$ be the number of students who still have both items unique to them, $s$ be the number of those who have only one unique item and $u$ the number of items which are shared by two or more students. If $p(s,u,d)$ is the probability of having such numbers, then we have the following recursive relation: \begin{equation} \begin{split} p(s,u,d)&=p(s-1,u,d) \left(1-{s+u+2d-1\over C}\right){1+2u\over C}+\\ &+p(s,u,d-1) \left(1-{s+u+2d-1\over C}\right)\left(1-{s+u+2d-2\over C}\right)+\\ &+p(s-2,u-1,d+1)\cdot 2{2d+2\over C}\left(1-{s+u+2d-1\over C}\right),\\ \end{split} \end{equation} where $C$ is the number of days in one year. This must be supplemented with the appropriate starting values: \begin{equation} \begin{split} &p(0,0,1)={C-1\over C},\ \ p(1,0,0)={1\over C},\ \ p(0,0,0)=0,\\ &p(s,u,d)=0\ \ \hbox{if $s<0$ or $u<0$ or $d<0$},\\ &p(s,u,d)=0\ \ \hbox{if $u>s/2$}.\\ \end{split} \end{equation} With respect to my previous solution there is one more complication, due to the presence of variable $u$, but now all results are fine: I've checked them with an explicit calculation in the case $C=5$. To get the probability $p_{tot}$ that given $N$ students all of them have at least one unique item, one has to sum up all the relevant $p(u,s,d)$. For instance: $$ p_{tot}(3)=p(3,0,0)+p(3,1,0)+p(2,0,1)+p(2,1,1)+p(1,0,2)+p(0,0,3). $$ This probability falls below $50$% for $31$ students: $p_{tot}(31)=0.489694$.