How many people must be at a party before you have even odds or better of two having the same bithday (not...
probability/birthday/same.day Added material
Problem
How many people must be at a party before you have even odds or better of two having the same bithday (not necessarily the same year, of course)?
Show solution
Assume people are selected at random, and that their birthdays are uniformly and independently distributed over the 365 days of the year excluding Feb. 29. Think instead about the probability, among n people, that none of them share a birthday. For a set of one person, the odds that he/she shares a birthday with no one else in the set is 1. Adding a 2nd person, the person can have 364 of 365 possible birthdays. Adding the 3rd, he/she can have any of 363 b'days, etc. So the desired expression for the odds that no one shares a b'day is: (365*364*...*(365-n+1)/365^n, and subtract that from 1 to get the odds that two people share a birthday. For n=22, this gives a probability of .476, and n=23 gives .507. see also entry "coupon" see also entry "line"
Additional material
Exact Solutions of the Generalized Birthday Problem
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 B. 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
I am grateful to Professor Bruce Levin for providing this table.
[ Editor: From the web page "Exact Solutions of the Generalized Birthday
Problem", www.mathsoft.com, 1998. ]
In article <4i6d1p$krg@elna.ethz.ch>, Hanspeter Schmid asked:
> 1. How many people need to gather to give a better than 50% probability
> that three people will have the same birthday (assuming that
> birthdays are spread evenly throughout the year)?
>
> 2. ... four people ...
>
> 3. ... n people ...
Assume birthdays are chosen uniformly at random from a year of 365 days.
Here are some probabilities that no 3 people (out of N) have the same
birthday.
N prob = p(N)
40 .9331105142
50 .8736248158
60 .7927696794
70 .6935126730
80 .5818310663
85 .5238117072
86 .5121737107
87 .5005451494
88 .4889348894
89 .4773517385
90 .4658044285
Your question asks for the complementary event, that at least 3 people
out of N have the same birthday. Its probability is 1-p(N). So you
need at least 88 people to have more than a 50% chance for this to
occur. 87 people gives you a near miss, at 1-p(87) = 0.4994548506
The formula that gives these numbers is as follows: let
f(x) = ( 1 + x + (x^2)/2 )^365.
Then f(x) is a polynomial in x of degree 730,
f(x) = sum( c(k) x^k , 0 <= k <= 730 )
Then p(N) = c(N) N! / 365^N
-- Barry Wolk <wolk@ccm.umanitoba.ca>
My solution works with the counting of lists. First, I calculate the
probability that NO three among n people share the same birthday if
the year has d days.
B is the ordered list of the birthdays of the people gathering:
B = {b1, b2, b3, ... bn}
Since every element bi can take on d different values with the same
probability 1/d, the probability that a certain list B occurs is
P[B] = (1/d)^n
My next list S (S stands for summation) is an ordered list
S = {s1, s2, s3, ... sd}
where si tells me how many people's birthday day i is. Therefore list
S tells me which numbers occur in the list B which produce this S and
how many times they occur. So every possible permutation of B will
give the same list S, and there are
#B c S = n! / (s1! s2! ... sd!)
different lists B which produce a certain S. I do exactly the same
again, which gives me the ordered list A (A stands for again):
A = {a0, a1, a2, ..., an}
where ai tells me how many days of the year are exactly i people's
birthday. Since the step from S to A is exactly the same as from B to
S,
#S c A = d! / (a0! a1! ... an!)
is the number of lists S that produce a certain list A. Inspection of
the term (s1! s2! ... sd!) shows that the order of the elements of S
is irrelevant as far as (#B c S) is concerned. In fact, ai tells me
how many times the factor i! occurs in (s1! s2! ... sd!). Therefore
#B c S = n! / ( (0!)^a0 (1!)^a1 ... (n!)^an )
Every list S that produces a certain A can result from exactly the
same number of lists B, and therefore
#B c A = (#B c S) (#S c A)
= n! d! / ( (0!)^a0 (1!)^a1 ... (n!)^an ) (a0! a1! ... an!)
Therefore the probability that a certain list A occurs is
P[A] = (#B c A) P[B]
= n! d! / d^n ( (0!)^a0 (1!)^a1 ... (n!)^an ) (a0! a1! ... an!)
If I want the probability that no three people share the same
birthday, I have to sum P[A] up for all possible lists A with ai=0 for
all i>=3. Inspection gives that a0+a1+a2=d, the number of days in the
year, and a1+2*a2=n, the number of people. Therefore I have to sum up
over all
A = { d-n+a2, n-2*a2, a2 }
for a2=0..n/2 which gives the probability P[no three people].
Then P[three people] = 1 - P[no three people]
You'd rather use a computer program to calculate all of this, and the
results are:
three people ... 88 people have to gather
four people ... 187 people have to gather
five people ... 313 people have to gather
-- Hanspeter Schmid <schmid@isi.ee.ethz.ch>
Using a quick and dirty Monte Carlo algorithm, I think the answer is
around 87 or 88. Here's the program:
#define MAX_PEOPLE 100
#define MAX_TRIALS 10000
#include <stdlib.h>
int random_in_range (int n, int k)
{
/* returns 1 with a probability of n/k */
return (((double)rand())/((double)RAND_MAX)*k)<n;
}
void main ()
{
int n_people;
int n_trial;
int n_person;
for (n_people=3;n_people<MAX_PEOPLE;n_people++) {
int successes=0;
for (n_trial=0;n_trial<MAX_TRIALS;n_trial++) {
int tri=0; /* do 3 people so far share a birthday? */
int duo=0; /* How many birthdays are shared by at least two people? */
int sin=0; /* How many birthdays is used by at least one person? */
for (n_person=0;n_person<n_people;n_person++) {
if (random_in_range(365-sin,365)) /*New birthday */
sin++;
else if (random_in_range(sin-duo,sin)) /* Shares with only one */
duo++;
else /* Shares with a pair */
tri=1;
} /* person for */
if (tri) successes++;
} /* trial for */
printf("For %5d people there were %5d successes out of %5d trials.\n",
n_people, successes, MAX_TRIALS);
} /* people for */
}
-- Wei-Hwa Huang <whuang@cco.caltech.edu>
I have found the dates of this my small note in: Technical Report
'Sources in Recreational Mathematics' by D. Singmaster (1993):
The first reference (the source) for the Extended-Birthday-Problem
and the solution is in AMM 67 (1960) p. 830 [Not-Yet-Seen]. In this
article is present the explicit formula for three (3) and the
solutions (using a Poisson approximation) for three, four, five:
three: 88 people ...
four: 187 people ...
five: 314 people ...
-- Mario Velucchi <velucchi@cli.di.unipi.it>
A Java page for the birthday problem:
http://www.cs.cornell.edu/home/karr/java/Birthday.html
-- David Karr <karr@cs.cornell.edu>
A related question: you want to find somebody with the same birthday as
yours. What's the least number of people you need to talk to to have a
50-50 chance? (Year of birth need not match.)
I assume you are finding these people at random, and that their
birthdays are uniformly and independently distributed over the 365
days of the year excluding Feb. 29 (which I assume is not your
birthday either).
Then any one person has 364/365 chance *not* to match your birthday.
You want the smallest N such that the chance of doing this N times
in a row is less than 1/2, that is, N such that
(364/365)^N < 1/2 < (364/365)^(N-1)
The answer is N = 253.
A way to get this quickly on a scientific calculator is to solve for
x in (364/365)^x = 1/2, which is the same as
x = (-log 2)/(log(364/365)) = 252.65.
You have to round upward to bring the final result below 1/2.
If you assume 365.2425 days per year (the correct number according to
the current civil calendar, though the last few digits are stretching
the point since the leap years are not quite evenly distributed over
the 400-year cycle), still uniformly distributed, and your birthday is
still not February 29, the probability of one person not matching you
is 364.2425/365.2425, and the answer is still 253.
But if your birthday is February 29, the probability of a person not
matching you is 365/365.2425, and the answer becomes 1044.
Did you mean to ask how many people you have to get together before
any two of *them* have the same birthday? Oops, that's an entirely
different question. According to your wording, you could gather
together 100 different matching birthday pairs and yet still not have
"success" because none of them happens to match *your* birthday.
-- David A. Karr (karr@cs.cornell.edu)
[ Editor: from a Web page "An Analysis of the Distribution of Birthdays
in a Calendar Year". The page's graphs (images) and its data file are
not preserved. ]
In the newsgroup alt.fan.cecil-adams on Usenet, there was a discussion
of the number of persons needed in a room to get a greater than 50%
chance of having two persons with the same birthday or having every
birthday represented. Perry Farmer questioned the reasonableness of
the assumption of uniformity of the distribution of birthdays in a
calendar year. I opined that the distribution was reasonably close to
uniform. Having access to a large number of birthdates from life
insurance policy applications, I volunteered to analyze the available
data.
I retrieved birthdates from 480,040 insurance policy applications made
between 1981 through 1994 of a Life Insurance Company. I summarized the
data by date, by month and by day of month.
If we hypothesize that the distribution of birthdays is uniform, then
the probability of a birthdate (other than Feb. 29) is 1/365.25 and the
probability of a Feb 29th birthdate is 1/1461. We can conclude that
the number of people with a given birthday is a binomial distribution
with mean=n*p=1314.28 (328.57 for Feb. 29) and variance=n*p*q=1313.41
(329.03 for Feb 29). [ Editor: a graph of the actual observations with
the expected values followed. ]
With a number of expected successes this large, we can use a normal
distribution with the same mean and variance as a close approximation
to the binomial distribution. Thus the z-statistic ([obs-mean]/std.dev.)
should be observations from a standard normal distribution. The sum of
n, squared standard normal Random Variables is distributed Chi-square
with n-1 degrees of freedom. The sum of the squared z's for the 366
birthdates was 1356.5. Compare this to the 99.9%ile point of a
Chi-square with 365 d.f which is 454.2. The z2 statistic is higher
which causes us to reject the hypotheses of uniformity.
In less formal terms, the data show too much variation to be accounted
for by random deviations from binomial (or normal) distributions with
the same mean. [ Editor: a histogram of the z statistics, with a
standard normal distribution for comparison, followed. ] The data z's
show much more dispersion than the standard normal with fewer
observations near the mean and more observations further away.
The analysis by day shows some interesting results. The squared z's
when tabulated by day of the month was 247.3 and the corresponding
99.9%ile from a Chi-square with 30 d.f. is 59.7. Again a significant
departure from expected. The histogram shows that some days are over
reported. The highest positive deviations are from the 1st and 15th
with the 20th and the 10th sticking out somewhat less. The data were
collected by insurance agents asking the person their birthdate. The
data are not otherwise checked until a claim is made and a death
certificate shows a significantly different birthdate. I suspect that
older persons may not know their exact date of birth. I can see no
other reason for dates to fall on such regular points. It has been
well documented by the U.S. Census Bureau that people overreport the
year of birth 1900 and underreport 1899 and 1901. I ran a smaller run
(n=116,979) with years of birth between 1960 and 1993. The z-squared
statistic was still larger than the chi-square indicating a significant
deviation from uniformity, but much closer (z2=74.7) for what its
worth.
The analysis by month is also instructive. The z-square is 612.5 and
the corresponding 99.9%ile Chi-square is 31.3 for 11 degrees of
freedom. Again there is more variance in the data than can be
accounted for by chance. An examination of the histogram shows
significant seasonal variations. The months July - October show higher
than expected births and March - May show the most significant decline
in births. Perhaps the most reasonable explanation is that conceptions
are up in the months of October through January and down in June
through August. You be the judge.
The implications for the original questions are that slightly fewer
persons are needed to get a single match and slightly more persons are
needed to have every day covered if the distribution is not uniform.
-- Roy Murphy <murphy@panix.com>
[ Editor: a bare data file, collected separately and unsigned: the
number of birthdates falling on each calendar date (MMDD). It appears
to be the data file of Roy Murphy's analysis of 480,040 insurance
applications given above, whose data file was otherwise not preserved.
Its total line reads 481040; the analysis gives 480,040, and its mean
1314.28 = 480,040/365.25. ]
date count
0101 1482
0102 1213
0103 1220
0104 1319
0105 1262
0106 1271
0107 1355
0108 1219
0109 1253
0110 1339
0111 1293
0112 1295
0113 1296
0114 1333
0115 1409
0116 1330
0117 1286
0118 1268
0119 1336
0120 1422
0121 1318
0122 1302
0123 1296
0124 1226
0125 1298
0126 1241
0127 1289
0128 1284
0129 1313
0130 1280
0131 1207
0201 1379
0202 1404
0203 1329
0204 1292
0205 1326
0206 1295
0207 1253
0208 1252
0209 1231
0210 1287
0211 1305
0212 1320
0213 1266
0214 1353
0215 1307
0216 1258
0217 1284
0218 1306
0219 1340
0220 1364
0221 1233
0222 1238
0223 1289
0224 1330
0225 1270
0226 1288
0227 1310
0228 1319
0229 325
0301 1428
0302 1313
0303 1371
0304 1318
0305 1262
0306 1318
0307 1322
0308 1345
0309 1256
0310 1363
0311 1267
0312 1262
0313 1307
0314 1278
0315 1292
0316 1300
0317 1196
0318 1244
0319 1282
0320 1323
0321 1344
0322 1232
0323 1306
0324 1292
0325 1350
0326 1243
0327 1216
0328 1269
0329 1262
0330 1175
0331 1204
0401 1321
0402 1292
0403 1310
0404 1386
0405 1272
0406 1256
0407 1270
0408 1284
0409 1244
0410 1246
0411 1272
0412 1313
0413 1219
0414 1234
0415 1321
0416 1279
0417 1210
0418 1279
0419 1248
0420 1248
0421 1200
0422 1188
0423 1212
0424 1254
0425 1177
0426 1241
0427 1134
0428 1248
0429 1249
0430 1234
0501 1296
0502 1281
0503 1306
0504 1292
0505 1308
0506 1258
0507 1228
0508 1266
0509 1179
0510 1316
0511 1194
0512 1246
0513 1280
0514 1223
0515 1400
0516 1255
0517 1247
0518 1247
0519 1276
0520 1350
0521 1324
0522 1298
0523 1237
0524 1212
0525 1303
0526 1286
0527 1256
0528 1226
0529 1261
0530 1240
0531 1197
0601 1388
0602 1352
0603 1308
0604 1330
0605 1286
0606 1308
0607 1302
0608 1248
0609 1241
0610 1275
0611 1266
0612 1217
0613 1232
0614 1226
0615 1371
0616 1212
0617 1239
0618 1282
0619 1317
0620 1336
0621 1294
0622 1260
0623 1313
0624 1301
0625 1247
0626 1276
0627 1315
0628 1338
0629 1344
0630 1365
0701 1444
0702 1344
0703 1323
0704 1265
0705 1270
0706 1381
0707 1463
0708 1342
0709 1351
0710 1402
0711 1310
0712 1338
0713 1365
0714 1376
0715 1429
0716 1343
0717 1423
0718 1278
0719 1349
0720 1412
0721 1332
0722 1331
0723 1346
0724 1367
0725 1368
0726 1302
0727 1380
0728 1394
0729 1370
0730 1353
0731 1397
0801 1462
0802 1349
0803 1362
0804 1395
0805 1299
0806 1371
0807 1412
0808 1473
0809 1370
0810 1433
0811 1380
0812 1479
0813 1309
0814 1353
0815 1559
0816 1381
0817 1345
0818 1358
0819 1368
0820 1436
0821 1362
0822 1376
0823 1371
0824 1389
0825 1402
0826 1395
0827 1327
0828 1404
0829 1391
0830 1308
0831 1361
0901 1389
0902 1339
0903 1381
0904 1314
0905 1434
0906 1353
0907 1310
0908 1367
0909 1383
0910 1409
0911 1366
0912 1373
0913 1320
0914 1385
0915 1522
0916 1432
0917 1429
0918 1418
0919 1442
0920 1435
0921 1492
0922 1482
0923 1419
0924 1397
0925 1395
0926 1445
0927 1430
0928 1484
0929 1422
0930 1345
1001 1470
1002 1414
1003 1435
1004 1447
1005 1450
1006 1357
1007 1357
1008 1432
1009 1430
1010 1466
1011 1290
1012 1384
1013 1357
1014 1315
1015 1425
1016 1340
1017 1305
1018 1328
1019 1335
1020 1380
1021 1322
1022 1274
1023 1323
1024 1278
1025 1241
1026 1290
1027 1280
1028 1335
1029 1259
1030 1264
1031 1291
1101 1412
1102 1278
1103 1331
1104 1359
1105 1254
1106 1311
1107 1244
1108 1224
1109 1307
1110 1340
1111 1339
1112 1350
1113 1286
1114 1278
1115 1395
1116 1311
1117 1327
1118 1278
1119 1281
1120 1352
1121 1244
1122 1297
1123 1260
1124 1238
1125 1290
1126 1237
1127 1243
1128 1313
1129 1273
1130 1288
1201 1350
1202 1305
1203 1286
1204 1377
1205 1310
1206 1359
1207 1305
1208 1289
1209 1290
1210 1320
1211 1259
1212 1404
1213 1339
1214 1270
1215 1380
1216 1279
1217 1314
1218 1352
1219 1254
1220 1292
1221 1218
1222 1333
1223 1179
1224 1193
1225 1216
1226 1126
1227 1256
1228 1426
1229 1332
1230 1355
1231 1352
total 481040