2
$\begingroup$

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 ?

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

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.

| cite | improve this answer | |
$\endgroup$

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.