22 LINEARITY OF EXPECTATION Say.E has type (a1....,a)if En vil =a Isisk.For these E. E[Xg]=h(E)Pr[EC S]=h(E)p"...p Combining terms by type E=∑p…p∑E a1++4=k E of type (a) When a =...=ag 1.all h(E)=I by assumption,so h(E)=n. E of type (1. For any other type,there are fewer than n terms,each1,so ∑.h(E)≤ E of type (a1…ag) Thus E[X]=nf(p1.....P). wherefE P.as defined by Lemma 2.2.4. Now select p1,.,Pk∈[0，l]with If(p,,Pkl≥ck-Then E[X]≥IEXI≥cn Some particular value ofmu eed or equal its expectation.Hence there is a particular set SC V with=h(S)c Theon m 2.2.3 has an interesting application to Ramsey Theory.It is known (see Erdos(1965b))that given any colo of th of an n-se there exist 01 ((In n so that all ),a least+of whose k-sets are the same color.This is somewhat surprising since it is known that there are colorings in which the largest monochromatic set has size at most the k-2-fold logarithm of n. 2.3 TWO QUICKIES Linearity of Expectation sometimes gives very quick results
22 LINEARITY OF EXPECTATION Say, E has type (a1, … , ak) if |E ∩ Vi| = ai, 1 ≤ i ≤ k. For these E, E[XE] = h(E)Pr[E ⊆ S] = h(E)p a1 1 ··· p ak k . Combining terms by type E[X] = ∑ a1+···+ak=k p a1 1 ··· p ak k ∑ E of type (a1,··· ,ak ) h(E) . When a1 =···= ak = 1, all h(E) = 1 by assumption, so ∑ E of type (1,…,1) h(E) = nk . For any other type, there are fewer than nk terms, each ±1, so | | | | | | ∑ E of type (a1,…,ak) h(E) | | | | | | ≤ nk . Thus E[X] = nk f( p1, … , pk) , where f ∈ Pk, as defined by Lemma 2.2.4. Now select p1, … , pk ∈ [0, 1] with |f( p1, … , pk)| ≥ ck. Then E[|X|] ≥ |E[X]| ≥ cknk . Some particular value of |X| must exceed or equal its expectation. Hence there is a particular set S ⊆ V with |X| = |h(S)| ≥ cknk. ◾ Theorem 2.2.3 has an interesting application to Ramsey Theory. It is known (see Erdos (1965b)) that, given any coloring with two colors of the ˝ k-sets of an n-set, there exist k disjoint m-sets, m = Θ((ln n) 1∕(k−1) ), so that all crossing k-sets are the same color. From Theorem 2.2.3, there then exists a set of size Θ((ln n) 1∕(k−1) ), at least 1 2 + 𝜖k of whose k-sets are the same color. This is somewhat surprising since it is known that there are colorings in which the largest monochromatic set has size at most the k − 2-fold logarithm of n. 2.3 TWO QUICKIES Linearity of Expectation sometimes gives very quick results
BALANCING VECTORS 23 Theorem 2.3.1 There is a two-coloring of K with at most (）2-) monochromatic K Proof [Outline] Take a random coloring.LetX be the number of monochromatic K and find E[X].For some coloring,the value of X is at most this expectation. In Chapter 16.it is shown how such a coloring can be found deterministically and efficiently. Theorem 2.3.2 There is a two-coloring of Kwith at most ()(6)2 monochromatic K。b Proof rOutlinel.Take a random coloring.Let X be the number of monochromatic K and find E[X].For some coloring,the value of X is at most this expectation. 2.4 BALANCING VECTORS The next result has an elegant non-probabilistic proof,which we defer to the end of this chapter.Here,is the usual Euclidean norm. Theorem 2.4.1 Let v.....ER",all =1.Then there exist e.....=tlso that le1e1+…+Enval≤Vn, and also there exist e.....=l so that le1“+…+enl2Vn Proof.Let e.....be selected uniformly and independently from(-1.+1).Set X=le11+…+enyn2 Then X=∑∑e4%
BALANCING VECTORS 23 Theorem 2.3.1 There is a two-coloring of Kn with at most (n a ) 2 1− ( a 2 ) monochromatic Ka. Proof [Outline]. Take a random coloring . Let X be the number of monochromatic Ka and find E[X]. For some coloring, the value of X is at most this expectation. ◾ In Chapter 16, it is shown how such a coloring can be found deterministically and efficiently. Theorem 2.3.2 There is a two-coloring of Km,n with at most (m a ) (n b ) 21−ab monochromatic Ka,b. Proof [Outline]. Take a random coloring. Let X be the number of monochromatic Ka,b and find E[X]. For some coloring, the value of X is at most this expectation. ◾ 2.4 BALANCING VECTORS The next result has an elegant non-probabilistic proof, which we defer to the end of this chapter. Here, |𝑣| is the usual Euclidean norm. Theorem 2.4.1 Let 𝑣1, … , 𝑣n ∈ Rn, all |𝑣i | = 1. Then there exist 𝜖1, … , 𝜖n = ±1 so that |𝜖1𝑣1 +···+ 𝜖n𝑣n| ≤ √n , and also there exist 𝜖1, … , 𝜖n = ±1 so that |𝜖1𝑣1 +···+ 𝜖n𝑣n| ≥ √n . Proof. Let 𝜖1, … , 𝜖n be selected uniformly and independently from { − 1, +1}. Set X = |𝜖1𝑣1 +···+ 𝜖n𝑣n| 2 . Then X = ∑n i=1 ∑n j=1 𝜖i𝜖j 𝑣i ⋅ 𝑣j
24 LINEARITY OF EXPECTATION Thus When i+j.E[e;e;Ele;lE[e;]=0.When i=j.e2=1 so E[e2]=1.Thus W=24= Hence there exist specifice,,n=±1with≥n and withX≤n.Taking square roots gives the theorem. The next result includes part of Theorem 2.4.1 as a linear translation of the p= …=pn=l/2case. Theorem2.4.2Lett,,en∈Rm,all≤l.Letp,…,Pn∈[0,1刂be arbitrary. and set w=P1+…+Pn'Then there exist e1,en∈(0，1)so that,setting D=610+…+en5n le-s Proof.Pick e;independently with Prle;=1]=pi.Prle;=0]=1-pi. The random choice of e gives a random v and a random variable X=w-2 We expand X=2-加-以-6-9 so that Fori≠ji E[(P:-e)(Pj-e)]=ELP:6lE(p-]=0. Fori=j. Ep,-eP門=(n-lP+1-Pp=pI-P)≤
24 LINEARITY OF EXPECTATION Thus E[X] = ∑n i=1 ∑n j=1 𝑣i ⋅ 𝑣jE[𝜖i 𝜖j] . When i ≠ j, E[𝜖i 𝜖j ] = E[𝜖i ]E[𝜖j ] = 0. When i = j, 𝜖2 i = 1 so E[𝜖2 i ] = 1. Thus E[X] = ∑n i=1 𝑣i ⋅ 𝑣i = n . Hence there exist specific 𝜖1, … , 𝜖n = ±1 with X ≥ n and with X ≤ n. Taking square roots gives the theorem. ◾ The next result includes part of Theorem 2.4.1 as a linear translation of the p1 = ···= pn = 1∕2 case. Theorem 2.4.2 Let 𝑣1, … , 𝑣n ∈ Rn, all |𝑣i | ≤ 1. Let p1, … , pn ∈ [0, 1] be arbitrary, and set 𝑤 = p1𝑣1 +···+ pn𝑣n. Then there exist 𝜖1, … , 𝜖n ∈ {0, 1} so that, setting 𝑣 = 𝜖1𝑣1 +···+ 𝜖n𝑣n, |𝑤 − 𝑣| ≤ √n 2 . Proof. Pick 𝜖i independently with Pr[𝜖i = 1] = pi , Pr[𝜖i = 0] = 1 − pi . The random choice of 𝜖i gives a random 𝑣 and a random variable X = |𝑤 − 𝑣| 2 . We expand X = | | | | | ∑n i=1 ( pi − 𝜖i )𝑣i | | | | | 2 = ∑n i=1 ∑n j=1 𝑣i ⋅ 𝑣j ( pi − 𝜖i )( pj − 𝜖j) so that E[X] = ∑n i=1 ∑n j=1 𝑣i ⋅ 𝑣jE[( pi − 𝜖i )( pj − 𝜖j)] . For i ≠ j, E[( pi − 𝜖i)( pj − 𝜖j )] = E[pi − 𝜖i]E[pj − 𝜖j ] = 0 . For i = j, E[( pi − 𝜖i) 2] = pi( pi − 1) 2 + (1 − pi)p2 i = pi(1 − pi ) ≤ 1 4
UNBALANCING LIGHTS (E[(p-e)2]=Var[e;).the variance to be discussed in Chapter 4.)Thus -2na-2hrs号 and the proof concludes as in that of Theorem 2.4.1. 2.5 UNBALANCING LIGHTS Theorem2.5.Let an=±Ifor1≤i,j≤n.Then there existxy=±l,1≤iJ≤n so that This result has an amus ng interpretation.Let annn array of lights be given each n row ere is a s andeachcolto column )all of the lights in that line will be"switched"on to off or off to on.Then eame2荒平房he namber of Proof [Theorem 2.5.1].Forget the x's.Let y...=l be selected indepen dently and uniformly and set R=∑g,R=∑RI Fix i.Regardless of ay ay;is1 with probability 1/2,and their values (over j) are independent;that is,whatever the ith row is initially after random switching,it becomes a uniformly distributed row,with all 2"possibilities equally likely.Thus R has distribution S.-the distribution of the sum of n independent uniform(-1.1) random variables-and so These asymptotics may be found by estimating S by VnN,where N is standard normal and using elementary calculus.Alternatively,a closed form E[lS,l]=n21-m n-1 (-1)/2
UNBALANCING LIGHTS 25 (E[( pi − 𝜖i ) 2] = Var[𝜖i ], the variance to be discussed in Chapter 4.) Thus E[X] = ∑n i=1 pi(1 − pi )|𝑣i | 2 ≤ 1 4 ∑n i=1 |𝑣i| 2 ≤ n 4 and the proof concludes as in that of Theorem 2.4.1. ◾ 2.5 UNBALANCING LIGHTS Theorem 2.5.1 Let aij = ±1 for 1 ≤ i, j ≤ n. Then there exist xi , yj = ±1, 1 ≤ i, j ≤ n so that ∑n i=1 ∑n j=1 aijxi yj ≥ (√2 𝜋 + o(1) ) n3∕2 . This result has an amusing interpretation. Let an n × n array of lights be given, each either on (aij = +1) or off (aij = −1). Suppose for each row and each column there is a switch so that if the switch is pulled (xi = −1 for row i and yj = −1 for column j) all of the lights in that line will be “switched” on to off or off to on. Then for any initial configuration it is possible to perform switchings so that the number of lights on minus the number of lights off is at least ( √2∕𝜋 + o(1))n3∕2. Proof [Theorem 2.5.1]. Forget the x’s. Let y1, … , yn = ±1 be selected independently and uniformly and set Ri = ∑n j=1 aijyj , R = ∑n i=1 |Ri | . Fix i. Regardless of aij, aijyj is ±1 with probability 1∕2, and their values (over j) are independent; that is, whatever the ith row is initially after random switching, it becomes a uniformly distributed row, with all 2n possibilities equally likely. Thus Ri has distribution Sn – the distribution of the sum of n independent uniform {− 1, 1} random variables – and so E[|Ri |] = E[|Sn|] = (√2 𝜋 + o(1) ) √n . These asymptotics may be found by estimating Sn by √nN, where N is standard normal and using elementary calculus. Alternatively, a closed form E[|Sn|] = n21−n ( n − 1 ⌊(n − 1)∕2⌋ )
26 LINEARITY OF EXPECTATION may be derived combinatorially (a problem in the 1974 Putnam competition!)and the asymptotics follows from Stirling's formula. Now apply the Linearity of Expectation to R: E网-2RI=(V+aa)n There exist y..=with R at least this value.Finally,pick with the same sign as R;so that Another result on unbalancing lights appears in"The Probabilistic Lens:Unbal- ancing Lights"(following Chapter 13).The existence of Hadamard matrices and the discus ion in Section 9.1 show that the estimate in the last theorem cannot be improved to anything bigger than 2.6 WITHOUT COIN FLIPS A non-probabilistic proof of Theorem 2.2.1 may be given by placing each vertex in eitherTor B sequentially.At each stage.placex in either Tor B so tha t at least half of the ed x to previous vertices are crossing.With this effective algorithm. at least half the edges will be crossing. There is also a simple sequential algorithm for choosing signs in Theorem 2.4.I When the sign for v;is to be chosen,a partial sum w=e+...+has been calculated.Now if it is desired that the sum be small,select e=l so that ev makes an obtuse (or right)angle with w.If the sum need be big,make the angle acute or right.In the extreme case when all angles are right angles,Pythago ras and induction give that the final has norm n:otherwise.it is either less than Vnor greater than Vn,as desired For Theorem 2.4.2.a greedy algorithm produces the desired .Given .. R",p.....E[0.1].suppose .....E(0.1)have already been chosen.Set w=(p:-e;)v;,the partial sum.Select e,so that =+n-G6-2n-6 has minimal norm.A randome,E(0,1)chosen with Prle,=1]=p,gives E0,=lw-2+20-1·e,p-e]+,2Ep,-e2 =w-2+P.(1-p,lu,2
26 LINEARITY OF EXPECTATION may be derived combinatorially (a problem in the 1974 Putnam competition!) and the asymptotics follows from Stirling’s formula. Now apply the Linearity of Expectation to R: E[R] = ∑n i=1 E[|Ri |] = (√2 𝜋 + o(1) ) n3∕2 . There exist y1, … , yn = ±1 with R at least this value. Finally, pick xi with the same sign as Ri so that ∑n i=1 xi ∑n j=1 aijyj = ∑n i=1 xi Ri = ∑n i=1 |Ri | = R ≥ (√2 𝜋 + o(1) ) n3∕2 . ◾ Another result on unbalancing lights appears in “The Probabilistic Lens: Unbalancing Lights” (following Chapter 13). The existence of Hadamard matrices and the discussion in Section 9.1 show that the estimate in the last theorem cannot be improved to anything bigger than n3∕2. 2.6 WITHOUT COIN FLIPS A non-probabilistic proof of Theorem 2.2.1 may be given by placing each vertex in either T or B sequentially. At each stage, place x in either T or B so that at least half of the edges from x to previous vertices are crossing. With this effective algorithm, at least half the edges will be crossing. There is also a simple sequential algorithm for choosing signs in Theorem 2.4.1. When the sign for 𝑣i is to be chosen, a partial sum 𝑤 = 𝜖1𝑣1 +···+ 𝜖i−1𝑣i−1 has been calculated. Now if it is desired that the sum be small, select 𝜖i = ±1 so that 𝜖i𝑣i makes an obtuse (or right) angle with 𝑤. If the sum need be big, make the angle acute or right. In the extreme case when all angles are right angles, Pythagoras and induction give that the final 𝑤 has norm √n; otherwise, it is either less than √ √ n or greater than n, as desired. For Theorem 2.4.2, a greedy algorithm produces the desired 𝜖i . Given 𝑣1, … , 𝑣n ∈ Rn, p1, … , pn ∈ [0, 1], suppose 𝜖1, … , 𝜖s−1 ∈ {0, 1} have already been chosen. Set 𝑤s−1 = ∑s−1 i=1 ( pi − 𝜖i )𝑣i, the partial sum. Select 𝜖s so that 𝑤s = 𝑤s−1 + ( ps − 𝜖s)𝑣s = ∑s i=1 ( pi − 𝜖i )𝑣i has minimal norm. A random 𝜖s ∈ {0, 1} chosen with Pr[𝜖s = 1] = ps gives E[|𝑤s| 2] = |𝑤s−1| 2 + 2𝑤s−1 ⋅ 𝑣sE[ps − 𝜖s] + |𝑣s| 2 E[ps − 𝜖s] 2 = |𝑤s−1| 2 + ps(1 − ps)|𝑣s| 2