2
$\begingroup$

For a formal problem statement, I quote from the text Introduction to Algorithms by Cormen et. al

Suppose we use a hash function $h$ to hash $n$ distinct keys into an array $T$ of length $m$. Assuming simple uniform hashing, what is the expected number of collisions? More precisely, what is the expected cardinality of $\{\{k, l\} : k\neq l \text{ and } h(k)= h(l)\}$ ?


Quite intuitive I proceeded as follows:

Let $X$ be the random variable indicating the number of collisions. Let us define an indicator random variable $X_{ij}$ which indicates whether the $i$th element ($e_i$) already in the table collides with the $j$ th element ($e_j$) when the $j$ th element is to be inserted.

$Pr\{h(e_i)=h(e_j)\}=\frac{1}{m}$. So $E[X_{ij}]=\frac{1}{m}$.

So based on that we have:

$$X= \sum_{i=1}^n \sum_{j=i+1}^n X_{ij}$$

Taking expectation on both sides we have: $$E[X]= E\left[\sum_{i=1}^n \sum_{j=i+1}^n X_{ij}\right]$$

Using linearity of expectation:

$$E[X]= \sum_{i=1}^n \sum_{j=i+1}^n E[X_{ij}]$$

But, $E[X_{ij}]=\frac{1}{m}$ , which is already found above.

So,

$$E[X]= \sum_{i=1}^n \sum_{j=i+1}^n \frac{1}{m}$$

$$=\frac{n(n-1)}{2m}$$


Below is how my peer approached:

Let $X$ be the random variable indicating the number of collisions. Let $X_i$ be the indicator random variable indicating collision during the $i$ th insertion of the element, $i=1,2,3,..,n$

So, $$X=\sum_{i=1}^n X_i$$

taking expectation on both sides, we have:

$$E[X]=E\left[\sum_{i=1}^n X_i\right]$$

Using linearity of expectation:

$$E[X]=\sum_{i=1}^n E[X_i]$$

Now let us find $Pr\{X_i=1\}$ then by the property of indicator random variable we shall have $E[X_i]=Pr\{X_i=1\}$.

Probability that there is collision during the first insertion =$0$ [First element is inserted without any collision.]

Probability that there is collision during the second insertion= $\frac{1}{m}$ [Assuming open addressing, $1$ slot is already occupied.]

Probability that there is collision during the third insertion= $\frac{2}{m}$ [Assuming open addressing, $2$ slots are already occupied.]

.

.

.

Probability that there is collision during the $i$th insertion= $\frac{i-1}{m}$ [Assuming open addressing, $i-1$ slots are already occupied.]

So,$$E[X]=\sum_{i=1}^n \frac{i-1}{m}=\frac{n(n-1)}{2m}$$


Though the final answer obtained by my peer is same as that of mine, but I guess there are quite a lot of issues with the approach. First it assumes open addressing, while my approach is a generalized one. Secondly, as per the formal problem statement given in the text, in the worst case if all elements hash to the same slot then we shall have $X=\binom{n}{2}$. So the spectrum of $X$ is , $X=0,1,2,..,\binom{n}{2}$

But the spectrum of $X$ as per my peer's method is $X=0,1,2..,n$. Is my peer's method actually correct?

$\endgroup$
1
  • $\begingroup$ In the second approach, it is not very clear how you are finding an empty slot after a collision happens. $\endgroup$ Dec 19, 2021 at 17:31

1 Answer 1

0
$\begingroup$

Both methods are correct in terms of probability analysis. It is just that the probability distributions of the two approaches are different. For example, take $n = m = 3$.

In the first approach, the probability distribution is as follows:

Pr $[\textrm{No. of Collisions} = 0 ] = 2/9$

Pr $[\textrm{No. of Collisions} = 1 ] = 6/9$

Pr $[\textrm{No. of Collisions} = 2 ] = 0$

Pr $[\textrm{No. of Collisions} = 3 ] = 1/9$

In the second approach, the probability distribution is as follows:

Pr $[\textrm{No. of Collisions} = 0 ] = 2/9$

Pr $[\textrm{No. of Collisions} = 1 ] = 5/9$

Pr $[\textrm{No. of Collisions} = 2 ] = 2/9$

Pr $[\textrm{No. of Collisions} = 3 ] = 0$

The expected costs in both the cases is $1$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.