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.$