How many friends do you need to make on Facebook in order to have at least one friend happy birthday every day of the year with a probability close to 100%?

Question

Mathematics

An interesting task.
More specific statement: An empty array is gradually filled with elements. Each element stores a numerical value in the range from 0 to 365, chosen at random.
Question:
How many elements should be added to the array so that with probability P each number from 0 to 365 is contained in it at least once.
Probability P:
1) 25%
2) 50%
3) 75%
4) ~99%
5) 100%
Maybe it can be nicely calculated in Mathematica?

Answer 1

If you need to find the exact probability that all birthdays are filled, then the formula is complicated. An equivalent formulation is to find the number of M-digit numbers in the base N number system in which all N digits occur.
We consider sets of N numbers a1,a2,a3,...,aN for which ai>=0 and a1+a2+...+aN=MN, and for all such sets (their C(M-1,N- 1), sets with different orders are considered different) we consider the sum S of the values ​​1^a1+2^a2+...+N^aN. Then the desired number of numbers is equal to S*N!, and the required probability is S*N!/(N^M).
The approximate probability, when M is noticeably greater than N, is easier to find. The probability that there will be no birthday on a given day is (1-1/N)^M, and the probability that there will be at least one birthday every day is (1-(1-1/N)^ M)^N (here we consider the events to be independent, which is generally not true). For large N and M/N, this can be estimated as exp(-N*exp(-M/N)). If N=365, then 3833 friends are needed to reach the 99% probability, and 4675 friends for the 99.9% probability.
The presence of February 29 further complicates the picture.
Answers to questions 1-5 with N=366: 2041, 2295, 2617, 3844, infinity.
Clarification: the number S, which is obtained in the exact solution, is the Stirling number of the second kind S(M,N) . The link has a simple explicit formula.

Answer 2

Enough 366 friends who were added purposefully with non-recurring dates. The condition of the problem does not prohibit such a solution.

Answer 3

It's almost like the birthday paradox. Each friend corresponds to a number from 0 to 365. Thus, N friends generate a number in the number system in base 366. You need to combinatorially calculate the number of such numbers M, which contain all the different digits, for each N. The ratio M/(366^N) and will be your probability.
Obviously, it is necessary to consider N>=366
M - the number of possible arrangements of 366 digits in N places, free places can be filled with any digits. For N=366, this is 366!, giving a probability of 10^-158 degrees.
As N increases, the formula for the number M becomes more complicated, it will be M=(366!)*(binomial coefficient from 366 to N-366).
Consider.

Answer 4

You need the distribution of birthdays by region in which you are looking for friends. And based on this distribution, calculate the confidence intervals for each day... The math can be a little tricky, but you can definitely write a program that emulates a given distribution, add N friends and see if they cover the whole year or not. Run the algorithm 1000 times for each N and get a practical probability for a given N. Then adjust N until you get the desired probability (99%, 99.9%).

Answer 5

Sociologists are aware of the phenomenon that on some days of the year there are extremely high and extremely low number of births. Especially in Southeast Asia. Therefore, the problem has a mathematical, but not an applied solution.