10/28/2005

6

•Instead of proving it –
assume it and let

•f : Rk ! [-1,1].

•N,M = standard normal vectors & E[Ni Mj] = h d(i = j).

•Define Sh(f) = E[f(N) f(M)].

•“Majority is Stablest” )

•__Thm B:__ sup { Sh(f) : E[f] = 0} = 2 arcsin h / p.

•__Pf:__ Approximate f by fn : {-1,1}k n ! {-1,1} with low influences and use Majority is
Stablest and the Central Limit Theorem.

•__Thm B__ was proven by Borell 85.

•The optimizer f is the

indicator of a half space.

N

M