Video 5-2: Universal Hashing Guarantees

0:02 What is it that a universal hash family or hash function guarantees us specifically? And so, the first lemma says we have n keys from some universe as before and m buckets. We use a hash function that's chosen from some c-universal hash family, so just the definition from before. And now we look at a certain uh maybe not so intuitive quantity, namely the pairwise collisions. So, it's just the the pairs of i's and j's of indices of these of these keys so that uh the two corresponding numbers have the same hash value. This sounds a bit like overcounting, and in a way it does. The point of c is not that this is the most natural quantity to to determine. It's the one that is easiest to analyze. That's why we're looking at it.

0:57 So, the statement is the expected value of this c is bounded by such a such a bound. Uh last time we already convinced ourselves that this is indeed very close to the best possible for this um quantity c. Uh clearly there's an upper bound for c, namely the set of all pairs. But there's also a lower bound because we're trying to distribute n numbers into m buckets. So, in the best possible situation all of the buckets have n over m numbers. And then uh even if that's in this perfectly like a evenly distributed scenario, all the buckets are same height full at all n divided m. We still have a number of collisions from within that bucket, namely that many. n over m choose two. I can pick any pair inside the bucket, and these will contribute one of these pairwise collisions. And I have that for m buckets. So, by and large, this uh is just square of this upper um component. So, n squared over m squared from the numerator here.

2:06 And I multiply by m. So, essentially, I get n squared over m. Which is roughly what I get, apart from the constant factor in front. So, I have a this constant c from the universality, and I have the factor two that I'm uh that I also get.

2:24 Anyway, this is this is the best case. I'm I'm lying away the factor two here. So, I think up up to the factor c, this is almost as good as it can possibly be. And this says, "Oh, in expectation, we're very close to this best possible scenario."

2:40 Now, uh the proof of this is very easy, because it's an expected value of something that is just a sum. Uh this is the sum of the expectations. Uh let me say c i j for the potential collision.

3:06 And c i j is an indicator random variable that says whether or not the hash values here are the same. All right, this this is Iverson bracket. It's one if the condition is true, zero otherwise. Uh clearly, mm expected value of these c i j is the probability that this happens.

3:34 That's the probability of some hash collision. And given that we're taking this function h from uh I mean, what what is random here? This is all is all of this is random over the hash function that we choose. The integers can be worst case. Uh they can be fixed up front. All of these are essentially over the hash function that we choose from our our family. And so this is by definition 1 over a C over M because it's a universal family of hash functions. So each of these individuals uh C I J has this uh expected value. So we can upper bound the whole thing by the number of these terms. Uh times this expected value.

4:30 And if you work out uh I mean I think I just did a crude upper bound here. That's precisely the bound that we state. So it's very easy to analyze precisely because this uh pairwise number of pairwise collisions is the sum of many simple terms. And crucially here what we needed was only the pairwise collision probabilities. That's why it's sufficient to have this fairly simple universal class of of hash function hash functions here. If you take three or more hash values, they are no longer independent or they don't behave anywhere close to this necessarily. But here we only need pairwise, so that's good enough.

5:16 Now you'll we'll actually see a direct application of this fact. Um but a bit more uh intuitive for for hashing is maybe the following statement. If we consider the same scenario, so these N keys hashed into M buckets, picked from a universal hash function family, etc. And let's look at how large the buckets are, how many elements hash to the same same uh same bucket. Uh let's call these XJ for the bucket J. Then we can compute well, easy is the um Uh I guess that's in the subscript, sorry. What is the the number of elements that hash into the same bucket as some given xi? That's the first statement. And the second is about the largest, the most loaded bin. We can also say something. Now, the bound here um may not be the strongest you can get from hashing, but this is what you get from universal hashing in in an advanced algorithms, we show that this is also the best bound you can prove for universal hash functions or pairwise independent hash functions.

6:30 Uh forget that for now if you like um I just wanted to show some some simple results you get from universality. Uh for the first one how many other keys are hashing to the same value as I am? Well, uh it's always going to be me. So, one. And then for all the other elements, not I I may have a collision, right? Between I and J. So, it turns out that's the same number as we had before. And so I have n minus one other things that might collide with me. And so, in expectation, that's the size of the bucket.

7:24 The second is maybe a bit more interesting, this this upper bound. And so, here this is just to convince you that these pairwise collisions are good for something.

7:38 The observation is that if you have any bucket with, say x hat elements in it. We have at least the pairwise collisions from that bucket by itself.

7:55 All of these keys X hat choose two Which means if any single bucket is really large, also this number of pairwise collisions has to be large. And intuitively, the number of pairwise collisions is the sum of essentially independent events. So, we should be able to get a decent upper bound for the probability. Now, they're not really independent, so we cannot apply something like Chernoff bounds or or stronger bounds. But, we can do something. We can at least do a simple bound. So, this means that then C is larger than X hat choose two. And this you can lower bound say by X minus one squared over two.

8:56 Now, um this bound from the lemma this one here. I'm just pulling this inside the square root. It's a bit nicer to write. And I'm I'm adding a plus one because this is strictly greater. Uh if I have this, that implies something about the bound we have here, namely X hat minus one squared over two is a I put the minus the one to the other side. I square the whole thing and I have X hat minus one squared is this thing and I divide by the two. So, what's left is the the C N squared over M.

10:02 that my C is at least C N squared over M. Well, because C is bigger than this guy. Uh and that by part by the lemma from before, that is two times its expected value. Or at least uh So, the statement we're trying to bound the probability of is a statement of this form. The variable is twice as large as its expected value.

10:35 What inequality would we like to apply to this? Let's see if people remember. So, by I'll leave that blank. The probability of the max X J There's one one tiny step, I guess. Uh the largest bucket is at least as large as this. So, all the argument here is about a single bucket being large. So, clearly if the largest is large, then all of uh there is one that is large.

11:19 So, here I'm just taking again uh the statement from the lemma. So, this this bound. Which is saying that some variable is twice the expected value.

11:45 Which uh I'm sure people will remember is for any non-negative random variable you can bound these precisely statements of this form. If you if you remember nothing else of probability, you should remember this one because anything else can kind of be shown from it. Is uh not hard to prove as well, but okay. Uh let's let's leave it here. So, what what have we learned? Um Basically, this pair of number of pairwise collisions gives us a relatively simple way to bound certain things. This is not again it's not a super convincing bound maybe because we have n divided square root m. But this is as as good as uh pairwise independence gets us.

12:41 And I hope you agree that the analysis wasn't hard. Uh all we had to do is argue a bit about these pairwise collisions.