Birthday problem (probability)

[r0bHadz]

Homework Statement

a)
Consider a class with 30 students. Compute the probability that at least two of them
have their birthdays on the same day. (For simplicity, ignore the leap year).

b)
How many students should be in class in order to have this probability above 0.5?

Homework Equations

The Attempt at a Solution

the answer to a is

P(at least two have birthday on same day) = 1 - P(none have bday on same day)

= 1 - ( (365)(364)...(336) / (365)^30 ) = about .71

Honestly, just computing the first answer was tedious enough. I had to multiply everything out and it took forever. So I decided to write a python script to make it faster.

Now for the second one it is

solving the equation 1- P(365,r)/365^30 > .5 => (365-r)! > (364!)/( (.5)(365)^29 )

but there must be some way to solve this without plug and chugging but my IQ is limiting me from arriving to how. Of course I can just plug numbers in but that doesn't seem practical. And my school doesn't allow graphing calculators, but even if it did I doubt the calc wouldn't overflow with numbers so large

 

[StoneTemplePython]

but there must be some way to solve this without plug and chugging but my IQ is limiting me from arriving to how. Of course I can just plug numbers in but that doesn't seem practical. And my school doesn't allow graphing calculators, but even if it did I doubt the calc wouldn't overflow with numbers so large

I'm not sure what your question is...

Let's start with an easier problem. If there are 30 students in a class, what's the expected number of pairs of people having the same birthday? (These are pairwise comparisons... so if Bob, Alice and RobHadz all have a birthday on Jan 2nd, then this is 3 'collisions')

Can you answer this?

 

[r0bHadz]

I'm not sure what your question is...

Let's start with an easier problem. If there are 30 students in a class, what's the expected number of pairs of people having the same birthday? (These are pairwise comparisons... so if Bob, Alice and RobHadz all have a birthday on Jan 2nd, then this is 3 'collisions')

Can you answer this?

The question would be: how can I find a way to solve for r without just plug and chugging? Is there some algebraic manipulation or something that I can do?

And I don't think I can answer that yet. The next chapter in my book is on expectation and variance. Without this knowledge, and just based on the day to day definition of "expectancy" I would say its well below .5 though

 

[StoneTemplePython]

The question would be: how can I find a way to solve for r without just plug and chugging? Is there some algebraic manipulation or something that I can do?

And I don't think I can answer that yet. The next chapter in my book is on expectation and variance. Without this knowledge, and just based on the day to day definition of "expectancy" I would say its well below .5 though

Ok then your underlined question exceeds your current grasp... this is a model problem for Poisson approximations (which you can easily get the answer for, working in logspace, and then plug in once to the actual formula to corroborate the exact solution). But you really should lock down the expected value first. (i.e. $\lambda = \text{expected value}$)

The birthday problem is a classic, and is used in many places (e.g. modelling collisions in hashtables, if you know some CS). Suggestion: return to this problem after you've gone through the section on expected values.

note: even for plugging and chugging, you can be smart about it -- e.g. do binary search while plugging. So you had to explicitly solve 30 students and found that is too much to get the the 50% probability, so then try 15 (which is too little) so then try 22 or 23...

solving the equation 1- P(365,r)/365^30 > .5 => (365-r)! > (364!)/( (.5)(365)^29 )

but there must be some way to solve this without plug and chugging but my IQ is limiting me from arriving to how. Of course I can just plug numbers in but that doesn't seem practical. And my school doesn't allow graphing calculators, but even if it did I doubt the calc wouldn't overflow with numbers so large

ok consider the complementary value: $\frac{P(365,r)}{365^{30}}$. Why are you talking about overflow? You should know to work in logspace for this... you might have to compute a few things by hand for the numerator (save the cumulative results in a table!) and obviously $\log\big(365^{30}\big) = 30 \cdot \log\big(365\big)$... so compute the answer in logspace and exponentiate your way out at the end.

 

[StoneTemplePython]

Ok, I have another idea of how to get to the Poisson approximation result without mentioning expected values. I'm a touch leery of this as a 'precalculus' forum idea, but

are you familiar with the result that $e^x \approx 1+x$ for 'small' $x$?

 

[WWGD]

Maybe another rule of thumb or useful result is : $0.71^2 =0.49$ close to 0.5. So you got this close with just 30 birthdays. So you need a new product involving 335, 335, etc. , to get close to .71. Sure they will . But still, I checked online and it seems like 23 people are enough for .49.

 

[r0bHadz]

Yes, it makes sense that e^x is approx = to 1+x for |x|< approx .5 and is especially close as x approaches 0

WWGD, that solution is brilliant.

 

[StoneTemplePython]

Yes, it makes sense that e^x is approx = to 1+x for |x|< approx .5 and is especially close as x approaches 0

ok so, write it out as a loose approximation for now

$\frac{P(365,r)}{365^r} = \big(\frac{365}{365}\big)\big(\frac{364}{365}\big)\big(\frac{363}{365}\big)...\big(\frac{365-(r-1)}{365}\big) = \big(1 - \frac{0}{365}\big)\big(1 - \frac{1}{365}\big)\big(1-\frac{2}{365}\big)...\big(1-\frac{(r-1)}{365}\big)$
$\approx e^{-\frac{0}{365}}\cdot e^{-\frac{1}{365}} \cdot e^{-\frac{2}{365}}\cdot ...\cdot e^{-\frac{(r-1)}{365}} = e^{\frac{-1}{365}(0 + 1 + 2 + ... + (r-1)}$

do you know how to get $\big(0 + 1 + 2 + ... + (r-1)\big)$ in closed form? (Hint: triangular number)

 

[Ray Vickson]

Homework Statement

a)
Consider a class with 30 students. Compute the probability that at least two of them
have their birthdays on the same day. (For simplicity, ignore the leap year).

b)
How many students should be in class in order to have this probability above 0.5?

Homework Equations

The Attempt at a Solution

the answer to a is

P(at least two have birthday on same day) = 1 - P(none have bday on same day)

= 1 - ( (365)(364)...(336) / (365)^30 ) = about .71

Honestly, just computing the first answer was tedious enough. I had to multiply everything out and it took forever. So I decided to write a python script to make it faster.

Now for the second one it is

solving the equation 1- P(365,r)/365^30 > .5 => (365-r)! > (364!)/( (.5)(365)^29 )

but there must be some way to solve this without plug and chugging but my IQ is limiting me from arriving to how. Of course I can just plug numbers in but that doesn't seem practical. And my school doesn't allow graphing calculators, but even if it did I doubt the calc wouldn't overflow with numbers so large

I think you are expecting too much. Sometimes the most practical way of getting an "exact" solution to a problem is to just go ahead and compute/plot and see where your resulting curve crosses the point of interest. So, if P(n) is the probability of (at least one) match in a group of size n, just plot P(n) vs. n and see where P(n) goes from < 0.5 to >= 0.5. If (as you say) you can write a Python script, that should be a snap. If you have access to any reasonable spreadsheet (EXCEL or an open-source alternative) that should be easy as well.

If you want some type of "symbolic" solution, involving nice functions and seemingly-nice equations you are likely out of luck, but various types of approximations (as suggested by others) may be available.

 

[Bosko]

You can do step by step calculation for n people.

Make two functions
Yes(n)= probability that at least two of them have birthday on the same day
No(n)=probability that everyone have the different birth day
You ca see that Yes(n)+No(n) =1 for any n

Yes(1)=0 - it is only one person . Can't have the same birthday as somebody else because it is only one person
No(1)=1 - Similar funny thinking

Yes(n)= Yes(n-1)+No(n-1) x (n-1)/365
Some of n people have a birthday on the same day if
- if some of n-1 people have a birthday on the same day and n-th person doesn't matter
- and if none of n-1 people doesn't have the same birthday but n-th person have the birthday on the same day as someone of them (n-1)/365

Also none of n people have a birthday on the same day if none of n-1 people nave a birthday on the same day
and n-th person have a birthday on some of other 365-(n-1) days
No(n)=No(n-1) x (365-n+1)/365

Excel Sheet ...
n 365-(n-1) No(n)
1 365 1.000
2 364 0.997
3 363 0.992
4 362 0.984
5 361 0.973
6 360 0.960
7 359 0.944
8 358 0.926
9 357 0.905
10 356 0.883
11 355 0.859
12 354 0.833
13 353 0.806
14 352 0.777
15 351 0.747
16 350 0.716
17 349 0.685
18 348 0.653
19 347 0.621
20 346 0.589
21 345 0.556
22 344 0.524
23 343 0.493 => Yes (23) = 1- 0.493 > 0.5
24 342 0.462
25 341 0.431
26 340 0.402
27 339 0.373
28 338 0.346
29 337 0.319
30 336 0.294