Linearity of Expectations

Key Takeaways

in this video let us look at a basic yet important Concept in probability known as linearity of expectations and use it to deduce some interesting consequences in combinatorics via the probabilistic method linearity of expectations set that if you're given random variables X1 through XM and constants C1 through CM then when we took it when we take a linear combination of these random variables as such so C1 * X1 so imagine these are real valued random variables and these are real constants for instance then the sum of these uh C1 * X1 plus C2 * X2 and so on Plus CN * XM so this sum has expectation the following which can be computed by Distributing this expectation symbol across to the individual variables so this is a basic and important property and it's worth noting that a similar statement written for products is often not true so it is not usually the case that the expectation of a product of two random variables is the product of their expectations unless you're in some special circumstances such as when X and Y are independent or uncorrelated okay anyway let us focus on the linearity of expectations and see some ways to use this in combinatorial applications and the first example is the following question which will be able to give a very quick and clean answer the question is what is the average number of fixed points of a permutation of 1 through n chosen uniformly at random as a reminder if we have numbers 1 2 3 4 here n equals to 4 then a permutation can be thought as some way to map these numbers the sets back to themselves in one to one correspondence and a fixed point is some number that gets mapped back back to themselves so in this permutation there are exactly two fixed points okay great let's answer this question using linearity of expectations well one way to think about the problem is that well there are n factorial permutations and maybe we want to try to go about counting how many of them have zero fixed points how many of them have one fixed points how many have two fixed points but that method can get pretty cumbersome and pretty difficult quite quickly however if we look at this problem through the lens of linearity of expectations there turns out to be a very quick solution and the method is to let introduce some random variables let X I be a random variable that equals to one if I is a fixed Point meaning that in this permutation I gets mapped to itself and zero otherwise so X of I is the indicator random variable for the element I being a fixed point of this random permutation what's the expectation of XI well this is the probability that I is a fixed point well this being a uniform permutation chosen uniformly at random I is sent to each of the elements 1 through n with equal probabilities so in particular it is sent back to itself with probability 1 / n and then the number of fixed points equals to the sum of the X XIs so X1 plus X2 so on to xn and now we can take expectation of both sides and apply linearity of expectations and see that while each individual term is 1 / n and there are n such terms so the answer is one and that is the answer to this question so the average number of fixed points of a permutation chosen uniformly at random is exactly one and you see that there's a very quick calculation once you get a hang of the idea of of linearity of expectations let us look at a slightly more interesting example and for this example we'll consider the concept of a tournament okay so a tournament is a concept in graph Theory referring to the following there are nend vertices think of nend players in some tournament and between every pair of vertices we have some directed Edge pointing in one of these two directions so every pair of vertices there's some Edge pointing to one of the two directions okay so that's an example of a tournament I'll need to introduce another concept which is that of a Hamilton path so a Hamilton path is a directed path meaning we travel along the directions of these ver these edges according to their directions so directed path that passes through each vertex so every vertex of the graph exactly once no more no less so let's see if we can find any hilon paths in this in this examp example well I see one so if we start with the middle vertex and go along this one this Edge then this Edge and then this Edge okay so that's a hemoton path that goes through all four vertices each vertex passing through it exactly once and it always traverses along the direction of the edges okay let us prove the following theorem for every n and there exists a tournament on N vertices with at least n factorial * 2 to the minus n + one hoton paths okay so in other words for every n there is some way to orient the edges of the complete graph on N vertices so that it has lots and lots of Hamilton paths specifically at least this many okay so that's a theorem that we're aiming to prove we will not prove this theorem by explicitly constructing such a tournament instead we'll invoke the probabilistic method and show that a random tournament has in expectation this property so here's the proof let's consider a random tournament on N vertices chosen uniformly at random one way to do this is to take a complete graph on n verticy and for every Edge flip a Fair coin and use that coin to decide which way the edge orients of the two different directions now let's think about the number of Hamilton paths right so each path of the so each um okay so each of the N factorial permutations of vertices forms a directed path okay so first consider a permutation of vertices so for example 2 1 3 3 4 and think about what is the probability that the edges that go in the direction of these uh of this permutation that the edges are all oriented according to the permutation well we have to Flip n minus one coins and all of them have to come up in such a way so that the edges are pointing in the direction of this permutation in order of this permutation so the probability that this is a directed path for a for each of these permutations is precisely 2 to the minus parenthesis n minus one okay and now we invoke the linearity of expectations to claim that the expected number of Hamilton paths must then be well each of the N factorial permutations has probability of 2 Theus n minus one of being a directed path right so this is a calculation that is analogous to the calculation that we did in the earlier part of this video this is what happens in expectation on average and thus there must be some instance where we can beat this average or at least be at least as large as this average so thus there exists a tournament with at least this many Hamilton paths okay and that concludes the proof of this theorem that we laid out earlier so this is an example of applying linearity expectations as a step in the probabilistic method to prove this nice and simple result that there exist tournaments with lots of Hamilton paths