[MUSIC] Hello everybody, welcome to our video lecture on discrete mathematics. In the last few sessions we have learned a lot about the binomial coefficient, n choose k. And today I want to show you an application of what we have learned. So, the last lecture ended with the following formula for the sum of the following powers of an integer, m. So, remember m to the following k was defined to be m*(m-1)*(m-2) and you continue until you have collected exactly k factors. So, your last factor is m- k +1. It's a little bit tricky to remember the +1 here so I always have to think twice to really figure out where I have to stop. Okay, so the application involve a little bit of probability theory but really only vanilla probability theory. So even if you haven't had a course and probability theory, you probably can follow everything I say here. So consider the following scenario, I have the numbers 1 to n and I select a set of size k uniformly at random. So, for example, let's say k=3 and I select three numbers without replacement randomly. Suppose I select these three numbers, and then I let x be the smallest number I have chosen. So in this case, x = 3. And I want to know what is the expectation of this minimum, right? So again, the setting is we have n numbers, we select a subset k of them, take the minimum and want to determine the expectation of this minimum. So here's the formula for the expectation. It is the sum over all the possible values. So here, the possible values are from 1 to n, i*Pr[X = i]. So well, this looks simple. So we only have to find out what is the probability that X = i. Well, this here is, it's the number of sets A in n choose k such that the minimum of A is exactly i. The number of these sets divided by, well the number of all subsets of size k. So now we have to do a little bit of thinking. How many sets are there that have i as a minimum? So i is in there and then the rest of A is somewhere between here. So, well, to the right of i, we have to select again k- 1 elements and how many possibilities do we have to do so. Well, how many numbers are there bigger than i up to n? Well, this is n- i. So, it's n- i, choose k- 1 divided by n choose k. So this is a probability that the minimum was exactly i. Let's see whether we get anything helpful here. So this is n-i factorial divided by this, times n- i- k + 1 factorial. It looks a bit nasty, but let's see. And then I have n factorial here, k factorial here, and n- k factorial here. And then you see actually you can do some a bit of cancellation. This and this cancels out and a factor of k survives, so you get something like this. It's k times n- i factorial, then n- k factorial. And here we have n- i- k + 1 factorial and n factorial. So another point is we might be able to write this in a little bit nicer way. The problem that remains is in order to compute the expectation, you see we have this i in front of here. So what we should do, we should sum up over all i, i times this. Also here, and now I have this very uncomfortable expression. I have i on the one hand side and I have n- i factorial and so on and I have no clue how to deal with that. So with all that we have learned in the last lectures I tried to make sense of this expression for maybe half an hour or something, I couldn't go anywhere. So this is a dead end. Maybe we should back up a little bit and try a different route. So let's do that. Here is actually something very important I can teach you about expectation. It's the following, if you have a non-negative random variable that takes integer values, you can rewrite the expectation with this formula. And well let's prove that. The expectation is the sum over all i, i*Pr[X = i]. And now, I rewrite that, I rewrite i in this weird way. Actually we can start with a 1 here. I rewrite it as the sum from j = 1 to i of 1. Another trick is to just pull in these sums together. So if you look at it, we just sum over all integers j and i such that j is between 1 and i. So, I can as well say I let j run from 1 up to infinity or whatever, and then I sum over all i, and where do I have to start? Well, I have to start at j. And now it's very nice because you see this sum here, we can write as the probability that X is larger or equal than i, Than j, sorry. X is larger or equal than j, and we sum up for all j from 1. All right, so this proves this lemma. The benefit is that in this sum here, we don't have any factor j. We don't have any factor in front of the probability. So maybe it's a little bit easier now to sum up. So let's try it. Again, in our case, so now we have to calculate the probability that X is at least i. So what is this? It basically means all the numbers we select are from the set and so we just have to count how many possibilities do we have to select k elements from the set. I mean how large is the set? It's n- i + 1 choose k divided by n choose k, nice. Okay, so let's see whether we are luckier here. So this n- i + 1 factorial divided by k factorial times n-i-k+1 factorial. And the n choose k gives us this. It looks pretty similar to what we get before, maybe a little bit easier. So now what is this? This is the k factorial cancels and what you get is (n-i+1) factorial divided by n factorial. And here we have (n-k) factorial divided by (n-i+k+1) factorial. Okay, so what is this? Well, this is, you can rewrite it as this. It's n to the following k. That takes care of these two factors. And to take care of these two factors here, we get n- i + 1. To the following k. So this is the probability that x is at least i. Okay, let's get some more space, so we've seen this is the sum over all i from 1 to n. And now what do we have here? The denominator is n to the following k. And up here we have n- i + 1 to the following k. Good, okay, so, the denominator, we can just pull it in front of the sum. This is very nice, because it doesn't depend on i. And now, again, let's do a change of variable. Let's say j = n + 1- i, all right? So now let's see, i runs from 1 to n. So what does j do? Well, if i = 1, then j = n. And if i = n, then j =1. So j just runs from n down to 1, right? So we basically sum over the same range. But now it kind of looks nicer, because we simple have a j to the following k. And now we apply what we have learned, we have a formula for this, right? What is this, so the sum is, it's n + 1 to the following k + 1 divided by k + 1. And then, of course, we have to take this denominator here, all right? So what is this? This is 1/k + 1 and we have (n +1) n (n- 1), and we go all the way until we have k factors. So the last factor is n- k + 1. And down here, we start with n. We have n- 1, and we go all the way until we have k factors. And everything cancels, and our result is n + 1/ k + 1. So this is nice. We had a very simple sounding problem. Determine the expectation of this minimum, we dutifully calculated what it needed to calculate, namely the probability that x is at least i. We got some messy expressions in the end but by some magic in the end almost everything cancels out and we have a supernized expression for this expectation. It's just n+1 /k+1. All right, so at this point we could stop and go home. But one of the point I want to tell you here, in mathematics there are often two ways to do something. The first way is just to do the calculation. Don't think too much, just calculate, try to cancel, try to get nice expressions until at some point you find something and the other way is be lazy, try to avoid calculations and replace calculations by clever thinking. And that's what I want to do in the second half of today's session. I want to prove the lemma again, but now I want to give you a proof where we basically don't have to calculate anything, but we have to think a little bit more. Okay, are you ready? Let's go. Second proof. So what I do is I take a circle and on this circle I put the numbers 0 up to n. And now what we do is we select k points to be in our set A. So the red points are A and we let the X be the minimum of A, so X is this and then see, X is simply also the distance from 0 to X, if you go clockwise. Right, so you start at 0, you go to X to the number of, how should I say, edge segments or something, you pass. This is the variable that we are looking for, this is X, okay? So we have the circle, we select k numbers from 1 to n, we mark them red, and take the distance from 0 to the first one. So this is not very exciting so far. Now, we color the vertex number 0, we color it blue. And now observe, we just take the circle and we forget about where the 0 is. You can imagine we take the circle and we just rotate it in some random way so now we don't know where the 0 is. So the 0 could be anywhere. So we select our set of k red vertices and then we select where the 0 is. Okay, now the 0 is here, and now the variable we are looking for is just, again, the distance from the blue vertex to the red vertex. So let's now call this X prime, and you see that X prime behaves exactly as X, so we can just as well try to determine the expectation of X prime. And this is easier. Why is this easier? Well, instead of selecting k red vertices and then one additional blue vertex, we could do it the other way around. So what we are doing now, we select k + 1 red points out of n + 1. So we have n + 1 points, right? Why? Well, because it's the point 0, up to n, because there's n + 1 many. And then we select, from this set here, we select k + 1 points, and we color them red, okay? Now what you are doing, we just pick one of them and color it blue. So we change the color of one of them and make it blue and then this is what we are after for. This is our random variable X prime. Okay, this is still nothing new, but now comes the trick. We have these k + 1 red points. And we say that Y1 is just the distance from the first point. So let's say up here is 12 o'clock, right? So Y1 is this distance and this is Y2, this is Y3, and so on. So we have now k + 1 numbers. And to what do they sum up? Well, they sum up n + 1, right? And now if we make one vertex blue, Suppose we make this vertex blue. This here, it just means we select this to be X prime. So basically, what we do, we take these k + 1 points, we get these distances Y1 up to Yk + 1, and by selecting one of the red vertices and make it blue, we basically say. Well, our value X is just one of these numbers Y1 until Yk + 1 and we select it randomly. And therefore, we see we have k + 1 choices so therefore the expectation if we take a random one of them just must be the average, and the average is just n + 1 divided by k + 1. And you see, let's again prove, actually you might think it's not a completely formal proof, but trust me, if you invest some work, you can make everything very formal. Bu the nice thing is we didn't do any calculation. The only calculation we did was saying, hey look, these numbers Y add up to n+1. And if you select one of them at random, on expectation, it gives you n+1 over k+1. That's the only calculation we did. So the message to take home here is there might be several ways to solve a problem and there's basically the, how should I say? Well there's often a way that requires a lot of work, but not too much thinking. And often, and these are the beautiful moments in mathematics, there is a way that requires some clever thinking but almost no work. And this whenever possible is the way I think you should go. Thank you. [MUSIC]