Video 3-10: Chain Length Distribution

0:02 this step here where we inserted the probability for a collision. That's where we use the uniform hashing assumption, right? And um that's also crucial. If we cannot assume this, if we don't know anything about our keys, this might be one for all of them and then we get an an N here. Then that wouldn't work. Uh but maybe note what we didn't need. uh we needed this implication from the uniform hashing assumption namely that the the collision probability is is like this. We did not need that the keys are somehow all independent or anything stronger than that. This one uh okay before the gazillion animations. This one has kind of um it it it has the appeal of having uniformly drawn slots for all of the items all independent.

1:00 Um that we didn't need. All we needed was this statement about the probability for a collision. And that's the hopeful part because we can keep that and um reduce that even if we don't have uh control over our inputs. Now I want to start here with a bit of ancillary question if you like.

1:43 It's a bit of um a trick question. It's maybe scarily looking. So, because the notation might pop up, it's worth having a look at and also uh brushing up your memories. Maybe it helps.

2:07 So the notation shouldn't be where this dice from this bin means the binomial distribution alpha tailum and uh if I write bin n comma p this is the distribution of flipping n times uh an unbiased coin that comes up comes up heads with probability P and I count the heads still busy? Otherwise, let me uh show the votes. Come on.

3:51 This is a nice even split. So it's um several statements can be correct um but not all of them are indeed you have to read carefully for these. Uh the first one most of you got right and then it's a mean off by one if you like. So the first one the first one is correct because there's complete symmetry. we haven't um at this point all the keys are essentially assumed to be same. So this uh gives the same marginal distribution for all of the lengths of lists. And um here for the length of the list, if you pick out one individual one and look just at its random distribution, you have to subtract one because here it's it's this the specific list that we for sure know x i gets hash two. So it it deterministically is one plus something random. That's by definition. If we subtract this random thing, this non-random thing, the deterministic part, then the rest is well all the collisions and the collisions are counted by a binomial distribution because they're by assumption independent coin flips with um a biased distribution uh prob probability of 1 over m for having a success something that we have to count. Uh but then if you take out this one item, there's only n minus one other keys. That's why it's not been n 1 m but n minus one. This is of course a nitpick that for large n is completely irrelevant. Is a lower order term. If you want to be precise or if you were to measure the precise distribution you can see the difference.