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

= (e^{D} - 1)^{-1} f

= (D + D²/2! + D³/3! + D^{4}/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}\)