Mini Program: Probability of Same Birthday Day
by Guillermo Castarés
Dic-2018
Given a group of n people, what is the probability that at least two of them share the birthday day?
Takes n from register X and put result on the same register.
Important program to have if you like to bet ;-)
Stack not preserved.
No flags and data registers used.
Examples of use:
10 [Psbd]
0.1169
23 [Psbd]
0.5073
25 [Psbd]
0.5687
50 [Psbd]
0.9704
70 [Psbd]
0.9992
Code:
00 { 32-Byte Prgm }
01>LBL "Psbd"
02 1
03>LBL 00
04 366
05 RCL- ST Z
06 365
07 ÷
08 ×
09 DSE ST Y
10 GTO 00
11 1
12 X<>Y
13 -
14 END
(12-05-2018 06:09 PM)morex Wrote: [ -> ]Given a group of n people, what is the probability that at least two of them share the birthday day?
What about a direct solution?
Code:
00 { 26-Byte Prgm }
01>LBL "BDAY"
02 365
03 X<>Y
04 PERM
05 365
06 LASTX
07 Y^X
08 ÷
09 1
10 X<>Y
11 -
12 END
Yes, on a real hardware 42s this will overflow for n > 195. Unlike your program that shoud be able to handle such cases.
But then... for n ≥ 135 the 12-digit result is 1 anyway. ;-)
Dieter
The generalised birthday problem (probability of at least n people in a group sharing a birthday) is a lot harder. Probably intractable on a HP-42S. (Now there's a challenge!)
(12-06-2018 04:32 AM)Valentin Albillo Wrote: [ -> ]Birthday problem generalizations
The probability of being born on February 29th is NOT zero. The above document seems to utterly ignore leap year babies.
(12-06-2018 04:32 AM)Valentin Albillo Wrote: [ -> ] (12-05-2018 11:46 PM)ijabbott Wrote: [ -> ]The generalised birthday problem (probability of at least n people in a group sharing a birthday) is a lot harder. Probably intractable on a HP-42S. (Now there's a challenge!)
Intractable on a 42S?
Birthday problem generalizations
V.
Specifically, the Multiple Birthday Problem. You may be able to get approximate results (up to about 3 decimal places) using Levin's approach mentioned in that paper, but a combinatorial approach blows up too quickly as
n increases, rendering it unsuitable for computation on a HP 42S.
I did knock up a program in C++ (but really C style but using C++ for convenence) using the GNU Multiple Precision library (which is a PITA to use in C, hence the use of C++ for convenience) to generate exact probabilities a while ago, although I'm not proud of it as the calculations are far from optimal (too many repeated sub calculations). Anyway, here is is:
ian-abbott/birthdays.cpp (
raw).
(12-06-2018 05:54 AM)Joe Horn Wrote: [ -> ]The probability of being born on February 29th is NOT zero. The above document seems to utterly ignore leap year babies.
Assume a spherical cow.
(12-06-2018 05:54 AM)Joe Horn Wrote: [ -> ]The probability of being born on February 29th is NOT zero.
Of course it's not zero (0.00068 > 0), no one would say it is so no need to highlight the "NOT", everybody knows that.
Quote:The above document seems to utterly ignore leap year babies.
Me too, I've never met anybody born on that date.
V.
(12-06-2018 03:59 PM)Valentin Albillo Wrote: [ -> ] (12-06-2018 05:54 AM)Joe Horn Wrote: [ -> ]The probability of being born on February 29th is NOT zero.
Of course it's not zero (0.00068 > 0), no one would say it is so no need to highlight the "NOT", everybody knows that.
I was NOT highlighting it; I was following HP Prime syntax, which insists on NOT being capitalized.
EDIT: Come to think of it, here's a mini-challenge for ya: Write a program for the Same Birthday Probability problem, taking leap years into account.
EDIT 2: Never mind, the following delightful article fully explains the solution and its impact on the probabilities, which (as everybody said above) is minimal.
http://www.efgh.com/math/birthday.htm
Learning about approximating summation formula, and apply to same birthday problem.
From Fundamentals of Numerical Analysis, by Stephen Kellison, page 139:
Σf = Δ-1 f
= (eD - 1)-1 f
= (D + D²/2! + D³/3! + D4/4! + ...)-1 f
= (D-1 - ½ + D/12 - D³/720 + ...) f
Approximate Σf using 3 terms:
XCas> f := ln(1-x/365)
XCas> expand(int(f) - f/2 + diff(f)/12)
\(365 - \frac{1}{(1-x/365)*4380} - \frac{731*ln(1-x/365)}{2}\) + x*ln(1-x/365) - x
Drop constant of integration, and simplify:
XCas> g(x) := ln(1-x/365) * (x-365.5) - x - 1/(4380-12*x)
XCas> g1 := g(1) // g1 ≈ -1/4379.99999
XCas> P(n) := 1 - e^(g(n)-g1) // approximated probability, very good
XCas> map([10,23,25,50,70], n -> [n, P(n), 1. - e^sum(f, x=1 .. n-1)])
\(\begin{bmatrix}
10 & 0.1169481777 & 0.1169481777 \\
23 & 0.5072972343 & 0.5072972343 \\
25 & 0.5686997040 & 0.5686997040 \\
50 & 0.9703735796 & 0.9703735796 \\
70 & 0.9991595760 & 0.9991595760 \\
\end{bmatrix}\)