Hash Table: Probability that the longest chain has length k Say I have a hash table of size $m$, with collision handled by chaining. Assume the hash function hashes uniformly, so every key has probability of $\frac{1}{m}$ of being hashed to any slot in the table. I insert $n$ keys into the table. What is the probability that the longest chain in the table is size $k$?
My initial idea is like this:
$$\sum_{i=1}^{m}p_k^ip_{lk}^i$$
where $p^i_k$ is the probability of having $i$ slots with chain size $k$, and $p_{lk}^i$ is the probability of having $m-i$ slots with chain size less than $k$. I am able to get the probability of one slot having chain size $k$,but not sure how to derive the other probabilities from it. A pointer in the right direction is appreciated!
 A: Leaving the following answer even though it applies to a slightly different model than the one asked about.
Consider the random variables $(A_{ij}\colon 1\leq i\leq m,\ 1\leq j\leq n)$ given by $A_{ij}=1$ if the $j^{th}$ inserted key hashes to slot $i$, and $A_{ij}=0$ otherwise. Then the variables $(A_{ij})$ are mutually independent and each distributed as a Bernoulli$(1/m)$ random variable. Let $S_i$ denote the length of the chain in slot $i$, or equivalently,
$$
S_i=\sum_{j=1}^n A_{ij}.
$$
Your question asks to find the distribution of $\max_{1\leq i\leq m}S_i$. Now we come to a branching off point: to some people, even rephrasing the problem in this way is already an answer, but I will outline some of the different paths one can choose to take from here.
Observe that $S_i$ is Binomial$(n,1/m)$ and the $S_i$ are independent. If an exact asymptotic is desired (for instance, assuming $m$ is $O(1)$ and $n$ tends to infinity) then one can use a Gaussian approximation to $S_i$ and follow similar approaches as in Expectation of the maximum of gaussian random variables or Bounds for the maximum of binomial random variables to get good bounds on the size of the maximum.
If weaker bounds suffice, you can follow the approach outlined here
Maximum of $k$ binomial random variables?
If you need an exact formula, you can simply use the probability mass function to express things as a complicated sum.
