In a recent paper by the same authors, we constructed a stationary 1-dependent 4-coloring of the integers that is invariant under permutations of the colors. This was the first stationary k-dependent q-coloring for any k and q. When the analogous construction is carried out for q>4 colors, the resulting process is not k-dependent for any k. We construct here a process that is symmetric in the colors and 1-dependent for every q>=4. The construction uses a recursion involving Chebyshev polynomials evaluated at $sqrt{q}/2$.
We prove that proper coloring distinguishes between block-factors and finitely dependent stationary processes. A stochastic process is finitely dependent if variables at sufficiently well-separated locations are independent; it is a block-factor if it can be expressed as an equivariant finite-range function of independent variables. The problem of finding non-block-factor finitely dependent processes dates back to 1965. The first published example appeared in 1993, and we provide arguably the first natural examples. More precisely, Schramm proved in 2008 that no stationary 1-dependent 3-coloring of the integers exists, and conjectured that no stationary k-dependent q-coloring exists for any k and q. We disprove this by constructing a 1-dependent 4-coloring and a 2-dependent 3-coloring, thus resolving the question for all k and q. Our construction is canonical and natural, yet very different from all previous schemes. In its pure form it yields precisely the two finitely dependent colorings mentioned above, and no others. The processes provide unexpected connections between extremal cases of the Lovasz local lemma and descent and peak sets of random permutations. Neither coloring can be expressed as a block-factor, nor as a function of a finite-state Markov chain; indeed, no stationary finitely dependent coloring can be so expressed. We deduce extensions involving d dimensions and shifts of finite type; in fact, any non-degenerate shift of finite type also distinguishes between block-factors and finitely dependent processes.
In discrete contexts such as the degree distribution for a graph, emph{scale-free} has traditionally been emph{defined} to be emph{power-law}. We propose a reasonable interpretation of emph{scale-free}, namely, invariance under the transformation of $p$-thinning, followed by conditioning on being positive. For each $beta in (1,2)$, we show that there is a unique distribution which is a fixed point of this transformation; the distribution is power-law-$beta$, and different from the usual Yule--Simon power law-$beta$ that arises in preferential attachment models. In addition to characterizing these fixed points, we prove convergence results for iterates of the transformation.
Interacting particle systems and percolation have been among the most active areas of probability theory over the past half century. Ted Harris played an important role in the early development of both fields. This paper is a birds eye view of his work in these fields, and of its impact on later research in probability theory and mathematical physics.
A strong negative dependence property for measures on {0,1}^n - stability - was recently developed in [5], by considering the zero set of the probability generating function. We extend this property to the more general setting of reaction-diffusion processes and collections of independent Markov chains. In one dimension the generalized stability property is now independently interesting, and we characterize the birth-death chains preserving it.
Aldous spectral gap conjecture asserts that on any graph the random walk process and the random transposition (or interchange) process have the same spectral gap. We prove the conjecture using a recursive strategy. The approach is a natural extension of the method already used to prove the validity of the conjecture on trees. The novelty is an idea based on electric network reduction, which reduces the problem to the proof of an explicit inequality for a random transposition operator involving both positive and negative rates. The proof of the latter inequality uses suitable coset decompositions of the associated matrices on permutations.
We introduce the class of {em strongly Rayleigh} probability measures by means of geometric properties of their generating polynomials that amount to the stability of the latter. This class covers important models such as determinantal measures (e.g. product measures, uniform random spanning tree measures) and distributions for symmetric exclusion processes. We show that strongly Rayleigh measures enjoy all virtues of negative dependence and we also prove a series of conjectures due to Liggett, Pemantle, and Wagner, respectively. Moreover, we extend Lyons recent results on determinantal measures and we construct counterexamples to several conjectures of Pemantle and Wagner on negative dependence and ultra log-concave rank sequences.
We consider a type of long-range percolation problem on the positive integers, motivated by earlier work of others on the appearance of (in)finite words within a site percolation model. The main issue is whether a given infinite binary word appears within an iid Bernoulli sequence at locations that satisfy certain constraints. We settle the issue in some cases, and provide partial results in others.
Strong negative dependence properties have recently been proved for the symmetric exclusion process. In this paper, we apply these results to prove convergence to the Poisson and normal distributions for various functionals of the process.
