Video 7-7: Concentration Bounds in Action

0:03 In the next section, we'll finally apply the uh concentration bounds, mostly the churnoff bound um to some some concrete algorithms uh both to show you that it's useful and to see how they are used. I I might try to go a little quicker over this. Um there's past recordings where this is done in maybe more excessive detail. Uh the first application is our standard strategy to boost the success probability for Monte Carlo algorithms. Um said already u if you're not happy with an algorithm that's wrong half the time, you just repeat it several times and take whatever the majority vote gave you. And we can even be more cautious. If there is no clear majority, we say we failed. Um so here is that formally written up. uh you do t independent runs of your Monte Carlo algorithm on the same input x but with fresh independent random bits. Uh if at least t half rounded up many runs um yield the same result then we output that.

1:14 Um I guess we always pick an odd t. So just that there's no ties. Uh and otherwise we we give up. So how good is this? uh and it turns out that depends on the exact type of the Monte Carlo algorithm we have. Uh here we look at bounded error Monte Carlo. So in particular if you remember the definition this meant that the probability that this algorithm a on an input X is the correct output.

1:46 This has to be at least 1/2 plus some epsilon. And this epsilon must be independent of the input that we pick. There's an absolute constant depending only on the algorithm so that we can bound the success probability away from 1/2. That was bounded error. And now we're saying uh if we have such an algorithm whatever the exact epsilon for this algorithm is uh we can make it with high probability. So essentially make epsilon a sub polomial shrinking like one over a super polomial function little of n to the minus c for all constant c by just a a moderate number of repetitions slightly more than logarithmic.

2:40 Um, so let's let's see how to prove that. The goal will eventually be to use the churnoff bound. So let's uh keep that handy.

2:53 Might have to make this a little smaller in the end. We'll see. So the goal is to do um something where we can apply the binomial turnoff bound. So we need to somehow generate um a binomial distribution.

3:09 Um for all intents and purposes you can assume that t is log squared. This is this is just for you to keep in mind. It would actually be uh good enough to take login time log login or whatever else small growth above login. Um but that's kind of uh morally the idea that you should keep in mind. So um we do t repetitions that means we can define t random variables x1 x2 up to xt where x i is the event for the random variable that the i run succeeds which means produces the right output. So on our input X we actually get what the function is supposed to output. And so this is an indicator random variable of this event that the run satisfies this and of course this is uh 01 variable.

4:22 So it has some probability to occur and we actually know a bound for this probability. Now because we pick the same X, we we don't know exactly what P is, but we pick the same X and we do independent repetitions. So really these um uh the sequence is IID independent and identically distributed and it has some uh some Bernoli P probability uh or Bernoli P distribution for each X I just don't know the P exactly we know a lower bound um but we can uh we can pretend that it is it is known exactly uh then the algorithm will only be more likely to succeed.

5:33 That makes the uh calculations a little easier if you don't have to uh have another inequality flying around. So we'll assume that we have exactly 1/2 plus epsilon for some constant epsilon greater than zero.

5:52 Now uh if you um define x by summing up all those indicator random variables, we get something that's a binomial distribution by definition. T repetitions, each event occurs with probability P. Um so what's the sense of doing that? Well, we can now express that our overall algorithm uh succeeds or rather that it fails. Say the majority vote fails if and only if we have not enough seance summing to one. So uh if and only if x is too small.

6:51 let's always assume that t is an odd number just to avoid kind of stupid corner cases. I don't think that adds any any interesting twists to it. Okay, now we're essentially in business. we uh have reformulated our algorithmic problem as a purely statistical one. What's the probability that a certain binomial is at most that value?

7:15 Uh so let's calculate the probability for that to happen. The probability that X is is less than um I'm making the event less likely. That makes the um more likely I'm making the u the condition weaker by dropping the floors.

8:01 So that is a more likely event which means the probability can only go up. And now we have to rewrite that in a form that matches the turnoff bound. Maybe we can afford that on this page a bit bigger.

8:18 The point is we need to rewrite it so that it's um matches that form. So we have to subtract the expected value and it turns out it's it's more convenient to flip it around and add P on both sides. So we do a whole rearrangement. Okay, let me first write it down.

8:55 So what have we done? Um I added p on both sides. Um well we divided by t first then we have x / t less or equal 12. Then multiply that by minus one. Then you have minus x / t greater equal minus 1/2. And then we add p. So that's the same same inequality just uh rewritten.

9:21 And so that that's close to what we need. Uh this is the wrong way around, but we'll take absolute values. Um but this expresses that essentially our um random variable is much smaller than the average. Uh that's half of the tails that we bound with the churn of bound. So we make the event again more likely by including both options being way too small or way too big. Okay. And so hopefully we express that as the uh the absolute value to be greater than what we have p minus one/2. And so that's now in the form that we need for churnov's bound. In particular, this p minus one/2 is exactly our epsilon which is greater than zero. So that matches it's called delta in the bound, but it's other than that the same. So here we apply turnoff bound uke and we have to insert what we have on the other side. So it's 2 e to the minus then we have delta squ which is epsilon squ in our case and the n is a t because our uh binomial has has t repetitions.

10:36 Okay, so far so good. Um, that's the probability that t repetitions fail. Now, uh, we're claiming that, uh, this is not happening. Uh, with high probability, this isn't happening. And so if you remember what that means, for every um exponent C, we have to show that the probability is in in this little O of N to the minus C.

11:30 So we're given such a C um and we compute N to the C times the probability that this algorithm fails. If that goes to zero, then we've proven the little low of bound.

11:52 So we claim that this goes to zero. From this we would follow that the probability that this fails is in little of n the minus c because c was arbitrary.

12:06 Um that implies that the algorithm doesn't fail. with high probability. Now, we still have to show uh that this this convergence here is true. Uh but that's not actually that hard using our bound from above. We can um let me copy it once.

12:42 So we take this we use our bound from above this one and um I'm I'm going to put the n to the c into the exponent so everything is within an x and then I have c * natural log of n and we have the minus 2 epsilon^ 2 t and at this point we have to use what we know about t namely that it is uh super polomial which means we have some some constant time log n minus another constant time something that grows much stronger than log n. So that means uh the overall thing in the exponent goes to minus infinity because the second part dominates uh the t grows bigger. So uh the um exponent goes to minus infinity which means the exponential is going to zero and that's what we claimed. Uh so this is protottypical of the type of with high probability proofs we apply churnoff bound. The creativity goes into how to define the x i here was very simple because we just repeat the same thing several times. Um then we reformulate what fails means in terms of bounding um a binomial and the again the magic is um majority means exactly t half is our threshold but the success probability is slightly bigger than 1/2.

14:45 So there will be when n go gets bigger and bigger there will be a linear difference between t half and the uh expectation t * p um and that's what we use here. So uh in in this case um you get this this exponential upper bound. Then the second step is also always the same. If you show with high probability you have this n to the c factor that you're supposed to dominate or the uh probability is supposed to go to zero faster than this n to the minus c. And so you multiply this together put it in the exponent and make sure that the exponent goes to negative infinity.

15:28 Okay, this was nice. Uh to finish off this part about majority voting, um let's drive home the point that really unbounded error is is pretty much uh different.

15:43 So the formal statement here says okay, you can still do majority vote of course, but there is an example where you have an unbounded error Monte Carlo algorithm that even has a restriction. It uses a linear number of bits. It could use polomially many but here say it only uses a linear number. Um and then we can say we can guarantee that the majority votes um even to reach a certain fixed uh probability we don't even aim for high probability bound uh requires already super polomially many repetitions. So there's no way to turn an unbounded error Monte Carlo algorithm into an a bounded error Monte Carlo algorithm while keeping the running time polomial. Um we're basically just showing here that the trivial way to do it fails. That's not it's not actually supporting my statement but we'll come back to that um in the next unit. Uh we start with essentially the same kind of setup. So all we know is that the success probability now is strictly greater than 1/2 with no uh bound and for sake of the argument again I guess we we can we can say that the number of random bits is exactly n you'll see this doesn't really uh change anything but at least in in the worst case a now has a different run for every random input.

17:34 So here it would be 2 to the n different runs for the same input depending on the random bits. And uh of course these are equally likely the way we define things. So uh each has probability of being chosen 2 to the minus n. Okay, that means we can follow the same approach as above.

18:28 if random variable X is less or equal half T half. And again X is a binomial distribution but this time all we can say is that the probability here P is strictly greater than 1/2.

18:48 Uh but we can say a little bit more under this assumption because remember the probabilistic Turing machine everything is is deterministic once the random bits are chosen. And if I only have 2 to the n different runs and it has to be strictly greater than 1/2, we actually know it could be 12 to the plus 2 to the minus n in the worst case like it has to be at least that big. And let's suppose that we pick an algorithm where this is indeed the the worst case that happens. Though in reality uh the bound on the probability is not completely uh unknown because the number of different runs is not completely unknown and unbounded. It depends on the number of random bits that you use. You can still make some statement about the probability. But the key thing here is that this epsilon is going to zero and even exponentially small. So we maybe smell the trouble there.

19:52 Okay. Um now the rest is a bit of uh road calculation. Um there's there's one step which may maybe may be uh worth doing. So maybe let me let me try to um give the argument.

20:07 First of all, we show that now if we take our x and we try to get into the um the range Um that's again going to use jirenov bounce. So what does that mean? If uh the number of equal outcomes is is a majority but uh below the expected value, we shouldn't expect it to be much larger than the expected value. So this is this is the range where um the majority vote succeeds, right?

21:16 But unfortunately this is uh this needs um this is is actually not yeah you want you want this probability to not be uh so I guess it's it's one part of this where where we have success if x is larger than the expected value uh will also succeed. Um but this range um is not is not very likely. Um because the the binomial distribution is symmetric.

22:03 The probability to fall above the expected um value is exactly 12. So from these two things um the probability that the majority vote overall fails is again the probability that our x is too small le than t half and that is at least as much as the probability that t is strictly less than t half. Okay.

22:52 And uh we'll we'll use that to rewrite for the two parts. So there's um if you think about the whole range that x could take there's t half here in the middle and then the expected value is is slightly bigger. It's a tiny bit to the right.

23:32 The range where we succeed is this green part. Uh sorry, X is greater than than T half. That's the green. That's where our majority vote is happy and succeeds.

23:56 And so the probability that it fails is the converse probability. And we express that by taking um the probability to be below the expected value and subtract the probability for the part in between.

24:32 So that's this tiny bit here is that blue part. And so we know uh this is at least one half It's essentially 1/2 um so this should be greater or equal if the random variable is symmetric you have exactly the same mass left and right of the expected value but because it's discrete the expected value itself could have non zero probability so uh it's it's half plus um the probability to hit exactly E of X but we need is an upper bound here. So that's right and what we subtract is um have an upper bound on this thing. So what we subtract then turns into a lower bound. So we have this epsilon t to the uh epsilon t and we'll see that this essentially converges to 1/2. So it's not going to be um that's what we uh want to show. uh um if if it was to converge to something well that's the probability that it fails and um if we can show that this converges to 1/2 unless you pick an absurd large t.

26:16 So suppose we pick the polomial number of repetitions and recall the epsilon was this 1 / 2 the minus n. 2 the - n to the c 3 2 the - n to the c.

27:09 So essentially this part uh is going that the exponent is going to zero very quickly. So the exponent part is going to one. This n to the c is fighting against an exponential. So the exponential wins and the whole thing goes to zero.

27:30 So what does that mean? uh if we do any polomial number of repetitions the majority vote fails with a probability that converges to 1/2 in particular it converge it it is below any kind of delta or any delta greater 1/2 or sufficiently large n and so no uh no polomial number of repetitions um suffices Okay.

28:18 Okay. What we uh still have to show is this claim up here. I should say uh we will show Probability that X lies in the range between T half and its expected value less or equal epsilon T3 to the epsilon t right?

29:00 Yep. Uh this is not something where you can use churn off bounds. So there um the easiest argument uh I found was essentially going by the definition.

29:15 So we take this um take this guy just plug in what what that what we know about that. It's a binomial distribution. So we know what the probability weights are like. And okay, let me try to write this a bit cleanly.

29:41 The values for X range from the lower bound. So t half excluded, so let's say T half + 1 up to um the expected value is P * T.

29:59 But we know what P is. That's half plus epsilon. So we have P half plus epsilon T. Here there's a plus minus rounding issue here that I'm I'm I'm uh trying to sweep under the rug to not make the calculation uglier than needed.

30:24 And what's the probability for a binomial to have a certain value I? It's the binomial coefficient and then this I times the success probability and the counter probability for the other attempts.

30:44 Right? So that's just the probability that binomial again remember X is a binomial with parameters T and P. And so that's just the probability that X has this value t I sorry.

31:05 And so we're going to bound this a bit. And it it turns out you can you can be relatively generous in how you bound it and still get this upper bound. This is pen doing.

31:39 So first uh let's leave the sum aside. Um the binomial coefficient. so this this whole uh this whole probability has a a certain shape. It goes up and then goes down again. So it has a peak at the expected value. If you plot that as a function, this gray thing and so um we can upper bound the sum by uh replacing all sums by the largest sumat. Okay.

32:41 I think one one step further would make sense here. Uh we're summing from t half to something larger. So the largest is actually the first amount but um just plug that in. We have 12 + epsilon to the t half minus epsilon to the t half. So largest amount and you can upper bound this binomial coefficient um if you think about it. So this a it's a set of we're picking from t elements t half elements that's effectively um it's effectively like a bit vector of size t where you know half of the bits are are one but certainly this this binomial is upperbounded by 2 to the t. So let's just use that here that this is at most 2 to the t. That's a generous upper bound actually but doesn't hurt. And uh if we if we want we can write that as 4 to the t half. Turns out that's convenient. So we can now rewrite the trick that we've changing the sum is that now all sums are the same. So I just get the number of sums which is epsilon t times um the sums themselves and there um we have four to the t half and then these guys all to the t half. So it's one big uh exponential half plus epsilon half minus epsilon and the whole thing to the power t half.

35:18 So, I wonder if I was too generous at that point. Okay, let's see. So this bit in in the sum here, you can multiply this out. So it's 1 - 4 epsilon^ 2 and you get a quarter from the 1/2^ 2 and then minus epsilon^ 2 and the whole thing* 4 that's certainly less than one so uh we get that here then I only get an epsilon* t upper bound I had an additional factor um written down. But I'm I'm not sure where to get that from. Uh let's see if we need this 3 to the epsilon t here. Really because it turned it went to one anyways So I'm going to say this is not needed. So let me uh remove that bit that wouldn't change anything. It just makes this um a bit easier.

37:27 Maybe it's just uh that I was here. I was generous here. I think I was overly cautious back then and I upper bounded not the entire amount by the largest amount but the individual parts. So this part is biggest for t half. This part is biggest for uh the other extreme point for i but I don't see why we would need that. So um should be fine and so the argument is slightly slightly shorter.

38:07 Again the point is unbounded error is not good enough. Uh we need an exponential number of of repetitions. Uh so that's an indication that this is it's not a suitable model.

38:20 Uh at this point I I thought it's it's useful to make um a short comment on uh what happens with randomization in optimization algorithms. Uh because the majority of um majority vote that we've just discussed makes a lot of sense if you have a decision problem where there's only yes or no outputs. If you have an optimization problem, um you could have a randomized algorithm that outputs any kind of feasible solution. um but it need not necessarily be an optimal one. Then if that's the situation, why would you take uh why would you follow the majority vote if you can just compare from all the solutions you got which one was best? And so um a natural approach for optimization problems would be not to do the majority vote, but just output the best solution you've ever seen in all the random trials. And then this is this is a natural thing to do. will um we'll have sometimes a hard time proving that this is doing any better than the majority vote and we'll kind of reserve this for the approximation part.

39:27 So in this for this chapter um we only allow the exact optimal solution and then the whole theory is is essentially uh equivalent to requiring that you have a majority vote. This doesn't seem to make make a big difference. There's there's more to come. I just wanted to make this point here because if you think about randomized algorithms for say a vertex cover and if if any of the independent runs found a smaller vertex cover why would you go with the majority vote and obviously uh you wouldn't um this is more to make uh make the theory around for the decision problems.

40:10 I have one last example where I'll uh I'll only sketch the proof and um I'll refer you to some some old recordings if you want to see the full details. Um what we've used so far is essentially the churnoff bound in its very raw plain vanilla form because the majority vote does exactly uh identical repetitions and that seems like an an obvious fit for the turnoff bound. But maybe this is not always uh as easy. And so um there's an example where you can with a trick apply the turnoff bound still even though it's not obvious why there would be an independent repetition of things. And that's this statement about um about quicksort. So you'll remember um what I mean by randomized quicksort here is that you pick a random pivot in each in each step.

41:17 and the other thing we have to talk about is the recursion tree. What do I mean by that? Um the original input for quicksort is some array and then you pick some pivot. We don't we don't know up front where it will be but after partitioning I know maybe it it lies here. That's my first pivot.

41:35 And then um I know these are lesser or equal. These are greater equal than the I'll just write P. And I'm going to recurse on the two sides. And so I I naturally get a tree from that where this is the root and then I have a a vertex here or node here and there will be some other pivot in this part and maybe here as well. So I keep splitting this till the parts are tiny.

42:18 And okay, if I draw this uh until the end, we're going to sit here for a while. So let me stop here. The thing is on each level if you sum up the effort on every level you have linear costs for each of them as an upper bound. Maybe some levels are not empty are partially empty. Let's do one more here because some uh elements already are done and so they don't have to participate any further. Um So you have a a linear cost on each level. If you can bound the height of this tree, you get a bound for the overall number of comparisons. That's what the corollery says. If you can bound the height of this tree, then the number of comparisons follows. And so we're interested in the uh the worst the worst branch of this tree. Intuitively you can say in each step you follow the the bigger sub problem. But uh of course that's only an expectation true. Um really what you mean is is the height of this tree the longest path from the root to any leaf. So if we show that this is logarithmic then we have shown that quicksort has order n log n cost not only in expectation but with high probability in our strong sense that's the reason why you'll essentially never see quicksort fail in a and never go quadratic if it's properly randomized.

44:03 Um maybe let me be picky here because uh the the statement kind of hinges on the fact that you don't have duplicate keys um because then the randomization kind of fails. You uh or you have to play further tricks but that's for a different that's for a different time. Um I've written a long paper about exactly that and what happens. uh there's there's much more known but this is not a not a lecture on quicksort. Uh I want to sketch how you can apply turnoff bounds to prove this this um logarithmic height statement.

44:49 But I have to identify something that behaves like a binomial distribution. And maybe that's at first not obvious how how that fits together. that's supposed to be a T. Where's the binomial distribution? We have to make it so that it appears. Um, so a little bit of notation. Let's say V is any node in this recursion tree.

45:34 and n of v is the number of elements there. So in my picture I would have said uh this guy is called v and n of v is the length of its range here. That's n of v.

46:03 And um let's call J of B the random number Okay. So in in this case the J would be this the size of the left child.

46:35 The thing is I want to focus on a on a single vertex for a single node for now. So I'm describing these quantities from the perspective of one vertex. Of course J of V is always this N of V of the left child.

46:55 That's that's clear. But I'm I'm trying to make make the point here. And now we say uh V is balanced if J of V divided N of V is in a good range say between 3/4 and one quarter. Right? So graphically you want your pivot to fall in the middle range and if it's too far is if it's in the outer half the left most or the rightmost quarter then you have decide that that sub tree somehow went wrong. Okay.

47:53 But the point is we don't care about individual failures. We just care about constantly failing. Um the the key observation is if you have a recursion tree or n elements the beginning then you cannot have arbitrarily many failure nodes which are unbalanced.

48:37 Um so you cannot have arbitrarily many balance nodes on this path. Namely uh okay number you uh basically work out backwards and insert but the idea is if you have a balanced node you lose at least a quarter of the elements and you continue with three quarters. So the question is how often do you have to multiply n by three quarters? So you start with n the number of balanced nodes is how much this reduces and uh you stop when you have a single vertex. So if you solve that for b you get this uh this quantity okay I computed that this is 3 * 5 ln n probably won't need that because we're we don't do the full computation, I think.

49:50 So, uh you can you can only have so many balanced nodes before essentially the size of your tree reach it reaches one and then you're at a leaf and you have to stop. The only way how your tree can grow arbitrarily tall is by having unbalanced nodes all the time.

50:08 And so we're now almost there. We'll define our um along any path. So we start at the root and then we just follow an arbitrary path.

50:23 And because the thing is symmetric, I'm going to just follow the left path. But the same statement applies in the end by a union bound over all paths.

51:13 So the unquantitative statement is this. That's why we can focus on a single path and we'll define indicator random variables that the the I And then you see uh that if you had a very long path you would have many x's um but they sum to something much smaller than their expected value. So um if we have uh x is the sum of many of these say depth d then um that's well well it's a hopefully binomially distributed with some probability p which will essentially be half. That's how we picked it. Uh we picked the balanced condition so that it's equally likely to be balanced and unbalanced. And if that is true, then the probabilities say that the path is longer whereas sorry that D is greater than um what's the constant that we should use in the end? Um A constant times log n or a large enough constant.

53:21 That's the probability that our x is less or equal the uh magic bound. It cannot be more than this. But x is the sum of d r random variables. So the expected value of x is um 12 * d.

53:55 And so you um you see if you put uh c large enough then the expected value of x is much larger than this 1.35 login. So you can apply churnoff to this.

54:29 I don't know. Maybe um we pick seven ln so it's uh 14. So it's twice as big just to make up some numbers. So you can apply turn of bound to something like this. Now I'm shortcutting a long computation for two reasons. Um, uh, maybe it's inside pole if you try it yourself to figure out the what the con what constants can make this work. Uh but there's one there's one little catch um that I glossed over and that you have to fix. Namely um these X I are not actually we're nearly one half random variables and they're not actually independent. They're close to it and you can fix it but not exactly as uh I defined it.

56:17 and the reason is is intuitively uh easy to see in the picture and it all comes just from stupid rounding issues. If you have a certain size n and you're trying to split this, you don't have exactly probability 1/2 that you fall between a quarter and 3/4ers with your pivot because uh n may not be divisible by four. And so the probability is not exactly 1/2. It's it's something close to that but rounded to multiples of 1 / n. It's got to be. But that also means the probability for this guy is not independent from the balancedness of the parent because the way the parent chose its pivot influences my size. So, there's a sneaky tiny little uh independ uh dependence that sneaks in because the pivot ranks has to be a multiple of 1 / n let's say it has to be integral. So it's not in the picture I pretended that we have a uniform random variable at each level and the truth is it's not exactly that. Uh but the the thing is you can fix this by um modifying your x i to be um the combination of two events that the pivot is in the middle or uh if you know because your size is is uh not divisible by four that this won't exactly work uh you add another option you flip a coin with a small probability that offsets things so that again the combined event has exactly probability 1/2 to succeed no matter what n of v is.

58:53 I'm going to leave it here with this um because I think it's the details there are very quicksort specific and maybe not not so exciting or general. Um but I found it cool that you can use the standard turnoff bound by just applying some uh elementary clever tricks outside of it and use it for things where the the exact um assumptions are violated. Uh as one concrete example you can show that quicksort's height of the tree is greater equal 42 log n out of all numbers with a probability of order n to the minus7.4 that's just what comes out of these numbers. There's actually even stronger statements about quicksort known. Um but standard churn of bound is enough to show our with high probability in big O. And remember that means the constant in front of the login can depend on the exponent for the probability that you want.

1:00:09 Okay. So that's uh that's all for this introductory part with all these models and uh and formal definitions. Uh we've we've seen already far far back at the beginning of the unit that there's examples where randomization is uh strictly more powerful than anything deterministic. Uh that was this example of of selecting the median.

1:00:31 uh we've seen a formal model for uh specifying exactly what randomized computation is which is mostly useful if you think about complexity classes. So we'll come back to that. Uh we won't have to talk about the Bernoli probability space much but uh it's it's there for you in case you want to have things formally defined. More importantly uh we've looked at two types of randomized algorithms. Las Vegas where we can never answer a wrong um output and Monte Carlo where this is fine as long as it's most of the time the correct answer. And we've seen uh turnoff bounds as the key tool to prove that independent repetitions are really very very likely to give something close to the expected value of some random process.