Timeline for What is the formal analysis with Simple Uniform Hashing that the load factor is $\alpha = \frac{n}{m}$
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 27, 2016 at 7:57 | comment | added | Yuval Filmus | In my approach, each value of $j$ has the same probability $1/m$. This distribution is known as the uniform distribution. This calculation works for any hash distribution, uniform or not. | |
| Feb 27, 2016 at 2:54 | comment | added | Charlie Parker | sorry for being really picky, I just genuinely want to understand your explanation. How does your answer differ from the one that I suggested? Also, What is your expectation over? Is the probability (of whatever event your summing across) $\frac{1}{m}$? More precisely, how does your first expression $\mathbb{E} [n_j]$ become $\frac{1}{m} \sum^m_{j=1} n_j$? Whatever step that was skipped there is what is throwing me off. Thanks for the patience and help Yuval. | |
| Feb 16, 2016 at 7:38 | comment | added | Yuval Filmus | The equation is correct, but useless here. You pick $j$ uniformly at random from $\{1,\ldots,m\}$, and this defines $n_j$. You can compute $\Pr[n_j = x] = \frac{1}{m}|\{ j : n_j = x \}|$, but this doesn't really help you compute the expectation of $n_j$. | |
| Feb 16, 2016 at 0:34 | comment | added | Charlie Parker | sorry for my question, but I am still a bit confused. Usually I think of expectation as a weighted sum so in that case we have $\mathbb{E}[n_j] = \sum_x x Pr[x]$, how does that equation come into play here? In particular $n_j$ must be a random variable and somehow have a distribution...right? In particular it has a distribution over weights, so it has $\mathbb{E}[n_j] = \sum^{m-1}_{x=0} x Pr[n_j = x]$. Is that equation not correct? I've update my question with details concerning this comment if it helps. | |
| Feb 16, 2016 at 0:18 | history | answered | Yuval Filmus | CC BY-SA 3.0 |