Fixee
Reputation
5,868
Top tag
Next privilege 10,000 Rep.
Access moderator tools
 Jun15 revised How many expected people needed until 3 share a birthday? added 263 characters in body Jun15 accepted How many expected people needed until 3 share a birthday? Jun15 comment How many expected people needed until 3 share a birthday? Following the link to your other question, and then to the Sedgewick/Flajolet book, and then a reference from there, I found a paper that gives the derivation for this result: sciencedirect.com/science/article/pii/S0021980067800759 Jun15 comment How many expected people needed until 3 share a birthday? Thanks, Byron. I had guessed that $E(T) \approx c M^{2/3}$, but simulations I ran showed $c$ growing slightly with $M$ so I thought the $2/3$ exponent was a tad low. It could instead be the effect of lower-order terms in the asymptotics. Jun15 comment How many expected people needed until 3 share a birthday? I am asking for the expected number of balls where a 3-way collision occurs. But I would be happy to learn the "median" value, which is the number of balls where the a 3-way collision has probability $\approx$ 1/2. Jun15 revised How many expected people needed until 3 share a birthday? deleted 37 characters in body Jun15 revised How many expected people needed until 3 share a birthday? added 1161 characters in body Jun14 asked How many expected people needed until 3 share a birthday? Jun14 comment Second pair of matching birthdays I have worked (unsuccessfully) at finding a closed form for the constant $c \approx 1.88$ that you approximate via your python program above. Unfortunately the integral that so nicely turns into $\sqrt{\pi/2}$ ends up being much harder with the ${n \choose 2}$ multiplier. Jun14 accepted A seeming paradox in a coin-flipping game Jun13 answered Why is it that, $\forall x \in \mathbb{Z},\ x^5 \equiv x \pmod{10}$? Jun10 comment Prove that if $n$ is a composite and $p \gt \sqrt[3]n$, then $n/p$ is a prime. If you look at the edit history, it used to say "composite" at the time my response was offered. Jun4 accepted Second pair of matching birthdays Jun1 comment Second pair of matching birthdays Very nice! I have been working on this problem since I posted it and I followed virtually the exact same steps as you do above, but you are faster. I just last night wrote the same program you did (in C instead of Python, but they're almost identical!). I feel guilty seeing all the work you did on this... I'm doing this just for fun (it's summer after all!). Cheers. Jun1 comment Second pair of matching birthdays Well, I mostly understand what you did, but you approximated the median (tosses needed to get a 50% probability) rather than the mean, and they are not asymptotically equal for this problem (as you point out). Based on computer simulations I've run, your 55% estimate isn't quite right: for small $M$ we need about 60% more, and for larger $M$ (say 100,000) it's less than 50%. I don't think this 2-collision mean is proportional to $\sqrt{M}$ like the 1-collision mean is. Jun1 revised Second pair of matching birthdays deleted 4 characters in body May31 revised Second pair of matching birthdays added 499 characters in body May31 comment Second pair of matching birthdays I agree with you that this is the probability of obtaining 2 (or more) collisions throwing $n$ balls into $M$ bins, but I was asking for an expectation. Every technique I know of requires computing a sum. May31 comment Second pair of matching birthdays My statement is "ball lands in an occupied bin" twice; that would encompass both or your scenarios. (Restricting to either of your two sub-cases would be interesting problems as well... I would be happy to see a solution to any of them.) May31 asked Second pair of matching birthdays