Algorithms: Design and Analysis, Part 1 - Problem Set 6 - Question 1

Problem:

Suppose we use a hash function $h$ to hash $n$ distinct keys into an array $T$ of length $m$. Assuming simple uniform hashing, that is, with each key mapped independently and uniformly to a random bucket --- what is the expected number of keys that get mapped to the first bucket? More precisely, what is the expected cardinality of the set $\{k:h(k)=1\}$.

Solution:

Intuitively, that would be $\frac{n}{m}$, let formalize and prove this fact.

Denote $X_i$ as the indicator random variable such that if the $i^{th}$ element get hashed to first bucket, then $X_i = 1$, otherwise $X_i = 0$.

$E[X_i] = 1 \times P(X_i = 1) + 0 \times P(X_i = 0) = P(X_i = 1) = \frac{1}{m}$.

Therefore, by linearity of expectation, we have $E[S] = E[\sum\limits_{i = 1}^{n}{X_i}] = \sum\limits_{i = 1}^{n}{E[X_i]} = \sum\limits_{i = 1}^{n}{\frac{1}{m}} = \frac{n}{m}$.