[Math] Hash table chain length probability -Simple uniform hashing

probability

Consider a hash table with $m$ slots that uses chaining for collision resolution. The table is initially empty. What is the probability that after 4 keys are inserted that at least a chain of size 3 is created? (Assume simple uniform hashing is used).

  1. $m^{–2}$
  2. $m^{–4}$
  3. $m^{–3}(m–1)$
  4. $3m^{–1}$

MY TRY

$P(atleast 3) = P(exactly 4) + P(exactly 3)$

$P(exactly 3) = {m \choose 1}\frac {1}{m^3} \frac {(m-1)}{m}*4 = \frac{4(m-1)}{m^3}$ [choose chaining slot and 4 positions for non-chaining slot ]

$P(exactly 4) = {m \choose 1}\frac {1}{m^4} = \frac {1}{m^3} $

$$P(atleast 3) = \frac {1}{m^3} + \frac{4(m-1)}{m^3} =\frac{4m-3}{m^3}$$

Doesn't match any of the options.

Best Answer

Note: Your approach is correct, given that we may assume four pairwise different keys.

If we consider a hashfunction $$h:\mathbb{N}\rightarrow \{1,\ldots,m\}$$ and four pairwise different keys $k_1,k_2,k_3,k_4$, we obtain

\begin{align*} &P\left(h(k_1)=h(k_2)\right)\cdot P\left(h(k_1)=h(k_3)\right)\cdot P\left(h(k_1)=h(k_4)\right)\\ &\qquad=\frac{1}{m^3}\\ &P\left(h(k_1)=h(k_2)\right)\cdot P\left(h(k_1)=h(k_3)\right)\cdot P\left(h(k_1)\neq h(k_4)\right)\\ &\qquad=P\left(h(k_1)=h(k_2)\right)\cdot P\left(h(k_1)=h(k_4)\right)\cdot P\left(h(k_1)\neq h(k_3)\right)\\ &\qquad= P\left(h(k_1)=h(k_3)\right)\cdot P\left(h(k_1)=h(k_4)\right)\cdot P\left(h(k_1)\neq h(k_2)\right)\\ &\qquad =P\left(h(k_2)=h(k_3)\right)\cdot P\left(h(k_2)=h(k_4)\right)\cdot P\left(h(k_1)\neq h(k_4)\right)\\ &\qquad =\frac{m-1}{m^3} \end{align*}

$$ $$

We conclude: \begin{align*} &P(\text{chain length }=4)+P(\text{chain length }=3)\\ &\qquad=\frac{1}{m^3}+4\frac{m-1}{m^3}\\ &\qquad=\frac{4m-3}{m^3} \end{align*}

Related Question