Video 9-2: Balls and bins

0:03 This is where we left off. Uh the three terms, don't u mix them up even though they're uh somewhat similar. Uh we've already discussed the uniform hashing assumption last time. Here is uh it's written up again slightly u more more formally. Um we have n elements that are inserted and we don't really know what their values are. All we care about is the hash sequence. So um in the order that the elements arrive, we apply the hash function to each of them. And the assumption called the uniform hashing assumption just uh says every possible sequence of hash values. All m to the n possible sequences are equally likely. And one way to read this is hold on there's no dependence on these input data elements x1 to xn. really the hash values are computed from them fine but we just post talk assume they're equally likely. So nothing in the data structure under this assumption may depend on the input data itself apart from their their number.

1:14 And so we might as well forget the data entirely and look at a mathematical abstract model of the situation that's a bit uh cleaner to study. And we'll briefly recap um what can be said in this in this model. That's the balls into bins model. And the name is is uh what it does you uh throw n balls into m bins. Now I'm I'm picking the parameters here so that they match the hashing application that I always have in my mind when I think about balls and bins uh or the balls into bins model. For some uh for some obscure reason the literature always swaps n and m. If you look up results some in some book almost always you have n bins and m balls. And I find this infuriating. So I'm just going to drop that convention and swap it around. It's always going to be n items that we insert and the hash table has to be of size m. That's kind of a law of physics to name that m. I don't know. Um I'll I'll stick with it and there's no inconsistencies on the slides hopefully.

2:24 But if you look up in books take take care of this. Um because we have this uniform hashing assumption. the ball I whichever one it is independently of all the other balls finds its bin uniformly at random. So if you wanted you could uh give the the bin of the E ball could give that a name and we can use our notation to say that this is uniform in the available bins.

3:06 Okay. Now I tried to write so clean and neatly and properly. Let's do this here as well. That's a way to write uh that assumption. It's a convenient abstraction from what actually happens. We normally think of uh hashts or I think of hashts as the prime application of this. Um but you can model other things um as balls into bins scenarios. You can also use it for um modeling um m servers and n are clients or or jobs that arrive and you have to load balance the the jobs on the servers. Then you could just uniformly at random pick a server each time. That's one assumption that you could try to um try to make and then analyze what the system does and many other situations where you have this uh this kind of model that can tell you something about the performance.

4:09 It is a bit optimistic in that it makes this strong assumption that everything is independent and uniform. And so you should keep in mind that for hashing it is almost the the best imaginable case and maybe a bit uh a bit um optimistic to assume it. On the other hand, if you take good random uh good good hash functions in a practical sense, things that uh that often are used for for constructing string hashes, and I'm not talking about cryptographic hashes here, uh just fast hash uh functions, this murmur hash, and then some implementations. We won't get into the details. These are all uristics, but they tend to work on the kind of data that people apply them on. they tend to work out to be almost like this uh uniform hashing assumption. So often you get results that are not completely uh uh only in theory land but it's a bit of a uristic and if the data is adversarial you can't you can't rely on it.

5:13 Now let's uh think about this model briefly and um even if you've seen it before I want to point you to some slightly uh to a headscratching moment maybe um throughout that's the the last bit of of notation for now I'll use you can forget about bi I'm not going to use that much but x i is the number of balls in bin i. I should have uh called that J. I think I'm using J for the bins most of the time. That's just the number of balls that fall into a specific bin. We have our M bins. Now, these are all equally distributed by assumption and they're all binomial because every ball independently of the others decides where to fall. So, every specific bin that I'm looking at has a one in m chance of getting the e ball. And so in total it has a binomial distribution with parameter n and 1 / m.

6:09 So again this is really only true under this strong iid assumption. But if you do that then it's a binomial distribution. Uh I've talked at length about this in previous chapters uh that they're highly concentrated. In particular, we have these turnoff bounds. Let's say these guys are going to be very close to their expected value. Right now, let's simplify things a bit and get rid of a parameter. We set the number of balls and bins the same. That's often the kind of uh starting point for analysis just to make life a bit easier. The expected number of balls per bin is just one, right? That's the expectation of the binomial distribution. n* p. p is one overn. At the same time, let's count how many bins are expected to be empty. No balls at all. Well, it's uh the total number is is linear. So I I can sum up for every for every bin are you empty or no? And so by linearity of the expectation, the expected number of empty bins is the sum over all the bins. And for each bin the probability that it is empty um that of course uh we can compute it's the same probability for each bin. It's m times the probability that all the balls fall not in this bin. So it's the counter probability of the 1 / m and to the power n. And so if we set n to m then we can use this approximation.

7:50 Um I mean it's it's really a a inequality in both directions but uh it's good enough say here for for youristic argument. Uh indeed yeah I'm including the error bounds here. You can take um uh I think it's 1 + 1 over n minus one. If you if you put that in that's less than e. And then that that's not true the other way around.

8:28 No, it converges to E. So there's a there's a plus minus one. But you can uh you can get uh a precise error bound like this for for this point. Um the derivation is not so important. It's an easy calculation. But the result means um there's a one. This is a one over e. For some reason I'm I've lost that here. There's a minus, right? So this is this is true. But then this thing has a minus. So it's e to the minus one. Maybe I'll smoke a little exponent here.

9:11 Okay. Nobody can read this. There's a constant fraction of all bins that we expect to be empty. The expected number of empty bins is a constant fraction of all bins. And that doesn't seem to go well together with having in expectation a ball in each bin, right? This is somehow we can't have both at the same time. And so uh one way to read this is if you just look at expected values is sometimes u misleading or they can give seemingly contradictory results at least as long as you uh interpret expected value as that's going to likely happen which of course here is not actually true if you I don't know if I managed to trick you here or not. Turnoff bounds of course are true for binomials of any parameter. But if you look up what they actually say it's uh the uh expected value but then the plus minus the the uh error bound depends only on n not on p. The bound you get from churn of bounds would say okay every bin is at most root n big with high probability or square root n plus a tiny bit. And that's a true statement, but not so useful and very far away from saying most bins have one ball. All right.

10:36 Okay. Uh, one way to uh resolve the puzzle would be to look at the birthday paradox and we'll we'll kind of uh use that later as a as an um intuition. So uh it's useful to have one intuitive uh result there in mind. So birthday paradox is this uh this scenario you have people at a party and the question is is it likely that you have two people with the same birthday uh translated into our formal model. It's just the number uh uh n the number of balls that you have that you have to throw into a given set of bins so that there is some bin that has two balls. And of course this is not a hard cutoff. Um but we can say uh when is it at least probability 1/2 that you uh see a bin with two balls or more.

11:32 The uh method to crack this or to approach this is to compute the counter probability. What's the probability that all the bins have at most one ball? And we go through the balls to determine that. So this is uh the first ball. It has all bins available. There's nothing that would make uh any bin over full. But for the second ball, there's the first bin, that ball one picked, that's no longer available without violating the constraint of having one ball per bin at most. So, one bin is gone, but everything else is still possible. And the same pattern goes on for the i ball. There's I bins that have been taken. They have to have exactly one ball because we don't allow more. And so uh you always have one over i over n one minus i / n. So of course you can just go and compute that product for fixed values of of n and m and see what the probability works out to.

12:36 uh to make a more general statement again um approximations help and it's the the tailaylor series of the exponential uh function that helps us here. So just uh add x equals 0 you get 1 plus x which is also the uh the tangent. So it's always below. So this uh would always be a a minus I guess but doesn't matter. It's a it's an error term of the order of x^2 as x goes to zero. If you plug that in for each of these terms then you get uh I'm using it reverse. Right? This is what we have on the left.

13:19 Now I'm I'm bringing the error term to the other side and I'm inserting into the exponent what I have here as the 1 plus x. And so these are all negative. So I'll get negative exponents and I get an overall error term that you can compute if you if you care. And now we have an exponential. So we can uh sum up all the exponents. And that's just uh the sum of the first integers divided by m. So we get roughly uh as an exponent minus n ^2 over 2m.

13:50 This assumes that n / m converges to zero. It's an asmtoic that's that's valid for this. And if you think about it, if n and m are close to each other, it's not going to be possible to have to avoid collisions. If you throw almost as many balls as bins at the very least, if you throw more balls than bins, then you'll definitely have a bin with two balls. So, this is is clearly not going to make sense if uh n is approaching n is approaching m but for smaller values of number of balls. And you can insert well when is this non-trivial meaning not entirely close to zero or one. It's going to start out if n is zero at one and then it's going to fall exponentially down even worse because it's squared right so it's very very quickly uh falling down and the range where it it falls from from essentially one to zero is exactly uh when this is a small number so when when this is close to one so that's when n is roughly square root of m Okay, specifically if you want to equate that to 1/2, you can calculate what the value of n is and if you have the application from from the birthday paradox, you get some 23 people, 22, uh then you have a probability of 1/2 that there's two with the same birthday.

15:23 And of course, the paradox is that you you intuitively maybe think you need more people for that to be likely because it's so many days in the year and you don't always meet people with the same birthday, but yeah, it's actually going to be a smaller number because the uh it's not uniform, right? There's always uh for obvious reasons there's certain certain periods of the year where it's more likely to be born than others, but that's a different story.

15:57 What it means for this uh paradox from before is we had two expected values. The expectation how many balls per bin and the expectation of how many empty bins. Um and the paradox only really came from somehow assuming that all bins simultaneously are close to their expectation. And that's just something you shouldn't shouldn't really expect. It's not actually so likely that all bins are closed to their expected occupancy. And uh that's true in many ways. All right, let's let's do some uh some real math. Um that has applications for for hashing. So one interesting question for hashing is if you just do this separate chaining everything that ends up in one bin is a linked list and you have to do the searches by following reading through the linked list. What's the worst that can happen under this uniform hashing assumption? So we're still assuming the best possible world in terms of the hash values. Um but you're you're using essentially a hash table of the same size as the number of items which is up to constant factors what you would use in practice. Maybe for chaining hashing you'd even use a few uh slightly smaller number of buckets and for open addressing a bit bigger but um the hash table as a linear function of the number of items is the usual setup.

17:27 And so this theorem says we should expect a weird number of balls in the most loaded bin. So you take the the maximum uh the fullest bin formally in our model is just the the maximum over all J among the bins and then XJ. Uh that's a random variable. You know what? This is popping up a few times. Maybe it's worth giving it a a name. I don't think I've used the x hat anywhere. Let's call that x hat. Um, and we're supposed to show that the bound is login over log login. What a weird bound. Also, uh well, we'll we'll come to uh the interpretation after doing the work, I guess. Um so you're maybe maybe you can already think a bit about it. Um, how can we prove this? Uh, we're just doing an upper bound here, but that's not where the intuition dies. You'll I'll comment on that later. The probability that this this largest xi is greater or equal than some specific threshold that we'll specify later. And this will eventually take this form.

18:52 Let's try to uh compute that. And that seems in general seems a a hard thing to compute because the maximum of random variables is a is a tricky beast. But because we're only interested in a tail bound that it's bigger than some value m, when is the maximum bigger than some value m? Well, when any of the elements is bigger than value m. And so we can use the union bound to get because they're also uh equally dist um identically distributed. It's just n times the probability that any yeah okay this is this is m nominally but uh we set n to m so it's the same. I'm going to keep m here because I think it's more logical.

19:55 Okay, so we've reduced the problem to tailbound for the for any specific bin say the first effectively that's that's just a binomial distribution, but we're we're summing over this. So we can rewrite this or you could express it as the sum over the probability weights for the binomial distribution. Another option is to say we uh take the union over all subsets of balls of the size that we want at least m and we take the event that the balls all balls I in this set I land in the given bin.

20:55 This is slightly more convenient than summing up the probabilities for X1 to be exactly a certain value because now we can use union bound again. That's a a union of events. So we're going to take the sum over all the events. They're all equally likely because everything's symmetric. So all we have to do is count how many subsets of size M are there out of the n balls. And that's a binomial coefficient and choose capital M.

21:23 And then we have the probability that any specific set to the power m because we need that many of them. I'm I'm just looking at those balls and not and forgetting about the others. Okay. Uh that's the easy bit. Now uh let's use that n and m are the same. So really this is uh let me just replace this here. Ah okay let me let me not do it. So uh that's Uh if we unfold this binomial coefficient then uh we can simplify this uh a good bit. This is n factorial divided m factorial and n minus m factorial. That's just plugging in the definition. And then we have the n to the m down here. Now if you look at uh a bunch of terms um namely all these uh there's an n factorial up here and there's an n minus m factorial so there's the largest terms are missing but then we have the largest term up here m times so the uh the denominator will be strictly bigger Right? There's the same number of terms and you can match them up. You have n and n minus one and n minus 2 and n down to n minus m and still n and then the others are cancelling exactly.

23:35 Right? So uh if you if you use the if you remember this this notation I might have used at some point balling factorials clearly this green part is is at most one. So we can upperbound the overall thing by uh 1 / m factorial and then again we can use sterling's approximation which is uh in this case we use the lower bound So this is this is true and then you can continue here to get e / m to the power m and then this this other term here uh because it's 1 / m factorial we get a a one over this 2 pi I m square root again that's less than one. So we we could just drop it if you want to continue our inequality.

25:17 if you if you go back this was the probability that a single bin is larger than m. If you look at that function if you make m big enough that's going to drop drop very rapidly right because this power m here we divide by m first and then it soon gets this below one and then the power m just goes exponentially down. uh we're using this in the union bound up here. So n times the whole thing and that's the the desired probability. So the probability that our x x head is at most m will be n * this thing. So we would like this to be essentially 1 / n then or smaller Then the overall probability that we get by multiplying by n will be an interesting bound. And of course we want an uh we want it substantially smaller than 1 / n if we want to prove this uh high probability bound.

26:30 So uh what can we plug in? Well, we need uh I think it's it's still useful to do this kind of uh site calculation. So, what what would you have to pick for M for that to match? Well, if you uh if you set M to ln divided ln ln ln, what happens? we get e divided this this stuff and then to the power m.

27:08 So I'm going to rewrite the whole thing as xlog. Now we can pull the m out. So it's factor m up here and then and then minus ln m and uh if you if you insert what m is now um you get the ln n that's uh becomes the 1 / n.

28:07 I'm missing one minus here, right? Okay, there's a there's a minus in total. And what's left from the rest is much smaller because we have uh a minus ln So the from the first term you get roughly this uh 1 / n.

28:59 Now for this I wouldn't have needed the log log right. Okay let's continue with the the proper calculation. If you want to show the high probability bound, uh we want that the the probability up there that X head is greater or equal than some threshold M. We want that to be big of n to the minusd for some some number. And so this we can upper bound with our bound from before n times this guy.

30:11 And so if we if we plug in this M with a factor C in front. that's from this this part here ln ln divided ln and it's like that's from the one over m and then we have the power.

31:11 Now, we still got to do the X block trick, but let's try to do it carefully this time. So, we take the log of this. That's an ln for the first term. Then we get so this we'll pick C greater than E so that this is less than one so that we can we can drop from the equation. Then we have uh the log of this whole term will have this in front as a factor and then you have to keep a log of things. Uh, and now we're splitting off this um this term in here, right?

32:26 And what you'll see is the ln here with the log login cancels with that. Um, no, not yet. No, it doesn't yet. So we get ln n the log of log log that's a triple log.

33:00 We'll only do this once guys. ln ln n that's from the first part. And then we have a a negative term with this minus log log n. And that's going to get the c ln n.

33:15 And now I'm pulling this this behind here. Then we have the log log n from the denominator here. And we have the old denominator log n. At least these cancel.

34:13 So we have this log and this minus C. Those combine. And we have this lovely term here still. And now we're going to pull this out. Then that becomes an n^ the 1 minus c times the exponential of this part. What's left?

35:50 this is going to get smaller and smaller. We take triple log and divide by log. So it's little of n in the end. And so it's going to be less than one for a large enough n.

36:35 Sorry, I'm not I'm not buying my uh my calculation here. if this was all there was there was still would still be n to the power of this thing. Uh that wouldn't wouldn't completely go away.

37:31 Ah okay. We'll borrow one more minus login. So I'm going to do um I'm going to do a a minus log n plus login. So we have two login up front here.

37:59 That's one way to show it. So this is going to be less than one for large enough n. So the whole thing gets negative and then x of a negative thing eventually becomes um less than one.

38:24 Okay. So key step was uh inserting um plus minus zero but um um that's why we get the factor two up front here. So for large enough n the overall thing is n^ the 2 minus c and now you see uh c was the constant in front of m. So for every remember with high probability bound says for every polomial decay you want for the probability there is a constant in front of the big O term that makes that true and that's what we've shown here. So whatever um D you want here, you can pick a C that's small enough so that this is less than less than this if you pick a C greater than D + 2.

39:23 Okay, lengthy proof. Uh what does what does it mean? First of all, um you can strengthen the analysis with different techniques. Uh the what what I showed you was still elementary calculations if you don't lose your terms. Um what we used was really just union bound and some simple um asmtoic tricks. You can uh show with other techniques that you actually get an uh asmtoic statement. First of all, what we've shown as an upper bound is also a lower bound. If you throw enough balls into bins, the fullest bin will have that exactly login over log log behavior, which is is still a bit weird. it popped out in the analysis where essentially we needed this to uh to cancel terms. So what did the uh the log log do really? It cancelled this log term here. So that you get a minus C login term. That's an algebraic reason why the lo login shows up, but it doesn't explain intuitively why that's the case. And if you have a slightly bigger number of balls than bins, then you get this factor alpha in here, but the main shape remains the same.

40:49 So in in a sense even under this uniform hashing assumption if you care about the worst possible query time hashing is not much better than a binary search tree just a tiny bit but of course it's only for the worst bin. Um and the second is you often study hashing with expected costs only and that's missing a little bit the uh long tails. There's a big difference here between the the average bin and this worst bin. All right, but of course the the bigger caveat is this uniform hashing assumption which is not always realistic. Uh I wanted to just mention without any further proofs. Um if you haven't seen this power of two choices idea, uh this sounds like um the answer is known and there's nothing you can do. If you throw if you use hashing, you're going to have some bin that's at least roughly login full. But that's not quite true if you use more than one hash function. If you use two hash functions and always check which is the smaller the least loaded bin of the two, then immediately you get a drop to log login log instead of login. An exponential improvement.

42:06 Uh if you could do more than two hash functions, this only changes the constant. So that's uh not not much more is happening there. Um the analysis for this is is doable but takes more time. So um uh if you want to see it is it's explained nicely in in their book. Uh but the idea is worth keeping in mind. If you just take the less loaded bin of two random ones, then you get much sharper concentration.

42:40 Uh there's a last balls and bins problem. Probably you've seen this one before, too. Uh it's called the coupon collector problem. So you have your favorite uh collectible items. They come in packs. You have to buy the blindfolded pack. You don't know which one you get. It's uniform. How many packs do you have to buy until you get all the collectibles in balls and bin language? Uh how many balls do you have to throw so that every bin gets at least a ball? then you've collected that bin. Uh we can analyze this by saying si is the number of balls that we need to reduce from i empty bins to i minus one. So I could throw any number of balls into bins that already have a ball and I'm I'm counting those but they don't get me closer to having all bins covered. But once I cover with my new ball the first empty bin, the first new empty bin, um I stop counting in SI.

43:40 And so the total number of of balls I have to throw until I've collected all bins is the sum of all these. And there the indices are reverse, right? You start with everything empty. So the initial SM will always be just deterministically one. But from then on, it's random. You could throw things in the occupied bins again or you could be lucky and get get a new thing.

44:05 Each of these is a geometric random distribution because you're essentially flipping a coin. You have the occupied bins. That's one one option that the outcome can be. And you have the others. So you're flipping a coin until you for the first time see the outcome uh hit one of the empty bins. Uh the PIs are different, right? there it gets less and less likely to hit a free bid a free bin. Uh but the expectation is always one over the probability for a geometric random uh variable. So that's it's easy to to memorize and reuse here. So we can just compute the um expectation how many balls do you have to throw to get all bins covered as the sum of the expectations of these si which is their um inverse probabilities and that just adds up to m * harmonic number m or m login roughly.

45:04 Uh this you've probably seen before. You can also compute the variance in roughly the same way because these si are independent. They're not identically distributed, but they're still independent. And so the sum of the variance of a sum of independent variables is the sum of the variances.

45:25 And if you do the math here, uh it gets a bit more tricky with the summations, but you can show that the variance is quadratic. And so the standard deviation is linear, which means of lower the term than the expectation. And that was enough with Chbby Chef's inequality to get some concentration in the sense that if you make n big enough, you'll see uh this random s converge to the expectation in probability at least.