Different probabilistic statement for Simple Uniform Hashing

Question

Let me denote the number of elements with $n$ and the size of the table with $m$. I was trying to understand the Simple Uniform Hashing assumption that people and books describe in works and make them into equations and realize which of the different equations are equivalent and which are not.

Simple Uniform Hashing as described by CLRS in page 259 says:

we shall assume that any given element is equally likely to hash into any of the m slots, independently of where any other element has hashed to.

So for that description I would mathematically write:

$$ Pr[h(k) = i] = \frac{1}{m}, \forall i \in \{0,...,m-1 \}$$

i.e. the probability that h(k) hashes to any index $i$ is equal to any index in the table of size $m$. Furthermore to satisfy the independence condition it requires I would also write:

$$ Pr[h(k) = i] = Pr[h(k) = i \mid Ops] = \frac{1}{m}, \forall Ops $$

Where $Ops$ is any set describing the keys that might have been hashed before $k$. So its conditionally independent of anything that might have happened before. Those are the equations and maths expressions I would use to describe uniform hashing.

However on page 260 (and on wikipedia ) we have a slightly differently phrased equation which I am having a hard time realizing if its the same as the one I wrote above which says:

$$ Pr[h(k_i) = h(k_j) ] = \frac{1}{m}, k_i \neq n_j$$

i.e. the probability that two non-equal elements map to a spot of the table is $\frac{1}{m}$.

Are these two definitions the same? Why is the second used moe often than the first?

Answer 1

They're not the same, but the one in Wikipedia is a consequence of the simple uniform hashing assumption.

Let $E$ be the event that $h(k_1)=h(k_2)$. Let $F_x$ denote the event that $h(k_1)=h(k_2)=x$. Note that

$$E = \bigcup_x F_x,$$

and the events $F_x$ are disjoint. Therefore,

$$\Pr[E] = \sum_x \Pr[F_x].$$

Now under the simple uniform hashing assumption,

$$\begin{align*} \Pr[F_x] &= \Pr[h(k_1)=x \land h(k_2)=x]\\ &= \Pr[h(k_1)=x | h(k_2)=x] \times \Pr[h(k_2)=x]\\ &= \frac{1}{m} \times \frac{1}{m}\\ &= \frac{1}{m^2}. \end{align*}$$

Plugging in, we find

$$\Pr[E] = \sum_x \Pr[F_x] = \sum_x \frac{1}{m^2} = \frac{1}{m}$$

since there are $m$ possible values of $x$.

Therefore, if the simple uniform hashing assumption holds, then the equation you found in Wikipedia also holds. The reverse isn't necessarily true.