Energy of Flows on Percolation Clusters

It is well known for which gauge functions H there exists a flow in Z ^d with finite H energy. In this paper we discuss the robustness under random thinning of edges of the existence of such flows. Instead of Z ^d we let our (random) graph cal C cal (Z ^d,p) be the graph obtained from Z ^d by removing edges with probability 1–p independently on all edges. Grimmett, Kesten, and Zhang (1993) showed that for d3,p>p _c(Z ^d), simple random walk on cal C cal (Z ^d,p) is a.s. transient. Their result is equivalent to the existence of a nonzero flow f on the infinite cluster such that the x ² energy _e f(e)² is finite. Levin and Peres (1998) sharpened this result, and showed that if d3 and p>p _c(Z ^d), then cal C cal (Z ^d,p) supports a nonzero flow f such that the x ^q energy is finite for all q>d/(d–1). However, for general gauge functions, there is a gap between the existence of flows with finite energy which results from the work of Levin and Peres and the known results on flows for Z ^d. In this paper we close the gap by showing that if d3 and Z ^d supports a flow of finite H energy then the infinite percolation cluster on Z ^d also support flows of finite H energy. This disproves a conjecture of Levin and Peres.     

Evolutionary trees and the Ising model on the Bethe lattice: a proof of Steel��s conjecture

A major task of evolutionary biology is the reconstruction of phylogenetic trees from molecular data. The evolutionary model is given by a Markov chain on a tree. Given samples from the leaves of the Markov chain, the goal is to reconstruct the leaf-labelled tree. It is well known that in order to reconstruct a tree on n leaves, sample sequences of length ??(log n) are needed. It was conjectured by Steel that for the CFN/Ising evolutionary model, if the mutation probability on all edges of the tree is less than ${p^{\ast} = (\sqrt{2}-1)/2^{3/2}}$ , then the tree can be recovered from sequences of length O(log n). The value p* is given by the transition point for the extremality of the free Gibbs measure for the Ising model on the binary tree. Steel??s conjecture was proven by the second author in the special case where the tree is ??balanced.?? The second author also proved that if all edges have mutation probability larger than p* then the length needed is n ^??(1). Here we show that Steel??s conjecture holds true for general trees by giving a reconstruction algorithm that recovers the tree from O(log n)-length sequences when the mutation probabilities are discretized and less than p*. Our proof and results demonstrate that extremality of the free Gibbs measure on the infinite binary tree, which has been studied before in probability, statistical physics and computer science, determines how distinguishable are Gibbs measures on finite binary trees.     

A note on the Entropy/Influence conjecture

The Entropy/Influence conjecture, raised by Friedgut and Kalai (1996) [9], seeks to relate two different measures of concentration of the Fourier coefficients of a Boolean function. Roughly saying, it claims that if the Fourier spectrum is “smeared out”, then the Fourier coefficients are concentrated on “high” levels. In this note we generalize the conjecture to biased product measures on the discrete cube.     

On the mixing time of a simple random walk on the super critical percolation cluster

 We study the robustness under perturbations of mixing times, by studying mixing times of random walks in percolation clusters inside boxes in Z ^d . We show that for d≥2 and p>p _c (Z ^d ), the mixing time of simple random walk on the largest cluster inside is Θ(n ² ) – thus the mixing time is robust up to a constant factor. The mixing time bound utilizes the Lovàsz-Kannan average conductance method. This is the first non-trivial application of this method which yields a tight result. Received: 16 December 2001 / Revised version: 13 August 2002 / Published online: 19 December 2002     

Gaussian Bounds for Noise Correlation of Functions

In this paper we derive tight bounds on the expected value of products of low influence functions defined on correlated probability spaces. The proofs are based on extending Fourier theory to an arbitrary number of correlated probability spaces, on a generalization of an invariance principle recently obtained with O’Donnell and Oleszkiewicz for multilinear polynomials with low influences and bounded degree and on properties of multi-dimensional Gaussian distributions.     

Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality

In this paper we studynon-interactive correlation distillation (NICD), a generalization of noise sensitivity previously considered in [5, 31, 39]. We extend the model toNICD on trees. In this model there is a fixed undirected tree with players at some of the nodes. One node is given a uniformly random string and this string is distributed throughout the network, with the edges of the tree acting as independent binary symmetric channels. The goal of the players is to agree on a shared random bit without communicating. Our new contributions include the following:

? In the case of ak-leaf star graph (the model considered in [31]), we resolve the open question of whether the success probability must go to zero ask » ∞. We show that this is indeed the case and provide matching upper and lower bounds on the asymptotically optimal rate (a slowly-decaying polynomial).

? In the case of thek-vertex path graph, we show that it is always optimal for all players to use the same 1-bit function.

? In the general case we show that all players should use monotone functions. We also show, somewhat surprisingly, that for certain trees it is better if not all players use the same function.

Our techniques include the use of thereverse Bonami-Beckner inequality. Although the usual Bonami-Beckner has been frequently used before, its reverse counterpart seems not to be well known. To demonstrate its strength, we use it to prove a new isoperimetric inequality for the discrete cube and a new result on the mixing of short random walks on the cube. Another tool that we need is a tight bound on the probability that a Markov chain stays inside certain sets; we prove a new theorem generalizing and strengthening previous such bounds [2, 3, 6]. On the probabilistic side, we use the “reflection principle” and the FKG and related inequalities in order to study the problem on general trees.     

Asymptotic learning on Bayesian social networks

We study a standard model of economic agents on the nodes of a social network graph who learn a binary “state of the world” $S$ , from initial signals, by repeatedly observing each other’s best guesses. Asymptotic learning is said to occur on a family of graphs $G_n = (V_n,E_n)$ with $|V_n| \rightarrow \infty $ if with probability tending to $1$ as $n \rightarrow \infty $ all agents in $G_n$ eventually estimate $S$ correctly. We identify sufficient conditions for asymptotic learning and contruct examples where learning does not occur when the conditions do not hold.     

A quantitative Arrow theorem

Arrow’s Impossibility theorem states that any constitution which satisfies independence of irrelevant alternatives (IIA) and unanimity and is not a dictator has to be non-transitive. In this paper we study quantitative versions of Arrow theorem. Consider n voters who vote independently at random, each following the uniform distribution over the six rankings of three alternatives. Arrow’s theorem implies that any constitution which satisfies IIA and unanimity and is not a dictator has a probability of at least 6^?n for a non-transitive outcome. When n is large, 6^?n is a very small probability, and the question arises if for large number of voters it is possible to avoid paradoxes with probability close to 1. Here we give a negative answer to this question by proving that for every ${\epsilon > 0}$ , there exists a ${\delta = \delta(\epsilon) > 0}$ , which depends on ${\epsilon}$ only, such that for all n, and all constitutions on three alternatives, if the constitution satisfies:

• The IIA condition.
• For every pair of alternatives a, b, the probability that the constitution ranks a above b is at least ${\epsilon}$ .
• For every voter i, the probability that the social choice function agrees with a dictatorship on i at most ${1-\epsilon}$ .

Then the probability of a non-transitive outcome is at least δ. Our results generalize to any number k ≥ 3 of alternatives and to other distributions over the alternatives. We further derive a quantitative characterization of all social choice functions satisfying the IIA condition whose outcome is transitive with probability at least 1 ? δ. Our results provide a quantitative statement of Arrow theorem and its generalizations and strengthen results of Kalai and Keller who proved quantitative Arrow theorems for k?=?3 and for balanced constitutions only, i.e., for constitutions which satisfy for every pair of alternatives a, b, that the probability that the constitution ranks a above b is exactly 1/2. The main novel technical ingredient of our proof is the use of inverse-hypercontractivity to show that if the outcome is transitive with high probability then there are no two different voters who are pivotal with for two different pairwise preferences with non-negligible probability. Another important ingredient of the proof is the application of non-linear invariance to lower bound the probability of a paradox for constitutions where all voters have small probability for being pivotal.