Video 7-2: Randomized selection by rank (deterministic adversary lower bound, Floyd-Rivest algorithm)

0:02 Uh in the next section I want to show you one concrete problem and make the point that randomization can indeed be more powerful than any deterministic algorithm. Um I wanted to show you one concrete example of this for one to make um to show show a concrete adversary because I think this is this is insightful for for other problems too. uh and also to make drive home that point that uh randomization is really doing more than just making algorithms a bit simpler. Um so I'll try to uh avoid detailed discussion of what the randomization formally means. Um we'll come back to that. Uh I want I should mention that this is not an NP hard problem that we're working with here. And so also the randomization is not going to decide between exponential and polomial or anything like this. The difference is smaller but we can prove that it exists here. And uh the example is the selection problem. Selection by rank um the thing that quick select solves. So uh just to recap is an the input is an array of numbers um or arbitrary objects that you can do pair-wise comparisons on. And uh you're also given a number k and you're trying to find the element that would be in that given position k if the array was sorted. That's um a convenient way of saying that you want the kith smallest. It's a bit more specific or a bit more precise in case there are duplicates in the input. Then uh if you say the kith smallest does that in count include duplicates and what about all the elements that are equal to the k smallest? You can avoid all that if you just say is an element that could be in position k in the sorted list. Uh makes discussions here a bit easier. Uh but for all for all that that follows you can assume that the numbers are distinct and then it's really the same. Uh special cases that we'll we'll focus on is is uh where k is n half then we're looking for the median element. So the element where half of the input is smaller and half of the input is larger. What you learned in undergrad is this quick select algorithm. Um different ways to write it. But here's uh one with a loop. you're uh maintaining um a range of the array where you still have to work in initially it's everything and as long as that's not uh empty you pick an a random element from that range you partition that range around that element everything smaller to the left everything larger to the right and then uh there's there's three different options sometimes you're lucky and the pivot element you picked is exact exactly the one that has rank K or is at position K in the end uh then you uh will eventually return it. Otherwise uh if the um splitting position where the pivot landed is too far to the right then you have to continue searching on the left K is still left of that then you adjust the upper bound and the other one is symmetric.

3:32 Uh I suppose people remember what this works like. Uh really the point here is if you don't do this random choice, the algorithm has a quadratic worst case just as uh as quick sort the more famous cousin of this. Um and the other bit is the algorithm is really simple. It's simple to write down. It's simple to code and it works really well. But it needs this uh randomization to be robust. Now you can uh you can show that it takes linear time and expectation and you can compute much more about this uh determine exactly how many comparisons it does and so on. Um but let's not go there yet.

4:21 Now uh I also want should mention that you can also solve the same problem deterministically and um the kind of algorithm you would have seen for that is the median of medians algorithm where you group elements in columns of five sort those then take the the middle third the the the third smallest of each five recursively find the median of that and then partition with that sub substantially more complicated than than this code for sure. Uh still very doable uh but also um much slower in in practice if you compare the two. Okay, so far so good. So let's let's take a a slightly closer look at uh what happens here and what we can do in um in the extreme cases or in in beyond these simple algorithms.

5:27 Um all of what happens is within theta of n. We can do uh expected costs linear in n and we can do deterministic cost linear in n and there will be a lower bound linear in n. Uh but the constant in front um makes a difference here. So first of all there's um a lower bound for any deterministic algorithm assuming it's comparison based uh as for sorting. So a deterministic comparison based algorithm for finding the median has to use roughly two n comparisons in the worst case. Okay. Uh that proof is uh is a bit tricky. Uh what I'll show you is um a simpler version that gets a slightly weaker bound. Annoyingly it's um yeah we we'll see. Um so the same statement just that now uh we have 1.5n comparisons or more precisely we have n minus one and uh n minus one/2. Uh the reason why I split this up this weird way is that's what you get from the proof. And so uh let's let's uh let's design um let's prove this. And there's essentially two parts. Uh there's two types of comparisons.

7:15 There's some comparisons which are necessary from an information theoretic perspective. Which means if the algorithm doesn't learn about the outcome of these comparisons, it cannot be sure that the output it produces is correct. So in our case, we want to output some element X and claim that this is the median. So if I'm output outputting this element X and claim this is the median, I as the algorithm I have to have proof of that otherwise some mean person modifies the in the input in a way that makes my claim wrong. is a bit like um the typical typical argument in this direction. An adversary argument would be to find the minimum of n elements you have to look at every element. Otherwise, if there's an element that you haven't even looked at that you have not compared with anything else, then the adversary could make this much bigger or much smaller than the other elements depending on what you claim the minimum is and it will fool you. it will make your your claim wrong.

8:28 In the same way, you have to show that there is comparisons with the other elements. Say n is 11. And the way we'll draw this is uh like a a has a diagram for partial orders. So an element with an arrow down means this one is bigger than this one and this one's bigger than this one and it's a partial order. So this is transitive. Uh but what I've shown you here is the certificate that acts as a median.

9:26 So the claim is unless the algorithm has done has learned a partial order of this form where your element x is in the middle and there's some way to say these five elements are larger than x and these five elements are smaller than x. Unless you have somehow learned the information of such a partial order, you cannot prove that your median is correct. If any of these edges is missing, I can modify the input so that your claim becomes wrong. Okay.

10:17 If you think about it, what this was for sorting or sorting, you can also make the case if you want to sort a bunch of elements. You have to learn which one's bigger than the others. Uh so you have to arrange them in some linear order. That's the largest, second, smallest, blah blah blah down to the smallest. So for nm elements the certificate is just n minus one comparisons but we know for sorting we need we actually need many more comparisons. So the certificate comparisons are not always um sufficient. And here as well this n minus one comparisons that you have to do to certify that the median is correct. But sometimes and most of the times you need extra comparisons to find the right certificate. And uh for sorting we know this gap is really big. um for medians. The second type of comparisons are comparisons. These are the ones where in hindsight, you know, I actually wouldn't have needed to do that comparison. If somehow someone would have told me uh what comparisons to make, I would not have done this one because it doesn't help me certify the median. So the thing is here if if I tell you um this is the median if I already give you that guess and uh then you can compare that median to all the others, it's like a one round of partitioning in quick select and you immediately find that that's correct and that's the answer. then you only need n minus one comparisons. Uh what we'll try to prove is that in general or in the worst case it's not possible to uh to make the correct guess without additional comparisons. Um in sorting you do that lower bound with decision trees. There's just too many different things you have to determine. You have to distinguish. Well the median this wouldn't work. the number of different things is basically just um is just n there's n different choices for the median and maybe you learn which ones are smaller which ones are bigger but you don't get this uh this big gap for uh an n login so how can we still do uh against deterministic algorithms some uh some bound or non-essential comparisons So, a non-essential comparison is one that's not part of the certificate.

13:35 So in particular, any comparison that compares an element that's at the end strictly larger than the median to another one that's strictly smaller than the median, it doesn't help us find the median.

14:16 Okay. The L and S are these sets. So let's define [Music] M as the true median. L is all the elements that are larger than the median. Likewise the smaller ones. And um by the way we know that these are of the same size, right? But that's uh it's not not needed here. So any uh any element from L and any element from S if I compare those two I kind of at the end I already know the one in L will be bigger than the one in S. So that comparison is wasted. But uh what we'll play now is adversary.

15:26 We're given some fixed deterministic algorithm that will do its thing, but uh it can only access the elements via pair wise comparisons. So at some point the algorithm has to pick two elements and ask which one of those is is larger. And at this point, we jump up as the adversary and we'll construct the input comparison by comparison trying to fool the algorithm to make to do as much work as we can make it do That's the general pattern uh that adversaries against some algorithm um always take they always have this this kind of uh form. In the specific case here, what we do is we maintain in uh we maintain the elements of the input in three sets. Two will be S and L where we've committed that this element will eventually be smaller than the median. So you you should think about it this way. We initially have the n elements lying around that are just uncolored marbles and uh we can decide what they are ordered like. Uh but we don't have to fix that choice until the algorithm asks us about specific comparisons. We can change our mind along the way if we feels if we feel like it. We just can't make it a lie what we've told the algorithm in the past. We have to stay consistent to the previous answers.

17:53 So initially uh every element will be u undecided. We don't know yet or we haven't committed yet to that element being eventually smaller or larger than the median. And so now uh whenever the algorithm asks a comparison asks a question which of the two is smaller we check if we've already decided where the elements are. So the algorithm asks us is x less than y. Now we check if if x and y are not in the same sets.

18:58 Then we answer according to the small one one elements are all larger than the undecided ones and these are all smaller than the large ones. Okay, that decides the comparison and that's all we do. Um, if the elements are both in S or both in L, then it doesn't matter. We just answer something according to uh an arbitrary order of these elements that we somehow fix. You could say uh by the time they entered this set and the last option that still is possible is that they are both in U. Okay, in this case we als we say arbitrarily that one is smaller, one is larger.

20:07 And now we put X in the small set and Y into the large set. And what have we done with this um with this step? Well, we've generated a non-essential comparison because at the end of the day, neither X nor L will be the median and they will lie on opposite sides of the median. So, this comparison that the algorithm has just done is turned into a non-essential one by the way we answer it. Okay.

21:09 And so uh that's that's all we do. Um how expensive is this for the algorithm? We always need the n minus one certificate uh comparisons. The algorithm has to learn those no matter what it does. That's this part.

21:26 And uh for the remainder because every element starts initially in U and we only move elements when we do this last step for the algorithm to learn about uh the true median. Well um we only reveal the median really at the very end if uh there's a single element left in u and this is kind of automatic by the first case. uh as long as there are elements in I know the if if the algorithm is is stupid enough to do comparisons where both elements are in S or in L then it pays more and we don't even charge it for that but it has to get all the elements out of you to make progress because we're never going to reveal an in useful information to it before that the useful information only comes from the first case so it has to get all the elements out of two uh all but the true median and so it's n minus one elements that have to go um but for each step we take two of them put them away so it's n minus one half that we get as comparisons right with each comparison that we generate two elements are moved away from u so we create one comparison for Okay.

23:17 So against this adversary any deterministic algorithm will have to pay the certificate comparisons and at least n minus one half additional comparisons which we had turned into non-essential ones but the algorithm couldn't have known. It's uh out of luck. This proves the 1.5N. Um there's a sequence of works that improves that bound up to the 2N which is where it currently stands. Um whereas the best the best upper bound is 2.95N and it's unknown how many comparisons you really need for finding for deterministically finding the median. It's uh kind of um unsatisfying that we don't know this simple question. What I wanted to say is uh how to get the higher lower bounds is by making this adversary more sophisticated. Uh here we immediately put X and Y from the unknown sets one up one down and we harvest one comparison. uh the generalized forms of that keep some some order within you unless that that that compares only a few elements.

24:36 You can keep them around and then do a lot of case distinctions on what the adversary should do and you can you can show you can make the algorithm pay a few extra comparisons. Uh but that gets gets super technical and uh I think is it's worth doing once but not uh digesting in a lecture. the the key idea is these kind of reasonings of uh maintaining the elements in some sets and choosing when to answer what. I wanted to go through this proof because I think it makes platon obvious that if the algorithm is randomized, a lot of this trickery is is harder to do. It's um you can't really um you can't really force the algorithm to make the same kind of uh uh now I'm struggling because this lower bound is also true for randomized algorithms and um I think this specific construction there's nothing that stops you from doing that against randomized algorithms. the more sophisticated algorithms that maintain this partial order, they make this harder.

25:53 Um uh but you can at least see from this proof that designing an an adversary might be easier if the algorithm has to uh commit to a fixed um fixed choice big sequence of comparisons up front.

26:17 The last bit to drive home is um randomized algorithms. The one we've seen quick select, it doesn't actually um beat this bound. In expectation, you need 3.39N with quick select. But that's just because the algorithm is is kind of wasteful and simple. You can do better. And I don't want to discuss the algorithm in in too much detail because that that leads us too far into uh analysis. The key idea is to take um a large random sample from your array and the rough size of the sample is this n to the 2/3. That's a a big sample, but it's a little o of n, right? So with this sample, you can do a lot. In particular, you could actually just sort it and make the algorithm simpler. it's a bit more efficient to recursively select from this. Uh the idea is that you um suppose you want to find the median. So here's your K. You pick a large sample from this array and find two elements whose ranks are just left and right of K by a small amount. And then you do one big partitioning step to narrow down the list to this tiny space.

27:38 The partitioning costs 1.5 n comparisons because you're doing it with two pivots. You compare every element to one of the pivots and those that are larger to the other one. And so uh because these are so close together is essentially half of the elements that you have to pay a second comparison for. So it's uh 1.5 on average. And then you can work out that all the rest in the algorithm is is little o of n work because you're working on a small sample or you're working on cases that are unlikely to occur. Uh what this needs is is knowledge from statistics about how likely is it that this estimator for the median that we get from the sample is off by so and so much as I don't want to get into this in detail. Uh but the the bottom line is that you can do randomized median finding in 1.5N comparisons and that's strictly less than the lower bound we've seen cited the 2n comparisons that you need deterministically. Okay. So at least um in terms of this uh constant factor of the number of comparisons, randomization gives you strictly more power. And um here I guess you can you can see it as you take away power from the adversary to make you pay extra comparisons by by hiding your your next steps.

29:18 Okay, that was a bit of a um a little detour deep dive in in one concrete problem where you can work out this this separation. Uh what we want to come back to next time is what happens on NP hard problems. Can we uh get more dramatic improvements from randomization there? And for that um I want to first define things properly. There's a few a few interesting things from just the the mathematical side that happen that I think is worth um setting straight first.