(42S) Probability of Same Birthday Day
12-05-2018, 06:09 PM
Post: #1
 morex Junior Member Posts: 18 Joined: Nov 2018
(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
12-05-2018, 08:36 PM
Post: #2
 Dieter Senior Member Posts: 2,398 Joined: Dec 2013
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?

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
12-05-2018, 09:02 PM
Post: #3
 morex Junior Member Posts: 18 Joined: Nov 2018
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
12-05-2018, 11:46 PM (This post was last modified: 12-05-2018 11:46 PM by ijabbott.)
Post: #4
 ijabbott Senior Member Posts: 676 Joined: Jul 2015
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
12-06-2018, 04:32 AM
Post: #5
 Valentin Albillo Senior Member Posts: 408 Joined: Feb 2015
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.

Find All My HP-related Materials here:  Valentin Albillo's HP Collection

12-06-2018, 05:54 AM
Post: #6
 Joe Horn Senior Member Posts: 1,479 Joined: Dec 2013
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-
12-06-2018, 08:49 AM
Post: #7
 ijabbott Senior Member Posts: 676 Joined: Jul 2015
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.

— Ian Abbott
12-06-2018, 03:59 PM
Post: #8
 Valentin Albillo Senior Member Posts: 408 Joined: Feb 2015
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.

V.

Find All My HP-related Materials here:  Valentin Albillo's HP Collection

12-06-2018, 07:49 PM
Post: #9
 morex Junior Member Posts: 18 Joined: Nov 2018
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
12-10-2018, 05:10 PM (This post was last modified: 12-10-2018 05:46 PM by Joe Horn.)
Post: #10
 Joe Horn Senior Member Posts: 1,479 Joined: Dec 2013
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.

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-
08-16-2019, 01:55 PM (This post was last modified: 08-16-2019 04:22 PM by Albert Chan.)
Post: #11
 Albert Chan Senior Member Posts: 695 Joined: Jul 2018
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}$$
 « Next Oldest | Next Newest »

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