Transcription
Welcome back. Okay. In the last uh, kind of set of lectures, we've been proving some pretty kind of heavy results and properties of, you know, random variables and functions of random variables like expectation, variance, things like that. And today, I just wanted to show kind of a fun, uh, interesting property called the tail sum formula. So this is a lot less heavy; it's pretty easy to derive, and it ends up being uh, kind of a useful formula and a little bit surprising. So here we go.
Um, so this is talking about the expectation of a random variable X, and I think it's worth uh, stating at the very beginning that we are assuming that X uh, takes on non-negative values. So we're going to say that X is non-negative.
Um, so for example, X could be um, I'm going to do this for a discrete random variable. X can take on values uh, um, like 0, 1, 2, dot dot dot, and dot dot dot, but not negative numbers like -1, -2. So, for example, the number of heads if I flip a coin 100 times, that would be a non-negative uh, distributed variable. So if X is, you know, binomial, that would be a case. Plus, on most of the examples we've seen, um, X takes on non-negative values. So this is pretty useful.
And so the tail sum formula says that the expectation value of X, the expected value of X, is equal to the sum of a, a, a, a cumulative sum of cumulative distribution probabilities. So I'll write it down, and then we'll talk about what it means. So it's the sum of the probabilities that X is greater than or equal to some value K, um, K is one of these numbers, and it's the sum for from K = 1 to the the largest value in this set, which is n. So let me just, you know, maybe there's not a dot dot dot; maybe this is um, a binomial distribution for the number of heads that you expect to get if you flip 100 coins. So X can't be bigger than 100, so this would be um, take values from 0 to 100. So there's like an upper limit to how to the values that this random variable X can take. So we sum over all of those possibilities; we sum this uh, this formula here, and specifically this is kind of uh, one minus the cumulative distribution function uh, evaluated at a value K.
Now, why is this true? This is not obvious at all that this should be true. The expectation value is usually written totally differently. So what I'm going to do is I'm going to dot dot dot dot, and I'm going to actually just write out this expectation the old old-fashioned way, like the way that we're used to writing it, and then show that you can get an expression that's equivalent to this new way of calculating the expectation value. Okay.
Um, so the idea is the expected value is typically written as the sum uh, from k equals um, let's say 1 to n or, let's say 0 to n in this case because there's it starts at zero; it doesn't really matter um, of K times the probability that my random variable x equals K. This is how the expected value of x is defined typically for a discrete random variable. X is this sum over all of the possible states X can take times that state times the probability of X equaling that state. And what we can do essentially is we can write this out um, in some shorthand. So we're going to say that this equals the sum at k equals 0; this term is just zero cuz k equals 0, so 0 * anything is 0. So we're really going to start at k = 1, and we get 1 times the probability that x = 1. I'm going to call that P sub 1, plus 2 * the probability that x = 2. I'm going to call that P sub 2, plus 3 * the probability uh, x = 3, plus dot dot dot, plus um, n-1 * the probability x = n-1, plus n * the probability that x equals n. This is just um, kind of brute force expanding out the traditional definition of expected value. Okay.
Now, the tail sum formula—this is where it gets really cool. There's this kind of geometric picture that we're going to introduce here where now what we're going to do is we're going to say, well, this equals P1 + P2 + P3 + dot dot dot + Pn-1 + Pn. So I've only counted this each term one time, and that's all of the P1s; there's only one of them, but there's two P2s, so plus P2 + P3 + dot dot dot + Pn-1 + Pn. Good. So now I have my two P2s, but I have three P3s, three P3s, so plus P3 + dot dot dot + uh, Pn-1 + Pn, and then this is kind of triangular dot dot dot + Pn-1 + Pn + Pn. So in this way, because there's it's 1 P1, 2 P2s, 3 P3s, dot dot dot, n-1 Pn-1's and n Pns, you can write down this kind of triangular sum where you actually explicitly count um, all of the terms in this. So you're breaking this up into single terms, and now this is where it's cool. Pn is the probability that X is greater than or equal to n, and Pn-1 + Pn is the probability that X is greater than or equal to n-1, and etc., etc. P, P2 + P3 + dot dot dot is the probability of X being greater than or equal to 2. So I'm going to write this out.
Um, so this is essentially this term is um, probability X greater than or equal to n; this term is probability of X greater than or equal to n-1; etc., etc.; probability um, dot dot dot; this one is probability of X being greater than or equal to 3; it's P3 + P4 + etc., etc.; uh, probability of X greater than or equal to 2, and probability of X greater than or equal to 1. And so this traditional way of computing the expected value is this this triangular sum of probabilities. Each row is the probability of X being greater than or equal to that the index of that row. And so if we take all of this together, the sum, it's this plus this plus this plus this dot dot dot plus this plus this, this is exactly equal to this sum here. It's the sum of all of these probabilities of X being greater than or equal to some K over all of the Ks, all the non-negative or positive K, and these are kind of the opposite of the cumulative distribution function. Um, probability of X, you know, being greater than or equal to K is essentially 1 minus the probability of X being less than K, where this is the cumulative distribution function. This is the cumulative uh, distribution or density function of that random variable X. So these are are useful quantities, and it turns out that the expected value is the sum of all of these kind of reverse cumulative density functions. That's really interesting. Um, it has this kind of cool geometric interpretation. We've seen sums like this when we looked at things like um, I want to say the, you know, pan and exponential, and you know, some of the distributions that we've looked at have this kind of interesting um, almost like geometric pattern. Um, but here it allows us to write down this kind of new way of computing or representing the expectation value. This is the traditional way, but if you do this kind of cool math, you can write it in terms of these cumulative density functions. Okay.
Um, that's it. That's all I wanted to show you today is just this kind of cool, useful formula for the expected value called the tail sum formula. Okay. Thank you.