Let $H$ be a $s$-wise independent family of hash functions from $\{1,\ldots,M\}$ to $\{1,\ldots,N\}$. It is easy to bound one collision, but are there good bounds for muliple collision ?

  • 2
    $\begingroup$ Unless $M$ is very small, this event is actually pretty likely. $\endgroup$ Aug 12, 2015 at 20:54
  • $\begingroup$ Yes thanks - but I would already be happy to bound it by $\frac{1}{2}$ . $\endgroup$
    – fact
    Aug 12, 2015 at 21:02
  • 1
    $\begingroup$ That's very optimistic. What values of $M$ and $N$ do you have in mind? $\endgroup$ Aug 12, 2015 at 21:03
  • $\begingroup$ Also, what do you mean by $(a'_1,\ldots,a'_s) \neq (a_1,\ldots,a_s)$? $\endgroup$ Aug 12, 2015 at 21:03
  • 1
    $\begingroup$ Then the probability is extremely close to 1 for completely independent hashing. $\endgroup$ Aug 12, 2015 at 21:15

1 Answer 1


You can upper-bound your probability using a union bound. In particular,

$$\Pr[\exists x \in S . \phi(x)] \le \sum_{x \in S} \Pr[\phi(x)].$$

Using a union bound we obtain ${M^s \choose 2}$ terms in the sum, and each term is upper-bounded by $1/N^s$, so we find that your probability is at most

$${M^s \choose 2}/N^s.$$

If $M < \sqrt{N}$, then this probability will be at most $1/2$. If $M \gg \sqrt{N}$, then this probability is close to $1$.

(Qualitatively, this upper bound is fairly close to tight for a wide range of settings of $M,N$. I am not going to prove this fact, but you can take my word on it. So there's not much hope for a significantly better bound using some other proof technique.)

In short: as Yuval Filmus says, unless $M$ is very small, your event is actually pretty likely.

No, something stronger than $s$-independence will not help. Even if you assume that $h$ is generated uniformly at random from the set of all hash functions with the right signature (something that is not actually implementable), you don't get a much better bound.

The only plausible approach I can see is to choose a hash function $h$ that does not have any collisions at all: e.g., choose $h$ from a family of injections, or use a perfect hash. Each of these has serious shortcomings: the former requires $M<N$, and the latter typically requires you to know in advance the full set of values that you will ever compute $h$ on.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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