Proof (continued) ECx]=E∑c Take expectation y∈7-{x} of both sides ∑Ecx1]. Linearity of y∈7-{x} expectation ∑1/m E XI y∈7-{x} o 2001 by Charles E Leiserson Introduction to Algorithms Day 12 l8.8© 2001 by Charles E. Leiserson Introduction to Algorithms Day 12 L8.8 Proof (continued) ∑ ∑ ∑ ∈ − ∈ − ∈ − = =   = { } { } { } 1/ [ ] [ ] y T x y T x xy y T x x xy m E c E C E c • E[cxy] = 1/m. • Linearity of expectation. • Take expectation of both sides