4 ms·
An even, shorter intuition would be that: number of pairs in a group of n people grows O(n^2), which implies some square root factor. I would lead with that bef
by bhl 7y ago
An even, shorter intuition would be that: number of pairs in a group of n people grows O(n^2), which implies some square root factor. I would lead with that before starting a more rigorous proof.
- waterhouse 7y agoAgreed. To narrow down some of the details: There are n*(n-1)/2 = roughly n^2 / 2 pairs. If each pair has a 1/k chance of matching, then the expected number of pairs that match is (n^2 / 2) / k. Therefore, if we set n = √k, we get roughly 0.5 pairs on average. Now, if it were impossible to ever get multiple matching pairs, then "the chance there's at least one match" would be equal to "the expected number of matches". Specifically: "chance of at least 1 match" = "expected number of matches" - "chance of at least 2 matches" - "chance of at least 3 matches" - ... . Since it's possible but unlikely to get multiple matches, the approximation should be reasonably close.