Post Reply 
(42S) Probability of Same Birthday Day
12-05-2018, 06:09 PM
Post: #1
(42S) Probability of Same Birthday Day
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

10C 11C 12C 15C 16C 28C 28S 32S 32SII 33C 41C 41CV 41CX 42S 48SX 48G 97 100LX
Find all posts by this user
Quote this message in a reply
12-05-2018, 08:36 PM
Post: #2
RE: (42S) Probability of Same Birthday Day
(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
Find all posts by this user
Quote this message in a reply
12-05-2018, 09:02 PM
Post: #3
RE: (42S) Probability of Same Birthday Day
(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!

10C 11C 12C 15C 16C 28C 28S 32S 32SII 33C 41C 41CV 41CX 42S 48SX 48G 97 100LX
Find all posts by this user
Quote this message in a reply
12-05-2018, 11:46 PM (This post was last modified: 12-05-2018 11:46 PM by ijabbott.)
Post: #4
RE: (42S) Probability of Same Birthday Day
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!)

— Ian Abbott
Find all posts by this user
Quote this message in a reply
12-06-2018, 04:32 AM
Post: #5
RE: (42S) Probability of Same Birthday Day
(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.

  
All My Articles & other Materials here:  Valentin Albillo's HP Collection
 
Visit this user's website Find all posts by this user
Quote this message in a reply
12-06-2018, 05:54 AM
Post: #6
RE: (42S) Probability of Same Birthday Day
(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.

<0|ɸ|0>
-Joe-
Visit this user's website Find all posts by this user
Quote this message in a reply
12-06-2018, 08:49 AM
Post: #7
RE: (42S) Probability of Same Birthday Day
(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. Smile

— Ian Abbott
Find all posts by this user
Quote this message in a reply
12-06-2018, 03:59 PM
Post: #8
RE: (42S) Probability of Same Birthday Day
(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. Smile

V.

  
All My Articles & other Materials here:  Valentin Albillo's HP Collection
 
Visit this user's website Find all posts by this user
Quote this message in a reply
12-06-2018, 07:49 PM
Post: #9
RE: (42S) Probability of Same Birthday Day
Quote:Me too, I've never met anybody born on that date. Smile

Superman! :-)

10C 11C 12C 15C 16C 28C 28S 32S 32SII 33C 41C 41CV 41CX 42S 48SX 48G 97 100LX
Find all posts by this user
Quote this message in a reply
12-10-2018, 05:10 PM (This post was last modified: 12-10-2018 05:46 PM by Joe Horn.)
Post: #10
RE: (42S) Probability of Same Birthday Day
(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. Big Grin

[Image: not0b.png]

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

<0|ɸ|0>
-Joe-
Visit this user's website Find all posts by this user
Quote this message in a reply
08-16-2019, 01:55 PM (This post was last modified: 08-16-2019 04:22 PM by Albert Chan.)
Post: #11
RE: (42S) Probability of Same Birthday Day
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}\)
Find all posts by this user
Quote this message in a reply
Post Reply 




User(s) browsing this thread: 1 Guest(s)