Noise Sensitivity of Boolean Functions
And Applications to Percolation
Gil Kalai
Hebrew University
September 23,
4:15pm
refreshments at 3:45pm
2338
ABSTRACT

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(atsign)math.huji.ac.il
Return to seminar home page
Page loaded on September 21, 1998 at 01:38 PM.

Copyright © 199899, Sara C. Billey.
All rights reserved.

