More Complex Birthday Problem

[pzhon]

[ QUOTE ]
isn't this basically a pvnp type deal

[/ QUOTE ]
No.

[d10]

Too many formulas.

If you want a statistical based answer, I threw together a simulation in Perl which randomly generates a number 0-364 (for 365 total possible outcomes) and kept on generating numbers until all 365 outcomes had hit at least once. I then recorded how many numbers I needed to pull from the RNG before all 365 outcomes had hit at least once. That process was looped 1000 times and each result was saved in a log file. I then took this file full of numbers and calculated the following from it:

Average = 2347
Minimum = 1412
Maximum = 5692
Std Dev = 461.37

[pzhon]

[ QUOTE ]
Too many formulas.

[/ QUOTE ]
I don't see another good way to solve the problem as thoroughly. Perhaps you could suggest one?

[ QUOTE ]

If you want a statistical based answer, I threw together a simulation in Perl which randomly generates a number 0-364 (for 365 total possible outcomes) and kept on generating numbers until all 365 outcomes had hit at least once.

[/ QUOTE ]
That is a bad idea for many reasons.

[img]/images/graemlins/diamond.gif[/img] It relies on the very high quality of your random number generator. A RNG that worked well for many other purposes could easily produce a very skewed result, on average.

[img]/images/graemlins/diamond.gif[/img] You can't compute a probability that is lower than 10^-100 (like the probability all birthdays are represented by the 400th person) by observing an experiment like this.

[img]/images/graemlins/diamond.gif[/img] It is far more complicated than 365(1 + 1/2 + ... + 1/365) = 2364.65 , one of those formulas you disliked.

[gaming_mouse]

[ QUOTE ]
[ QUOTE ]
Too many formulas.

[/ QUOTE ]
I don't see another good way to solve the problem as thoroughly. Perhaps you could suggest one?

[ QUOTE ]

If you want a statistical based answer, I threw together a simulation in Perl which randomly generates a number 0-364 (for 365 total possible outcomes) and kept on generating numbers until all 365 outcomes had hit at least once.

[/ QUOTE ]
That is a bad idea for many reasons.

[img]/images/graemlins/diamond.gif[/img] It relies on the very high quality of your random number generator. A RNG that worked well for many other purposes could easily produce a very skewed result, on average.

[img]/images/graemlins/diamond.gif[/img] You can't compute a probability that is lower than 10^-100 (like the probability all birthdays are represented by the 400th person) by observing an experiment like this.

[img]/images/graemlins/diamond.gif[/img] It is far more complicated than 365(1 + 1/2 + ... + 1/365) = 2364.65 , one of those formulas you disliked.

[/ QUOTE ]

Not to mention that the point wasn't to have an answer per se -- I know I, at least, didn't care about that. The point was to see how to solve the problem.

[BillsChips]

I think there's something wrong with your calculations. How could the Standard Deviation be less then the minimum?

[d10]

I guess it's harder to appreciate a simulation like that if you're only looking at the results. I understand that in hypothetical problems like these the point is to discover the means to an answer and not the answer itself, so I got much more out of writing the code for the simulation than anyone could get out of viewing the results of it.

I have to disagree with the earlier post. Statistical analyses of a computer simulation is often, in the practical sense, just as useful as deriving a formula. Look at the question posed again in the first post of this thread. Are you saying that the results of my simulation don't accurately reflect the correct answer to this question? If you want the answer simply because you're curious, then you might prefer the more exact answer offered by a formula. However if you were looking for a practical answer, say if you actually needed to find 365 people with different birthdays for whatever reason, and you wanted to know how many people you should expect to contact before you found your 365 representatives, my answer of 2347 is just as practical as 2364.65.

Yes, there are problems in the real world that can only be solved through formulas, there are also problems that can only be solved through statistics (Can you give me a formula that says how often you can expect to win with AA at a 10 player table? I'd prefer to look at the statistics after it's dealt to me 1,000 times and assume that the number I get is, in all practical senses, the number I can expect in the future). I think the question in this thread, as it was posed, can be effectively solved either way. And I think the fact that both of our methods produced similar answers is a good check which validates both of our methods and ensures that neither one of us missed anything as we thought through the problem. I'm sorry that all I could provide from my method was the results. I had thought about posting the code I used to create the simulation but it's been years since I wrote software for a living, and the code I put together for this problem is quite inefficient and embarassing, but it works.

[d10]

I'm not sure what one has to do with the other. Given a sample of 19,10,1, the standard deviation will be greater than the minimum value. Given 5001,5000,4999, the standard deviation will be less than the minimum value. I think given the sample of this problem both the standard deviation and the minimum values I arrived at look OK.

[fishfeet]

Cool! A discussion about the thread I made...

I never got to all 365 bdays... I ran out of forums to post on!!

Anyway, here is the data I collected so far.. maybe Ill pick it up again sometime...


254 Birthdays
427 Responces (173 repeats)

I tried reading this tread to understand how to solve for an expected value... but it went way over my head.
Ive always been a good at math.. just took Stats last semseter.. got an A.
But damn, This stuff is confusing.

[Jonas Wa]

Your Problem is with union and interscetions (inclusion-exlcusion)
your:
365*(364/365)^N - (365 choose 2)*(363/365)^N
should be followed if done right (havnt look realy at it)
+(365 choose 3))*(362/365)^N -(365 choose 4))*(361/365)^N
and so on........
Smartest should be to take 1-P(all found) I think.

[gaming_mouse]

[ QUOTE ]
Your Problem is with union and interscetions (inclusion-exlcusion)
your:
365*(364/365)^N - (365 choose 2)*(363/365)^N
should be followed if done right (havnt look realy at it)
+(365 choose 3))*(362/365)^N -(365 choose 4))*(361/365)^N
and so on........

[/ QUOTE ]


Yes, I know that. I was confused about why the first two terms were so far off, but, as pzhon pointed out, it just takes longer to converge in this problem.

[ QUOTE ]
Smartest should be to take 1-P(all found) I think.

[/ QUOTE ]

To do what? We're trying to estimate, eg, the chance that they have all been found after 400 trials, or 1000 trial, or whatever. The "1 - " trick doesn't apply here in any way I can see.