Concentration and influences

Consider the discrete cube Ω={0,1} ^N , provided with the uniform probabilityP. We denote byd(x, A) the Hamming distance of a pointx of Ω and a subsetA of Ω. We define the influenceI(A) of theith coordinate onA as follows. Forx in Ω, consider the pointT _i (x) obtained by changing the value of theith coordinate. Then We prove that we always have Since it is easy to see that , this recovers the well known fact that ∫_Ω d(x, A)dP(x) is at most of order whenP(A)≥1/2. The new information is that ∫_Ω d(x, A)dP(x) can be of order only ifA reassembles the Hamming ball {x; ∑_1≤N x _i ≥N/2}.