Exact Solutions of the Generalized Birthday Problem Bruce Levin Assume N people are in a room. What is the smallest N such that there is at least probability 0.5 that M people have the same birthday? Assume the birthday distribution is uniform over 365 days. Assume X~Mult(N;P) on k=365 categories, with P=(1/365,...,1/365) and calculate Prob(M;N) = P[max X[i] is at least M] using the exact method of Levin, "A representation for multinomial cumulative distribution functions", Annals of Statistics, 9:1123-1126 (1981). M N Prob(M;N) ----- ----- --------- 1 1 1 1 0 0 2 23 0.507297234324 2 22 0.475695307663 3 88 0.511065110625 3 87 0.499454850632 4 187 0.502685373189 4 186 0.495825706383 5 313 0.501070475849 5 312 0.496195571644 6 460 0.50244941037 6 459 0.498637523705 7 623 0.502948948663 7 622 0.499795687887 8 798 0.500320275207 8 797 0.497616714463 9 985 0.500948416378 9 984 0.498568067031 10 1181 0.500931161057 10 1180 0.498796176416 11 1385 0.501001958747 11 1384 0.499059528126 12 1596 0.501166734721 12 1595 0.499379622274 13 1813 0.501104224633 13 1812 0.499445407288 14 2035 0.500348626509 14 2034 0.498798065243 15 2263 0.501295448239 15 2262 0.499836197505