Birthday paradox

Birthday paradox

There is more than 50% probability that 2 people in a room of 23 will share the same birthday…

…but what is the minimum number of tunes 2 people need to know to have a 50% chance of having one tune in common?

Re: Birthday paradox

1 tune. (probably Silver Spear) 😛

Re: Birthday paradox

You first need to know the total number of tunes available to those two individuals.

Re: Birthday paradox

Yes please state your assumptions.

e.g. both players are dot-learners with a copy of O’Neill’s 1001.

Re: Birthday paradox

Are the two people
the same age (implying the similar influences i.e., I don’t want to be accused of ageism)
different ages
from the same country
from the same area
do they play the same instrument?
Or
is this a trick question and one is a bodhran player?

Posted by .

Re: Birthday paradox

…or let’s say both players been picking up tunes at random from the c.250 you can download off the comhaltas site.

Re: Birthday paradox

Depends on what instruments they play and what countyr they come from too?

Re: Birthday paradox

*country*

Re: Birthday paradox

That’s not a paradox - it’s just a bit counterintuitive.

Your question about tunes is unanswerable without knowing what the relevant parameters are set to. But if there were only 365 tunes and there were 23 people in a session who randomly knew only one tune each, then the chances of two people knowing the same tune would be more than 50%!

Re: Birthday paradox

Here’s a precise version of the question. If two people randomly choose k tunes from a fixed collection of n tunes, what is the smallest value of k (as a function of n) for which the probability that they have chosen at least one tune in common is greater than or equal to 1/2?

First, we need to know the probability that they have chosen at least one tune in common, as a function of both n and k. This is 1-[C(n-k,k)/C(n,k)], where C(n,k)=n!/k!(n-k)!.

I made a spreadsheet, computing these probabilities for all values of n from 2 to 500 and all values of k from 1 to 100. I then found the smallest k for each such n where the probability was at least 1/2. These values ranged from 1 to 19. For each of these, I found the smallest value of n for which this value was the least k making the probability at least 1/2. That gave me a table of pairs (k,n), which I plotted. I tried exponential, quadratic, and power function regressions on this data.

A quadratic function fit exceptionally well. This gives a quadratic function ak^2+bk+c which approximates the smallest n for which k is as small as possible with probability at least 1/2. a is around 1.45, b is around -2, and c is around 1. Solving for k as a function of n, and rounding down to the nearest integer should give a good approximation to the answer.

For large values of n (we know there are lots of tunes to choose from), the quadratic formula is not very sensitive to rounding the values of a, b, and c. Additionally, the b^2 under the square root has little significance. So k=(2+sqrt(6n))/3 rounded down gives a very good approximation. (For small values of n, it’s likely to be wrong because of rounding the values of a, b, and c.)

I tried it for n=1000 (e.g. O’Neill’s). The formula predicts that the two people would each need to learn 26 tunes. For n=2000, it predicts that they would each need to learn 37 tunes. I tested these by computing the probabilities, and indeed they are both a hair greater than 1/2, while 25 and 36 are not enough.

I also tried it for n=2000. In that case

Re: Birthday paradox

Oops. Kill that last line.

Re: Birthday paradox

Hmm.
a. What’s the probability for finding a set of three tunes in common?

b. What if the pair in question are not dot learners but have learned their tunes from thesession.org?
( and does anyone know how many tunes are noted in the tunes section are on this site?)
or
c. What if they learned their tunes exclusively from CDs - there must be only a finite amount of tunes recorded. Anyone out there know that figure, i.e., how many tunes have actually been recorded?

Posted by .

Re: Birthday paradox

a.
1-{[C(n-k,k)C(k,0)+C(n-k,k-1)C(k,1)+C(n-k,k-2)C(k,2)]/C(n,k)} where n and k are as in my post above.

b.
The number changes nearly every day. As of now, there have been 9319 submissions, but some of those have been deleted and others are duplicates. If you go to the Tunes section and mouse over the most recent submission, you’ll see the number of the most recent tune in the status bar.

c.
That number is also changing all the time. How could anybody own such a comprehensive library, keep it up-to-the-minute, and do all the cross-checking to find which tunes are the same but with different titles? That said, http://www.irishtune.info has done this for 442 albums, finding 4634 tunes.

Re: Birthday paradox

Thanks Gary that is the answer I was looking for.

Next question. Let’s say there c.4500 tunes in total.
The average session might play say c.100 of these on any given night.
How many tunes would you need to know to have a >50% chance of knowing 1 of those 100?

I realise locality is relevant, so the question is how many tunes would you need to know attending a session anywhere in the world.

Re: Birthday paradox

If they play 100 randomly chosen tunes out of 4500 and you know k randomly chosen tunes, here are the approximate probabilities that they will play at least one that you know:
k Probability
1 2.2%
2 4.4%
3 6.5%
4 8.6%
5 10.6%
6 12.6%
7 14.6%
8 16.5%
9 18.3%
10 20.1%
11 21.9%
12 23.7%
13 25.4%
14 27.0%
15 28.7%
16 30.2%
17 31.8%
18 33.3%
19 34.8%
20 36.3%
21 37.7%
22 39.1%
23 40.4%
24 41.8%
25 43.1%
26 44.3%
27 45.6%
28 46.8%
29 48.0%
30 49.2%
31 50.3%
41 60.4%
54 70.5%
71 80.0%
102 90.2%
131 95.0%
199 99.0%
281 99.9%
376 99.99%

Re: Birthday paradox

Can I just say, this is one of my favourite discussions ever.

Re: Birthday paradox

With grateful thanks to Gary and his painstaking calculations we can conclude that anyone who has been playing Irish music for a reasonable length of time and so is likely to know (for whatever value of "know") 200+ tunes, is therefore almost certain to recognise and join in at least one tune in any session anywhere. This has been borne out by my own experiences when on holiday in Ireland.

Re: Birthday paradox

Of course they might play it in a different key, though!

Re: Birthday paradox

Only a problem if you’re one of those unfortunates cursed with perfect pitch.

Re: Birthday paradox

Fascinating stuff lads. I’m of the ‘other side’ of the brain than y’all, but I can dig it. Great formula Gary!

Re: Birthday paradox

lazyhound…Thanks for that. You made me laugh out loud.

Re: Birthday paradox

You might know some tunes in common, but if they are "chestnuts" , what’s the probability of either party admitting it?

Here is my table based on age:
0-13years - 100%
14 - 26years old - 0%
27 - 45 years old - 50%
46 - 65 years old - 75%
66 - 100 - 100%

Posted by .

Re: Birthday paradox

Really cool thread. Brings me back to engineering school!

I am certainly impressed…but if you use the quadratic for a fit isn’t one of the solutions imaginary?

Its been along time since I did this sort of thing in SpaceTime Physics!

Re: Birthday paradox

No. If one solution is real, so is the other. In this case one of them is irrelevant.

Re: Birthday paradox

I have joked with our very smart heir to the throne when he got on a roll, that the last time I used statistics, calculus and some of the more lofty quantum stuff I took, was in graduate school when Richard Nixon was living in the White House. Then I had to pay a morrtgage and educate the kids- translate had to get a real job, while in a paralell universe computers and living in a basically four function world eliminated the need for me to use most of the stuff.

So the details get lost in he mists of time!

Thanks for the answer!

Re: Birthday paradox

Here was me thinking I could maths alone after my exams last year!!!