3
$\begingroup$

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!

$\endgroup$
8
  • $\begingroup$ Exactly size $k$ or at least size $k$? $\endgroup$
    – saulspatz
    Jul 30 '19 at 22:23
  • $\begingroup$ Exactly size $k$ $\endgroup$ Jul 30 '19 at 22:34
  • 1
    $\begingroup$ The events aren't independent, so multiplying the probabilities doesn't look right. $\endgroup$
    – saulspatz
    Jul 30 '19 at 22:41
  • $\begingroup$ I see... Then I am stuck... Can you point me in the right direction? $\endgroup$ Jul 30 '19 at 22:46
  • 5
    $\begingroup$ I took it to mean: Given $n$ iid variables $X_i$ taking values uniformly from $\{1,2, \ldots, m\}$, what is the probability that $\max_j( |\{i | X_i = j\}| ) = k$? $\endgroup$ Jul 30 '19 at 23:44
1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ But the $S_i$ are not independent. e.g., if $S_1 = n$ then we know $S_2 = \ldots = S_m = 0$. $\endgroup$ Jul 31 '19 at 16:46
  • $\begingroup$ The $A_{ij}$ are also not independent. There can only be one $i$ with $A_{ij} = 1$ for each $j$, since each key hashes to only one slot. $\endgroup$ Jul 31 '19 at 16:52
  • $\begingroup$ @JairTaylor good catch, somehow I transformed the model in my mind when writing the answer. That being said, if one is interested in asymptotics when $m=o(n)$ then my model is a good approximation of the one in the problem statement, up to a simple rescaling. $\endgroup$
    – pre-kidney
    Aug 1 '19 at 2:57
  • $\begingroup$ Right, I think the asymptotics should be similar in that domain, although I'm not sure how to prove it. $\endgroup$ Aug 1 '19 at 4:51
  • $\begingroup$ It should be a relatively straightforward consequence of the strong law of large numbers at least for the regime $m=o(n)$, although I will hold off on working out the details until @William clarifies the question further. $\endgroup$
    – pre-kidney
    Aug 1 '19 at 5:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.