Alternative hash table analysis Let us say that we have to hash $n$ elements to $m$ hash slots.
Now what could be the average length of a chain. We can assume that prob. that 2 elements will map to a particular location will be $1/m^{2}$, for  3, it will be $1/m^{3}$ and so on for the $n$th element will be $1/m^{n}$
The expected length for the chain on that location will be
\begin{equation}
 E[x]=1.\frac{1}{m^{1}} + 2.\frac{1}{m^{2}} + 3.\frac{1}{m^{3}} + ...n.\frac{1}{m^{n}}
\end{equation}
Is this step correct?
 A: If you intend the chain lengths to averaged over all slots, including the empty slots, then the answer is just the average number of elements per hash slot. This is obviously $\dfrac{n}{m}$ no matter what the probability distribution is.
If you intend the chain lengths to be averaged over only the non-empty slots, then we want the expected number of elements in the first slot, say, given that that slot is not empty. If we let $X$ be the number of elements in slot $1$ then:
\begin{eqnarray*}
E[X \mid X \neq 0] &=& \sum_{j=0}^{n}{jP(X=j \mid X \neq 0)} \\
&=& \sum_{j=0}^{n}{jP(X=j \cap X \neq 0)} \bigg/ P(X \neq 0) \\
&=& \sum_{j=1}^{n}{jP(X=j)} \bigg/ \left(1 - P(X = 0) \right) \\
&&\\
&=&\dfrac{n}{m \left(1- \left(\dfrac{m-1}{m}\right)^n \right)} \\
\end{eqnarray*}
A: The distribution in each bin is binomial. You have $n$ "trials", which are the $n$ elements. For any given bin, you have a probability $p = \frac{1}{m}$ of any given element winding up in the bin.
The mean of the binomial distribution is given by $\mu = np$, which in your case is $$\mu = \frac{n}{m}$$
