(42S) Probability of Same Birthday Day

[morex]

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

[Dieter]

(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

[morex]

(12-05-2018 08:36 PM)Dieter Wrote:  What about a direct solution?

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

Nice. Thanks!

[ijabbott]

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!)

[Valentin Albillo]

(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.

[Joe Horn]

(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.

[ijabbott]

(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.

[Valentin Albillo]

(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.

[morex]

Quote:Me too, I've never met anybody born on that date. Smile

Superman! :-)

[Joe Horn]

(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

[Albert Chan]

Learning about approximating summation formula, and apply to same birthday problem.
From Fundamentals of Numerical Analysis, by Stephen Kellison, page 139:

Σf = Δ^-1 f
= (e^D - 1)^-1 f
= (D + D²/2! + D³/3! + D⁴/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}\)