Fixee
Reputation
6,328
Top tag
Next privilege 10,000 Rep.
Access moderator tools
 Jun 15 comment How many even number in a sequence are there? Your iff is false in both directions. Jun 15 comment Second pair of matching birthdays @ShreevatsaR: The reason my simulation made me believe the answer was not proportional to $\sqrt{M}$ was that--as your program shows--the multiplier starts above 2.1 and gradually settles to 1.88... But your argument in your answer that it must be a multiple of $\sqrt{M}$ is quite convincing. Jun 15 revised How many expected people needed until 3 share a birthday? added 263 characters in body Jun 15 accepted How many expected people needed until 3 share a birthday? Jun 15 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 Jun 15 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. Jun 15 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. Jun 15 revised How many expected people needed until 3 share a birthday? deleted 37 characters in body Jun 15 revised How many expected people needed until 3 share a birthday? added 1161 characters in body Jun 14 asked How many expected people needed until 3 share a birthday? Jun 14 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. Jun 14 accepted A seeming paradox in a coin-flipping game Jun 13 answered Why is it that, $\forall x \in \mathbb{Z},\ x^5 \equiv x \pmod{10}$? Jun 10 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. Jun 4 accepted Second pair of matching birthdays Jun 1 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. Jun 1 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. Jun 1 revised Second pair of matching birthdays deleted 4 characters in body May 31 revised Second pair of matching birthdays added 499 characters in body May 31 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.