the FKG inequality and facility location problem

 Spent one day working on Sviridenko's paper on one inequality and finally see why it is   
 true.  
 Let y1,y2,...y_m be the probabilities that each facility open, sum of the y_i's is 1. Now   
 the expected distance is  
 dist=  
 c1*y1 + c2*y2*(1-y1) + c3*y3*(1-y1)(1-y2) + ... + cm*ym*(1-y1)...(1-y_m-1) + c_m+1*(1-  
 y1)...(1-ym)   
 and we want to show  
 dist <= (c1*y1+c2*y2+...+cm*ym)(1-1/e) + c_m+1 * 1/e  
 We know that y1+...+ym=1  
 Sviridenko noticed that  
 dist <= c1*(1-e^-y1) + c2*(e^-y1 - e^-(y1+y2)) + c3*(e^(-y1-y2)-e^(-y1-y2-y3)) + ... + cm*  
 (e^(-y1-...-y_m-1) - e^(-y1-...-ym)) + c_m+1*(1/e)=rhs  
 This is because c1<=c2<=...<=cm<=c_m+1  
 and the fraction of dist is always leading the rhs.  
 y1 >= 1-e^-y1  
 y1+y2(1-y1) >= 1-e^(-y1-y2)  
 Now we want to show rhs <= (c1*y1+c2*y2+...+cm*ym)(1-1/e) + c_m+1 * 1/e  
 and this is the part that took me a full day.  
 We actually use a similar idea. Notice that the sum of fractions are the same on both sides,  
 1-e^-y1 + e^-y1 - e^(-y1-y2) + ... + e^(-y1-y2-...-y_m-1) - e^(-y1-y2-...-y_m) = 1-e^-1  
 and  
 (y1+y2+...+ym)(1-1/e)=1-1/e  
 So we only need to show that the fraction of lhs is always leading.  
 1-e^-y1 >= y1(1-1/e)  
 1-e^-y1-y2 >= (y1+y2)(1-1/e)  
 ...  
 1-e^-y1-y2-...-ym >= (y1+y2+...+ym)(1-1/e)  
 This can be proved by noticing the function f(x)=1-(e^-x)-x(1-1/e) evaluates to 0 at x=0 and   
 x=1, and in between it is always nonnegative. And y1, y1+y2, ... , y1+...+ym area all   
 between 0 and 1.  
 A slightly different proof due to Byrka uses FKG inequality  
 (u1*f1+u2*f2+...+um*fm)(u1*g1+u2*g2+...+um*gm) >= (u1+...+um)  
 (u1*f1*g1+u2*f2*g2+...+um*fm*gm)  
 assuming u1,u2,...,um >= 0 and f is increasing and g is decreasing.  
 Now we use   
 u1=y1  f1=c1  g1=1  
 u2=y2  f2=c2  g2=1-y1  
 u3=y3  f3=c3  g3=(1-y1)(1-y2)  
 The FKG inequality gives  
 (y1+...+ym)(y1*c1*1 + y2*c2*(1-y1) + ... + ym*cm*(1-y1)...(1-y_m-1))   
 <= (y1*c1+y2*c2+...+ym*cm)(y1*1+y2(1-y1)+...+ym(1-y1)(1-y2)...(1-y_m-1))  
 Notice this part (y1*1+y2(1-y1)+...+ym(1-y1)(1-y2)...(1-y_m-1)) = 1-(1-y1)...(1-ym) since   
 they are complementary events. lhs is one of y1,...,ym happen, rhs is one minus none happen.  
 Therefore  
 (y1*c1*1 + y2*c2*(1-y1) + ... + ym*cm*(1-y1)...(1-y_m-1))   
 <= (y1*c1+y2*c2+...+ym*cm)(1-(1-y1)(1-y2)...(1-ym)  
 Add (1-y1)...(1-ym)c_m+1 to both sides we have  
 expected dist <= (c1*y1+c2*y2+...+cm*ym)(1-(1-y1)...(1-ym)) + c_m+1(1-y1)...(1-ym)  
 <= (c1*y1+...+cm*ym)(1-1/e) + c_m+1*1/e since c1<=c2<=...<=cm<=c_m+1