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?
