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} $.
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} $.
No comments:
Post a Comment