Timeline for A balls and urns model for a hashing problem
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 3, 2015 at 16:41 | vote | accept | Mark Wildon | ||
| Mar 3, 2015 at 12:58 | comment | added | Douglas Zare | @Mark Wildon: That urns with $k$ balls are $k$ more times as likely to have the special ball is the difference between the distribution of balls in the special ball's urn, about $\textrm{Pois}(1)+1$, and the distribution of balls in a general urn, roughly $\textrm{Pois}(1).$ $P(Y+1=10) = 10 P(Y=10).$ | |
| Mar 3, 2015 at 11:02 | comment | added | Mark Wildon | (+1) I agree with this answer on the assumption that $X$ is close to Poisson with mean $1$. But my intuition (which may well be wrong) is that the special ball is disproportionately likely to be in an urn containing many other balls. Yes, of course the problem makes sense with different domain and range, and I'd be interested to have a general answer. | |
| Mar 2, 2015 at 22:52 | comment | added | Douglas Zare | This is similar to the analysis of the expected value of buying $2$ lottery tickets with the same combination. You can extend this to the case that you don't have an equal number of tickets purchased by other people as combinations, or where your hash function has a range that is not the same size as the domain. | |
| Mar 2, 2015 at 22:51 | history | answered | Douglas Zare | CC BY-SA 3.0 |