Search

Consider $k$-colorings of the complete tree of depth $\ell$ and branching factor $\Delta$. If we fix the coloring of the leaves, as $\ell$ tends to $\infty$, for what range of $k$ is the root uniformly distributed over all $k$ colors? This corresponds to the threshold for uniqueness of the infinite-volume Gibbs measure. It is straightforward to show the existence of colorings of the leaves which ``freeze'' the entire tree when $k\le\Delta+1$. For $k\geq\Delta+2$, Jonasson proved the root is ``unbiased'' for any fixed coloring of the leaves and thus the Gibbs measure is unique. What happens for a {\em typical} coloring of the leaves? When the leaves have a non-vanishing influence on the root in expectation, over random colorings of the leaves, reconstruction is said to hold. Non-reconstruction is equivalent to extremality of the free-boundary Gibbs measure. When $k<\Delta/\ln{\Delta}$, it is straightforward to show that reconstruction is possible and hence the measure is not extremal. We prove that for $C>1$ and $k =C\Delta/\ln{\Delta}$, that the Gibbs measure is extremal in a strong sense: with high probability over the colorings of the leaves the influence at the root decays exponentially fast with the depth of the tree. Closely related results were also proven recently by Sly. The above strong form of extremality implies that a local Markov chain that updates constant sized blocks has inverse linear entropy constant and hence $O(N\log N)$ mixing time where $N$ is the number of vertices of the tree., Comment: Suggestions by journal referees were incorporated

We study Markov chains for randomly sampling $k$-colorings of a graph with maximum degree $\Delta$. Our main result is a polynomial upper bound on the mixing time of the single-site update chain known as the Glauber dynamics for planar graphs when $k=\Omega(\Delta/\log{\Delta})$. Our results can be partially extended to the more general case where the maximum eigenvalue of the adjacency matrix of the graph is at most $\Delta^{1-\eps}$, for fixed $\eps > 0$. The main challenge when $k \le \Delta + 1$ is the possibility of "frozen" vertices, that is, vertices for which only one color is possible, conditioned on the colors of its neighbors. Indeed, when $\Delta = O(1)$, even a typical coloring can have a constant fraction of the vertices frozen. Our proofs rely on recent advances in techniques for bounding mixing time using "local uniformity" properties., Comment: Preliminary version appeared in STOC 2007. This version contains revised proofs

We present a near-optimal reduction from approximately counting the cardinality of a discrete set to approximately sampling elements of the set. An important application of our work is to approximating the partition function $Z$ of a discrete system, such as the Ising model, matchings or colorings of a graph. The typical approach to estimating the partition function $Z(\beta^*)$ at some desired inverse temperature $\beta^*$ is to define a sequence, which we call a {\em cooling schedule}, $\beta_0=0<\beta_1<...<\beta_\ell=\beta^*$ where Z(0) is trivial to compute and the ratios $Z(\beta_{i+1})/Z(\beta_i)$ are easy to estimate by sampling from the distribution corresponding to $Z(\beta_i)$. Previous approaches required a cooling schedule of length $O^*(\ln{A})$ where $A=Z(0)$, thereby ensuring that each ratio $Z(\beta_{i+1})/Z(\beta_i)$ is bounded. We present a cooling schedule of length $\ell=O^*(\sqrt{\ln{A}})$. For well-studied problems such as estimating the partition function of the Ising model, or approximating the number of colorings or matchings of a graph, our cooling schedule is of length $O^*(\sqrt{n})$, which implies an overall savings of $O^*(n)$ in the running time of the approximate counting algorithm (since roughly $\ell$ samples are needed to estimate each ratio).

We present an improved coupling technique for analyzing the mixing time of Markov chains. Using our technique, we simplify and extend previous results for sampling colorings and independent sets. Our approach uses properties of the stationary distribution to avoid worst-case configurations which arise in the traditional approach. As an application, we show that for $k/\Delta >1.764$, the Glauber dynamics on $k$-colorings of a graph on $n$ vertices with maximum degree $\Delta$ converges in $O(n\log n)$ steps, assuming $\Delta =\Omega(\log n)$ and that the graph is triangle-free. Previously, girth $\ge 5$ was needed. As a second application, we give a polynomial-time algorithm for sampling weighted independent sets from the Gibbs distribution of the hard-core lattice gas model at fugacity $\lambda <(1-\epsilon)e/\Delta$, on a regular graph $G$ on $n$ vertices of degree $\Delta =\Omega(\log n)$ and girth $\ge 6$. The best known algorithm for general graphs currently assumes $\lambda <2/(\Delta -2)$., Comment: Published at http://dx.doi.org/10.1214/105051606000000330 in the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

We address phylogenetic reconstruction when the data is generated from a mixture distribution. Such topics have gained considerable attention in the biological community with the clear evidence of heterogeneity of mutation rates. In our work, we consider data coming from a mixture of trees which share a common topology, but differ in their edge weights (i.e., branch lengths). We first show the pitfalls of popular methods, including maximum likelihood and Markov chain Monte Carlo algorithms. We then determine in which evolutionary models, reconstructing the tree topology, under a mixture distribution, is (im)possible. We prove that every model whose transition matrices can be parameterized by an open set of multi-linear polynomials, either has non-identifiable mixture distributions, in which case reconstruction is impossible in general, or there exist linear tests which identify the topology. This duality theorem, relies on our notion of linear tests and uses ideas from convex programming duality. Linear tests are closely related to linear invariants, which were first introduced by Lake, and are natural from an algebraic geometry perspective., Comment: 3 figures

We study Markov chains which model genome rearrangements. These models are useful for studying the equilibrium distribution of chromosomal lengths, and are used in methods for estimating genomic distances. The primary Markov chain studied in this paper is the top-swap Markov chain. The top-swap chain is a card-shuffling process with $n$ cards divided over $k$ decks, where the cards are ordered within each deck. A transition consists of choosing a random pair of cards, and if the cards lie in different decks, we cut each deck at the chosen card and exchange the tops of the two decks. We prove precise bounds on the relaxation time (inverse spectral gap) of the top-swap chain. In particular, we prove the relaxation time is $\Theta(n+k)$. This resolves an open question of Durrett., Comment: Published in at http://dx.doi.org/10.1214/105051607000000177 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

The sequential importance sampling (SIS) algorithm has gained considerable popularity for its empirical success. One of its noted applications is to the binary contingency tables problem, an important problem in statistics, where the goal is to estimate the number of 0/1 matrices with prescribed row and column sums. We give a family of examples in which the SIS procedure, if run for any subexponential number of trials, will underestimate the number of tables by an exponential factor. This result holds for any of the usual design choices in the SIS algorithm, namely the ordering of the columns and rows. These are apparently the first theoretical results on the efficiency of the SIS algorithm for binary contingency tables. Finally, we present experimental evidence that the SIS algorithm is efficient for row and column sums that are regular. Our work is a first step in determining the class of inputs for which SIS is effective.

Markov chain Monte Carlo algorithms play a key role in the Bayesian approach to phylogenetic inference. In this paper, we present the first theoretical work analyzing the rate of convergence of several Markov chains widely used in phylogenetic inference. We analyze simple, realistic examples where these Markov chains fail to converge quickly. In particular, the data studied are generated from a pair of trees, under a standard evolutionary model. We prove that many of the popular Markov chains take exponentially long to reach their stationary distribution. Our construction is pertinent since it is well known that phylogenetic trees for genes may differ within a single organism. Our results shed a cautionary light on phylogenetic analysis using Bayesian inference and highlight future directions for potential theoretical work., Comment: Published at http://dx.doi.org/10.1214/105051600000000538 in the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

We consider finite-state Markov chains that can be naturally decomposed into smaller ``projection'' and ``restriction'' chains. Possibly this decomposition will be inductive, in that the restriction chains will be smaller copies of the initial chain. We provide expressions for Poincare (resp. log-Sobolev) constants of the initial Markov chain in terms of Poincare (resp. log-Sobolev) constants of the projection and restriction chains, together with further a parameter. In the case of the Poincare constant, our bound is always at least as good as existing ones and, depending on the value of the extra parameter, may be much better. There appears to be no previously published decomposition result for the log-Sobolev constant. Our proofs are elementary and self-contained., Comment: Published at http://dx.doi.org/10.1214/105051604000000639 in the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)