2 Linearity of Expectation The search for truth is more precious than its possession -Albert Einstein 2.1 BASICS Let X1,....Xn be random variables,X =cX+..+cnXn.Linearity of expectation states that E[X]=CEX+...+cnE[Xn]. The power of this principle comes from there being no restrictions on the dependence or independence of the Xi.In many instances EX]can easily be calculated by a judicious decomposition into simple (often indicator)random variables X. Let o be a random permutation on {1,....n},uniformly chosen.Let X(o)be the number of fixed points of To find E we decompose where X is the indicator random variable of the event()=i.Then EX=Pra(@=司= The Probabilistic method.Third edition By Noga Alon and Joel Spencer Copyright 2008 John Wiley Sons.Inc. 15 2 Linearity of Expectation The search for truth is more precious than its possession. - Albert Einstein 2.1 BASICS Let Xi,..., Xn be random variables, X = c\Xi + • • • + cnXn. Linearity of expectation states that E[X]=c1E[X1} + ---+cnE[Xn] . The power of this principie comes from there being no restrictions on the dependence or independence of the Xi. In many instances E [X] can easily be calculated by a judicious decomposition into simple (often indicator) random variables Xi. Let o be a random permutation on {1,... , n}, uniformly chosen. Let X(a) be the number of fixed points of a. To find E [X] we decompose X = Xy + • • • + Xn where X¿ is the indicator random variable of the event a(i) = i. Then E [Xi] = Pr [a(i) =i] = - The Probabilistic Method, Third Edition By Noga Alón and Joel Spencer Copyright © 2008 John Wiley & Sons, Inc. 15