A simple variant of first passage percolation (FPP) can be described as follows. Consider the plane grid on which the length of each edge is assigned the value 1 with probability 1/2 and 2 with probability 1/2.

What will be the length D(n) of the shortest path from the point (0,0) to the point (0,n) ?? D(n) is a random variable whose expected value is a constant times n. It takes some effort, however, to show that D(n)/n tends in probability to a constant. Kesten showed that the variance of D(n) is O(n) and Talagrand gave a matching sub-gaussian tail estimate.

``Novice readers might expect to next hear of a central limit theorem being proved,'' writes Durrett in a paper describing these results, ``however physicists tell us that in two dimensions the standard deviation is of order $n^{1/3}$''.

We prove that the variance is o(n). The discussion that follows is central to our proof.

Consider n voters who vote for candidates '0' and '1' and a voting scheme(like the popular-vote or the electoral college) that produces from the list of n votes the elected candidate.

How sensitive is the scheme to random errors in the process of counting the votes?? How sensitive is the scheme to fraud?


Joint work with I. Benjamini and O. Schramm