Mixing times of the biased card shuffling and the asymmetric exclusion process

Consider the following method of card shuffling. Start with a deck of cards numbered 1 through . Fix a parameter between 0 and 1. In this model a ``shuffle' consists of uniformly selecting a pair of adjacent cards and then flipping a coin that is heads with probability . If the coin comes up heads, then we arrange the two cards so that the lower-numbered card comes before the higher-numbered card. If the coin comes up tails, then we arrange the cards with the higher-numbered card first. In this paper we prove that for all , the mixing time of this card shuffling is , as conjectured by Diaconis and Ram (2000). Our result is a rare case of an exact estimate for the convergence rate of the Metropolis algorithm. A novel feature of our proof is that the analysis of an infinite (asymmetric exclusion) process plays an essential role in bounding the mixing time of a finite process.

     

Glauber dynamics on trees and hyperbolic graphs

We study continuous time Glauber dynamics for random configurations with local constraints (e.g. proper coloring, Ising and Potts models) on finite graphs with n vertices and of bounded degree. We show that the relaxation time (defined as the reciprocal of the spectral gap |₁–₂|) for the dynamics on trees and on planar hyperbolic graphs, is polynomial in n. For these hyperbolic graphs, this yields a general polynomial sampling algorithm for random configurations. We then show that for general graphs, if the relaxation time ₂ satisfies ₂=O(1), then the correlation coefficient, and the mutual information, between any local function (which depends only on the configuration in a fixed window) and the boundary conditions, decays exponentially in the distance between the window and the boundary. For the Ising model on a regular tree, this condition is sharp.Research supported by Microsoft graduate fellowship.Supported by a visiting position at INRIA and a PostDoc at Microsoft research.Research supported by NSF Grants DMS-0104073, CCR-0121555 and a Miller Professorship at UC Berkeley.Acknowledgement We are grateful to David Aldous, David Levin, Laurent Saloff-Coste and Peter Winkler for useful discussions. We thank Dror Weitz for helpful comments on [19].     

On Reverse Hypercontractivity

We study the notion of reverse hypercontractivity. We show that reverse hypercontractive inequalities are implied by standard hypercontractive inequalities as well as by the modified log-Sobolev inequality. Our proof is based on a new comparison lemma for Dirichlet forms and an extension of the Stroock–Varopoulos inequality. A consequence of our analysis is that all simple operators ${L = Id - \mathbb{E}}$ as well as their tensors satisfy uniform reverse hypercontractive inequalities. That is, for all q < p < 1 and every positive valued function f for ${t \geq \log \frac{1-q}{1-p}}$ we have ${\| e^{-tL}f\|_{q} \geq \| f\|_{p}}$ . This should be contrasted with the case of hypercontractive inequalities for simple operators where t is known to depend not only on p and q but also on the underlying space. The new reverse hypercontractive inequalities established here imply new mixing and isoperimetric results for short random walks in product spaces, for certain card-shufflings, for Glauber dynamics in high-temperatures spin systems as well as for queueing processes. The inequalities further imply a quantitative Arrow impossibility theorem for general product distributions and inverse polynomial bounds in the number of players for the non-interactive correlation distillation problem with m-sided dice.     

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.