# Mean and variance of number of buckets of length $i$ in hashing with chaining

Consider a hash table with $m$ buckets, with chaining as collision resolution policy. Given the set $S$ that will be stored in the hash table, let $X_i$ be the number of buckets whose chain length is $i$. Then the cardinality $s = |S|$ of the set $S$ is $$s = X_1 + 2 X_2 + \cdots + i X_i + \cdots \enspace.$$ Clearly the summation can end at $i=s$. The number of non-empty buckets $s_m$ is $$s_m = X_1 + X_2 + \cdots + X_s \enspace.$$ I am interested in upper bounding $s-s_m$ for my application. $$s-s_m = X_2 + 2 X_3 + \cdots + (i-1)X_i + \cdots \enspace.$$ In the previous equation:

1. $s_m$ is known by $s$ isn't. However, $s$ is fixed and is not a random variable.
2. $X_i$ for $i\geqslant 2$ is also the number of $i$-wise collisions.

For $i=2$, if we are using k-independent hash functions with $k$ at least 4, we know the mean and variance of $X_2$ as a random variable [1, Lemmas 1 and 2]. Therefore we can bound $X_2$ from above w.h.p. using Chebyshev's inequality: $X_2\leqslant s_m^2/m$.

I am asking whether other works discussed the mean/variance of $X_i$ for $i>2$, or whether it possible to bound the quantity above with other means.

I can already generalise lemma 1:

Lemma Suppose that $s$ elements, denoted by $e_1,\ldots,e_s$, are hashed into a table of size $m=\beta s$ by a random function $h$ is a $k$-independent class $H_k$, $k\geqslant t$ for $t\geqslant s$. Let $Y_{i_1\cdots i_t}$ be an indicator variant whose balues is $1$ if and only if elements $e_{i_1},\ldots,e_{i_t}$ hash to the same
location. That is $h(e_{i_1})=\cdots=h(e_{i_t})$. Let $X$ be the
random variable whose value is the number of $t$-wise collisions
between elements, that is, $$X=\sum_{1\leqslant i_1 < i_2 <\cdots < i_t \leqslant s} Y_{i_1\cdots i_t} \enspace.$$ Then $$\mathbb E[X] = \binom{s}{t} \frac{1}{m^{t-1}} = \binom{s}{t} \frac{1}{(\beta s)^{t-1}} \enspace.$$

Proof Since $H$ is $k$-independent for some $k\geqslant t$, $$\mathbb E[Y_{i_1 \cdots i_t}] = 1/m^{t-1} \enspace.$$ Hence $$\mathbb E[X] = \sum_{1\leqslant i_1 < i_2 < \cdots < i_t \leqslant s} \mathbb E[Y_{i_1\cdots i_t}] = \binom{s}{t} \frac{1}{m^{t-1}} = \binom{s}{t} \frac{1}{(\beta s)^{t-1}} \enspace.$$

Probably Lemma 2 can be generalised as well, although the combinatoric counting will be a little bit more challenging. However, is there a solution that we can stick only with 4-independent hash function not with s-independent hash functions, since $s$ is unknown?

UPDATE: A generalisation of Lemma 2 may be obtained. The combinatoric counting is shown here.

Thank you,

1 Broder, A., & Karlin, A. R. (1990). Multilevel Adaptive Hashing. SODA'90. http://dl.acm.org/citation.cfm?id=320181.

• The calculation in  concerns the number of collisions, which is $\sum \binom{k}{2} X_k$. It shows that the expected number of collisions is roughly $s^2/(2m)$, and the variance is at most $s^2/(2m)$. Note that these formulas depend on $s$ rather than on $s_m$. In fact, you can't bound the number of collisions as a function of $s_m$, since for large $s$ you will get $s^2/(2m)$ collisions, a quantity growing to infinity, but $s_m$ is bounded by $m$. May 12, 2016 at 19:33
• @YuvalFilmus Would kindly elaborate why $\binom{k}{2}$ is a factor in the sum? May 12, 2016 at 20:03
• The number of collisions is the number of unordered pairs of inputs which map to the same hash value. Given this description, it's an exercise to derive my formula. May 12, 2016 at 20:10