Search

The stochastic block model is a canonical model of communities in random graphs. It was introduced in the social sciences and statistics as a model of communities, and in theoretical computer science as an average case model for graph partitioning problems under the name of the ``planted partition model.'' Given a sparse stochastic block model, the two standard inference tasks are: (i) Weak recovery: can we estimate the communities with non trivial overlap with the true communities? (ii) Detection/Hypothesis testing: can we distinguish if the sample was drawn from the block model or from a random graph with no community structure with probability tending to $1$ as the graph size tends to infinity? In this work, we show that for sparse stochastic block models, the two inference tasks are equivalent except at a critical point. That is, weak recovery is information theoretically possible if and only if detection is possible. We thus find a strong connection between these two notions of inference for the model. We further prove that when detection is impossible, an explicit hypothesis test based on low degree polynomials in the adjacency matrix of the observed graph achieves the optimal statistical power. This low degree test is efficient as opposed to the likelihood ratio test, which is not known to be efficient. Moreover, we prove that the asymptotic mutual information between the observed network and the community structure exhibits a phase transition at the weak recovery threshold. Our results are proven in much broader settings including the hypergraph stochastic block models and general planted factor graphs. In these settings we prove that the impossibility of weak recovery implies contiguity and provide a condition which guarantees the equivalence of weak recovery and detection., Comment: 78 pages

Fixing $\beta \ge 0$ and an integer $q \ge 2$, consider the ferromagnetic $q$-Potts measures $\mu_n^{\beta,B}$ on finite graphs ${\sf G}_n$ on $n$ vertices, with external field strength $B \ge 0$ and the corresponding random cluster measures $\varphi^{q,\beta,B}_{n}$. Suppose that as $n \to \infty$ the uniformly sparse graphs ${\sf G}_n$ converge locally to an infinite $d$-regular tree ${\sf T}_{d}$, $d \ge 3$. We show that the convergence of the Potts free energy density to its Bethe replica symmetric prediction (which has been proved in case $d$ is even, or when $B=0$), yields the local weak convergence of $\varphi^{q,\beta,B}_n$ and $\mu_n^{\beta,B}$ to the corresponding free or wired random cluster measure, Potts measure, respectively, on ${\sf T}_{d}$. The choice of free versus wired limit is according to which has the larger Potts Bethe functional value, with mixtures of these two appearing {as limit points on} the critical line $\beta_c(q,B)$ where these two values of the Bethe functional coincide. For $B=0$ and $\beta>\beta_c$, we further establish a pure-state decomposition by showing that conditionally on the same dominant color $1 \le k \le q$, the $q$-Potts measures on such edge-expander graphs ${\sf G}_n$ converge locally to the $q$-Potts measure on ${\sf T}_{d}$ with a boundary wired at color $k$., Comment: 46 pages

For rotationally invariant first passage percolation (FPP) on the plane, we use a multi-scale argument to prove stretched exponential concentration of the first passage times at the scale of the standard deviation. Our results are proved under hypotheses which can be verified for many standard rotationally invariant models of first passage percolation, e.g. Riemannian FPP, Voronoi FPP and the Howard-Newman model. This is the first such tight concentration result known for any model that is not exactly solvable. As a consequence, we prove a version of the so called KPZ relation between the passage time fluctuations and the transversal fluctuations of geodesics as well as up to constant upper and lower bounds for the non-random fluctuations in these models. Similar results have previously been known conditionally under unproven hypotheses, but our results are the first ones that apply to some specific FPP models. Our arguments are expected to be useful in proving a number of other estimates which were hitherto only known conditionally or for exactly solvable models., Comment: 98 pages, 21 figures

The local behavior of typical solutions of random constraint satisfaction problems (CSP) describes many important phenomena including clustering thresholds, decay of correlations, and the behavior of message passing algorithms. When the constraint density is low, studying the planted model is a powerful technique for determining this local behavior which in many examples has a simple Markovian structure. Work of Coja-Oghlan, Kapetanopoulos, M\"{u}ller (2020) showed that for a wide class of models, this description applies up to the so-called condensation threshold. Understanding the local behavior after the condensation threshold is more complex due to long-range correlations. In this work, we revisit the random regular NAE-SAT model in the condensation regime and determine the local weak limit which describes a random solution around a typical variable. This limit exhibits a complicated non-Markovian structure arising from the space of solutions being dominated by a small number of large clusters. This is the first description of the local weak limit in the condensation regime for any sparse random CSPs in the one-step replica symmetry breaking (1RSB) class. Our result is non-asymptotic, and characterizes the tight fluctuation $O(n^{-1/2})$ around the limit. Our proof is based on coupling the local neighborhoods of an infinite spin system, which encodes the structure of the clusters, to a broadcast model on trees whose channel is given by the 1RSB belief-propagation fixed point. We believe that our proof technique has broad applicability to random CSPs in the 1RSB class., Comment: 43 pages, 2 figures

In this paper we continue to rigorously establish the predictions in ground breaking work in statistical physics by Decelle, Krzakala, Moore, Zdeborov\'a (2011) regarding the block model, in particular in the case of $q=3$ and $q=4$ communities. We prove that for $q=3$ and $q=4$ there is no computational-statistical gap if the average degree is above some constant by showing it is information theoretically impossible to detect below the Kesten-Stigum bound. The proof is based on showing that for the broadcast process on Galton-Watson trees, reconstruction is impossible for $q=3$ and $q=4$ if the average degree is sufficiently large. This improves on the result of Sly (2009), who proved similar results for regular trees for $q=3$. Our analysis of the critical case $q=4$ provides a detailed picture showing that the tightness of the Kesten-Stigum bound in the antiferromagnetic case depends on the average degree of the tree. We also prove that for $q\geq 5$, the Kestin-Stigum bound is not sharp. Our results prove conjectures of Decelle, Krzakala, Moore, Zdeborov\'a (2011), Moore (2017), Abbe and Sandon (2018) and Ricci-Tersenghi, Semerjian, and Zdeborov{\'a} (2019). Our proofs are based on a new general coupling of the tree and graph processes and on a refined analysis of the broadcast process on the tree., Comment: 52 pages

In the interchange process on a graph $G=(V,E)$, distinguished particles are placed on the vertices of $G$ with independent Poisson clocks on the edges. When the clock of an edge rings, the two particles on the two sides of the edge interchange. In this way, a random permutation $\pi_\beta:V\to V$ is formed for any time $\beta >0$. One of the main objects of study is the cycle structure of the random permutation and the emergence of long cycles. We prove the existence of infinite cycles in the interchange process on $\mathbb Z ^d$ for all dimensions $d\ge 5$ and all large $\beta $, establishing a conjecture of B\'alint T\'oth from 1993 in these dimensions. In our proof, we study a self-interacting random walk called the cyclic time random walk. Using a multiscale induction we prove that it is diffusive and can be coupled with Brownian motion. One of the key ideas in the proof is establishing a local escape property which shows that the walk will quickly escape when it is entangled in its history in complicated ways.

In a collection of particles performing independent random walks on $\mathbb Z^d$ we study the spread of an infection with SIR dynamics. Susceptible particles become infected when they meet an infected particle. Infected particles heal and are removed at rate $\nu$. We show that when $\nu$ is small, with positive probability the infection survives forever and grows linearly. Furthermore, after the infection reaches a region, it quickly passes through and leaves behind a $\textit{herd immunity}$ regime consisting of recovered particles, a small positive density of susceptible particles, and no infected particles. One notable feature of this model is the simultaneously existence of supercritical and subcritical phases on either side of an infection front of $O(1)$ width.

In causal inference on directed acyclic graphs, the orientation of edges is in general only recovered up to Markov equivalence classes. We study Markov equivalence classes of uniformly random directed acyclic graphs. Using a tower decomposition, we show that the ratio between the number of Markov equivalence classes and directed acyclic graphs approaches a positive constant when the number of sites goes to infinity. For a typical directed acyclic graph, the expected number of elements in its Markov equivalence class remains bounded. More precisely, we prove that for a uniformly chosen directed acyclic graph, the size of its Markov equivalence class has super-polynomial tails., Comment: 29 pages, 5 figures

We study the contact process on random graphs with low infection rate $\lambda$. For random $d$-regular graphs, it is known that the survival time is $O(\log n)$ below the critical $\lambda_c$. By contrast, on the Erd\H{o}s-R\'enyi random graphs $\mathcal G(n,d/n)$, rare high-degree vertices result in much longer survival times. We show that the survival time is governed by high-density local configurations. In particular, we show that there is a long string of high-degree vertices on which the infection lasts for time $n^{\lambda^{2+o(1)}}$. To establish a matching upper bound, we introduce a modified version of the contact process which ignores infections that do not lead to further infections and allows for a shaper recursive analysis on branching process trees, the local-weak limit of the graph. Our methods, moreover, generalize to random graphs with given degree distributions that have exponential moments., Comment: 43 pages

We study mixing times for the totally asymmetric simple exclusion process (TASEP) on a circle of length $N$ with $k$ particles. We show that the mixing time is of order $N^2 \min(k,N-k)^{-1/2}$, and that the cutoff phenomenon does not occur. This confirms behavior which was separately predicted by Jara, Lacoin and Peres, and it is more broadly believed to hold for integrable models in the KPZ-universalty class. Our arguments rely on a connection to periodic last passage percolation with a detailed analysis of flat geodesics, as well as a novel random extension and time shift argument for last passage percolation., Comment: 56 pages, 9 figures; substantial revision

Georgiou, Katkov and Tsodyks considered the following random process. Let $x_1,x_2,\ldots $ be an infinite sequence of independent, identically distributed, uniform random points in $[0,1]$. Starting with $S=\{0\}$, the elements $x_k$ join $S$ one by one, in order. When an entering element is larger than the current minimum element of $S$, this minimum leaves $S$. Let $S(1,n)$ denote the content of $S$ after the first $n$ elements $x_k$ join. Simulations suggest that the size $|S(1,n)|$ of $S$ at time $n$ is typically close to $n/e$. Here we first give a rigorous proof that this is indeed the case, and that in fact the symmetric difference of $S(1,n)$ and the set $\{x_k\ge 1-1/e: 1 \leq k \leq n \}$ is of size at most $\tilde{O}(\sqrt n)$ with high probability. Our main result is a more accurate description of the process implying, in particular, that as $n$ tends to infinity $ n^{-1/2}\big( |S(1,n)|-n/e \big) $ converges to a normal random variable with variance $3e^{-2}-e^{-1}$. We further show that the dynamics of the symmetric difference of $S(1,n)$ and the set $\{x_k\ge 1-1/e: 1 \leq k \leq n \}$ converges with proper scaling to a three dimensional Bessel process., Comment: 24 pages, 4 figures

Continuing our earlier work in \cite{nss20a}, we study the random regular k-NAE-SAT model in the condensation regime. In \cite{nss20a}, the 1RSB properties of the model were established with positive probability. In this paper, we improve the result to probability arbitrarily close to one. To do so, we introduce a new framework which is the synthesis of two approaches: the small subgraph conditioning and a variance decomposition technique using Doob martingales and discrete Fourier analysis. The main challenge is a delicate integration of the two methods to overcome the difficulty arising from applying the moment method to an unbounded state space., Comment: 57 pages, 1 figure. Accepted to Communications in Mathematical Physics. arXiv admin note: text overlap with arXiv:2011.14270

It was recently shown that almost all solutions in the symmetric binary perceptron are isolated, even at low constraint densities, suggesting that finding typical solutions is hard. In contrast, some algorithms have been shown empirically to succeed in finding solutions at low density. This phenomenon has been justified numerically by the existence of subdominant and dense connected regions of solutions, which are accessible by simple learning algorithms. In this paper, we establish formally such a phenomenon for both the symmetric and asymmetric binary perceptrons. We show that at low constraint density (equivalently for overparametrized perceptrons), there exists indeed a subdominant connected cluster of solutions with almost maximal diameter, and that an efficient multiscale majority algorithm can find solutions in such a cluster with high probability, settling in particular an open problem posed by Perkins-Xu '21. In addition, even close to the critical threshold, we show that there exist clusters of linear diameter for the symmetric perceptron, as well as for the asymmetric perceptron under additional assumptions.

This paper is motivated by the reconstruction problem on the sparse stochastic block model. Mossel, et. al. proved that a reconstruction algorithm that recovers an optimal fraction of the communities in the symmetric, 2-community case. The main contribution of their proof is to show that when the signal to noise ratio is sufficiently large, in particular $\lambda^2d > C$, the reconstruction accuracy for a broadcast process on a tree with or without noise on the leaves is asymptotically the same. This paper will generalize their results, including the main step, to a general class of the sparse stochastic block model with any number of communities that are not necessarily symmetric, proving that an algorithm closely related to Belief Propagation recovers an optimal fraction of community labels., Comment: 34 pages, improved presentation

In the slow bond problem the rate of a single edge in the Totally Asymmetric Simple Exclusion Process (TASEP) is reduced from 1 to $1-\varepsilon$ for some small $\varepsilon>0$. Janowsky and Lebowitz posed the well-known question of whether such very small perturbations could affect the macroscopic current. Different groups of physicists, using a range of heuristics and numerical simulations reached opposing conclusions on whether the critical value of $\varepsilon$ is 0. This was ultimately resolved rigorously in Basu-Sidoravicius-Sly which established that $\varepsilon_c=0$. Here we study the effect of the current as $\varepsilon$ tends to 0 and in doing so explain why it was so challenging to predict on the basis of numerical simulations. In particular we show that the current has an infinite order phase transition at 0, with the effect of the perturbation tending to 0 faster than any polynomial. Our proof focuses on the Last Passage Percolation formulation of TASEP where a slow bond corresponds to reinforcing the diagonal. We give a multiscale analysis to show that when $\varepsilon$ is small the effect of reinforcement remains small compared to the difference between optimal and near optimal geodesics. Since geodesics can be perturbed on many different scales, we inductively bound the tails of the effect of reinforcement by controlling the number of near optimal geodesics and giving new tail estimates for the local time of (near) geodesics along the diagonal., Comment: 33 pages, 4 figures. Revised according to referee reports. Comm. Pure Appl. Math. to appear

A well-known question in the planar first-passage percolation model concerns the convergence of the empirical distribution along geodesics. We demonstrate this convergence for an explicit model, directed last-passage percolation on $\mathbb{Z}^2$ with i.i.d.\ exponential weights, and provide explicit formulae for the limiting distributions, which depend on the asymptotic direction. For example, for geodesics in the direction of the diagonal, the limiting weight distribution has density $(1/4+x/2+x^2/8)e^{-x}$, and so is a mixture of Gamma($1,1$), Gamma($2,1$) and Gamma($3,1$) distributions with weights $1/4$, $1/2$, and $1/4$ respectively. More generally, we study the local environment as seen from vertices along the geodesics (including information about the shape of the path and about the weights on and off the path in a local neighborhood). We consider finite geodesics from $(0,0)$ to $n\boldsymbol{\rho}$ for some vector $\boldsymbol{\rho}$ in the first quadrant, in the limit as $n\to\infty$, as well as the semi-infinite geodesic in direction $\boldsymbol{\rho}$. We show almost sure convergence of the empirical distributions along the geodesic, as well as convergence of the distribution around a typical point, and we give an explicit description of the limiting distribution. We make extensive use of a correspondence with TASEP as seen from a single second-class particle for which we prove new results concerning ergodicity and convergence to equilibrium. Our analysis relies on geometric arguments involving estimates for the last-passage time, available from the integrable probability literature., Comment: 53 pages, 11 figures

We consider a model where an infection moves through a collection of particles performing independent random walks. In this model, Kesten and Sidoravicius established linear growth of the infected region when infected and susceptible particles move at the same speed. In this paper we establish a linear growth rate when infected and susceptible particles move at different speeds, answering an open problem from their work. Our proof combines an intricate coupling of Poisson processes with a streamlined version of a percolation model of Sidoravicius and Stauffer.

We consider the symmetric binary perceptron model, a simple model of neural networks that has gathered significant attention in the statistical physics, information theory and probability theory communities, with recent connections made to the performance of learning algorithms in Baldassi et al. '15. We establish that the partition function of this model, normalized by its expected value, converges to a lognormal distribution. As a consequence, this allows us to establish several conjectures for this model: (i) it proves the contiguity conjecture of Aubin et al. '19 between the planted and unplanted models in the satisfiable regime; (ii) it establishes the sharp threshold conjecture; (iii) it proves the frozen 1-RSB conjecture in the symmetric case, conjectured first by Krauth-M\'ezard '89 in the asymmetric case. In a recent work of Perkins-Xu '21, the last two conjectures were also established by proving that the partition function concentrates on an exponential scale, under an analytical assumption on a real-valued function. This left open the contiguity conjecture and the lognormal limit characterization, which are established here unconditionally, with the analytical assumption verified. In particular, our proof technique relies on a dense counter-part of the small graph conditioning method, which was developed for sparse models in the celebrated work of Robinson and Wormald.

We study the ferromagnetic Ising model on the infinite $d$-regular tree under the free boundary condition. This model is known to be a factor of IID in the uniqueness regime, when the inverse temperature $\beta\ge 0$ satisfies $\tanh \beta \le (d-1)^{-1}$. However, in the reconstruction regime ($\tanh \beta > (d-1)^{-\frac{1}{2}}$), it is not a factor of IID. We construct a factor of IID for the Ising model beyond the uniqueness regime via a strong solution to an infinite dimensional stochastic differential equation which partially answers a question of Lyons. The solution $\{X_t(v) \}$ of the SDE is distributed as \[ X_t(v) = t\tau_v + B_t(v), \] where $\{\tau_v \}$ is an Ising sample and $\{B_t(v) \}$ are independent Brownian motions indexed by the vertices in the tree. Our construction holds whenever $\tanh \beta \le c(d-1)^{-\frac{1}{2}}$, where $c>0$ is an absolute constant., Comment: 34 pages. CMP to appear

We study a natural random walk on the $n \times n$ upper triangular matrices, with entries in $\mathbb{Z}/m \mathbb{Z}$, generated by steps which add or subtract a uniformly random row to the row above. We show that the mixing time of this random walk is $O(m^2n \log n+ n^2 m^{o(1)})$. This answers a question of Stong and of Arias-Castro, Diaconis, and Stanley.

In a broad class of sparse random constraint satisfaction problems(CSP), deep heuristics from statistical physics predict that there is a condensation phase transition before the satisfiability threshold, governed by one-step replica symmetry breaking(1RSB). In fact, in random regular k-NAE-SAT, which is one of such random CSPs, it was verified \cite{ssz22} that its free energy is well-defined and the explicit value follows the 1RSB prediction. However, for any model of sparse random CSP, it has been unknown whether the solution space indeed condenses on O(1) clusters according to the 1RSB prediction. In this paper, we give an affirmative answer to this question for the random regular k-NAE-SAT model. Namely, we prove that with probability bounded away from zero, most of the solutions lie inside a bounded number of solution clusters whose sizes are comparable to the scale of the free energy. Furthermore, we establish that the overlap between two independently drawn solutions concentrates precisely at two values. Our proof is based on a detailed moment analysis of a spin system, which has an infinite spin space that encodes the structure of solution clusters. We believe that our method is applicable to a broad range of random CSPs in the 1RSB universality class., Comment: 125 pages, 4 figures. This version was revised according to the referee's reports

This paper is motivated by the reconstruction problem on the sparse stochastic block model. The paper "Belief Propagation, robust reconstruction and optimal recovery of block models" by Mossel, Neeman, and Sly provided and proved a reconstruction algorithm that recovers an optimal fraction of the communities in the 2 community case. The main step in their proof was to show that when the signal to noise ratio is sufficiently large, in particular $\theta^2d > C$, the reconstruction accuracy on a regular tree with or without noise on the leaves is the same. This paper will generalize their results, including the main step, to any number of communities, providing an algorithm related to Belief Propagation that recovers a provably optimal fraction of community labels., Comment: 49 pages

We study one-dimensional multi-particle Diffusion Limited Aggregation (MDLA) at its critical density $\lambda=1$. Previous works have verified that the size of the aggregate $X_t$ at time $t$ is $t^{1/2}$ in the subcritical regime and linear in the supercritical regime. This paper establishes the conjecture that the growth rate at criticiality is $t^{2/3}$. Moreover, we derive the scaling limit proving that $$\big\{ t^{-2/3}X_{st} \big\}_{s\geq 0} \overset{d}{\rightarrow} \Big\{ \int_0^s Z_u du \Big\}_{s\geq 0}, $$ where the speed process $\{Z_t\}$ is a $(-\frac{1}{3})$-self-similar diffusion given by $Z_t = (3V_t)^{-2/3}$, where $V_t$ is the $\frac{8}{3}$-Bessel process. The proof shows that locally the speed process can be well approximated by a stochastic integral representation which itself can be approximated by a critical branching process with continuous edge lengths. From these representations, we determine its infinitesimal drift and variance to show that the speed asymptotically satisfies the SDE $dZ_t = 2Z_t^{5/2}dB_t$. To make these approximations, regularity properties of the process are established inductively via a multiscale argument.

We establish universality of cutoff for simple random walk on a class of random graphs defined as follows. Given a finite graph $G=(V,E)$ with $|V|$ even we define a random graph $ G^*=(V,E \cup E')$ obtained by picking $E'$ to be the (unordered) pairs of a random perfect matching of $V$. We show that for a sequence of such graphs $G_n$ of diverging sizes and of uniformly bounded degree, if the minimal size of a connected component of $G_n$ is at least 3 for all $n$, then the random walk on $G_n^*$ exhibits cutoff w.h.p. This provides a simple generic operation of adding some randomness to a given graph, which results in cutoff., Comment: 41 pages

The problem of learning graphons has attracted considerable attention across several scientific communities, with significant progress over the recent years in sparser regimes. Yet, the current techniques still require diverging degrees in order to succeed with efficient algorithms in the challenging cases where the local structure of the graph is homogeneous. This paper provides an efficient algorithm to learn graphons in the constant expected degree regime. The algorithm is shown to succeed in estimating the rank-$k$ projection of a graphon in the $L_2$ metric if the top $k$ eigenvalues of the graphon satisfy a generalized Kesten-Stigum condition., Comment: 32 pages

Let $x_1,\ldots,x_n$ be a fixed sequence of real numbers. At each stage, pick two indices $I$ and $J$ uniformly at random and replace $x_I$, $x_J$ by $(x_I+x_J)/2$, $(x_I+x_J)/2$. Clearly all the coordinates converge to $(x_1+\cdots+x_n)/n$. We determine the rate of convergence, establishing a sharp "cutoff" transition, answering a question of Jean Bourgain., Comment: 21 pages, 2 figures. Final version. To appear in Ann. Probab

Recent progress in the study of the contact process [2] has verified that the extinction-survival threshold $\lambda_1$ on a Galton-Watson tree is strictly positive if and only if the offspring distribution $\xi$ has an exponential tail. In this paper, we derive the first-order asymptotics of $\lambda_1$ for the contact process on Galton-Watson trees and its corresponding analog for random graphs. In particular, if $\xi$ is appropriately concentrated around its mean, we demonstrate that $\lambda_1(\xi) \sim 1/\mathbb{E} \xi$ as $\mathbb{E}\xi\rightarrow \infty$, which matches with the known asymptotics on the $d$-regular trees. The same result for the short-long survival threshold on the Erd\H{o}s-R\'enyi and other random graphs are shown as well., Comment: 57 pages, 5 figures

For the Voter Model on $\mathbb{Z}^d$, $d\geq 3$, we show that the (extremal) stationary distributions are isomorphic to Bernoulli shifts, and answer an open question asked by Steif and Tykesson. The proof gives explicit constructions of the stationary distributions as factors of IID processes on $\mathbb{Z}^d$., Comment: 21 pages, 2 figures. Revised according to comments of a referee. AOP to appear

In this paper, we establish the necessary and sufficient criterion for the contact process on Galton-Watson trees (resp. random graphs) to exhibit the phase of extinction (resp. short survival). We prove that the survival threshold $\lambda_1$ for a Galton-Watson tree is strictly positive if and only if its offspring distribution $\xi$ has an exponential tail, i.e., $\mathbb{E} e^{c\xi}<\infty$ for some $c>0$, settling a conjecture by Huang and Durrett [12]. On the random graph with degree distribution $\mu$, we show that if $\mu$ has an exponential tail, then for small enough $\lambda$ the contact process with the all-infected initial condition survives for $n^{1+o(1)}$-time w.h.p. (short survival), while for large enough $\lambda$ it runs over $e^{\Theta(n)}$-time w.h.p. (long survival). When $\mu$ is subexponential, we prove that the contact process w.h.p. displays long survival for any fixed $\lambda>0$., Comment: 39 pages

Bi-infinite geodesics are fundamental objects of interest in planar first passage percolation. A longstanding conjecture states that under mild conditions there are almost surely no bigeodesics, however the result has not been proved in any case. For the exactly solvable model of directed last passage percolation on $\mathbb{Z}^2$ with i.i.d. exponential passage times, we study the corresponding question and show that almost surely the only bigeodesics are the trivial ones, i.e., the horizontal and vertical lines. The proof makes use of estimates for last passage time available from the integrable probability literature to study coalescence structure of finite geodesics, thereby making rigorous a heuristic argument due to Newman., Comment: 27 pages, 6 figures, revised version

We study the Swendsen-Wang dynamics for the $q$-state Potts model on the lattice. Introduced as an alternative algorithm of the classical single-site Glauber dynamics, the Swendsen-Wang dynamics is a non-local Markov chain that recolors many vertices at once based on the random-cluster representation of the Potts model. In this work we derive strong enough bounds on the mixing time, proving that the Swendsen-Wang dynamics on the lattice at sufficiently high temperatures exhibits a sharp transition from "unmixed" to "well-mixed," which is called the cutoff phenomenon. In particular, we establish that at high enough temperatures the Swendsen-Wang dynamics on the torus $(\mathbb{Z}/n\mathbb{Z})^d$ has cutoff at time $\frac{d}{2} \left( -\log (1-\gamma) \right)^{-1} \log n$, where $\gamma(\beta)$ is the spectral gap of the infinite-volume dynamics., Comment: 44 pages, 2 figures

For first passage percolation on $\mathbb{Z}^2$ with i.i.d. bounded edge weights, we consider the upper tail large deviation event; i.e., the rare situation where the first passage time between two points at distance $n$, is macroscopically larger than typical. It was shown by Kesten (1986) that the probability of this event decays as $\exp (-\Theta(n^2))$. However the question of existence of the rate function i.e., whether the log-probability normalized by $n^2$ tends to a limit, had remained open. We show that under some additional mild regularity assumption on the passage time distribution, the rate function for upper tail large deviation indeed exists. Our proof can be generalized to work in higher dimensions and for the corresponding problem in last passage percolation as well. The key intuition behind the proof is that a limiting metric structure which is atypical causes the upper tail large deviation event. The formal argument then relies on an approximate version of the above which allows us to dilate the large deviation environment to compare the upper tail probabilities for various values of $n.$, Comment: 40 pages, 12 figures

It is well known that sequential decision making may lead to information cascades. That is, when agents make decisions based on their private information, as well as observing the actions of those before them, then it might be rational to ignore their private signal and imitate the action of previous individuals. If the individuals are choosing between a right and a wrong state, and the initial actions are wrong, then the whole cascade will be wrong. This issue is due to the fact that cascades can be based on very little information. We show that if agents occasionally disregard the actions of others and base their action only on their private information, then wrong cascades can be avoided. Moreover, we study the optimal asymptotic rate at which the error probability at time $t$ can go to zero. The optimal policy is for the player at time $t$ to follow their private information with probability $p_{t} = c/t$, leading to a learning rate of $c'/t$, where the constants $c$ and $c'$ are explicit., Comment: 19 pages; v2: minor changes

Directed last passage percolation models on the plane, where one studies the weight as well as the geometry of optimizing paths (called polymers) in a field of i.i.d. weights, are paradigm examples of models in the KPZ universality class. In this article, we consider the large deviation regime, i.e., when the polymer has a much smaller (lower tail) or larger (upper tail) weight than typical. Precise asymptotics of large deviation probabilities have been obtained in a handful of the so-called exactly solvable scenarios, including the Exponential (Johansson, '00) and Poissonian (Sepp\"al\"ainen, '98 and Deuschel, Zeitouni, '99) cases. How the geometry of the optimizing paths change under such a large deviation event was considered in (Deuschel, Zeitouni, '99), where it was shown that the paths (from $(0,0)$ to $(n,n)$, say) remain concentrated around the straight line joining the end points in the upper tail large deviation regime, but the corresponding question in the lower tail was left open. We establish a contrasting behavior in the lower tail large deviation regime, showing that conditioned on the latter, in both the models, the optimizing paths are not concentrated around any deterministic curve. Our argument does not use any ingredient from integrable probability, and hence can be extended to other planar last passage percolation models under fairly mild conditions; and also to other non-integrable settings such as high dimensions., Comment: 28 pages, 4 figures

Group synchronization requires to estimate unknown elements $({\theta}_v)_{v\in V}$ of a compact group ${\mathfrak G}$ associated to the vertices of a graph $G=(V,E)$, using noisy observations of the group differences associated to the edges. This model is relevant to a variety of applications ranging from structure from motion in computer vision to graph localization and positioning, to certain families of community detection problems. We focus on the case in which the graph $G$ is the $d$-dimensional grid. Since the unknowns ${\boldsymbol \theta}_v$ are only determined up to a global action of the group, we consider the following weak recovery question. Can we determine the group difference ${\theta}_u^{-1}{\theta}_v$ between far apart vertices $u, v$ better than by random guessing? We prove that weak recovery is possible (provided the noise is small enough) for $d\ge 3$ and, for certain finite groups, for $d\ge 2$. Viceversa, for some continuous groups, we prove that weak recovery is impossible for $d=2$. Finally, for strong enough noise, weak recovery is always impossible., Comment: 21 pages

Totally Asymmetric Simple Exclusion Process (TASEP) on $\mathbb{Z}$ is one of the classical exactly solvable models in the KPZ universality class. We study the "slow bond" model, where TASEP on $\mathbb{Z}$ is imputed with a slow bond at the origin. The slow bond increases the particle density immediately to its left and decreases the particle density immediately to its right. Whether or not this effect is detectable in the macroscopic current started from the step initial condition has attracted much interest over the years and this question was settled recently (Basu, Sidoravicius, Sly (2014)) by showing that the current is reduced even for arbitrarily small strength of the defect. Following non-rigorous physics arguments (Janowsky, Lebowitz (1992, 1994)) and some unpublished works by Bramson, a conjectural description of properties of invariant measures of TASEP with a slow bond at the origin was provided in Liggett's 1999 book. We establish Liggett's conjectures and in particular show that TASEP with a slow bond at the origin, started from step initial condition, converges in law to an invariant measure that is asymptotically close to product measures with different densities far away from the origin towards left and right. Our proof exploits the correspondence between TASEP and the last passage percolation on $\mathbb{Z}^2$ with exponential weights and uses the understanding of geometry of maximal paths in those models., Comment: 45 pages, 9 figures

Coalescence of semi-infinite geodesics remains a central question in planar first passage percolation. In this paper we study finer properties of the coalescence structure of finite and semi-infinite geodesics for exactly solvable models of last passage percolation. Consider directed last passage percolation on $\mathbb{Z}^2$ with i.i.d. exponential weights on the vertices. Fix two points $v_1=(0,0)$ and $v_2=(0, \lfloor k^{2/3} \rfloor)$ for some $k>0$, and consider the maximal paths $\Gamma_1$ and $\Gamma_2$ starting at $v_1$ and $v_2$ respectively to the point $(n,n)$ for $n\gg k$. Our object of study is the point of coalescence, i.e., the point $v\in \Gamma_1\cap \Gamma_2$ with smallest $|v|_1$. We establish that the distance to coalescence $|v|_1$ scales as $k$, by showing the upper tail bound $\mathbb{P}(|v|_1> Rk) \leq R^{-c}$ for some $c>0$. We also consider the problem of coalescence for semi-infinite geodesics. For the almost surely unique semi-infinite geodesics in the direction $(1,1)$ starting from $v_3=(-\lfloor k^{2/3} \rfloor , \lfloor k^{2/3}\rfloor)$ and $v_4=(\lfloor k^{2/3} \rfloor ,- \lfloor k^{2/3}\rfloor)$, we establish the optimal tail estimate $\mathbb{P}(|v|_1> Rk) \asymp R^{-2/3}$, for the point of coalescence $v$. This answers a question left open by Pimentel (Ann. Probab., 2016) who proved the corresponding lower bound., Comment: 30 pages, 7 figures. Optimal tail estimates for semi-infinite geodesics added in this version

In the study of Markov chain mixing times, analysis has centered on the performance from a worst-case starting state. Here, in the context of Glauber dynamics for the one-dimensional Ising model, we show how new ideas from information percolation can be used to establish mixing times from other starting states. At high temperatures we show that the alternating initial condition is asymptotically the fastest one, and, surprisingly, its mixing time is faster than at infinite temperature, accelerating as the inverse-temperature $\beta$ ranges from 0 to $\beta_0=\frac12\mathrm{arctanh}(\frac13)$. Moreover, the dominant test function depends on the temperature: at $\beta<\beta_0$ it is autocorrelation, whereas at $\beta>\beta_0$ it is the Hamiltonian., Comment: 16 pages, 1 figure

We prove that the the mixing time of the Glauber dynamics for sampling independent sets on $n$-vertex $k$-uniform hypergraphs is $O(n\log n)$ when the maximum degree $\Delta$ satisfies $\Delta \leq c 2^{k/2}$, improving on the previous bound [BDK06] of $\Delta \leq k-2$. This result brings the algorithmic bound to within a constant factor of the hardness bound of [BGG+16] which showed that it is NP-hard to approximately count independent sets on hypergraphs when $\Delta \geq 5 \cdot 2^{k/2}$., Comment: 36 pages, 3 figures

Given an infinite connected regular graph $G=(V,E)$, place at each vertex Pois($\lambda$) walkers performing independent lazy simple random walks on $G$ simultaneously. When two walkers visit the same vertex at the same time they are declared to be acquainted. We show that when $G$ is vertex-transitive and amenable, for all $\lambda>0$ a.s. any pair of walkers will eventually have a path of acquaintances between them. In contrast, we show that when $G$ is non-amenable (not necessarily transitive) there is always a phase transition at some $\lambda_{c}(G)>0$. We give general bounds on $\lambda_{c}(G)$ and study the case that $G$ is the $d$-regular tree in more details. Finally, we show that in the non-amenable setup, for every $\lambda$ there exists a finite time $t_{\lambda}(G)$ such that a.s. there exists an infinite set of walkers having a path of acquaintances between them by time $t_{\lambda}(G)$., Comment: 43 pages

We prove that reconstruction in the $k$-colouring model occurs strictly below the threshold for freezing for large $k$., Comment: 34 pages, 1 figure

We prove that the one dimensional Multi-Particle Diffusion Limited Aggregation model has linear growth whenever the particle density exceeds 1 answering a question of Kesten and Sidoravicius. As a corollary we prove linear growth in all dimensions d when the particle density is at least 1., Comment: 16 pages

Extending results of Bahadoran and Bodineau we show that the flux rate of TASEP with independent and identically distributed disorder always has a plateau of densities around $\frac12$., Comment: 4 pages

We consider the problem of embedding one i.i.d.\ collection of Bernoulli random variables indexed by $\mathbb{Z}^d$ into an independent copy in an injective $M$-Lipschitz manner. For the case $d=1$, it was shown by Basu and Sly (PTRF, 2014) to be possible almost surely for sufficiently large $M$. In this paper we provide a multi-scale argument extending this result to higher dimensions., Comment: 48 pages, 13 figures

Recent work has made substantial progress in understanding the transitions of random constraint satisfaction problems. In particular, for several of these models, the exact satisfiability threshold has been rigorously determined, confirming predictions of statistical physics. Here we revisit one of these models, random regular k-NAE-SAT: knowing the satisfiability threshold, it is natural to study, in the satisfiable regime, the number of solutions in a typical instance. We prove here that these solutions have a well-defined free energy (limiting exponential growth rate), with explicit value matching the one-step replica symmetry breaking prediction. The proof develops new techniques for analyzing a certain "survey propagation model" associated to this problem. We believe that these methods may be applicable in a wide class of related problems., Comment: Correction added starting on page 73

Reconstructing evolutionary trees from molecular sequence data is a fundamental problem in computational biology. Stochastic models of sequence evolution are closely related to spin systems that have been extensively studied in statistical physics and that connection has led to important insights on the theoretical properties of phylogenetic reconstruction algorithms as well as the development of new inference methods. Here, we study maximum likelihood, a classical statistical technique which is perhaps the most widely used in phylogenetic practice because of its superior empirical accuracy. At the theoretical level, except for its consistency, that is, the guarantee of eventual correct reconstruction as the size of the input data grows, much remains to be understood about the statistical properties of maximum likelihood in this context. In particular, the best bounds on the sample complexity or sequence-length requirement of maximum likelihood, that is, the amount of data required for correct reconstruction, are exponential in the number, $n$, of tips---far from known lower bounds based on information-theoretic arguments. Here we close the gap by proving a new upper bound on the sequence-length requirement of maximum likelihood that matches up to constants the known lower bound for some standard models of evolution. More specifically, for the $r$-state symmetric model of sequence evolution on a binary phylogeny with bounded edge lengths, we show that the sequence-length requirement behaves logarithmically in $n$ when the expected amount of mutation per edge is below what is known as the Kesten-Stigum threshold. In general, the sequence-length requirement is polynomial in $n$. Our results imply moreover that the maximum likelihood estimator can be computed efficiently on randomly generated data provided sequences are as above., Comment: To appear in Probability Theory and Related Fields

We study random walks on the giant component of the Erd\H{o}s-R\'enyi random graph ${\cal G}(n,p)$ where $p=\lambda/n$ for $\lambda>1$ fixed. The mixing time from a worst starting point was shown by Fountoulakis and Reed, and independently by Benjamini, Kozma and Wormald, to have order $\log^2 n$. We prove that starting from a uniform vertex (equivalently, from a fixed vertex conditioned to belong to the giant) both accelerates mixing to $O(\log n)$ and concentrates it (the cutoff phenomenon occurs): the typical mixing is at $(\nu {\bf d})^{-1}\log n \pm (\log n)^{1/2+o(1)}$, where $\nu$ and ${\bf d}$ are the speed of random walk and dimension of harmonic measure on a ${\rm Poisson}(\lambda)$-Galton-Watson tree. Analogous results are given for graphs with prescribed degree sequences, where cutoff is shown both for the simple and for the non-backtracking random walk., Comment: 29 pages, 3 figures

In this paper we examine a variant of the voter model on a dynamically changing network where agents have the option of changing their friends rather than changing their opinions. We analyse, in the context of dense random graphs, two models considered in Durrett et. al.(Proc. Natl. Acad. Sci. 109: 3682-3687, 2012). When an edge with two agents holding different opinion is updated, with probability $\frac{\beta}{n}$, one agent performs a voter model step and changes its opinion to copy the other, and with probability $1-\frac{\beta}{n}$, the edge between them is broken and reconnected to a new agent chosen randomly from (i) the whole network (rewire-to-random model) or, (ii) the agents having the same opinion (rewire-to-same model). We rigorously establish in both the models, the time for this dynamics to terminate exhibits a phase transition in the model parameter $\beta$. For $\beta$ sufficiently small, with high probability the network rapidly splits into two disconnected communities with opposing opinions, whereas for $\beta$ large enough the dynamics runs for longer and the density of opinion changes significantly before the process stops. In the rewire-to-random model, we show that a positive fraction of both opinions survive with high probability.

Information percolation is a new method for analyzing stochastic spin systems through classifying and controlling the clusters of information-flow in the space-time slab. It yielded sharp mixing estimates (cutoff with an $O(1)$-window) for the Ising model on $Z^d$ up to the critical temperature, as well as results on the effect of initial conditions on mixing. In this expository note we demonstrate the method on lattices (more generally, on any locally-finite transitive graph) at very high temperatures., Comment: 11 pages

The mixing time of the Glauber dynamics for spin systems on trees is closely related to reconstruction problem. Martinelli, Sinclair and Weitz established this correspondence for a class of spin systems with soft constraints bounding the log-Sobolev constant by a comparison with the block dynamics. However, when there are hard constraints, the block dynamics may be reducible. We introduce a variant of the block dynamics extending these results to a wide class of spin systems with hard constraints. This applies for essentially any spin system that has non-reconstruction provided that on average the root is not locally frozen in a large neighborhood. In particular we prove that the mixing time of the Glauber dynamics for colorings on the regular tree is $O(n\log n)$ in the entire known non-reconstruction regime., Comment: 25 pages