Post #169,080
8/12/04 10:32:26 PM
|
WOW.
Just spoke to my neighbor - it's her birthday. Ross' birthday is today and SO is my wife's!
What are the odds? Ben? You're an applied math guy...
bcnu,
Mikem
If you can read this, you are not the President.
|
Post #169,083
8/12/04 10:36:08 PM
|
Geez - had I known
I would have taken you out for a beer!
Imric's Tips for Living
- Paranoia Is a Survival Trait
- Pessimists are never disappointed - but sometimes, if they are very lucky, they can be pleasantly surprised...
- Even though everyone is out to get you, it doesn't matter unless you let them win.
|
Nothing is as simple as it seems in the beginning,
As hopeless as it seems in the middle,
Or as finished as it seems in the end.
|
|
Post #169,091
8/12/04 10:59:36 PM
|
Re: Geez - had I known
Had some, thankee.
-drl
|
Post #169,086
8/12/04 10:39:06 PM
|
Re: applied math guy
If I recall correctly, all it takes is 23 people to have a more than even chance that at least one pair of people has a common birthday.
Hey, and it's Barry's too!
Alex
"If I seem unduly clear to you, you must have misunderstood what I said." -- Alan Greenspan, Federal Reserve chairman
|
Post #169,087
8/12/04 10:40:53 PM
|
But we have 2 pairs.
And I see from the next post it's Barry's as well. So, it is a trivial exercise, but then, all of applied mathematics is trivial ;0)
bcnu,
Mikem
If you can read this, you are not the President.
|
Post #169,090
8/12/04 10:57:16 PM
|
2 pairs are at least one pair! :)
Alex
"If I seem unduly clear to you, you must have misunderstood what I said." -- Alan Greenspan, Federal Reserve chairman
|
Post #169,094
8/12/04 11:07:48 PM
|
I'm not about to do a "odds of n people the same" program
At least not right now.
If I'm still interested in the morning, I'll code that in Ruby. (There it is easier to avoid roundoff issues.)
Cheers,
Ben
To deny the indirect purchaser, who in this case is the ultimate purchaser, the right to seek relief from unlawful conduct, would essentially remove the word consumer from the Consumer Protection Act
- [link|http://www.techworld.com/opsys/news/index.cfm?NewsID=1246&Page=1&pagePos=20|Nebraska Supreme Court]
|
Post #169,093
8/12/04 11:04:29 PM
8/13/04 3:02:48 AM
|
Here's a program which SHOULD be correct
I have not tried optimizing it. And yes, there are some obvious optimizations which would make it better, for instance memoizing the factorial function. You will need Ruby to run this program. \n#! /usr/bin/ruby -w\n\n# With one argument, the product 1*2*..*n\n# With two arguments with m <= n, the product m*(m+1)*..*n\n# With two arguments with n < m, 1.\ndef factorial(n, m=1)\n n = n.to_i;\n m = m.to_i;\n product = 1;\n (m..n).each {|i| product *= i}\n product\nend\n\n# Sums an array.\ndef sum(numbers)\n ans = 0;\n numbers.each{|i| ans += i}\n ans\nend\n\n# The number of ways to divide a set of n things into a combination of\n# sizes[0] and sizes[1] and ... and leftover things. If sizes has only one\n# argument, is the familiar "n choose m" function.\ndef choose(n, *sizes)\n n = n.to_i\n ans = factorial(n, n + 1 - sum(sizes));\n sizes.each { |i| ans /= factorial(i) };\n ans\nend\n\n# This calls the function with each descending sequence whose terms sum to\n# total and whose maximimum element is max (that optionally starts with the\n# initial subsequence).\ndef call_with_each_descending_sequence(total, max, function, initial=[])\n for i in 1..max\n sequence = [ initial, i ].flatten()\n if i < total\n call_with_each_descending_sequence(total - i, i, function, sequence)\n elsif i == total\n function[sequence];\n end\n end\nend\n\n# Calculate the number of possible birthday assignments to some number of\n# people with a given maximimum number of people getting the same day.\ndef possible_birthday_assignments(people, max_one_day)\n ans = 0;\n call_with_each_descending_sequence(\n people.to_i,\n max_one_day.to_i,\n proc {|duplicate_sequence| \n people_to_duplicate_sequence = choose(people, *duplicate_sequence);\n\n day_groupings = []\n last_count = 0;\n duplicate_sequence.each {|count|\n if (last_count != count)\n day_groupings.push(1);\n last_count = count;\n else\n day_groupings[-1] += 1;\n end\n }\n days_to_day_groupings = choose(365, *day_groupings);\n\n ans += days_to_day_groupings * people_to_duplicate_sequence;\n }\n );\n ans;\nend\n\ncount = possible_birthday_assignments(*ARGV);\nprob = ( count * 1_000_000 / 365**(ARGV[0].to_i) ).to_f / 1_000_000;\nputs "Odds #{prob} that #{ARGV[0]} people have at most #{ARGV[1]} birthdays together";\nThis program suggests that to get better than even odds of 2 birthdays together you need 23 people, 3 birthdays together you need 88, and 4 birthdays you need 187. This program does not believe that people are born on leap day. To make that fix you would want to take a weighted average of, for each number of people born together on leap day, what the probability is that you'll have no more than X people born on the same day. To deny the indirect purchaser, who in this case is the ultimate purchaser, the right to seek relief from unlawful conduct, would essentially remove the word consumer from the Consumer Protection Act
- [link|http://www.techworld.com/opsys/news/index.cfm?NewsID=1246&Page=1&pagePos=20|Nebraska Supreme Court]
Edited by ben_tilly
Aug. 13, 2004, 12:48:21 AM EDT
Edited by ben_tilly
Aug. 13, 2004, 03:02:48 AM EDT
|
Post #169,113
8/12/04 11:43:32 PM
8/13/04 8:25:25 AM
|
Neato. I'll have to find Ruby for Win32. Thanks.
More on this topic is here: [link|http://www.maa.org/mathland/mathtrek_11_23_98.html|Birthday Surprises] It's possible to derive a simple formula that gives an approximate answer for the number required to get a 50-percent chance of a match. That number is 1.2 times the square root of the number of categories. For 365 categories (days of the year), the number is 1.2 multiplied by the square root of 365, or 23.
[...]
What about triple matches? That's a trickier calculation, but the answer turns about to be 88 people. Cheers, Scott.
|
Post #169,148
8/13/04 9:38:14 AM
|
Cygwin is your friend
Both Ruby and Python interpreters are available there.
jb4
shrub\ufffdbish (Am., from shrub + rubbish, after the derisive name for America's 43 president; 2003) n. 1. a form of nonsensical political doubletalk wherein the speaker attempts to defend the indefensible by lying, obfuscation, or otherwise misstating the facts; GIBBERISH. 2. any of a collection of utterances from America's putative 43rd president. cf. BULLSHIT
|
Post #169,152
8/13/04 10:03:29 AM
|
I've got Cygwin. I'll track down Ruby. Thanks, jb.
|
Post #169,136
8/13/04 4:02:10 AM
|
And with minor optimizations
It is nearly twice as fast now. The next obvious speedup is to avoid calculating the day groupings at each leaf. But that is more work than I care to do... \n#! /usr/bin/ruby -w\n\n# With one argument, the product 1*2*..*n\n# With two arguments with m <= n, the product m*(m+1)*..*n\n# With two arguments with n < m, 1.\n@known_factorials = { "0|1"=>1 };\ndef factorial(n, m=1)\n unless @known_factorials.has_key?(n.to_s + "|" + m.to_s)\n n = n.to_i;\n m = m.to_i;\n product = 1;\n (m..n).each {|i| product *= i}\n @known_factorials[n.to_s + "|" + m.to_s] = product\n end\n @known_factorials[n.to_s + "|" + m.to_s]\nend\n\n# Sums an array.\ndef sum(numbers)\n ans = 0;\n numbers.each{|i| ans += i}\n ans\nend\n\n# The number of ways to divide a set of n things into a combination of\n# sizes[0] and sizes[1] and ... and leftover things. If sizes has only one\n# argument, is the familiar "n choose m" function.\ndef choose(n, *sizes)\n n = n.to_i\n ans = factorial(n, n + 1 - sum(sizes));\n sizes.each { |i| ans /= factorial(i) };\n ans\nend\n\n# This calls the function with each descending sequence whose terms sum to\n# total and whose maximimum element is max (that optionally starts with the\n# initial subsequence).\ndef call_with_each_descending_sequence(total, max, function, initial=[])\n # Special case for 1\n sequence = initial + (1..total).collect { 1 };\n function[sequence];\n\n (2..max).each {|i|\n sequence = initial + [i];\n if i < total\n call_with_each_descending_sequence(total - i, i, function, sequence)\n elsif i == total\n function[sequence];\n end\n }\nend\n\n# Calculate the number of possible birthday assignments to some number of\n# people with a given maximimum number of people getting the same day.\ndef possible_birthday_assignments(people, max_one_day)\n ans = 0;\n call_with_each_descending_sequence(\n people.to_i,\n max_one_day.to_i,\n proc {|duplicate_sequence| \n people_to_duplicate_sequence = choose(people, *duplicate_sequence);\n\n day_groupings = []\n last_count = 0;\n duplicate_sequence.each {|count|\n if (last_count != count)\n day_groupings.push(1);\n last_count = count;\n else\n day_groupings[-1] += 1;\n end\n }\n days_to_day_groupings = choose(365, *day_groupings);\n\n ans += days_to_day_groupings * people_to_duplicate_sequence;\n }\n );\n ans;\nend\n\ncount = possible_birthday_assignments(*ARGV);\nprob = ( count * 1_000_000 / 365**(ARGV[0].to_i) ).to_f / 1_000_000;\nputs "Odds #{prob} that #{ARGV[0]} people have at most #{ARGV[1]} birthdays together";\nCheers, Ben To deny the indirect purchaser, who in this case is the ultimate purchaser, the right to seek relief from unlawful conduct, would essentially remove the word consumer from the Consumer Protection Act
- [link|http://www.techworld.com/opsys/news/index.cfm?NewsID=1246&Page=1&pagePos=20|Nebraska Supreme Court]
|
Post #169,166
8/13/04 10:42:02 AM
|
"If I'm still interested in the morning ... "
Post #169093
By ben_tilly
2004-08-13 03:02:48 With timezone conversion that was 2 minutes after midnight your time. Yeah, I guess that counts as "tomorrow morning." ===
Implicitly condoning stupidity since 2001.
|
Post #169,169
8/13/04 10:44:45 AM
|
I knew he couldn't resist ;-)
bcnu,
Mikem
If you can read this, you are not the President.
|
Post #169,181
8/13/04 12:17:17 PM
|
Well, it is not so technically morning now...
So time for a redo. And the much faster version goes like this: \n#! /usr/bin/ruby -w\n\nclass RepeatedSequence\n attr_reader :value, :repeat;\n\n def to_s\n "<#{@value}x#{@repeat}>"\n end\n\n def initialize(value, repeat)\n @value = value;\n @repeat = repeat;\n end\nend\n\n# With one argument, the product 1*2*..*n\n# With two arguments with m <= n, the product m*(m+1)*..*n\n# With two arguments with n < m, 1.\n@known_factorials = { "0|1"=>1 };\ndef factorial(n, m=1)\n unless @known_factorials.has_key?(n.to_s + "|" + m.to_s)\n n = n.to_i;\n m = m.to_i;\n product = 1;\n (m..n).each {|i| product *= i}\n @known_factorials[n.to_s + "|" + m.to_s] = product\n end\n @known_factorials[n.to_s + "|" + m.to_s]\nend\n\n# Sums an array.\ndef sum(numbers)\n ans = 0;\n numbers.each{|i| ans += i}\n ans\nend\n\n# The number of ways to divide a set of n things into a combination of\n# groups of sizes. The sizes arguments are expected to be constant sequences.\n# The familiar "n choose m" function is a special case.\ndef choose(n, *sizes)\n n = n.to_i\n ans = factorial(n, n + 1 - sum(sizes.collect {|i| i.value*i.repeat}));\n sizes.each { |i| ans /= (factorial(i.value)**i.repeat) };\n ans\nend\n\n# This calls the function with each descending sequence whose terms sum to\n# total and whose maximimum element is max (that optionally starts with the\n# initial subsequence).\ndef call_with_each_descending_sequence(total, max, function, initial=[])\n if 1 == max\n function[initial + [RepeatedSequence.new(1, total)]];\n return;\n end\n\n call_with_each_descending_sequence(\n total, max - 1, function, initial\n );\n\n (1..(total/max)).each {|count|\n subsequence = RepeatedSequence.new(max, count);\n call_with_each_descending_sequence(\n total - max*count, max - 1, function, initial + [ subsequence ]\n )\n }\nend\n\n# Calculate the number of possible birthday assignments to some number of\n# people with a given maximimum number of people getting the same day.\ndef possible_birthday_assignments(people, max_one_day)\n ans = 0;\n call_with_each_descending_sequence(\n people.to_i,\n\n max_one_day.to_i,\n proc {|duplicate_sequence| \n people_to_duplicate_sequence = choose(people, *duplicate_sequence);\n\n day_groupings = duplicate_sequence.collect {|i|\n RepeatedSequence.new(i.repeat, 1)\n }\n days_to_day_groupings = choose(365, *day_groupings);\n\n ans += days_to_day_groupings * people_to_duplicate_sequence;\n }\n );\n ans;\nend\n\ncount = possible_birthday_assignments(*ARGV);\nprob = ( count * 1_000_000 / 365**(ARGV[0].to_i) ).to_f / 1_000_000;\nputs "Odds #{prob} that #{ARGV[0]} people have at most #{ARGV[1]} birthdays together";\nWith this version, I've been able to show that to get even odds of 5 people with the same birthday you need 313 or 314 people. At that point the possibility of leap day births is significant. Skipping leap day, the odds of not having 5 with 312 people are 0.498929, and with 313 is 0.498929. Taking into account a rough estimate of the odds that 1 person will be born on leap day out of 313 (i.e. 313*1/(365*4+1)), my odds are 0.499973404517454. That's close enough that I'd have to really do the leap day calculation right to figure out whether the answer is 313 or 314. And I don't have the energy at the moment. Cheers, Ben To deny the indirect purchaser, who in this case is the ultimate purchaser, the right to seek relief from unlawful conduct, would essentially remove the word consumer from the Consumer Protection Act
- [link|http://www.techworld.com/opsys/news/index.cfm?NewsID=1246&Page=1&pagePos=20|Nebraska Supreme Court]
|
Post #169,246
8/13/04 5:52:09 PM
|
And a better answer and algorithm improvements
The answer for 5 really is 313. The probability of not having any group of 5 with 313 people is 0.499972. I'm including a program with a different algorithm that can answer that. It scales worse than the previous one for up to 3 people on the same birthday, but better for 4 or more after that. It takes leap years into account. It does not take into account the 3 missing leap days every 400 years, but there aren't many people around who are 104 (and even fewer who are 204) so I think that is a reasonable omission. \n#! /usr/bin/ruby -w\n\n# With one argument, the product 1*2*..*n\n# With two arguments with m <= n, the product m*(m+1)*..*n\n# With two arguments with n < m, 1.\ndef factorial(n, m=1)\n n = n.to_i;\n m = m.to_i;\n product = 1;\n (m..n).each {|i| product *= i}\n product\nend\n\n# Sums an array.\ndef sum(numbers)\n ans = 0;\n numbers.each{|i| ans += i}\n ans\nend\n\n# The number of ways to find m things in n.\n@choose_cache = Hash.new\ndef choose(n, m)\n key = "#{n} #{m}";\n unless @choose_cache.has_key?(key)\n if (m > n/2)\n m = n - m;\n end\n @choose_cache[key] = factorial(n, n + 1 - m) / factorial(m);\n end\n return @choose_cache[key]\nend\n\n# Calculate the number of possible birthday assignments to some number of\n# people using some number of days with a given maximimum number of people\n# getting the same day.\n@birthday_assignments = Hash.new();\ndef possible_birthday_assignments(people, days, max_one_day)\n if (people > days*max_one_day)\n return 0;\n elsif days < 2\n return 1;\n else \n key = "#{people}|#{days}|#{max_one_day}";\n ans = 0;\n unless @birthday_assignments.has_key?(key)\n if (days/2*2 == days)\n # Divide the days in half\n (0..people).each {|people_in_first|\n ans += possible_birthday_assignments(\n people_in_first,\n days/2,\n max_one_day\n ) * possible_birthday_assignments(\n people - people_in_first,\n days/2,\n max_one_day\n ) * choose(people, people_in_first);\n }\n else\n # Divide people in 1 day, people in the rest\n limit = people < max_one_day ? people : max_one_day\n (0..limit).each{ |people_in_first|\n ans += possible_birthday_assignments(\n people - people_in_first,\n days - 1,\n max_one_day\n ) * choose(people, people_in_first)\n }\n end\n @birthday_assignments[key] = ans;\n end\n return @birthday_assignments[key];\n end\nend\n\ndef fraction_to_float(a, b)\n precision = 100_000_000;\n return ( (a * precision + a/2)/b ).to_f / precision;\nend\n\n# Calculate birthday probability but ignore leap day.\ndef basic_birthday_probability(people, max_one_day)\n count = possible_birthday_assignments(people.to_i, 365, max_one_day.to_i)\n return fraction_to_float(count, 365**(people.to_i));\nend\n\n# Calculate birthday probability and include leap day.\ndef birthday_probability(people, max_one_day)\n people = people.to_i;\n max_one_day = max_one_day.to_i;\n limit = people < max_one_day ? people : max_one_day;\n ans = 0;\n (0..limit).each {|i|\n ans += basic_birthday_probability(\n people - i, max_one_day\n ) * fraction_to_float(\n choose(people, i) * (365*4)**(people-i),\n (365*4 + 1)**people\n );\n }\n return ans;\nend\n\nprob = birthday_probability(*ARGV);\nputs "Odds #{prob} that #{ARGV[0]} people have at most #{ARGV[1]} birthdays together";\nCheers, Ben To deny the indirect purchaser, who in this case is the ultimate purchaser, the right to seek relief from unlawful conduct, would essentially remove the word consumer from the Consumer Protection Act
- [link|http://www.techworld.com/opsys/news/index.cfm?NewsID=1246&Page=1&pagePos=20|Nebraska Supreme Court]
|
Post #169,378
8/15/04 10:49:34 AM
|
It's nice to see there's at least one person in the world...
... with a more keenly-developed distaste for not-quite-rightness than me.
===
Implicitly condoning stupidity since 2001.
|
