Video 7-6: Contrenration Bounds: Markov, Chebyshev, Chernoff

0:02 To make the distinctions between these two types of Monte Cara algorithms, we'll look at some uh probabilistic tools uh to talk about the the kind of differences that come up when we try to boost the success probability there. And this is um I guess depending on on the flavor or and and the focus is either called tail inequalities uh in the sense of um the tales of a probability distribution or random variable or concentration bounds.

0:35 But let's take a step back. So uh the the key question or key the pro the key problem is with randomized algorithms the running time is a random variable. Now, as always in in algorithms, you'd like to know for two algorithms which one is better and that's always uh always been a tricky question already with asmtoics and so on. But here is even for a single input, it's not so clear. Um it can always happen that one algorithm is faster than the other because it's random. So how should we compare these? Um there's a direct way. If you just take the random variables for one algorithm, the time on a specific input, right? This is the easiest possible case. You have a fixed input and then they both do something random and then take their time. Uh one simple option is called stochastic dominance where you directly compare two random variables and the definition is just uh say it's a real valued random variable for all possible values. The probability that this one variable is above that value has to be bigger than the probability for the other random variable. Then we would say that this dominates stochastically dominates this one. I put weekly here. The definition in books usually includes this for all t and there's one t where the probability is strictly greater. But we don't I don't care so much here. The the point is this is actually a very stringent requirement.

2:07 uh the the graphic you should have in mind is to draw the uh cumulative density function uh the cumulative probability function. Um so you f ofx and here are the possible values of x.

2:27 Uh let's make this bigger. So I'm I'm comparing let's say this is is X maybe that's a yeah let's let's still call it X and Y nicer to write. So cumulative probability function is just what's the probability for um capital X to be smaller than a certain value. Right? So this is for this value x. And so this is going to be some increasing function, right? Maybe for x it looks like this. Plateaus a bit like that. Um and then we have our variable y on the same space. And now what the dominance means at any point right if if I look at some point x the probability that um y is bigger than that point has to be say you want uh x is let me write this as this it's larger than y then at any point the probability that x is larger than this point should be bigger than the probability that x is greater as it says Here for the cumulative density function we have to take the inverse probabilities right. So 1 minus f ofx is greater or equal 1 - f of y that's what what this translates to.

4:06 Um and then of course it means f ofx is less or equal f of y at any point x. Um uh I should have sorry I should have not written this like that. The uh random variable should go in the subscript or something like that.

4:29 And that's the y. Oh. Oh dear. Let's call this t. And here we should have fy of t. They're on the same axis. And I didn't draw Y. So it might be the same for a while. Then maybe it trails.

4:54 And then it's maybe like this. They both have to end up at one. I guess so. So at every point it's below which what I drew here is exactly not like that.

5:12 Okay. Maybe like this. Okay. Okay, sorry for the messy uh write up. Um let me just write it like this. Okay, so it's a simple concept, but if you think about it, this uh is actually very unlikely uh to happen. I mean, if if that's true, then we would certainly want the algorithm that's most that's at at each point more likely to be faster than that point than the other. uh but we can't actually expect this for algorithms to happen is a most of the time this is the world is not so simple that one algorithm is strictly worse than the other. Yeah. Sorry. Yeah.

6:03 So y is always greater than uh did I draw it the other way around somehow? So this is the probability that x is greater than some value t.

6:31 If I include the t here then that matches right. Then uh putting x on this side y on this side we get fx of t is less than uh f_sub_y of t which is certainly not what I was drawing. So the formula was right but the picture was wrong. So maybe I jumps to a higher value straight away and then maybe looks like this. Yeah, good catch. Yeah, of course I was just checking if you pay attention as always.

7:11 The point is that this is hardly ever true. So if you can do this, it's nice. Um it can be useful for other purposes sometimes. Uh but we'll we'll not get into this here. Um the other option we have is well what what else do we know about random variables? we can take expected values and hope that that's that's going to uh be well defined. Um that also has the benefit that you can compare the the running time of some random variable against some absolute threshold. Say you have proven some general lower bound that holds for all thinkable algorithms. How close does your algorithm get to that lower bound? Well, with stochastic dominance, it's hard to answer that question. uh with expected values uh you can at least compare the two numbers. Um but has to be taken with a grain of salt because of course expectation is only the typical value. Uh the the problem there is if you just look at expected values as all the data scientists know is not it's not always representative. Just to make a tiny example, suppose you have two algorithms um both with expected time two but one takes uh in half the cases one time step and the other cases uh the other half cases three time steps whereas B is much more unbiased. 99% it's fast but then there's this completely uh destroying outlier. Now it's actually an interesting question which of the two you would want to use in practice.

8:45 uh but uh certainly the expected value being the same is kind of annoying because we can't even distinguish that they are doing different things and uh I guess the second algorithm is not so great because it'll always be slow in in the time when you use it where you require some quick answer. Uh so we probably prefer algorithm A but uh expectation certainly doesn't tell us.

9:14 So uh one option is to look more closely and we'll do that. Uh but the the algorithmic solution actually is try to make an algorithm where this doesn't happen. Right? This is this is a flaw in algorithm B. So we'll try to make it so that the the actual time an algorithm takes is rarely far away from its expected value. That has two benefits. we can deal with the expected value and compare single numbers which makes life easier but also a robust performance is anyways desirable.

9:47 Uh formally what we'll do is is this uh concentration bounds we'll try to say that a random variable is not too far from its expected value. That's what this this chapter is about. Um and then if we can achieve that we're happy both from the practical side and from the theoretical side. Um so let's have some some tools for this. Uh first of all um some terminology and so the caveat is that this uh this term with high probability as vague as it sounds I'm using it here in a very technical and formal sense. It means a very precise thing which we'll get to in a second. It's used very much in the literature because uh I'll I'll show you why. But not always the definition is exactly the same. So you have to be a little careful.

10:53 Uh maybe you can call this with very high probability. I've rarely seen a stricter notion. Okay. Um all of this has to do with asmtoics. So is always assuming that there's some dependence on a variable n that goes to infinity input sizes. Uh an event happens with high probability when the probability for that event is one minus a small error term but really it has to be very small namely super polomially small.

11:25 One way to write this is to say for every constant C every degree of the polomial for the error term you give me still you can uh you can show this asintoic okay so it's it's a strong requirement um that's for events uh the slightly more widespread version or more useful one is to bound random variables and this is a tad more subtle so we say A random variable again assume assuming it depends on some parameter is an uh O of F of N with high probability. So the whole phrase this whole thing is one technical statement. Okay. Uh well when this is true what does mean? Um again with high probability you should have some error probability that's super polomial. But now the constant in the big O right there's an a hidden constant in front of F that's the D that is allowed to depend on your on your uh exponent.

12:30 This may may sound bit arbitrary but this turns out to be the right definition in many cases. This is often what you can show and it's sufficient when you can show it. Um I think it's also justified to say that this is really with very high probability. So intuitively it feels like uh if the probability goes down super polomially that's that's going to be a safe bet and uh you'll soon reach the point that is more likely that some quantum physics uh behavior breaks down then that the algorithm is is incorrect if n is large. questions or clear so far.

13:17 Uh it's a very strong notion as I said and the reason why we pick this specific and very strong notion is is this simple lema. If you have some uh say the event is that our algorithm a does not fail then I can repeat my algorithm a polomial number of times. If I make these independent repetitions, that's important independent repetitions of of that event still uh not a single of them fails again with high probability. So it's it's a very robust notion. If you can prove this um you basically uh can iterate things a polomial number of time without seeing a change at at the level of this definition. And so let's let's briefly prove this just to see um uh why this why this is true. And let me take uh the definition with us.

14:31 Okay. Of course it will jump away as soon as I click to the next part. uh well C is the uh constant from the definition. So we have to show the claim again um if you look up we're we're trying to show uh independent repetitions n to the d independ independent repetitions of a are such that not a single of them fails. That's a new event. The new event is the union of all those previous failure events. Okay. uh the E version of of the event fails. That's our uh that's our event AI. And then the event we're now looking at is that any of them fails.

15:33 That's the event we're studying and we're trying to show that B happens with high probability. Uh sorry, not B. We're trying to show uh the negation happens with high probability. So none of the AIS fail.

15:58 Okay. So C is given from the definition. We have to show this for any exponent. Uh of course consistency in notation. Um imagine I would have written FI here for fail.

16:22 FI is the event that the E run fails. Now uh this happens with high probability by definition. So we can pick an arbitrarily big exponent in the error probability and I mean it said in the lema that the algorithm does not fail with high probability. So that means the converse event has this this small probability at most.

16:45 uh then we write the union of all those events that's the probability that any number of them fails but not none now by the union bound right this is uh the events are not well I guess here they are independent but we don't want to get into the question of how many fail we just uh use the union bound and I guess here it's an equal because they're independent but it does it's good enough to upper bound it. Um so we sum up the probability that each of the events fails and that by assumption is this. This uh is bounded by this and we have n of d to n to the d of those. So if you multiply that out of course you get the n to the minus c that we wanted to show. Okay. So with high probability if we can show this then uh that an algorithm does not fail with high probability you can repeat it a lot of times and we'll we'll also use this to combine other things.

17:50 It's a very robust notion that's why we make it so strict and you can work out the details if you don't require roughly this this definition um these kind of repetitions uh wouldn't be allowed. All right, time to get into business with actual inequalities to uh bound probabilities like this. And uh the first one is Marov's inequality which you may or may not have seen. Um but it's it's cute enough. Uh is a very simple simple thing too. Um all we know I wish I had that in red. we need a random variable that's positive or non- negative and a real valued. Okay, it's is emphasized here. Uh then we can say the probability that this val this val random variable exceeds a certain number can be bounded in terms of its expectation and that number. Okay. Uh let me prove it first and then we'll come to what it means. The proof is really kind of cute.

18:59 So we uh have this a given and it's greater zero and then we define some uh some event or or indicator random variable that's this indicator of x being greater than A so it's a 01 event that is you could also write it as X being greater equal one uh with Ivers in bracket same as saying it's one if this is true and else other zero okay So, uh I claim that that I is less than X / A and uh for this you uh you have to take the two possibilities right if um X is indeed greater than A then I is 1 but then x is greater than a. So x / a is greater than one and the inequality is true.

21:07 The other option is if x is strictly less than a then i is zero and well x is non- negative so it's it's not going to be negative.

21:30 So in both cases this is true. Okay, no matter what values X takes, this is always true in terms of the actual random variables. Clear? Uh, now let's let's take this inequality and take expected values on both sides.

21:54 So what we get is um the expected value of i is less or equal the expected value of x divided a. And so we're getting closer to this. Let me write the inequality the other way around. I think this is convenient here.

22:20 I've already used linearity of expectation because a is a constant. I can pull the expectation up to only cover X, right? Um uh sorry that's expectation of I and because this is an indicator random variable I mean the expectation is the sum of 1 times this probability plus 0 * this. So that's exactly the probability that X is greater or equal A and that's it right that's the statement. So the proof is is almost boring. Um but the inequality turns out to be tight in the general case. That's the best you can say if you want to relate X um or bounds for X to be large to its expected value.

23:14 Um a good a good thing to um to memorize is maybe the statement below here. So you just reformulate the inequality a bit. Uh I think this is slightly more intuitive in the following sense. We expect that x is roughly half the time larger and smaller than its expected value. Um so here the question is if it has to be a times larger than it expect its expected value, how likely is that? And Markov's inequality says well at most one over a probability for that. So keep that in mind. Um before we move on uh I want to give a brief uh visualization of this of this inequality because I think it's good to stick in mind. Um which only works for for natural numbers. Uh but often times we have that anyways.

24:05 So the the thing about natural numbers if x is a random variable over n0 is that we can rewrite the expected value in a nice way. Probably you've seen this before. That's just the definition. Sum of all possible values times their probability. But then if you group this, I'd say uh X takes values one 2 3 four with certain probabilities.

24:38 Then what this uh what this first sum does is sum this up time 1 * 2 * 3 * 4. So you're basically doing this and then you have two * this small thing, three times the large guy and four times the little one. That's your expected value, right? Um and another way to uh to write that is uh if you look at this sum, it gives you uh the same the same terms. Um Yeah, I think the way uh to group it is to say previously this came from one, but you could say the one is summed up. The one gets one contribution from each then the two gets one here and three only gets these and the four only gets the last. Right? So uh the probability that X is greater or equal 1 that's comprised of this part and this part and this part and this part. Um and I'm starting with zero. That's a that's the mistake. So you could rewrite this as one large pole where you have probability for one then the probability for being value two probability for value sorry the probability for two was the small one then this this one maybe like this that's greater equal zero.

27:16 uh the probability for greater equal 2 is just this little guy then these guys this and so on. So what's missing here is exactly probability for X being one And then we have the last bit greater equal four.

27:55 Now, uh what is what is Marov's inequality doing? It takes um it takes the if if you draw this um in the more general case, you would draw the probability that X is greater or equal A and plot that over a. Now this is the inverse of the cumulative density function or primitive probability function. So this will be something that goes down in our example.

28:33 Maybe like this. Uh there's a bigger step down here and then okay one more step and then zero. Okay. Um, if you pick any any position for a, then the probability that X is is uh greater A is this point.

29:09 And so you can take uh this rectangle has area probability x greater or equal a time a and the whole region below the curve here this entire thing that's exactly the uh expected value right that's um from summing up from this from this sum you sum up for each value the probability that it that it's larger than a um and so of course the red area lies below the curve and so it must be a subset of of this one. So you get that this one has to be less or equal e of x. That's another way to get Markov's inequality, right? If you um divide by a now, all right, maybe it's not not that useful. Um maybe this picture is worth keeping in mind, but you have to be have to remind yourself what what is on the y- axis.

30:17 Okay, good. So, uh as I said, there's examples of random variables that you can construct where Markov's inequality is in a sense the best you can show. Um but it's not actually such a strong result. Uh if you apply it to some you'll do it in the exercises, you don't get as much from it. And so it seems like a weak bound, but it's a general result because it doesn't restrict the uh random variable that you put in much. So most of the time when you use it, you're not using it on the original say random variable of interest like the running time of your algorithm, but you apply some function on this random variable. As long as it keeps it positive, uh you can apply Markov's inequality to that mapped random variable and that's actually much more powerful.

31:12 So the first version of this um applies it to essentially the uh difference from its expected value. For that we should um define moments of random variables briefly. Um given a random variable a moment of the random variable the kith moment is just the kith power and then taking expectations. So also it means the expected value is just the first moment.

31:47 Sometimes people call it like that. Uh there's two flavors. The kith moment in this case is the the pure moment just taking powers. Um often more convenient is to take the centered moment and also take absolute values. So you take x you subtract the expected value so that it the result has expected value zero. now but then you raise it to the kth power. So what this does is is kind of um well the centering means expected value is zero but then you're also taking powers which means you make make the variable more extreme. If it was close to zero before it's much much closer to zero now. If it was far away from zero it's much further away from zero now depending on whether it's larger or smaller than one. Um well we'll see uh the effect of this in a second. Um you'll be familiar with the second centered moment. That's just the variance.

32:41 And sometimes people use standard deviation because a bit more intuitive. That's just the square root of the variance. Um and of course you can do similar things with the higher moments if you want. Now one one thing to take care of is these are expected values of some random variables. We may may or not have convergence. Um in general this are infinite sums or integrals and they may not exist. Uh so you you shouldn't assume that. Um but often times you can just calculate them and then you know the first the first usage of these moments and markups inequality is called chevy inequality. Uh more more Russian names. Um the statement gives you uh similar flavor as before for marov. You have some uh some notion of x being far away from its expectation. Here it's two-sided in the sense that you take the absolute value of the difference. Mark was just being above a threshold. Here it's being by a factor away from the expectation. And now the upper bound is uh involving the variance. But also you should notice that there's an a^ squ. Previously marov it was x greater or equal a is expected value over a. Now we get an a squared which means for large a this bound is going to be much smaller. Okay. I mean lying away that the variance is there but uh um often times the variance is not much much bigger than the expectation.

34:22 Um let's also prove this is actually very simple. I'm almost tempted to leave it at that statement, but maybe um it's worth doing it once.

34:47 Use normal parenthesis. Uh we just define a new random variable because of the square it's for sure non- negative. And then I'm applying Markov's inequality to this guy. So Markov's inequality again says the probability that this is greater or equal a less or equal than the expected value of this divided by a. Now um let's just pick this apart. So what's the probability that this is greater or equal a? Let me call this B here just in anticipation of a change of variables.

35:31 If I plug in the definition, that's almost what we want. But there's a square. So if I take uh this is an inequality. If I take monotonic function on both sides, it doesn't change the inequality or the validity. So I'm taking square roots on both sides.

36:20 And then I'm just going to plug in what we have here. And we'll use that the expected value of this guy. It's the definition of the variance. If you forgot, it's right here.

36:37 So that's nothing but the definition of the variance of X. And here we still have B. But if a a is the root of b, then that's the same as a squ.

36:52 Okay. And so see what we've done. We've taken a random variable and uh I'm implicitly assuming I mean the bound makes no statement if the variance is infinite. Let's assume the variance is is well defined and converges and the expectation then two. So if I have a random variable with slightly more assumptions namely that is expectation and variance exist I can turn that into a more centered variable or a more extreme variable say by centering and squaring and if I then apply markers inequality I get a stronger result just because this is a more extreme random variable that I'm applying the bound to.

37:48 Okay. Where does the square come from? Uh we're taking so from in this step here And so I have B turns into square root B. And I'm just reabeling that as a the change of variables.

38:30 uh here well it was a b right um we're applying markers inequality to the to the original thing so maybe I should have left it and then said the the thing we apply it to is is the v random variable Y being greater than some arbitrary constant B and then that's uh the expectation. So let me leave here the expectation of Y divided B. That's what Marov gives us literally and then I'm plugging in the definition of variance and the definition of A. If you want is is basically just a calculation. Uh the the the key thing is is this first line only. uh what we get from this um apart from obviously the the inequality as stated I think slightly more intuitive is is the following. If you have a sequence of random variables, so they depend on n um where expectation and variance exist and the crucial additional property here is that the uh standard deviation or square root of the variance is little o of the expectation.

39:59 And I think this is very intuitive statement because that's how standard deviation is used in statistics. you uh look for a random variable around it expectation and then to left and right a certain multiple of the standard deviation that's where you expect the random variable to land. Now uh in parenthesis if everything is normal and so on uh but here uh at least something can be said in this under this assumption. If the standard deviation compared to the to the expectation goes down becomes smaller um then these uh these random variables converge in probability to their expected value. more formally written, the ratio goes to one. And convergence in probability is just the definition of this guy. Um, or any epsilon that you pick, a fixed any fixed epsilon, the probability that you're further away than epsilon from this limit point converges to zero. The probability converges to zero.

41:04 It's not the strongest notion of stochastic convergence, but let's not get into that that too much. um at least Jebbyef's inequality is is strong enough to show that if you have standard deviation smaller than the variance asmtoically the things will get very very centered you'll get closer and closer to the expected value as as bigger uh the bigger n gets all right um so this looks promising we're getting uh closer to um replacing a random thing by its expectation and getting away with it. But this is still not quite this strong notion of high probability. If you if you stop here and try to get this this it doesn't work. And uh if all you know about your algorithm is expectation and variance or standard deviation, again, this is kind of the best you can do. So you're out of luck. You have to make stronger assumptions.

42:12 So the third and final point of this journey um is to think about scenarios where you can make a much stronger statement. And so we we'll come from the other end. So far we've kept things as general as possible and and saw how good a statement we can get out. Now let's go the other extreme. um pick a very specific scenario, but at least one where we know we get the sufficient um results that we want. And intuitively, what we look at is a random variable X that's made up uh from a sum of many small parts. And these are all uh bounded in how much they contribute and they're independent. So the the larger you make n um the more the uh randomness has to average away because there's independent random bits but each contributes just a tiny little uh additional factor. Um and so maybe intuitively you'll you'll expect something like a a central limit theorem type of convergence.

43:18 Uh so I don't know how much the vakeness helps you here. uh we'll see concretely what this means um in these bounds. Um that's the most general version that we'll use and it's it's usually good enough for most algorithms. Um you could push this further but I'm not going to do it here and we'll make a simpler statement on the next slide. The setup is you have indicator random variables so just 01 uh random variables. So uh they're boni trials. They're mushially independent. That's the crucial bit.

43:58 Uh but the generality we allow ourselves is that the success probability may be different for the different uh x i. Okay. Then the thing that we're interested in is their sum and we keep summing more and more of those little parts.

44:15 Then you can write the expected value of x. So that's that's denoted by mu here. It's really just the expectation of x uh by linearity. That's the sum of all those pi. Um and then you can prove these inequalities. The probability that x is uh a 1 plus delta fraction larger than its its expected value is some more or less ugly uh constant depending on delta. But say you put delta to one right then what would we get? This is e and we divide by two squared. So e e over 4. Uh the big the important point is this is uh less than 3 over4. Okay, it's less than one and a good bit away from one. Actually, E is also less strictly less than three. So you have some some constant on the left that you take to the power of the expectation and the expectation here is growing uh because you add more and more of those variables. I mean the expectation is is effectively uh linear in n if the pi are constant.

45:39 If say the pi are all 1/2 then n half is the expectation. So the probability that you exceed your expectation by a factor two goes down like an exponential function 3 quarters to the n or n half. Right? So it's a very very strong concentration because you have an exponential bound on the probability. uh and you can prove um a weaker version um for for a specific delta where just the the right hand side is a bit more convenient to work with. So uh this the second equation follows from the first uh that's just a um if if you make the assumption that delta is is less than one then uh you can bound things in that way that's not uh not so interesting. uh what I want to give you the proof for is the first part because it it shows exactly why this is this kind of result is possible. Now uh it gets a bit more um arithmetic in a way uh but I think it's worth suffering through this once just to to grasp where this is coming from so that you can generalize it if you ever need to.

47:08 Um maybe before we do the proof, let me show uh the simple version that we'll mostly use. This is just the special case of the previous statement where we um say all the XI have success probability 1/2. You're summing up independent identical Bernoli trials. That's called the binomial distribution. as in particular you have n independent coin flips each succeeds with probability P and you take the sum how many came up with heads say that's your random variable X and then you can essentially plug in what you have from the previous bound um what I've done here is combine the uh the two um you take n minus this uh to get a bound that is is two-sided n. So you take x, you divide it by n to kind of uh um remove the scaling because x would grow with n. You take x divide it by n and subtract the subtract p which is the expected value.

48:15 So the probability that this this uh difference from the expectation is larger than some constant delta is bounded by an exponential function and you even are allowed to square the delta in there. But this is x + e to the minus uh something squared. So this is really really small. Okay.

48:39 Um in particular you can use this to show that in our sense with high probability we're finally there. Uh a binomial random variable is in this interval expected value plus minus a tiny bit more than square root n. Okay, that's uh where we want to get to and uh we'll then apply this theorem to some algorithms uh may maybe uh maybe tomorrow or just the end of it today. We'll see. Uh I do want to give the proof here. So um but we have to pick a variable that's even more extreme. What we had before was take x minus the expected value and then take a power squared. What's more extreme than taking polomials? Exponentials. Uh so uh it's a bit more tricky this time. Um first we need a parameter. So uh what we'll do is it will show a general bound depending on this parameter t and then you can at the end pick the best t to get the the actual um inequalities that we claim.

50:16 Then we um apply our mark of inequality to the following random variable e to the t * x. So we take our um our sum of uh independent things, we multiply it by t and that's the uh exponent.

50:43 Um so far this is essentially just falling from the sky. But uh uh that's where you um apply Markov's inequality to uh is not is not exactly uh following this the straight schema. So let's start from the beginning. We want this part x to be 1 + delta greater than its expected value. That probability we want to upper bound. Now I'm I'm using this transformation in this in here on both sides.

51:32 I'm applying the function e to the t * the thing that's there. So I get the y on on this side and on the right hand side I get this lovely expression e to the t * delta 1 plus delta time mu. Okay let's see uh what we can make of that. Um let me stress here that this this exponential is always greater than zero. So we can apply Markov's inequality to that guy.

52:18 Um to do that though we have to rewrite it somehow right Mark's inequality had you have to be greater than uh so you have to know um the expectation of y so and then we divide by this uh friendly thing.

52:45 What's the expected value of y? Well, we just plug it in and see what what happens. Um, we're going to carry around this factor in front for quite a while. So, we're going to take a pause here and just evaluate what the expected value of y is.

53:08 Of course, just by definition, it's this thing. And what was what was x? XD sum of all those independent renewalies. Okay. Now, uh here comes the trick. Um that's an exponential function. We have a sum in the exponent that turns into a product.

53:43 So the e to the t is is in front and then we have the product Um uh it's you can also leave the t inside as turns out that's that's convenient. Let's leave this inside. Um, pull it into the sum.

54:18 And now again a crucial step. These are these x i are independent random variables by assumption. And e to the txi as a random variable. So if you say y i is this guy, these are also then independent because the x eyes are and what have we learned about the probab the the expected values of independent random variables? They factor. So in in particular the expected value of the product is the product of the expected values and of course this is the step that you uh would not have been able to do with without this strict setup right this is uh Jeffef's inequality can never get to this so you're forever stuck at kind of on this left side or I don't know okay um then the expected value of these Guys, X I is 01.

55:34 So let's do another side calculation of the side calculation. X I can be 0 or one. So that's easy. If it's zero, then E to the T * 0 becomes E to the 0. That's one.

56:02 And if I plug in one then I get e to the t and of course we know what these are by definition again you know is a boli pi so it's 1 * 1 - pi plus e to the t * pi because here the one get rid of. So that's this expected value that we're now going to plug in up here. Okay, let's do that. So, We can slightly rewrite this as one this guy and then plus pi * e to the t minus one. That's just uh rewriting this bit.

57:45 And now we have to use a little trick. Um, we're basically using the uh inequality 1 + y is less equal e to the y, which you could either look up on the TCS cheat sheet, or you remember that um I guess that's essentially the definition of uh convexity. But uh the the the prototypical example of a convex function is e to the x. So that's a convex function. It bends upwards. And if you look from a from below, you never see concavities, I guess. Well uh and you can pick at any point you can uh you can pick a tangent and the function will lie above it. Okay. And this 1 + y well that's exactly the tangent at zero. Let me just rem let me move my y- axis. Then it's the right one. If you plug in zero then you get the value one. That's where you start. And if you take the derivative, that's the slope of the tangent at this point. The derivative of e to the y is e to the y. Plug in 0, you get tangent 1. So 1 + 1 * y is the line uh that you get there. And so of course 1 + y has to be less than e to the y.

59:28 That's a if you don't want to learn formulas by heart um then uh this thing right by the formula is less than e to the whatever we have here p i e e to the t minus one and then you have a product of these is a product of e to the something let's pull out the exponential function Okay. Now one more step. We can pull out this con this common factor from the sum.

1:00:26 Let's do a slow-mo. So, it's e to the t minus one. And then the sum. But the sum of the pi, we know what that is. That's got a name that's exactly mu because that's the expected value of x.

1:00:51 Okay. So now we're at the point we've computed E of Y or an upper bound for it. Let's uh continue the original equation for where we started the uh probability that X is greater or equal 1 + delta * mu which was this guy and it ended with expectation of Y divided something. That's where we're continuing. All right. So um make a bit more space. Maybe the probability that X is greater or equal 1 + delta mu was less or equal e to the y divided this lovely uh term e to the t 1 + delta mu.

1:01:46 Now we plug in this part and we get e to the mu e to the t minus one divided e to the mu t 1 + delta.

1:02:11 And so the last bit is you have a an exponent at the top, an exponent at the bottom, and uh there's a a common e to the mu. So you pull this out. Um yeah, I guess you could do this already at this step.

1:03:02 Because it's a minus. Sorry, you cannot pull it out at this point. Yeah, I confused myself. It's e to the this minus this. So, you can't pull it out yet. Um, I guess that's the end of what you can do for general t. So far, this worked. The whole derivation is true for all possible values of this parameter.

1:03:27 So you can plug in any value that satisfies this and you get some specific bound. And uh one convenient choice because we have this e to the t term that's really uh annoying. We plug in something that gets rid of that and relates that to delta. And this is kind of something people found out by trial and error. So you you plug in here continue the equation kind of a equal then it's e to the mu e to the t turns into this log uh sorry yeah turns into 1 + delta and we have the minus one and here we uh keep the and the log 1 plus delta moves into the uh basis of this whole thing. We're using e to the log of the thing and what's left is mu and 1 + delta.

1:04:58 And now you pull out the mu. Uh I guess I could have could have done this up here. Yeah, you could have written it like that. So because that that's the whole thing. It's e to the e to the t minus one to the mu e to the t 1 + delta to the mu and then pull it out. But uh okay, the one cancels, right? It's just e to the delta divided this longer term 1 + delta to the 1 + delta the whole thing to the power mu. Okay, that's finally what we wanted to prove. Okay, is a bit heavier on the calculation side admittedly. The thing is you don't have to ever do this again unless you run into an application where the given theorems aren't general enough. But let's let's recap the key trick. The key trick was again to use Marov's inequality but to a variable that's much more extreme. If x is extreme uh away from zero then this is even much further away from zero.

1:06:29 Um, and because we could factor the random variable by taking the sum into the exponent, you get a product that you can then factor because of independence.

1:06:44 That's what makes this uh this statement tick. And the rest is a bit of uh road calculation. We'll actually mostly try to use this version just because it's it's much cleaner and Many times the random variable we're bounding comes from repeated applications of something. So we can assure that it it has this binomial form.