So today, we're going to be continuing our probability unit. So I just want to remind you where we were. So when I was last lecturing, I introduced the basics of probability. I told you what a sample space was. And then it led to things like events, where we talked about what was the probability of different events. We talked about independence. We talked about random variables that are functions from our sample space to the real values. And once we had random variables, that allowed us to do a lot of exciting things, like we could talk about the expectation and the variance of the random variables. It allowed us to do things, talk about conditioning, like when we condition on some event in the sample space occurring—how does that change the probability of other events, how does that change the expectation of random variables. And then we talked about this powerful tool of inclusion-exclusion. And then after that, Peter gave you a bunch of lectures on counting methods, on generating functions. And the truth is, for the introductory lectures in this class, there are a lot of tight connections between probability and counting. So we really need both perspectives. And we're going to go back and forth between them.
But today, we're going to cover one of the other important topics in probability, something that we're going to spend a bunch of time on, which are called tail bounds. So the idea for a tail bound is to get a handle on how likely it is for random variables to be far away from their expectation. So remember that we take a random variable and we look at its expectation. And that tells us, on average, what we expect the random variable to be. But of course, some random variables might have large averages just because they have some very tiny probability of having a gigantic value. So then we talked about notions of variation and variance that told us how well a random variable concentrates around its expectation. So today, we're going to make that precise. We're actually going to get bounds on what's the probability that a random variable is very far away from its expectation. So let me tell you one simple tail bound in action. And really, the theme of today and Thursday's lecture will be we're going to use more and more information about random variables to get tighter and tighter control. So let's start off with a very basic example of a theorem that needs very little information about my random variable, but gives me a rudimentary baseline of what's the probability it's far away from its expectation. So this is a very simple to state and prove bound. It's called Markov's inequality. And here, we're going to assume that x is not just a random variable, but it's a non-negative random variable.
Then what I claim is that the probability that x is larger than some constant C is bounded by the expectation of x all divided by C. So this makes intuitive sense because, if I have this non-negative random variable, as C gets larger and larger, I'm going way out into the tails of my random variable. The probability that the random variable is actually that large should be getting smaller and smaller. Now, the important thing is that the expectation shows up on the right-hand side, because that gives us some baseline of how large we expect x to be, on average. So the larger its expectation is, the weaker my bound on this tail probability is. But as C increases, I also get some width. So we're going to prove this bound. And then we'll state another corollary, an equivalent way to rephrase Markov's bound. And you can go back and forth between them, depending on what's more convenient. But one thing I want to emphasize is that, here, I'm crucially going to need the fact that x is non-negative. So just as a spoiler, I'm going to ask you where in this proof I'm really appealing to non-negativity. And after I give you the proof, I'm going to expect you guys to tell me where this fact was used. So let's prove this. And the proof for this is really just breaking up the expectation into different pieces. So let's start off with our random variable x. We know its expectation, E of x. And I'm going to break this up using conditional expectation.
So I'm going to break it up into two terms. I look at the conditional expectation of x given that x is at least some value C times the probability that x is at least C. And then I'm going to add the other contribution, which is the conditional expectation of x if that event does not happen, if x is strictly less than C, times the probability that x is less than C. So this should look familiar. This is basically a random variable version of something we covered way back when, which is we talked about the law of total probability. We had things, the probability of some event B. And we talked about it as the probability that B happens conditioned on event A happening times the probability that event A happens plus the probability that B happens conditioned on A not happening times the probability A does not happen. So when we talked about conditional probability, this was one of our first applications, once we had Bayes' rule, was we used it to reason using the law of total probability. And this is just the same thing, but expectations of random variables. Sometimes, you'll hear this referred to as the law of total expectation. But it's just breaking up my space into two different things—either this event A happens, that x is at least C, or it does not happen. And then I average the conditional expectation in those two different possibilities. And so now, what I claim is that I can look at each of these pieces. I claim that the first piece right here is at least C. And then I'm going to pick up this probability of x at least C. And then I claim that the second piece right here is non-negative. So that I'm just going to drop. And I'll get a lower bound. So I've really just used the fact that the expectation of x, given that x is at least C, had better be a value at least C because x always takes on a value that's at least C. And then I'm still going to pick up the probability that that event happens. And for this term, I'm just going to drop it, because this term is non-negative. And so now, what I can do is I can just rearrange to finish the proof. That's it. So that's our first tail bound. Our tail bounds will get a bit more sophisticated from this. But this already gives us some rudimentary understanding of the probability that x is very, very large. So now, let me ask you the question that I promised I was going to ask you. Where in this proof did I use the fact that x is non-negative? Yeah?
When you were counting x [INAUDIBLE] x given, x less than c, [INAUDIBLE].
That's right. That's exactly right, because if x were not a non-negative random variable, I couldn't say that this term is non-negative. This term is definitely non-negative. But otherwise, if x took on negative values, this could be negative. And dropping it, I wouldn't get an inequality like this. Perfect. So we definitely have to use this. And that's crucial for Markov's bound, at least the intuition behind it. I mean, this is the algebraic proof. But the intuition is just that if x had a very large probability of being at least C, then its expectation could not be what I promised it was, because the expectation would actually be too large. Any questions? Make sense? All right. So let me restate this in another form. I'll state it as a corollary. This is just a restatement of Markov's bound. But sometimes, you'll find it convenient to invoke it in one form versus the other. So I claim, under the same conditions, if x is non-negative, then the probability that x is at least C times its expectation of x is at most 1 over C. So let me make sure we're all on the same page. So why is this a corollary? How do I get from here, the thing I proved, to here? In fact, let me make it a bit easier. Let me just call this a different constant, C-prime. Why is this a corollary? They seem related. Yeah?
You just substitute c prime [INAUDIBLE] c times e. [INAUDIBLE]
Yeah, so let me do it the other way. Let me substitute for C is equal to C-prime times Ex. Then I get exactly this bound right here. And then on the right-hand side, I cancel out the E of x. And I get 1 over C-prime. So this is very intuitive because, if I have a non-negative random variable, the probability that it's twice as large as its expectation is at most 0.5. Because otherwise, if that probability were larger than 0.5, the expectation would be wrong. So any questions about this? All right. So just to illustrate my point that, in tail bounds, we're going to be asking for tighter and tighter bounds that use more and more information about our random variable, let me do a running example, which we'll use as a way to check how much progress we're making. So let's do the following running example. And we'll come back to it with our next tail bound. So in the US, the average male height is about 69 inches. So we can use this fact to reason about the probability that someone is super duper tall, because x being the height of a random male in the US is a random variable. So we know its expectation. And we can use Markov's bound and just see what Markov's bound tells us. It tells us the probability that x, which, remember, is our random variable—this would be the height of a randomly chosen US male. The probability that it's at least 2 times its expectation, which is equal to 138 inches, or 11 foot 6 inches, that probability is at most 0.5. So we've proven this amazing fact. You're walking down the street in Boston. The probability you see someone who's above 11 foot 6 is at most 0.5. So pretty good or maybe not. So see, the problem is that Markov's bound—you can actually check—really is tight. It's just that real random variables, a lot of times, there's more information we know about it—things like the variation of the random variable. The more information you tell me about the random variable, the tighter my tail bound will be. And this Markov is just the get me over first warm-up for a tail bound. So we'll come back to this example. I want to make sure we still have the right intuition for this proof. So let me ask you a diagnostic question, just to make sure we're on the same page. I think probably you can guess the answer to this. But what I really care about is to find an example. So does Markov's bound hold without non-negativity? So in the statement of the theorem, I definitely assumed that the random variable was non-negative. In the proof I gave you, I definitely used the fact that x was non-negative. We talked about where we used that. But could I hope for some bound that looks like this, even when x is not non-negative? Maybe there's some other proof out there that doesn't use non-negativity that still bounds the probability that x is twice its expectation by 0.5 or something like this. So I claim that this is spectacularly false, but this is good intuition. So how would I come up with some random variable that has negative values and completely breaks any kind of statement like this, that the expectation gives you a handle on the tails? Anyone have any intuition? Yeah?
Perfect. I love it. So this is definitely not true. It's spectacularly false. So let's just consider some x where the right-hand side doesn't make any sense because the expectation is 0. So what if x is 1 with probability 0.5 and it's minus 1 otherwise? The trouble is that the expectation of x is equal to 0. But the probability that, say, x is at least 3 times its expectation, which is still 0, is definitely not less than 1/3. So non-negativity really is essential. And sometimes, these examples are very useful for both building intuition and conveying a proof to your reader. So these kinds of things, when you start thinking about your term paper, even if I didn't literally need to show this to you, this is the good kind of thing to keep in mind as a pedagogical device. All right, so let's prove our next tail bound. This one will be fairly simple as well, but it's much more powerful. And we're going to get some awesome applications of it. And this is called Chebyshev's bound. Actually, I'm not even sure about the history because I think Chebyshev's bound was proved before Markov's bound, even though it's going to use the proof of Markov's bound. So I don't know. Maybe Markov just looked at his proof and called the thing inside it his own bound. So in any case, now, we're going to start off with any random variable x. So this is already very different than Markov's bound because I'm not going to assume non-negativity. I don't even need it for this proof. So for any random variable x, what I claim is that the probability that the absolute value of x minus the expectation of x is larger than C—so it deviates not by a multiplicative factor of C, but by some additive factor of C from its expectation—is bounded by the variance of x all over C squared. So this will be my standard form of Chebyshev's bound. And the same way for Markov's bound—I stated it in one form, and then I stated a corollary—I'll do the same after we prove this bound. But this is what I promised because now we're going to use extra information. See, Markov's bound did not have the variance showing up. So you have to actually be able to compute the variance in order to appeal to the Chebyshev bound. But as we'll see, it's going to give us much tighter bounds and some really cool qualitative corollaries. So let's prove Chebyshev's bound. And then I'll state the other corollary. The proof will also be short and sweet. But it's going to have a really cool trick to it, which is a hint about the tricks to come later when we do much fancier tail bounds. So the first thing I'm going to do—I can rewrite the quantity I care about, the probability that the absolute value of x minus E of x is at least C, I claim is equal to the probability that x minus E of X quantity squared is at least C squared. So this is trick number 1 for Chebyshev's bound. It's not a hard trick to explain. But this is a trick. Why are these two probabilities equal? Why am I allowed to say that these two probabilities are equal? It's because they're the same event. So at the end of the day, what's happening in here is I have an event. Once you fix the random variable, I know its expectation, and you fix C, I have this event, whether or not x is far from its expectation. And I claim that these two probabilities—what's going on in here are two different events. But these events coincide. The only way that one event triggers is if the other one does too, just because we're taking the absolute value. Make sense? So that's trick number one for Chebyshev. And now, here's the really cool trick. What we're going to do is we're going to define a new random variable. So I'm going to call this random variable y. And it's going to be equal to just the thing that shows up in here on the right-hand side—x minus the expectation of x quantity squared. See, I told you, in Chebyshev, we're going to appeal to Markov's bound in order to prove it. But if you remember, for Markov's bound, we needed that the random variable we are looking at is non-negative. For Chebyshev, I'm not assuming that x is non-negative to begin with. So what I have to do is I have to manufacture my own non-negative random variable. And that's this new random variable y that I just constructed right here. This is definitely non-negative because I'm taking the square of a value. And now, I can appeal to Markov's bound. So using Markov on y, we know that this quantity right here, which I'll call star—star is equal to the probability that y is at least C squared. That's literally just using the definition of what my random variable y was. And now, appealing to Markov's bound, which is allowed because y is non-negative, this is at most the expectation of y all over C squared. Notice that my threshold here is C squared, not C, as in the original statement of Markov's bound. And now, what I can do is I can just remember what y is. So y is just the expectation—y itself is x minus the expectation of x quantity squared. I still have my C squared. And when I take the expectation of y, this is literally the definition I gave you earlier for the variance of x. So that's my proof. Any questions? Good? All right. So as before, I'm going to state another equivalent way to think about Chebyshev, which is sometimes a bit more convenient. So feel free to use whichever is easier in a proof. So again, for any random variable x, the probability that the absolute value of x minus its expectation is larger than C times sigma of x—I'll define what sigma of x is—is at most 1 over C squared. And sigma of x is called the standard deviation. And it's just defined to be the square root of the variance of x. So the same way I had this simple version of Markov that allowed me to remember it—the probability that a non-negative random variable is twice its expectation is at most 0.5—the probability that a random variable is 2 times away from its expectation in terms of its standard deviation is at most 0.25. All right, so let's go back to our running example. And let's see why Chebyshev is a lot more useful for us. So in particular, I need to tell you more information about this random variable, about the height of a random male, US male. And what I claim is that the standard deviation of male height is 2.7 inches. So now, we're in good shape because instead of using Markov, we can instead use Chebyshev. We have the probability that x, where x is our same random variable as before—the probability that you're 2 standard deviations above average, which is the same thing as 6 foot 2.4, is at most 0.25. So this is still not a great bound. But it's at least not a nonsensical bound, like our 11 foot 6 inches version before. And so you can do the same types of exercise. When you tell me not just the variance of x but more information about the moments of x, you would get tighter and tighter bounds until you would actually get something pretty reasonable. All right. So now, I want to tell you—now that we have Chebyshev, it may not be obvious, but it turns out to be very qualitatively powerful, not just numerically in these examples like height. So let me tell you about one really cool corollary. I'll state it as a theorem. And then we'll talk about some applications to gambling. So Chebyshev allows you to prove one of the most important results in tail bounds, which is called the weak law of large numbers. Now, the weak law of large numbers, we're going to strengthen it at various times and get better quantitative bounds. But already, we can see some of the power of tail bounds. So let me state what this weak law of large numbers is. And then we're going to prove it just using the tail bound technology we've developed so far. Now, for the weak law of large numbers, you have to be very careful with the quantifiers. So let me write it down. And then we'll talk about it. So first, I'm going to fix some positive epsilon. That'll be some measure of how close I want a random variable to be to its expectation. And I'm going to let x1 all the way up to xn be independent copies of some fixed random variable x. And moreover, let's assume that the expectation of x is equal to some value C. And I'm also going to assume—and this is critical for the weak law of large numbers—that its variance is not infinity—so just some basic bounds that my random variable is somewhat well-behaved. Well, what I'm going to do is I'm going to look at averages of these random variables as a way to try and approximate this expectation C. So I'm going to define a new random variable, Sn, that's just going to be the average. It'll be 1 over n sum from i equals 1 to n of xi. So just to make sure that we're on the same page, let's keep some mental model of this in mind. So one of the most important applications of the weak law of large numbers is to something like polling. So maybe you have some random variable, which is the probability that a random person selected from the electorate votes for one candidate, candidate A over candidate B. Now, you want to know what's the expectation of x because you want to know who's going to win the election. So you want to do this forecasting before election day. The natural thing you could try is you can try and get independent samples from x just by calling random people and asking them who they're going to vote for. Now, there are a lot of issues with that. That won't really give you independent random variables. But if we pretend for the moment that it did, each of these xi's is a realization of these random variables. What would my polling scheme do? I would just choose some large denominator n for the number of people I'm going to poll. I'm going to average up all of their votes, which way they're voting. Are they voting for candidate A or candidate B? And what I'm hoping is that the empirical average of their votes of these random variables converges very well to my true expectation so that I can forecast who's going to win the election. And so that's exactly what the weak law of large numbers tells us. You just have to be careful with all the quantifiers. Then what I claim is that the probability that Sn is epsilon away from the true value C, that this quantity, as you take the limit, as the number of people you're sampling in your poll goes to infinity, is going to go to 0. So there are a ton of quantifiers here. So let's say that I fix epsilon at the very outset. I want to figure out the probability people are voting for candidate A within some additive tolerance, 0.01. And so once I've fixed my epsilon, this is my success criteria, is that my empirical average of the people I poll—that empirical average should be within an additive 0.01 of the truth. And the claim is whatever you fix for epsilon, there's an n that's large enough so that the probability that you're far away by more than this 0.01 is going to go to 0. So the weak law of large numbers is deliberately non-quantitative. And we will get quantitative versions out of it, even just from the proof and from strengthening of our tail bounds. But it just tells you some basic conditions that, if you're given enough samples, you really can approximate the expectation to any desired accuracy. And in the proof, we'll see how large little n needs to be. So this is quite a mouthful of a statement. Are there any questions about the weak law of large numbers? Give me a thumbs up if this makes sense, at least as a statement. OK, good. All right. So the order of quantifiers is super important for this. Now, let's prove the weak law of large numbers. The good thing is that the proof will be pretty straightforward now that we have Chebyshev's bound. So first, I claim that the expectation of Sn—remember, that's a random variable itself because each of the xi's is a random variable. And I could first care about—is its expectation correct? So now, I can use linearity of expectation to write it out as the sum of the expectations of each of the individual xi's that form it. Now, because each of these xis are assumed to be independent copies of this fixed random variable x, whose expectation is C, I know that each of their expectations is C. So that means, when I average their expectations, I get the same thing back again. I get C. So this is just a basic sanity check. If I'm trying to approximate the expectation of my random variable x with another random variable Sn, I better have that the expectation of Sn is equal to x. Otherwise, I'm going to have trouble. So this makes sense. This just means that I have an unbiased estimator of the thing that I really care about. Now, the crucial thing is computing the variance. We're not going to be able to get by by using Markov's bound. We're really going to have to use Chebyshev. And that's where independence is going to save us. So remember, for Chebyshev's bound, I need to know what the variance of my random variable is in order to quantify how close a random variable will be to its expectation, because that's the thing that shows up in my statement of Chebyshev. The main action for the weak law of large numbers is just computing what this variance of Sn is. So I can do the same thing as before. I can replace Sn with what it is defined as, in terms of the xi's. And now, what happens when I scale a random variable by some scalar C—in this case 1 over n? Well, the variance is going to scale by a C squared, because I'm taking the expectation of some quantity squared in there. So this is the same thing as 1 over n squared times the variance of the sum of the xi's from i equals 1 to n. And now, the main trick is that I claim that this is now equal to—I'll carry through my 1 over n squared. I claim that this is equal to n times the variance of each of these random variables x. So this is the key step in the weak law of large numbers. This is the part that I want to dwell on. So why is this step OK? So how did I go from here to here? We have to remember way back when with what I told you when we did the probability unit. Yes?