# Collisions in independent hashing

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 ?

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

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.