Noise Sensitivity of Boolean Functions And Applications to Percolation

Gil Kalai

Hebrew University

September 23,
refreshments at 3:45pm


It is shown that a large class of events in a product probability space are highly sensitive to noise, in the sense that with high probability, the configuration with a few random errors gives almost no prediction whether the event occurs. This may be viewed as a concentration of measure phenomenon. Consider, for example, bond percolation on an $n+1$ by $n$ grid. A configuration is a function that assigns to every edge the value $0$ or $1$. Let $\omega$ be a random configuration, selected according to the uniform measure. A crossing is a path that joins the left and right sides of the rectangle, and consists entirely of edges $e$ with $\omega(e)=1$. By duality, the probability for having a crossing is $1/2$. Fix an $\epsilon\in(0,1)$. For each edge $e$, let $\omega'(e)=\omega(e)$ with probability $1-\epsilon$, and $\omega'(e)=1-\omega(e)$ with probability $\epsilon$, independently of the other edges. Let $p(\tau)$ be the probability for having a crossing in $\omega'$, conditioned on $\omega=\tau$. Then for all $n$ sufficiently large, $\mbox{Prob}\big\{\tau : |p(\tau)-1/2|>\epsilon\big\}<\epsilon$."

Speaker's Contact Info: kalai(at-sign)

Return to seminar home page

Combinatorics Seminar, Mathematics Department, MIT, sara(at-sign)

Page loaded on September 21, 1998 at 01:38 PM. Copyright © 1998-99, Sara C. Billey. All rights reserved.