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 5, 2015 at 19:49 | comment | added | esg | I should have stated that the $X_i$ are jointly Multinomial (with $n$ and $p_1=...=p_k=1/k$), which makes clear that (1) it agrees with the model of a randomly chosen hash function and (2) that each $X_i$ is $Bin(n,1/k)$. A proof along the elegant lines of the first solution can also be given, by showing that the no. $X_c$ of pwds which hash to the same value as a randomly chosen pwd has distribution $1+Bin(n-1,1/k)$, and computing $\mathbb{E}(R)=\mathbb{E}{n+1 \over 1+X_c}$. But I found the approach above simpler. | |
| Mar 5, 2015 at 14:55 | comment | added | Mark Wildon | Of course. Linearity of expectation strikes again. Thank you for the explanation. | |
| Mar 5, 2015 at 12:33 | comment | added | Douglas Zare | @Mark Wildon: Independence isn't required. We can write the stopping time as a sum of random variables that are $r$ when the special ball goes into the $i$th bin, and $0$ otherwise, and use linearity of expectation, so only the distributions of balls in each bin matters. | |
| Mar 5, 2015 at 10:26 | comment | added | Mark Wildon | But if each $X_i$ is independent $\mathrm{Bin}(n,1/k)$ then we need not have $\sum_{i=1}^k X_i = n$. So I don't think this agrees with the intended model for a randomly chosen hash function. Of course it may still be a good approximation. | |
| Mar 4, 2015 at 19:01 | history | answered | esg | CC BY-SA 3.0 |