Video 1-4: Properties of Random BSTs

0:03 After we've introduced this random model that we want to aspire to with the randomized data structure, let's have a a bit closer look at how good this model is. Um and for all the following descriptions, I'll always use the following convention for naming the elements of a binary search tree. So, let's again look at some some example. Maybe a tree could look like this.

0:35 The internal vertices are numbered by the numbers the integers one up through n. And uh if you nicely draw the tree in in order, then you get the numbers left to right. That's what my original drawing had had them projected down on the line and then this is uh you get the numbers in order.

1:05 But, we also have these um null pointers or leaves. In computer science, we always represent them as null pointers if you implement this as a pointed structure.

1:17 Uh this is unfortunate. Let's modify the trees that we don't have only leaves like this. Sorry, let's make it a bit more general. I'm going to add one more node here.

1:37 I just left that part. Um choke. So, we have one leaf here and then two more here. And we also need a name for the leaves. And there the convention will be to start with zero because then they also go up to n.

1:59 Clearly here n n is 6. And so in both cases we range up to n, but for the leaves there's a zero, for the internal nodes there's no zero. Um this is an arbitrary decision, but it is the one that Don Knuth uses in his books. I think it's the one that uh many people have copied in papers, so it's somewhat standard, so I want to also use this.

2:26 Just in case someone watches old recordings of some formal lectures of mine, I've deviated from this at the time, and I think it's a was a bad choice. Okay, so keep that keep that in mind. Uh also internal nodes always as circles and leaves as squares.

2:47 If you take such um maybe before we uh even do the analysis, let's uh take a look at some randomly chosen So it's the same same authors have a different book where they also discuss what uh random trees look like and some of the analysis we do is also found there, but uh I want to just high-check the following picture. This is a a randomly chosen binary search tree over I think in the book they say 237. Of course you could have just counted it, but let me copy that to uh the notes as well. Come on.

3:38 Is that uh a tree chosen from our distribution by inserting a random permutation and then drawn in the usual way, and on the side you see the profile, which is how many vertices how many nodes are at this depth. And it seems that here they counted only internal nodes, not the leaves. The leaves you would know where they go. Uh they skew the picture a bit further. Um So, this is roughly what these trees tend to look like. Of course, this is just one random example. Uh who who promises us that this is a typical one? Uh we can't really be sure. Um but we'll see from the analysis that we do that they tend to have fairly low height. They tend to have this kind of uh I don't want to give it a specific name, but it's it's a bit of a almost a bell curve that most vertices are somewhere in the middle.

4:49 And then there's a few that range further down. And you can describe these there there's um a final slide where I just cite some results about these that we don't go into the proofs. A lot is known about these that we can um make our statements for the data structures based on.

5:10 I want to restrict it to some of the properties about these trees that are really simple to analyze with the right trick, but that give us uh a fairly good picture of how well they perform. And the easiest to analyze is in our picture the depth of this guy.

5:30 The leftmost leaf in such a random binary search tree. You don't see it. Ha. Sorry. So, you didn't see my uh my fancy attempts to make this picture part of the lecture notes. Uh Uh, all I was otherwise doing is just circle this guy in red. So, put him on the side. This tends to be the easiest to analyze. And the result or what we analyze precisely is the expected depth. So, the expected number of of edges you have to follow down to reach this leftmost leaf.

6:11 And it turns out the expected number is precisely HN, the harmonic number, which is this uh the sum of reciprocals. Right? I mean, if you want to be a bit more precise, it's 1 over I. In case you don't trust this dot dot dot notation. And um before we go into the proof, let's remind ourselves why this has something to do with logarithms. Uh, people may know, but I think it's good to uh make this point right here. If you draw such um a large harmonic number, what you're adding up is these these bars of certain heights. So, there's one of height one, then height two, uh 1/2, 1/4, and so on. Nobody can read this.

7:06 And of course, these points here, the heights, they form a certain curve. If you continue this, this is just the function 1 over X. Maybe let me try to do it in red. Um So, what we take for the harmonic numbers are these uh the um the areas here of these boxes.

7:44 And that's some number. It's well-defined. It's always going to be a rational number, but it's a bit painful to know exactly how big it is. To get a rough feel of how big it is, uh it's much more convenient to say we do a a continuous version of this and include these upper parts, then it's an integral. And now you got to be a bit careful with this function that goes up to infinity. So, you skip the first part. Maybe you want to start integration um from here to here. Uh but then roughly without going into the error analysis how precise this is, this should be something like the integral from 1 to n of 1 over x dx. And now you know that the antiderivative of 1 over x is the natural log. Or the uh derivative of natural log is 1 over n.

8:47 And that guy is zero, so that's fine. Now, of course, this isn't a proof that this this tilde statement for me has a very specific meaning. This is not a rough hand-wavy roughly approximate, but it's precisely saying that the quotient between these two things tends to 1 as n goes to infinity.

9:13 And you can prove this by analyzing precisely this this function is smooth enough that you can bound the error in some some standard way. Uh you can even make this uh a bit more precise. Uh I think it pops up later on the slides. Mm.

9:32 It's a good point to open the computer science cheat sheet as well that I need my keyboard for Was the protector gone for a sec? Ah, so much for fixing the cable.

9:54 Do people know the theoretical computer science cheat sheet? Okay. That's good. At some point I had some fun with it and smuggled in my favorite definition of a big O notation.

10:12 So I have my own one now. Of course I got to use that one now. There we go. Okay, maybe that's good enough. Where do I open this raw? Okay, download my file.

10:46 On the cheat sheet there's tons of formulas, but in particular there's asymptotic approximations for things like these harmonic numbers. In case you ever want to know very precisely the nth harmonic number is essentially log n then plus a constant and then the error term that is left is going down to zero roughly as one over n and this this gamma is a a known constant, the Euler-Mascheroni constant. That must be given somewhere too. Mhm. Somewhere on the cheat sheet.

11:24 Was it? At the top of the sheet there's the At the very top? Um, there it is. Yeah. There's the approximation at least, yeah. Goody.

11:38 So, all I'm saying is that this harmonic number is somewhat well-known, well-understood, and fairly close to uh the logarithm. And that's good, right? Because we expect that this binary search tree in the best case will be logarithmic in height. Now, it's actually um log base two of n that we would expect, not log base e of n. But this is even better, right? It's a smaller number. So, how can this be? We'll find out that as you see in the picture maybe a bit, the um outsides of the tree tend to be a bit higher than the typical uh nodes in the tree. Okay. Um Let's go and prove this. Uh here I prepared much of the proof, so not much to write. The depth of this leftmost leaf tends to be uh is is exactly the number of a certain combinatorial quantity, namely the left-to-right minima in the insertion sequence. And left-to-right minima is if you uh write down some insertion sequence, and imagine these drawn as as poles of the certain height, then if you look from the front, the left-to-right maxima are those that you can see. I guess minima is uh less intuitive to draw.

13:22 Let's look at left-to-right maxima. So, you see this guy, the first one you always see. You also see the five. But, the next three elements are hidden behind the five. You can't see them if you look from the front. But, the six again is uh visible.

13:54 So, uh I guess there's connections to Stalin sort, etc. But, let's uh leave it at that. It's the minimum of some um the maximum of some prefix or the minimum of some prefix. It's uh a current record when you move from the left through the permutation. Either a current largest or current smallest. Why does this has have anything to do with um these leaves? Uh let's let's stick with maxima and everything will be symmetric. So, if you insert this sequence as a binary search tree, you get the one here. Then, the five all over there. Uh the three in the middle.

14:39 Then, we do two and four, doesn't matter in which order. And we got the six. Now, uh the right most leaf, the six, is going to be all the way here. And its ancestors, it goes down one level for each ancestor, are precisely these left-to-right maxima.

15:03 Right? Whenever I I have a new record, a new largest number, this joins this right spine of the tree and pushes this right most leaf one down. The same happens with minima on the left. It's completely symmetric. Just my nice picture with the poles doesn't work. Maybe I should modify this to be the largest. Um by the very same argument, the left-to-right minima give you uh here the depth of the zero in this sequence because the smallest element came first, the left-to-right minima is just this single element, and hence the depth is also one. Okay?

15:48 It's lovely that we don't even need a plus minus one error correction term is precisely left-to-right minima. Uh and you can reinterpret this. So, this uh this number of left-to-right minima you can write as well, for every position, are you a left-to-right minima? Again, this Iverson bracket notation means an indicator event, so it's one if that is true and zero otherwise. And clearly, the total number of left-to-right minima is the sum over all the decision variables, are you a left-to-right minimum? Why are we writing this in this weird way? If we're interested in expected values, sums are great because expectation is linear. If we want the expected number of these left-to-right minima, then we can sum up the expectations of these indicators, and these will turn out to be not too hard to analyze.

16:50 The reason why this is not so hard to analyze is that the position I in such an insertion order is a left-to-right minima if and only minimum if and only if nothing to the left is smaller. Now, because these are random permutations, they have this nice property that any prefix is essentially a random permutation of the numbers in that prefix. This may not be directly the numbers one up to I. There may be There may be gaps left by numbers that come further at the back. But, it's bijective. It's isomorphic to a permutation of the first I integers. It behaves the same in terms of relative order of these. And so, the probability that this last one is the smallest is 1 over I. You could also say the position of the minimum in this prefix in a random permutation is uniformly distributed over the possible positions. There are I positions. So, the probability that the last element is the smallest is 1 over I.

18:01 So, the probability for for this XI is 1 over I, and then we sum up the reciprocals 1 over I. That's precisely our our harmonic number from above. Okay?

18:18 So, in a way, uh there was a bit of computation, but not very complicated. There were two insights in this proof. One is we could somehow connect properties of the tree to uh relatively simple uh quantities about the insertion order. Sp- Sp- In this case, specifically these left-to-right minima. And then, the second trick was rewriting this this quantity a bit and using that in a random permutation many things are just uniform and simple. In particular, the position of any specific uh value.

19:05 Now, this maybe sounds not so exciting because we don't usually care about just this leftmost leaf. That's uh a weird corner case of searching in a binary search tree. You may even remember if you just care about the minimum, you might as well keep a pointer to the smallest element and so on. Uh it turns out you can take the very same argument, the very same trick, and analyze any fixed leaf. So, here we take the kth leaf in our notation. Again, these guys here, right? The the boxes. So, numbered from left to right starting with zero.

19:47 And we can take the expected depth of that leaf and calculate that. And to see why that might um You see from the result that it somehow looks a bit similar. So, why might that be the case? So, here's our kth leaf. What does the search path from the root to that leaf look like?

20:10 Or it it always looks like a binary search. It is narrowing in from the left and from the right until you've uh identified the only gap that's left. So, maybe there's some uh the root is somewhere over here. And maybe the next uh is on this side, so the search path crosses over.

20:36 >> [snorts] >> And maybe there's another vertex on this side, and then maybe you go back to this side. Maybe back here and here.

20:48 This is what the search path could look like. And it's the general picture. It'll start on some side, and it move it'll move between the two sides a few times, and eventually K will be the child of some some internal node.

21:08 Now, if you look at only one of these two sides, say um um only only on this side, then among all the keys that are on the right, that are larger than K, so remember K is the is the leaf that is among all the keys on on the right side, so again, this is this somewhere some internal node K here.

21:43 Uh it kind of Kind of has to be on the path, right? Could we ever not have key K on the path? Maybe I it needs to be right here.

22:23 And the tree could still go continue like this. My point was the keys that are to the right of this dashed line are all the numbers K and larger.

22:38 Among all those that are larger, conditional that things are larger, the number of green nodes that are on this path to leaf K, that's precisely again left-to-right minima, but on this restricted input sequence where I'm ignoring everything that's to the left of the line.

23:22 that are greater or equal than K. And of course, we have symmetrically the same on the left. Here, if you just look at all the keys less than K, among those, the ones that fall on the path are the left to right maxima among the keys that are smaller. So we just have to add these two things up. Now it sounds like this may be complicated to compute. The good thing is that the number of keys on the right, how they appear in the input sequence may be a mess. They might be mixed between green and blue in whatever order. But we don't actually care. All that counts for the left to right minima of the green guys are the other green guys. And so whatever order they come in mixed with the blue elements that are smaller than K, it's actually the same as before. It's a a permutation of all those keys, namely N minus K many.

24:25 And among those, we want to know how many left to right minima are there. So it's the very same analysis. A bit more formally speaking, the depth of this Kth leaf is the number of comparisons we need to find that leaf to reach that leaf in a search. And these comparisons, you can split into ones that compare with some key in the tree that is bigger or smaller than some uh some search uh some some key X. I guess here I could say X is just a K minus a half, right? Way we chose the um the keys for the internal uh nodes.

25:12 That is the number of comparisons, that's this funneling in path. So, that's left to right minima respectively maxima. And luckily they're symmetric, so the number doesn't change. There's exactly K keys that are to the left and N minus K keys to the right. So, by the same analysis from the last slide, you know, uh counting how many times is the rightmost the minimum or maximum, you get these two terms. And as we do expectations, they're just summed up. Um so, up to this point it's even true precisely as random variables. But, uh they're not independent necessarily.

26:12 I guess here they even are. But, for the expectation we can sum up uh the contribution. Now, I haven't commented on this picture up here. Uh that is um I didn't fit it in the plot. Uh It's a bit hard to read. So, this was for 100. And then the next one, I guess powers of 10, yeah.

26:49 1,000, 10,000. Let's suppose it was like this. Uh for sure the higher one is the one with larger n. This is when you take this expected depth of the case leaf and divide it by say the depth of this leftmost. Then you see this eventually converges to the number two.

27:25 That's something you can you can compute. Um especially if you use the asymptotic approximation. I think I have that as a lemma. Let me let me postpone this. The picture is just trying to show you what this depth looks like if you move from left to right in the tree. So this is leftmost. This is right rightmost. Well, this is uh k divided n which is on the on the axis. Uh then the the deepest leaves in expectation tend to be in the middle around the median. Uh again, let me go to the example picture that we had from the book. Where you roughly see this that the middle tends to be a little lower than the outside. In any specific tree, it's not quite true. And that's because we're compute comparing expected values for the depths. Right? In any specific tree, you have this with more chaotic up and down. But if you take the average over many trees and just look at a single fixed leaf, you'll find as expected picture this curve.

28:31 Okay. Uh from that, there's two things we can conclude. The second part is what I was already jumping forward to. If you take the leaf um of position alpha times n. So, you make n very big and you fix a number alpha between 0 and 1 and not the extreme points. Something that's properly away from uh the end, then the cost, the expected depth of this leaf is always the same. Asymptotically, it's two times ln n. So, two times as deep as the outermost. And essentially, as soon as you move any little epsilon inwards, you're jumped down to this. So, in the limit, this curve is really a a rectangle.

29:27 How would you prove this? I just called it corollary, so it uh supposed it doesn't even need a fancy proof. If you take your hk and hn minus k, uh we can approximate both for large n and alpha fixed, right? This becomes our alpha n and 1 minus alpha n.

29:57 So far, it's an equality if I'm uh doing this. And now I'm using our asymptotic approximation for the harmonic numbers, namely the logarithm. So, it's ln of alpha n ln of 1 minus alpha n. And now you're using the laws of logarithm, product inside splits, so you have ln n as a common factor for both. And then you have ln alpha ln 1 minus alpha.

30:45 Where did we get the factor two from though? Um All right, it's a plus. Um sorry, I'm uh I said we apply the logarithm laws and then I didn't, right? It's This is uh log alpha plus log n. This is log 1 minus alpha plus log n. So, we get the two ln two and this is a indeed a term that depends on alpha, but it doesn't involve n anymore. So, this is some constant. So, as an asymptotic approximation, you're indeed left with two ln n. And there's a small additional term that indeed is larger in the middle and slightly smaller to the outside, but it's a constant uh only.

31:33 That was that part. Okay, could be checked. Uh what you can also do is compute the external path length. That is just the sum of the depths or the sum of the search times for all the gaps. Uh I'll comment on that in a second why why that is is indeed useful to do. So, external path length by definition is the sum of the depth of this And we go from zero to n. And now, if you want the expected external path length we can insert what we just proved. The expectation of this inner term is Hk plus Hn minus k.

32:37 Same bounds. Uh It will come back eventually. Oh, yeah. We've been there before. Getting closer. Stop. So, this, of course, is a sum that sums the same thing twice, once backward and once forward. Here K goes from 0 to N. Here N minus K, if you start with N, it starts at 0 and it goes to N. So, both cases you're summing up the same thing.

33:48 And that's actually a a slightly thorny sum to simplify. Uh but luckily, there's the cheat sheet for us, which happens to have a formula for this. It's right at the front page because this is uh one that you commonly need. But it's precisely this one. Okay.

34:13 It starts at one, not at zero, but H is a a sum, so starting at zero is the empty sum. So, uh H0 is 0.

34:26 If you plug that in, um and use that this H N plus one is the same as H n plus one over To get to this form you need to modify this a bit. That's just by definition splitting off the last term. Right? Uh and then taking two times this on the right you can you can rewrite it in this form. Yeah. I don't know which one you like better. Uh but that's that's uh where this corollary comes from.

35:06 Now, let's see. Has anyone seen this term before? I don't know how formulate people think or if this is something you're uh you've seen or remember from somewhere else. >> [snorts] >> Uh that happens to be the expected number of comparisons in quicksort on a random permutation, the average case. It's precisely the same. And that's no coincidence. It's because quicksort and binary search trees are really very similar in some way. Uh the connection is that if you build the recursion tree of quicksort which means you put the pivot that you currently used in the root and then there's a left and a right recursive call with the elements that are smaller respectively larger than the pivot. That gives you a binary search tree. And uh if the pivot you chose is the first in the list you get precisely the binary search tree you would have obtained from inserting the elements in order. With a bit of a caveat that the standard partitioning function permutes elements, but if you do a stable partition leaving the elements in the same order, you get precisely the same thing.

36:27 So, uh uh binary search tree is some some version of quicksort uh where you do the comparisons in a slightly different order, but you do the same comparisons. Hence, they kind of have to have the same cost.

36:46 So, we found a new way to analyze quicksort. If you uh you've probably seen If you've done efficient algorithms with me, you've certainly seen one. Uh I usually do the the recursion and solve it by clever manipulation of the full history recurrence. This is another way. Comes to the same result, of course, but via different route.

37:14 So far, we've talked about expected values. Now, I want to do a brief detour, also in preparation for uh some other data structures we want to look at. Um you could hypothetically have two algorithms with the same expected cost, where algorithm A has a 50/50 chance of either needing cost one or cost three. Averages to two. You could also have an algorithm B. Uh I did the math right. In 99% of the time, it uses one step, but sometimes uh 1%, it does this annoying 101 steps. Hopefully, that also averages out to two steps. But, the algorithms are fairly different. I think we probably want algorithm A most of the time because it's more robust. It has the better worst-case guarantee. Maybe you even sometimes want algorithm B, but certainly you want to be able to tell them apart. And the expected cost just is the same. So, what you could do is a whole different topic for uh another lecture.

38:16 Um in advanced algorithms, I go a bit deeper into the other alternatives. Um a convenient way if you can make it happen is that you favors this algorithm A so that the actual cost is never too far from the expected cost. If that is if that is true, then instead of talking about the expected case, you can talk about essentially this this upper bound that holds most of the time. To make this a bit more, um, formal this this again two options. One is to prove concentration bounds, which is literally the probability that your actual cost is much more than the expected cost is very small. And we'll see an example, um, if people have seen Chernoff bounds, that's what I'm getting at.

39:11 The other option, uh, is the with high probability formulation, which, uh, popped up at some point earlier. The two are related. Usually, we use Chernoff bounds to prove high probability bounds. Okay. >> [snorts] >> If that works out, then the fact that the algorithm is randomized is much less of a concern because we have a much stronger guarantee than just the expected cost being good. We have the guarantee that almost all the time the costs are really good. So, let's dive a little bit into this. I won't torture you with the math here, promise. Um, I just want to introduce the tools, and we may apply them to some other data structures, uh, again, usually you can get away with the simplest version of these. Um, and the results that you get give you much higher confidence in the resulting data structures. This is the term that came up last yesterday, and I asked you, "What do you think this means?" Because with high probability sounds like a very vague statement.

40:14 It's a bit unfortunate that usually people have a very specific meaning in mind when they say this. Uh when I use it in this module, uh I always mean this definition. There's actually two things. You can either talk about um a specific statement of a cost, or you can have a big O statement, and they're slightly different in a in a slightly subtle way. We say some random variable or some um well, a random variable attains a certain value, or an event, that's the the more general version, happens with high probability when the probability that it it does happen is essentially one plus minus a small can only be minus, right? Minus a small error term. Now, here the quantifier is very important. For every possible constant C that you give me, I can show you that the error the probability is away from one goes to zero like n to the minus C. The big O here means that there's a hidden constant in front of this n to the minus C, and that constant will depend on C.

41:26 Uh usually you prove this in that there's it's one minus D of C times n to the minus C. And then if you give me a a value for the exponent, I'm going to blow up the constant in front of this thing. Or uh I'm making I'm making it small, I guess.

41:49 No, I'm blowing it up. Sorry. This gets weaker with larger larger constants. And at some point um I'm making Is Is usually meant as an upper bound, I think. Uh Sorry. This way around. A lower bound. It happens with probability at least one minus a very small thing.

42:18 The second version uh uses a big O statement, so it says that uh a certain random variable is within big O of some function with high probability. Is again a statement about some probabilities of this of this form that for every C there's this uh polynomial um drop to zero. But here I'm including this this constant of the big O also in the statement. Here there's a hidden constant for the error bound that depends on the on the C. Here also the bounds the the constant in this O There's two O's now, right? There's this O and there's this O. And both of the constants are allowed to depend on the exponent you give me. Okay? So uh Do I have this? No, I don't have this right here. So one example, let's make this concrete so that you see why this is the definition that you often want. We're not going to prove this.

43:24 Um but the height or the expected the the um external path length We'll say the depth This is in big O of log n with high probability.

43:57 Is a non-trivial statement that would need a proof. Um I'm just trying to illustrate what the statement says. It means whatever exponent you give me, say you want that the error or this the probability that this is false, this should go down as n to the minus 10.

44:23 Then from this constant 10, there's some constants D1 and D2 so that this this let's call it H. I'm going to flip it around so that we don't have this one all the time.

44:57 There's some constants which are from the top of my head, I don't want to say wrong things, but you can work out sufficient constants so that the the probability that this thing is larger than constant one times log n is at most constant two times n to the minus 10. That's what it means.

45:19 What I'm saying is this is very strong is a very strong requirement because you can pick this exponent as large as you want. It's not the same as exponential because it's still polynomial, but it works for every exponent.

45:38 So far I uh I've tried to convince you that we want to make data structures simpler. And now I'm throwing this at you so you may question is this needed? Do we need to make it so strong or do we need to make it so complicated with these quantifiers? The reason why this is convenient, if you can prove this part, if you can prove with high probability in this sense, then um you can compose data structures of this form and you retain this property. For example, you can do polynomially many repetitions of some you can try something polynomially many times or do polynomially many operations after each other uh, where each has a failure probability of this form and the result still succeeds with high probability. Because precisely any uh, polynomial factor you can hide in picking a large enough C so that it doesn't change the result. Formally, this is uh, written in this lemma. So, you have an an algorithm and it has some sometimes it fails, which uh, it tells you say, uh, it tries something and then sometimes it says, "Ah, bad luck. The randomness was against us.

46:58 I couldn't compute the answer." Um, or it could mean it doesn't fail, but it it works slower than you want it. It could be quicksort and you stop running quicksort. You take take a timer and if it used up too many comparisons, you say, "That's it. Stop. I'm you're you lost." Uh, >> [snorts] >> that could fail that could be fail. If you do a polynomial number n to the D independent repetitions of this on some input of size n, with high probability none of them fails.

47:36 The proof is is a simple exercise. So, let's do that. Um, to prove this, I'm going to start at the end. This we want to show with high probability that this uh, composite algorithm the many repetitions do not fail. How do I show this? Well, with high probability means for any possible C that you give me, I have to show the error probability is small. Or the failure probability is small. That's what this C means. It's the with high probability from the second part of the statement. I mean, maybe I not flip the page.

48:13 That's the C. Now, I have to flip the page. Let's call FI the failure event in the ith repetition. This by assumption with high probability doesn't fail. The algorithm doesn't fail with high probability.

48:31 So, I can pick any constant for the exponent. I might as well pick one that depends on my C that you gave me initially. It's still a constant. And I'm going to add uh another D to this.

48:49 The D is the number of repetitions, right? N to the D repetitions. So, this is one possible choice for the exponent, uh D plus C.

48:58 And now I'm just going to analyze the failure probability of the whole thing. The failure probability, the probability or the the event that the overall algorithm fails is the union of the failures of each of these. If any of the repetitions fails or many of several of them fail, the overall thing failed.

49:17 So, it's the union of these events. And I I use an upper bound for this, the union bound that we discussed last time. The probability for this union is upper bounded by the sum of the probabilities. But each of these fails only with this tiny small probability N to the minus C plus D. But I have N to the D of them. But again, if you multiply this out, that's N to the minus C, and that was what we needed for with high probability.

49:52 So, it just means that this strong notion is is a bit annoying to work with, I agree. But if you have it, it gives you the guarantees you want for composing things.

50:04 A typical way to prove with high probability bounds is often via a tail bound. Uh and most of the time we'll get by with the same same trick. Uh namely Chernoff bounds. Um this is something maybe you've seen Markov or Chebyshev inequalities in in some stochastics or statistics program module. They're fine, but they're relatively relatively weak. If you have better assumptions on the random variables that you work with, in particular that they are the sum of many small independent parts then vaguely speaking the law of large number uh law of large numbers means that you shouldn't expect a lot of variation. So, for example, the classical one would be uh random coin flips and you sum them up in the following sense that uh heads counts as one and tails counts as zero or as minus one. Uh let's say plus one minus one. Then if you sum up many of these coin flips, of course you're going to move up and down.

51:16 Uh sometimes you have a few more heads, sometimes you have a few more tails. But if you do a lot of those you don't get far away from zero usually. And the point here is really it's the two things they must be independent components and each of them must be of small overall influence. Then you should intuitively expect something that is essentially well controlled or sharply concentrated around the expectation. Something of this form. But let's make this a bit quantitative so that we can use it for for actual proofs.

51:52 Uh the more the most general statement that I'll I'll give you here is this Chernoff bound. You have uh mutually independent Bernoulli variables. They may have a different probabilities. So, these are all 0 1 variables. And Xi is 1 with probability Pi and 0 otherwise. But, the Pis can be different. So, it's a a different coin each time, if you like. Then, we'll denote the expected value of the overall sum, which by linearity is the sum of the expectations. That uh is mu. That's just the sum of the Pis. Um and then you can prove statements of this form. The probability that X, the sum of all these independent flips, is a constant is a a certain factor larger than the expected value is upper bounded in some by some uh lovely term. Uh this is the version that's easier to prove. It's not the one that is convenient to use. The second is a a weaker version of the first, but it has a a more convenient right-hand side. It's essentially just saying an exponential decrease. It's an e to the minus something.

53:13 If that something can be made to go to infinity, this right-hand side goes to zero exponentially fast. So, Chernoff bounds show exponential decays of probability, if you're picking the parameters right. And here, when does mu times delta squared go to infinity? I guess if delta squared is slightly bigger than mu, Right? Uh sorry, is there Yeah, if they together go to infinity, what whatever that means, we usually want to pick mu small. But you have to pick it so that the overall term is still positive. It doesn't go to zero. Positive it will be.

54:06 I'm used to the normalized version to apply this. This first part you could in principle prove in a slide or two. Um if you want to see this, then uh advanced algorithms is your is your better bet. Um [snorts] for the experts, if you've seen it before, you take Markov's inequality and apply it to this random variable, and the rest is computation. For here, I thought this is not needed to dig through the proof. Uh instead, we'll use a simpler version of the statement that's more convenient to apply. In this case, we assume that the random variable we're working with is binomially distributed. So, that's the same setup as here, except that all the PIs are the same. I'm here, this is really the sum of coin flips. And uh in the 0 1 sense, so um tails is one and uh heads is zero. And I'm summing how many how many what do you say, tails? How many tails I got in n coin flips?

55:10 And P is the probability for one one tails. Could be 1/2, or it could be uh skewed a bent coin. Then we have this statement, which doesn't look simpler, but it's easier to apply if you uh do the computations. It says uh you can pick this delta. Then the probability that your your number of coin flips divided by n, so the fraction you've seen come up heads, the fact that the probability that this is further away from the expected, namely p, further away than delta, that is also exponentially small in this term. And here is a bit easier to interpret. N is the number of coin flips you do. So, if n gets bigger, you want this overall to be going Uh this part you want to be large. Now, this delta you want to pick small because you're interested in small deviations around the expectation. And uh this term tells you exactly how small you can pick delta.

56:21 The cutoff is at square root n because then square root n 1 over square root n then uh the n and the 1 over square root n squared would just cancel to a constant and you get no interesting uh upper bound. If you pick delta to be uh slightly slightly small slightly larger than So, delta has to be slightly larger than 1 over square root n. For example, we're forgetting this here.

57:00 So, that's n to the minus 1/2. And if you want it slightly bigger, you say n to the minus 1.4 or so. Uh that's not the numbers here. >> [laughter] >> Or 99, but then you're square it. Okay.

57:23 If you plug that in here, then the result is still n to the 0.001. That still goes to infinity, although slowly. But asymptotically as n becomes very large, you get an upper bound for the probability that is almost zero, exponentially close to zero.

57:44 The fact you should keep in mind, which is quantitative, but also easier to remember, is if you have a binomial random variable, so n coin flips, the expectation is n times p. And with high probability, there it is from the previous slides again, you're close to this expectation with an error of a little over square root n. You don't actually need this. You can make it a a bit more tight, but usually this is good enough. Okay? So, essentially n times p is where you're at, but you might be square root n um up and down. That's to be expected. If you make this a bit bigger than square root n, you're in this range almost all the time.

58:32 Okay. That's what we'll um what we'll occasionally use in in data structures uh just to show um that things behave well. Again, I don't want to go through the detail. How does this all connect to binary search trees? Uh you could, for example, say that um your your coin flips are that the root of the binary search tree is very far away from the middle. So, uh for a binary search tree to behave badly, the root has to be either very small or very large. You could say, "I'm going to pick 9 over 10ths, and the other the outside 10th uh that is what I call bad. Then my P will be 0.9.

59:34 Um Uh-oh. What did I do? >> So, you're counting if you have a large tree, you have to have a long sequence of steps where in each case the the root was chosen from the the bad area of very small or very large keys. So, you have to have seen many coin flips where although each was just 10% likely to go out this way, a lot of them went this way. And this you can put in this form to show that this is unlikely. That's how you connect it to binary search trees and the height. Uh there you have to The details are a bit messy because it's not exactly uh the same distribution. This P uh I'm cheating here by saying there's an outermost 10% if N is uh a finite number, there has to be a a multiple of 1 over N as the probability. So, you have to work a bit harder for this case.

1:00:59 Uh that's why I didn't want to go there for this lecture. Uh what we can show with a little combinatorial trick is a different um statement, namely back to our left-to-right minima. Remember the left-to-right minima was the depth of the leftmost leaf or the rightmost leaf. And we can show that not only is this in expectation HN, but also it's log n bigger of log n with high probability. So, you don't just have this expectation. It's very rarely to to be far away from log n. So, the the results from all the way back about uh the search costs um or the path length, they're uh true with high probability up to constant factors. The way to prove this is kind of cute. So, let's maybe the last thing for today that we have time for. It uses a trick to rewrite the permutation using an inversion table. And what's that? Uh if we start with a permutation written in the form that A1 is the first number in the permutation.

1:02:15 So, for the mathematicians, a permutation is a function, right? Mapping the first n integers back to itself. So, A1 would be the function value at one. That's how we normally in computer science write a permutation. It's just a a sequence of the um of the values. Now, we associate with these different numbers, these BJs, where the jth entry is the number of inversions, so the number of pairs where uh the number of indices where the the left index index has a larger number than the right index. These are if you wanted to have this list sorted, these are wrong. That's they're inverted. All right. So, uh in my pulse picture again, I have I and J, then I has a a bigger value than J. I'm counting with BJ the number of inversions where the right side is fixed to be index J. And the left side can be anything but really only anything to the left by definition.

1:03:21 So, it's the number of values that are left of J that are bigger than the value at J. Let's leave it the way I wrote it. Um depends if an inversion is that a pair of indices or a pair of values. Normally say indices. Then my notation would be a bit um inconsistent.

1:04:17 The trick here is that you can go from a permutation to the perm to the inversion table simply by counting these inversions. But you can also go back. They're in bijection. And because you're counting only the values to the left of a certain index there can be at most that many that are larger. So, BJ is always a number between 0 and n minus J. And because they're in bijection, a random permutation gives you BJs that are uniformly distributed in this range. And so, uh if you pick a random permutation, each of these is independent and uniform from its range.

1:05:05 Now, the last step, what does this have to do with our left-to-right minima? is that this value uh this position J is a left-to-right minima exact minimum exactly if nothing to the left is smaller. And that's precisely what is counted here. So, I think this should be AJ, not J.

1:05:41 Number of values to the left of J that are larger. Yeah, I wonder if this should be maxima or this should be minima. They're of course symmetric, so either either works. Um but to match this this definition, I guess it's a maximum because nothing to the left was bigger. So, I think um To properly prove that statement, we need to appeal to the symmetry of the process. Um it's more convenient to write maxima here. You could have I guess you can reformulate it for minima also at this level. Uh Um the indicators with zero are bits more convenient to deal with.

1:06:59 Okay, I think it all comes comes down to fixing the the definition properly. Again, the trick is that by splitting up the inversions, you get something where uh these entries are independent.

1:07:13 And the left to right maximals are depend are given by just a single value of these uh of this inversion table. They don't depend on the other values. And thereby, you can apply essentially these Chernoff bounds that we've seen before to get to that statement or to Yeah, I guess here we have different PIs. So, you would have to go through the first uh Chernoff bound for the for getting this statement.

1:07:58 Let me finish with this. The rest is um mostly citations of some other things that are known. Uh you can give for for a specific tree, you can write down the probability that this arises as the binary search tree from a random permutation. So, you can essentially work your way backwards. Remember that we said for n equals three, this tree had probability of a third. And you can get this by um recursively evaluating this formula. The probability for for seeing this shape is 1 over n times the probability for the left and the right subtrees separately. And here n is one each, so you have another 1 over 1. And then the recursion on the empty trees gives you a one. So, all the rest is one. So, you're left with the 1/3. Whereas, if you apply this to our say unbalanced tree, It doesn't matter which shape, I guess. Um you would have the 1/3 at the top, but now you're left with the probability for this little tree here.

1:09:15 And that again gives you a a 1/2 or n equals two here. And then you're left with small subtrees, so the rest is a one. So you get the 1/6 that we also found manually.

1:09:32 And why does this work in general? Um the probability that you get uh the specific value in the root that you did see, that is uniform because it's a random permutation and you look at the first entry. Any value from one to n is equally likely to appear there. And from there on, what happens on the numbers smaller than this this root value which go left and what happens on the values larger than this value which go right is independent. And how they interleave in the overall permutation is is irrelevant for the subtrees. So all you're going to look at is the two subtrees. There's one crucial fact here that's also hidden in this.

1:10:24 Which is sometimes called randomness preservation. If you take a random permutation and you filter out all the values less than a certain threshold, then conditional on these, just taking these smaller values, among those, they're again a random permutation and it's still uniform.

1:11:14 >> It's the same property that when you analyze quick sort you implicitly use for setting up any recurrence. You crucially need this. I just found that formula cute. I don't think we need it for anything. Uh And here's a collection of some some other results. Um in this area analysis of algorithms people studied these random binary search trees up and down. And for example, we didn't talk about the height, which is the the maximum of all these steps of the leaves. Maxima expected values of maxima are very hard to work with because they don't really nicely work with each other. But with much more probabilistic techniques, you can prove a very precise asymptotic statement about the height with some numbers that are known as kind of the the roots of some polynomial or some some equation. Uh but they don't have a a nice closed form, but they're known precisely. Um you can show convergence in stochastic senses.

1:12:17 Again, not something um I want to go into. You can also be more on the combinatorial side. You can count the number of leaves at a precise depth in a tree of size n as some closed form with Stirling numbers. Uh The statement here that we've shown for the expected value also holds in some stochastic convergence sense. Uh you can then you can look at standardized random variables. So, you subtract the mean and you divide by the standard variance standard deviation. Um and then you can study what does the this distribution look like for large n, and it turns out it converges to some Gauss distribution or well. This is uh at a level of precision and detail where it's not clear if you care about it for algorithms. Uh So, the takeaway for this part, and that's maybe where we should leave leave this detour is that random binary search trees are very well-behaved.

1:13:22 They're not perfectly balanced, that would mean height log base two of n, but they have heights roughly uh well, three times. This is log base e, not base two. So, if you factor that into the constant, maybe they're three times as high as they could be. Uh but what's a factor three among friends, as Tommy would say? Uh and the expected the expected depth is even closer to uh the optimal. We've seen the expected depth of a leaf is two times ln of n. I think that's roughly 1.38 log base two of n. So, uh in a way, within 40% of the optimum tree. So, it's a good goal to attain to. Now, uh it's a bit sad that we're at the end of the time. Now would the data structures start, but I guess there's always a next week, uh we'll talk about how to achieve having this shape distribution that we now analyze to death um in an algorithm that cannot control the insertion order, but has to establish it via randomization itself.

1:14:38 Okay.