# Slot size bound for chaining

This is a question from CLRS

Q) Suppose that we have a hash table with n slots, with collisions resolved by chain-ing, and suppose that $n$ keys are inserted into the table. Each key is equally likely to be hashed to each slot. Let $M$ be the maximum number of keys in any slot after all the keys have been inserted.

a) Argue that the probability Q$_{k}$ that exactly $k$ keys hash to a particular slot is given by

Q$_{k}$ = ($\frac{1}{n})$$^{k}(1-\frac{1}{n})^{n-k} \binom{n}{k}. Which is pretty straight forward as hashing of a particular key at any slot is binomial trial with prob. of success = (\frac{1}{n}) and prob. of failure = (1-\frac{1}{n}) . So according to binomial trial probability that exactly k keys hash to a particular slot is Q_{k} = (\frac{1}{n})$$^{k}$(1-$\frac{1}{n}$)$^{n-k}$ $\binom{n}{k}$.

b) Let P$_{k}$ be the probability that $M = k$, that is, the probability that the slot containing the most keys contains $k$ keys. Show that $P_{k} \leq nQ_{k}$.

Which is, that a particular slot contains exactly $k$ keys and other slots less than $k$ keys.

Pr (a slot contains less than $k$ keys)= It contains 0 keys or It contains 1 key or It contains 2 keys........ or it contains k-1 keys

Given by

($\frac{1}{n})$$^{0}(1-\frac{1}{n})^{n-0} \binom{n}{0} + (\frac{1}{n})$$^{1}$(1-$\frac{1}{n}$)$^{n-1}$ $\binom{n}{1}$+......+ ($\frac{1}{n})$$^{k-1}$(1-$\frac{1}{n}$)$^{n-(k-1)}$ $\binom{n}{k-1}$.

So $P_{k}$ = $Q_{k}$ . Pr (a slot contains less than $k$ keys) = $\left(\frac{1}{n}\right)^k\left(1-\frac{1}{n}\right)^{n-k}\binom{n}{k}\times\Bigg(\left(\frac{1}{n}\right)^{0}\left(1-\frac{1}{n}\right)^{n-0} \binom{n}{0} + \left(\frac{1}{n}\right)^{1}\left(1-\frac{1}{n}\right)^{n-1}\binom{n}{1}+\cdots+ \left(\frac{1}{n}\right)^{k-1}\left(1-\frac{1}{n}\right)^{n-(k-1)}\binom{n}{k-1}\Bigg)$

My question is that how do i converge this. ?

To solve the task you should consider events $E_i$ which is that $i-$slot has $k$ elements hashed into and all other slots have less elements. Thus, $Pr(E_i) \le Q_k.$
From above $Pr(M=k) \le \Sigma_{i=1}^nE_i = nE_i \le nQ_k.$