At the classic version of the birthday problem we check for collisions of scalars $ b_i $ sampled from a uniform distribution. How can this be generalised over sets with more than one samples per person? E.g. in the case of two dates (birthday and name day), we will have to pick a set of two scalars $\mathbf{b}_i = \{b^1_i, b^2_i\}$ for each person. If a collision means that the two sets over two random people are identical, which is the probability of a collision for a population of $m$ people?

  • $\begingroup$ If a collision means the birthdays match and the name days match, you are just drawing from a distribution of $365^2$ possibilities. The generalized birthday problem covers that. $\endgroup$ – Ross Millikan Mar 25 '17 at 19:49
  • $\begingroup$ I assume no ordering in the set, so $ \{b_i^1, b_i^2\} $, $ \{b_i^2, b_i^1\} $ collide $\endgroup$ – Dionysis M Mar 26 '17 at 1:13
  • $\begingroup$ Then you have $\frac 12 (365)(366)$ possibilities. $365$ of them, the cases where the two dates are the same, are half as likely as the others, but that is the only difference with the usual generalized problem. It will make the algebra more messy because you have to keep track of the two. $\endgroup$ – Ross Millikan Mar 26 '17 at 14:02
  • $\begingroup$ thanks. How is this generalized over sets of cardinality $n$ ? $\endgroup$ – Dionysis M Mar 27 '17 at 9:42
  • $\begingroup$ Wikipedia has a discussion. You just replace $365$ in the calculation with $n$. The number of draws to have $\frac 12$ chance of having a hit is about $\sqrt{2n \ln(2)}$ $\endgroup$ – Ross Millikan Mar 27 '17 at 14:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.