3 ms·
The result is that the non-uniformity does have an impact effect, but it's very, very small. When there were four or less people in the room, from my experiment
by nkurz 7y ago
The result is that the non-uniformity does have an impact effect, but it's very, very small. When there were four or less people in the room, from my experiments, the non-uniformity of distribution resulted in a slight decrease in the chances of a birthday collision (but this could loss of precision from too small a sample size as the percentage of times, for instance that two people collide is just 0.274%). After five people, the non-unformity provided a slight increase in the chances of all collisions. This is what I would expect.
Does this make any sense? The author says that with a realistic non-uniform distribution of birthdays, they found that collisions were less likely when there were fewer than 5 people involved. I can't think of any reason this would be the case. If certain birthdays are more common than others, I'd think that the chances of a collision must go up regardless of the number of people involved.
Is there any plausible mathematical explanation for this effect? Or was the experiment just underpowered? Or worse, might the simulation code be buggy? Presumably they would have run the simulation more than once after getting such such a counterintuitive answer, and it seems really unlikely that this effect would be consistent unless something was broken.
- ordu 7y ago> I can't think of any reason this would be the case. The author suggests such a reason: the loss of precision. As I understand it hints to a limited precision of float/double number representation. When you calculate a sum of millions of fractions some of fractions could turn into zero, because you have divided a too small number on a too large one.
- nkurz 7y agoI think the floating-point precision interpretation is negated by the author's suggestion that the loss of precision is "because of the small sample size". I can sort-of see how a purely analytical solution might be susceptible to rounding issues (and I say sort-of because I don't think such an approach would actually include multiplying millions of fractions, and the straightforward approach involves numbers near 1 instead of near 0), but the reference to "sample size" makes me think that this was a numerical simulation. But presuming the author ran the simulation more than once (wouldn't you do this if you had such a surprising result?) I don't see how there could be any consistent effect unless there was a bug in the logic of the program. Unless maybe they ran it multiple times with the same random seed and got exactly the same results?
- waterhouse 7y agoI agree with your intuition. I think the author must either be looking at statistical noise or have made a mistake. At least for the case of two people, if we say that a_n is the probability of a person's birthday being chosen (so that ∑(a_n) = 1), then the chance of a match is ∑(a_n^2). To construct a rigorous argument, one could bring in the power mean theorem[1], which states that, if x > y and the sequence {a_n} is all nonnegative, then (avg(a_n^x))^1/x ≥ (avg(a_n^y))^1/y, with equality if and only if all elements of {a_n} are the same. This can be used to show that, if ∑(a_n) is fixed, then ∑(a_n^2) (i.e. the probability of a match) is minimized only when {a_n} are all equal. It's less obvious how to make a rigorous argument for the cases of 3 and more people, but https://en.wikipedia.org/wiki/Muirhead%27s_inequality https://en.wikipedia.org/wiki/Muirhead%27s_inequality might help (if you trust the proof of it). [1] https://en.wikipedia.org/wiki/Generalized_mean#Generalized_mean_inequality https://en.wikipedia.org/wiki/Generalized_mean#Generalized_m...