-1

I was doing a Monte Carlo implementation of the Birthday Paradox in Python and I wanted to check if the results where the same as in the analytical implementation of the same problem (As they should be).

The question I'm answering is:

If 20 people are chosen at random, what is the probability that some of them share the same birthday?

To my surprise I get a systematically slightly higher value of the estimated probability using the Monte Carlo Method than the one I'm getting with the analytical solution.

I'm assuming a 365 days year and uniform probabilities for the birthdays.

the code for the Monte Carlo implementation is the following:

def MonteCarloBDay(num_people,num_simu):
    Bool = np.zeros(num_simu)
    for i in range(num_simu):
        test = np.random.choice(range(365),size=num_people, replace=True)
        Bool[i] = (len(set(test))!=num_people) # Check if we have             num_people different birthdays --> If we do, then it means that no couple of people have the birthday in the same day
    return np.mean(Bool)

The code for the analytical implementation is the following:

def PropShareSameBirthday(n):
    NumPairs = n*(n-1)/2
    ProbDiffBirthday_2People = 1 - 1/365 # We consider 366 days and uniform probabilities
    ProbNoCoupleHaseSameBirthday = ProbDiffBirthday_2People**NumPairs
    return 1-ProbNoCoupleHaseSameBirthday

The results I get from running the Monte Carlo 20 times with num_people = 20 and num_simu = 1e5 are:

Results = [0.41207, 0.40994, 0.41335, 0.41142, 0.40799, 0.4107 , 0.41296, 0.41209, 0.41211, 0.41397, 0.41257, 0.4118 , 0.40946, 0.41218, 0.41281, 0.41194, 0.41123, 0.41268, 0.41195, 0.40982]

with a mean of 0.4116

The result I get from the analytical version is AnaliticalProb = 0.4062.

When I run a t-test to check if the mean of the Results I got from Monte Carlo could be 0.4062 I get the following result:

stats.ttest_1samp(Results,AnaliticalProb)

Ttest_1sampResult(statistic=16.734969235912583, pvalue=7.910033425967028e-13)

Rejecting the Null Hypothesis with really high confidence.

I must have an error in one of the two implementations, but I can't seem to find where. Please let me know if you see some problem with my code or my reasoning.

  • 1
    Just to clarify the question, I'm assuming it is "why are the random results biased higher than the analytical result - in particular, no random result (in a sample of 20) falls at or below the analytical result, but many fall significantly above, suggesting systematic bias". – Steve Nov 24 '19 at 16:31
  • 1
    @Steve Exactly, thanks for clarifying for everybody – Edoardo Busetti Nov 24 '19 at 16:34
4

Consider when your number of people, n, is 366.

Using your proposed analytic solution for n=366, you get NumPairs = n*(n-1)/2 = 66,795. You then say that the probability of two people having different birthdays, let's call that PD2, is PD2 = 1 - 1/365 = 364/365. You then say that the probability that none of the 66,795 pairs of people have the same birthday is PD2**NumPairs, ie, (364/365)**(66,795) which is going to be a very small number, approximately 2.6E-80, but still something bigger than zero.

But think of it... How can 366 people possibly all have different birthdays? (Remember you decided to only allow 365 days, ignoring Feb 29, which is possible in leap years.) If 365 people all have different birthdays out of a pool of 365 possible birthdays, they are all taken, and there are no birthdays left for the 366th person to have that won't already match someone else's birthday. This sort of thing is known as the "pigeon-hole principle".

So you see, your proposed analytic solution must be wrong. But where?

The problem is when you multiply the probabilities of each pair having different birthdays all together to get the chance of them all having different birthdays. (Key Point:) You can only multiply probabilities when they are independant; these are not, not when they have to hold simultaneously.

Suppose you and two friends, Alice and Bob, each flip a coin? What is the probability that all three of you got a different result? IE, You != Alice, You != Bob, and Alice != Bob?

Your proposed analytic solution is saying:

  • The chance that You != Alice is 1/2
  • The chance that You != Bob is 1/2
  • The chance that Alice != Bob is 1/2
  • So the chance that all three are different is (1/2)^3 = 1/8.

But that can't be! Since the only possible results are heads and tails, there is no way all three of you can have different results.

The problem is when you try to string 'and' together. You need to consider the successive probabilities given that the previous probabilites ended up true:

  • The chance that You != Alice is 1/2
  • The chance that You != Bob -- given that You != Alice -- is still 1/2,
  • So the chance that You != Alice and You != Bob is 1/2 * 1/2 = 1/4
  • Now the chance that Alice != Bob -- given that You != Alice and You != Bob -- is not 1/2!
  • If You != Alice and You != Bob, then it must be that Alice = Bob!
  • So the chance that Alice != Bob -- given that You != Alice and You != Bob -- is actually 0!
  • Thus the chance that You != Alice and You != Bob and Alice != Bob is 1/2 * 1/2 * 0 = 0
  • n*(n-1)/2 is 190 for 20 pairs. (364/365)^190 gives 0.593..., 1 - 0.593...=0.407... – Pieter B Dec 6 '19 at 11:00
  • Yes, for n=20, n*(n-1)/2 = 190. But if the proposed analytic solution is valid, it should work for n=366. That's what I'm computing above, and showing that it fails for n=366, hence cannot be a correct solution. – WRSomsky Dec 6 '19 at 17:57
  • This is the answer. The approach for calculating the chance that no one has the same birthday is incorrect. I'm slightly under-caffeinated but I think its: 2 people 364/365, 3: (364/365) * (363/365), 4: (364/365) * (363/365) * (362/365) etc. the OP is using (364/365)^n – JimmyJames Dec 6 '19 at 18:21
0

According to wikipedia, the probability for 20 people should be 41.1% , which means your monte-carlo is correct and your analytical calculation is incorrect or an approximation at best.

Looking at the wikipedia, I find the best fit for your analytical solution is A simple exponentiation equation, which is titled as an approximation. The exact solution, as shown on the wiki page, requires factorial and a binominal coeficient, which I don't see in your analytical solution.

  • Thank you for your answer, I've seen on Wikipedia that this problem could be solved using factorials, but I wanted to solve it analytically with a different logic. The logic behind my equation is: For any possible couple of people if no couple has the same birthday. then all of the people have different birthdays. What I'm asking essentially is where that logic is flawed or where the code to implement that logic is flawed. – Edoardo Busetti Nov 25 '19 at 10:43
  • 1
    @EdoardoBusetti If you want your analytical "different logic" verified, then I recommend math.stackexchange.com – Euphoric Nov 25 '19 at 10:45
  • The thing with "different logic", like with "alternative facts", is that if it's wrong it's just wrong :-) – Hans-Martin Mosner Nov 25 '19 at 11:51
  • @Euphoric Thanks, I will publish there! – Edoardo Busetti Nov 25 '19 at 15:03
  • @Hans-MartinMosner Hehe I guess so, but knowing where I'm wrong could help me not make the same mistake in the future – Edoardo Busetti Nov 25 '19 at 15:04
0

WRSomsky's answer tells you what is wrong at a high level but I think it's helps to simplify the problem to see where you've gone wrong. Replace people with dice.

What is the chance you roll two dice and get the same number on both:

Easy: 1 out of 6. What ever you roll on the first, you have a 1/6 chance to roll on the second.

What is the chance you roll three dice and get the same number on a least two:

A little more tricky but you've got this figured out. You need to subtract the chance that all three are different from one. The chance they are all different is (5/6) * (4/6).

For four it's (5/6) * (4/6) * (3/6). For 7 it's (5/6) * (4/6) * (3/6) * (2/6) * (1/6) * (0/6) = 0

Now look at your analytic algorithm. Do you see the error?

Not the answer you're looking for? Browse other questions tagged or ask your own question.