Search

We study the mixing time of a random walker who moves inside a dynamical random cluster model on the d-dimensional torus of side-length n. In this model, edges switch at rate μ between open and closed, following a Glauber dynamics for the random cluster model with parameters p, q. At the same time, the walker jumps at rate 1 as a simple random walk on the torus, but is only allowed to traverse open edges. We show that for small enough p the mixing time of the random walker is of order n 2 / μ . In our proof we construct a non-Markovian coupling through a multi-scale analysis of the environment, which we believe could be more widely applicable. [ABSTRACT FROM AUTHOR]

Differential privacy is a mathematical concept that provides an information-theoretic security guarantee. While differential privacy has emerged as a de facto standard for guaranteeing privacy in data sharing, the known mechanisms to achieve it come with some serious limitations. Utility guarantees are usually provided only for a fixed, a priori specified set of queries. Moreover, there are no utility guarantees for more complex—but very common—machine learning tasks such as clustering or classification. In this paper we overcome some of these limitations. Working with metric privacy, a powerful generalization of differential privacy, we develop a polynomial-time algorithm that creates a private measure from a data set. This private measure allows us to efficiently construct private synthetic data that are accurate for a wide range of statistical analysis tools. Moreover, we prove an asymptotically sharp min-max result for private measures and synthetic data in general compact metric spaces, for any fixed privacy budget ε bounded away from zero. A key ingredient in our construction is a new superregular random walk, whose joint distribution of steps is as regular as that of independent random variables, yet which deviates from the origin logarithmically slowly. [ABSTRACT FROM AUTHOR]

We introduce a natural measure on bi-infinite random walk trajectories evolving in a time-dependent environment driven by the Langevin dynamics associated to a gradient Gibbs measure with convex potential. We derive an identity relating the occupation times of the Poissonian cloud induced by this measure to the square of the corresponding gradient field, which—generically—is not Gaussian. In the quadratic case, we recover a well-known generalization of the second Ray–Knight theorem. We further determine the scaling limits of the various objects involved in dimension 3, which are seen to exhibit homogenization. In particular, we prove that the renormalized square of the gradient field converges under appropriate rescaling to the Wick-ordered square of a Gaussian free field on R 3 with suitable diffusion matrix, thus extending a celebrated result of Naddaf and Spencer regarding the scaling limit of the field itself. [ABSTRACT FROM AUTHOR]

Co-evolving network models, wherein dynamics such as random walks on the network influence the evolution of the network structure, which in turn influences the dynamics, are of interest in a range of domains. While much of the literature in this area is currently supported by numerics, providing evidence for fascinating conjectures and phase transitions, proving rigorous results has been quite challenging. We propose a general class of co-evolving tree network models driven by local exploration, started from a single vertex called the root. New vertices attach to the current network via randomly sampling a vertex and then exploring the graph for a random number of steps in the direction of the root, connecting to the terminal vertex. Specific choices of the exploration step distribution lead to the well-studied affine preferential attachment and uniform attachment models, as well as less well understood dynamic network models with global attachment functionals such as PageRank scores (Chebolu and Melsted, in: SODA, 2008). We obtain local weak limits for such networks and use them to derive asymptotics for the limiting empirical degree and PageRank distribution. We also quantify asymptotics for the degree and PageRank of fixed vertices, including the root, and the height of the network. Two distinct regimes are seen to emerge, based on the expected exploration distance of incoming vertices, which we call the 'fringe' and 'non-fringe' regimes. These regimes are shown to exhibit different qualitative and quantitative properties. In particular, networks in the non-fringe regime undergo 'condensation' where the root degree grows at the same rate as the network size. Networks in the fringe regime do not exhibit condensation. Further, non-trivial phase transition phenomena are shown to arise for: (a) height asymptotics in the non-fringe regime, driven by the subtle competition between the condensation at the root and network growth; (b) PageRank distribution in the fringe regime, connecting to the well known power-law hypothesis. In the process, we develop a general set of techniques involving local limits, infinite-dimensional urn models, related multitype branching processes and corresponding Perron–Frobenius theory, branching random walks, and in particular relating tail exponents of various functionals to the scaling exponents of quasi-stationary distributions of associated random walks. These techniques are expected to shed light on a variety of other co-evolving network models. [ABSTRACT FROM AUTHOR]

The Erdős–Taylor theorem (Acta Math Acad Sci Hungar, 1960) states that if L N is the local time at zero, up to time 2N, of a two-dimensional simple, symmetric random walk, then π log N L N converges in distribution to an exponential random variable with parameter one. This can be equivalently stated in terms of the total collision time of two independent simple random walks on the plane. More precisely, if L N (1 , 2) = ∑ n = 1 N 1 { S n (1) = S n (2) } , then π log N L N (1 , 2) converges in distribution to an exponential random variable of parameter one. We prove that for every h ⩾ 3 , the family { π log N L N (i , j) } 1 ⩽ i < j ⩽ h , of logarithmically rescaled, two-body collision local times between h independent simple, symmetric random walks on the plane converges jointly to a vector of independent exponential random variables with parameter one, thus providing a multivariate version of the Erdős–Taylor theorem. We also discuss connections to directed polymers in random environments. [ABSTRACT FROM AUTHOR]

In this paper, we study the online nearest neighbor random tree in dimension d ∈ N (called d-NN tree for short) defined as follows. We fix the torus T n d of dimension d and area n and equip it with the metric inherited from the Euclidean metric in R d . Then, embed consecutively n vertices in T n d uniformly at random and independently, and let each vertex but the first one connect to its (already embedded) nearest neighbor. Call the resulting graph G n . We show multiple results concerning the degree sequence of G n . First, we prove that typically the number of vertices of degree at least k ∈ N in the d-NN tree decreases exponentially with k and is tightly concentrated by a new Lipschitz-type concentration inequality that may be of independent interest. Second, we obtain that the maximum degree of G n is of logarithmic order. Third, we give explicit bounds for the number of leaves that are independent of the dimension and also give estimates for the number of paths of length two. Moreover, we show that typically the height of a uniformly chosen vertex in G n is (1 + o (1)) log n and the diameter of T n d is (2 e + o (1)) log n , independently of the dimension. Finally, we define a natural infinite analog G ∞ of G n and show that it corresponds to the local limit of the sequence of finite graphs (G n) n ≥ 1 . Furthermore, we prove almost surely that G ∞ is locally finite, that the simple random walk on G ∞ is recurrent, and that G ∞ is connected. [ABSTRACT FROM AUTHOR]

In the Fastest Mixing Markov Chain problem, we are given a graph G = (V , E) and desire the discrete-time Markov chain with smallest mixing time τ subject to having equilibrium distribution uniform on V and non-zero transition probabilities only across edges of the graph. It is well-known that the mixing time τ RW of the lazy random walk on G is characterised by the edge conductance Φ of G via Cheeger's inequality: Φ - 1 ≲ τ RW ≲ Φ - 2 log | V | . Analogously, we characterise the fastest mixing time τ ⋆ via a Cheeger-type inequality but for a different geometric quantity, namely the vertex conductance Ψ of G: Ψ - 1 ≲ τ ⋆ ≲ Ψ - 2 (log | V |) 2 . This characterisation forbids fast mixing for graphs with small vertex conductance. To bypass this fundamental barrier, we consider Markov chains on G with equilibrium distribution which need not be uniform, but rather only ε -close to uniform in total variation. We show that it is always possible to construct such a chain with mixing time τ ≲ ε - 1 (diam G) 2 log | V | . Finally, we discuss analogous questions for continuous-time and time-inhomogeneous chains. [ABSTRACT FROM AUTHOR]

We explore the relationship between recursive distributional equations and convergence results for finite difference schemes of parabolic partial differential equations (PDEs). We focus on a family of random processes called symmetric cooperative motions, which generalize the symmetric simple random walk and the symmetric hipster random walk introduced in Addario-Berry et al. (Probab Theory Related fields 178(1–2):437–473, 2020). We obtain a distributional convergence result for symmetric cooperative motions and, along the way, obtain a novel proof of the Bernoulli central limit theorem. In addition, we prove a PDE result relating distributional solutions and viscosity solutions of the porous medium equation and the parabolic p-Laplace equation, respectively, in one dimension. [ABSTRACT FROM AUTHOR]

We prove that for recurrent, reversible graphs, the following conditions are equivalent: (a) existence and uniqueness of the potential kernel, (b) existence and uniqueness of harmonic measure from infinity, (c) a new anchored Harnack inequality, and (d) one-endedness of the wired uniform spanning tree. In particular this gives a proof of the anchored (and in fact also elliptic) Harnack inequality on the UIPT. This also complements and strengthens some results of Benjamini et al. (Ann Probab 29(1):1–65, 2001). Furthermore, we make progress towards a conjecture of Aldous and Lyons by proving that these conditions are fulfilled for strictly subdiffusive recurrent unimodular graphs. Finally, we discuss the behaviour of the random walk conditioned to never return to the origin, which is well defined as a consequence of our results. [ABSTRACT FROM AUTHOR]

We study a natural random walk on the n × n uni-upper triangular matrices, with entries in Z / m 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 2 n log n + n 2 m o (1)) . This answers a question of Stong and of Arias-Castro, Diaconis, and Stanley. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

We study the dimer model on subgraphs of the square lattice in which vertices on a prescribed part of the boundary (the free boundary) are possibly unmatched. Each such unmatched vertex is called a monomer and contributes a fixed multiplicative weight z > 0 to the total weight of the configuration. A bijection described by Giuliani et al. (J Stat Phys 163(2):211–238, 2016) relates this model to a standard dimer model but on a non-bipartite graph. The Kasteleyn matrix of this dimer model describes a walk with transition weights that are negative along the free boundary. Yet under certain assumptions, which are in particular satisfied in the infinite volume limit in the upper half-plane, we prove an effective, true random walk representation for the inverse Kasteleyn matrix. In this case we further show that, independently of the value of z > 0 , the scaling limit of the centered height function is the Gaussian free field with Neumann (or free) boundary conditions. It is the first example of a discrete model where such boundary conditions arise in the continuum scaling limit. [ABSTRACT FROM AUTHOR]

We obtain various new limit theorems for random walks on SL 2 (C) under low moment conditions. For non-elementary measures with a finite second moment we prove a Local Limit Theorem for the norm cocycle, yielding the optimal version of a theorem of É. Le Page. For measures with a finite third moment, we obtain the Local Limit Theorem for the matrix coefficients, improving a recent result of Grama-Quint-Xiao and the authors, and Berry–Esseen bounds with optimal rate O (1 / n) for the norm cocycle and the matrix coefficients. The main tool is a detailed study of the spectral properties of the Markov operator and its purely imaginary perturbations acting on different function spaces. We introduce, in particular, a new function space derived from the Sobolev space W 1 , 2 that provides uniform estimates. [ABSTRACT FROM AUTHOR]

We correct a proof in the article 'D. Shiraishi, Exact value of the resistance exponent for four dimensional random walk trace, Probab. Theory and Related Fields 153 (2012), no. 1–2, 191–232'. [ABSTRACT FROM AUTHOR]

The explicit biorthogonalization method, developed in [24] for continuous time TASEP, is generalized to a broad class of determinantal measures which describe the evolution of several interacting particle systems in the KPZ universality class. The method is applied to sequential and parallel update versions of each of the four variants of discrete time TASEP (with Bernoulli and geometric jumps, and with block and push dynamics) which have determinantal transition probabilities; to continuous time PushASEP; and to a version of TASEP with generalized update. In all cases, multipoint distribution functions are expressed in terms of a Fredholm determinant with an explicit kernel involving hitting times of certain random walks to a curve defined by the initial data of the system. The method is further applied to systems of interacting caterpillars, an extension of the discrete time TASEP models which generalizes sequential and parallel updates. [ABSTRACT FROM AUTHOR]

We consider continuous-time random walks on a random locally finite subset of R d with random symmetric jump probability rates. The jump range can be unbounded. We assume some second-moment conditions and that the above randomness is left invariant by the action of the group G = R d or G = Z d . We then add a site-exclusion interaction, thus making the particle system a simple exclusion process. We show that, for almost all environments, under diffusive space–time rescaling the system exhibits a hydrodynamic limit in path space. The hydrodynamic equation is non-random and governed by the effective homogenized matrix D of the single random walk, which can be degenerate. The above result covers a very large family of models including e.g. simple exclusion processes built from random conductance models on Z d and on crystal lattices (possibly with long conductances), Mott variable range hopping, simple random walks on Delaunay triangulations, random walks on supercritical percolation clusters. [ABSTRACT FROM AUTHOR]

Let ξ 1 , ξ 2 , ... be a sequence of independent copies of a random vector in R d having an absolutely continuous distribution. Consider a random walk S i : = ξ 1 + ⋯ + ξ i , and let C n , d : = conv (0 , S 1 , S 2 , ... , S n) be the convex hull of the first n + 1 points it has visited. The polytope C n , d is called k-neighborly if for any indices 0 ≤ i 1 < ⋯ < i k ≤ n the convex hull of the k points S i 1 , ... , S i k is a (k - 1) -dimensional face of C n , d . We study the probability that C n , d is k-neighborly in various high-dimensional asymptotic regimes, i.e. when n, d, and possibly also k diverge to ∞ . There is an explicit formula for the expected number of (k - 1) -dimensional faces of C n , d which involves Stirling numbers of both kinds. Motivated by this formula, we introduce a distribution, called the Lah distribution, and study its properties. In particular, we provide a combinatorial interpretation of the Lah distribution in terms of random compositions and records, and explicitly compute its factorial moments. Limit theorems which we prove for the Lah distribution imply neighborliness properties of C n , d . This yields a new class of random polytopes exhibiting phase transitions parallel to those discovered by Vershik and Sporyshev, Donoho and Tanner for random projections of regular simplices and crosspolytopes. [ABSTRACT FROM AUTHOR]

Given integers d ≥ 2 , n ≥ 1 , we consider affine random walks on torii (Z / n Z) d defined as X t + 1 = A X t + B t mod n , where A ∈ GL d (Z) is a invertible matrix with integer entries and (B t) t ≥ 0 is a sequence of iid random increments on Z d . We show that when A has no eigenvalues of modulus 1, this random walk mixes in O (log n log log n) steps as n → ∞ , and mixes actually in O (log n) steps only for almost all n. These results are similar to those of Chung et al. (Ann Probab 15(3):1148–1165, 1987) on the so-called Chung–Diaconis–Graham process, which corresponds to the case d = 1 . Our proof is based on the initial arguments of Chung, Diaconis and Graham, and relies extensively on the properties of the dynamical system x ↦ A ⊤ x on the continuous torus R d / Z d . Having no eigenvalue of modulus one makes this dynamical system a hyperbolic toral automorphism, a typical example of a chaotic system known to have a rich behaviour. As such our proof sheds new light on the speed-up gained by applying a deterministic map to a Markov chain. [ABSTRACT FROM AUTHOR]

We define a fragmentation process which involves rectangles breaking up into progressively smaller pieces at rates that depend on their shape. Long, thin rectangles are more likely to break quickly, whereas squares break more slowly. Each rectangle is also more likely to split along its longest side. We are interested in how the system evolves over time: how many fragments are there of different shapes and sizes, and how did they reach that state? Using a standard transformation this fragmentation process with shape-dependent rates is equivalent to a two-dimensional branching random walk in continuous time in which the branching rate and the direction of each jump depend on the particles’ position. Our main theorem gives an almost sure growth rate along paths for the number of particles in the branching random walk, which in turn gives the number of fragments with a fixed shape as the solution to an optimisation problem. This is a result of interest in the context of spatial branching systems and provides an example of a multitype branching process with a continuum of types. [ABSTRACT FROM AUTHOR]

The goal of this article is two-fold: in a first part, we prove Azuma–Hoeffding type concentration inequalities around the drift for the displacement of non-elementary random walks on hyperbolic spaces. For a proper hyperbolic space M, we obtain explicit bounds that depend only on M, the size of support of the measure as in the classical case of sums of independent random variables, and on the norm of the driving probability measure in the left regular representation of the group of isometries. We obtain uniform bounds in the case of hyperbolic groups and effective bounds for simple linear groups of rank-one. In a second part, using our concentration inequalities, we give quantitative finite-time estimates on the probability that two independent random walks on the isometry group of a hyperbolic space generate a free non-abelian subgroup. Our concentration results follow from a more general, but less explicit statement that we prove for cocycles which satisfy a certain cohomological equation. For example, this also allows us to obtain subgaussian concentration bounds around the top Lyapunov exponent of random matrix products in arbitrary dimension. [ABSTRACT FROM AUTHOR]

A correction to this paper has been published: 10.1007/s00440-016-0699-z [ABSTRACT FROM AUTHOR]

This paper studies the mixing behavior of the Asymmetric Simple Exclusion Process (ASEP) on a segment of length N. Our main result is that for particle densities in (0, 1), the total-variation cutoff window of ASEP is N 1 / 3 and the cutoff profile is 1 - F GUE , where F GUE is the Tracy-Widom distribution function. This also gives a new proof of the cutoff itself, shown earlier by Labbé and Lacoin. Our proof combines coupling arguments, the result of Tracy–Widom about fluctuations of ASEP started from the step initial condition, and exact algebraic identities coming from interpreting the multi-species ASEP as a random walk on a Hecke algebra. [ABSTRACT FROM AUTHOR]

We study exceptional sets of the local time of the continuous-time simple random walk in scaled-up (by N) versions D N ⊆ Z 2 of bounded open domains D ⊆ R 2 . Upon exit from D N , the walk lands on a "boundary vertex" and then reenters D N through a random boundary edge in the next step. In the parametrization by the local time at the "boundary vertex" we prove that, at times corresponding to a θ -multiple of the cover time of D N , the sets of suitably defined λ -thick (i.e., heavily visited) and λ -thin (i.e., lightly visited) points are, as N → ∞ , distributed according to the Liouville Quantum Gravity Z λ D with parameter λ -times the critical value. For θ < 1 , also the set of avoided vertices (a.k.a. late points) and the set where the local time is of order unity are distributed according to Z θ D . The local structure of the exceptional sets is described as well, and is that of a pinned Discrete Gaussian Free Field for the thick and thin points and that of random-interlacement occupation-time field for the avoided points. The results demonstrate universality of the Gaussian Free Field for these extremal problems. [ABSTRACT FROM AUTHOR]

We study ballisticity conditions for d-dimensional random walks in strong mixing environments, with underlying dimension d ≥ 2 . Specifically, we introduce an effective polynomial condition similar to that given by Berger et al. (Comm. Pure Appl. Math. 77:1947–1973, 2014). In a mixing setup we prove that this condition implies the corresponding stretched exponential decay, and obtain an annealed functional central limit theorem for the random walk process centered at the limiting velocity. This paper complements previous work of Guerra (Ann. Probab. 47:3003–3054, 2019) and completes the answer about the meaning of condition (T ′) | ℓ in a mixing setting, an open question posed by Comets and Zeitouni (Ann. Probab. 32:880–914, 2004). [ABSTRACT FROM AUTHOR]

We prove the law of large numbers for the drift of random walks on the two-dimensional lamplighter group, under the assumption that the random walk has finite (2 + ϵ) -moment. This result is in contrast with classical examples of abelian groups, where the displacement after n steps, normalised by its mean, does not concentrate, and the limiting distribution of the normalised n-step displacement admits a density whose support is [ 0 , ∞) . We study further examples of groups, some with random walks satisfying LLN for drift and other examples where such concentration phenomenon does not hold, and study relation of this property with asymptotic geometry of groups. [ABSTRACT FROM AUTHOR]

We prove a quenched local central limit theorem for continuous-time random walks in Z d , d ≥ 2 , in a uniformly-elliptic time-dependent balanced random environment which is ergodic under space-time shifts. We also obtain Gaussian upper and lower bounds for quenched and (positive and negative) moment estimates of the transition probabilities and asymptotics of the discrete Green's function. [ABSTRACT FROM AUTHOR]

In a recent breakthrough, Teyssier (Ann Probab 48(5):2323–2343, 2020) introduced a new method for approximating the distance from equilibrium of a random walk on a group. He used it to study the limit profile for the random transpositions card shuffle. His techniques were restricted to conjugacy-invariant random walks on groups; we derive similar approximation lemmas for random walks on homogeneous spaces and for general reversible Markov chains. We illustrate applications of these lemmas to some famous problems: the k-cycle shuffle, sharpening results of Hough (Probab Theory Relat Fields 165(1–2):447–482, 2016) and Berestycki, Schramm and Zeitouni (Ann Probab 39(5):1815–1843, 2011), the Ehrenfest urn diffusion with many urns, sharpening results of Ceccherini-Silberstein, Scarabotti and Tolli (J Math Sci 141(2):1182–1229, 2007), a Gibbs sampler, which is a fundamental tool in statistical physics, with Binomial prior and hypergeometric posterior, sharpening results of Diaconis, Khare and Saloff-Coste (Stat Sci 23(2):151–178, 2008). [ABSTRACT FROM AUTHOR]

We study local regularity properties of linear, non-uniformly parabolic finite-difference operators in divergence form related to the random conductance model on Z d . In particular, we provide an oscillation decay assuming only certain summability properties of the conductances and their inverse, thus improving recent results in that direction. As an application, we provide a local limit theorem for the random walk in a random degenerate and unbounded environment. [ABSTRACT FROM AUTHOR]

We consider one-dimensional excited random walks (ERWs) with i.i.d. Markovian cookie stacks in the non-boundary recurrent regime. We prove that under diffusive scaling such an ERW converges in the standard Skorokhod topology to a multiple of Brownian motion perturbed at its extrema (BMPE). All parameters of the limiting process are given explicitly in terms of those of the cookie Markov chain at a single site. While our results extend the results in Dolgopyat and Kosygina (Electron Commun Probab 17:1–14, 2012) (ERWs with boundedly many cookies per stack) and Kosygina and Peterson (Electron J Probab 21:1–24, 2016) (ERWs with periodic cookie stacks), the approach taken is very different and involves coarse graining of both the ERW and the random environment changed by the walk. Through a careful analysis of the environment left by the walk after each "mesoscopic" step, we are able to construct a coupling of the ERW at this "mesoscopic" scale with a suitable discretization of the limiting BMPE. The analysis is based on generalized Ray–Knight theorems for the directed edge local times of the ERW stopped at certain stopping times and evolving in both the original random cookie environment and (which is much more challenging) in the environment created by the walk after each "mesoscopic" step. [ABSTRACT FROM AUTHOR]

This article investigates the heat kernel of the two-dimensional uniform spanning tree. We improve previous work by demonstrating the occurrence of log-logarithmic fluctuations around the leading order polynomial behaviour for the on-diagonal part of the quenched heat kernel. In addition we give two-sided estimates for the averaged heat kernel, and we show that the exponents that appear in the off-diagonal parts of the quenched and averaged versions of the heat kernel differ. Finally, we derive various scaling limits for the heat kernel, the implications of which include enabling us to sharpen the known asymptotics regarding the on-diagonal part of the averaged heat kernel and the expected distance travelled by the associated simple random walk. [ABSTRACT FROM AUTHOR]

We study the isoperimetric and spectral profiles of certain families of finitely generated groups defined via actions on labelled Schreier graphs and simple gluing of such. In one of our simplest constructions—the pocket-extension of a group G—this leads to the study of certain finitely generated subgroups of the full permutation group S (G ∪ { ∗ }) . Some sharp estimates are obtained while many challenging questions remain. [ABSTRACT FROM AUTHOR]

We consider a directed polymer of length N interacting with a linear interface. The monomers carry i.i.d. random charges (ω i) i = 1 N taking values in R with mean zero and variance one. Each monomer i contributes an energy (β ω i - h) φ (S i) to the interaction Hamiltonian, where S i ∈ Z is the height of monomer i with respect to the interface, φ : Z → [ 0 , ∞) is the interaction potential, β ∈ [ 0 , ∞) is the inverse temperature, and h ∈ R is the charge bias parameter. The configurations of the polymer are weighted according to the Gibbs measure associated with the interaction Hamiltonian, where the reference measure is given by a Markov chain on Z . We study both the quenched and the annealed free energy per monomer in the limit as N → ∞ . We show that each exhibits a phase transition along a critical curve in the (β , h) -plane, separating a localized phase (where the polymer stays close to the interface) from a delocalized phase (where the polymer wanders away from the interface). We derive variational formulas for the critical curves and we obtain upper and lower bounds on the quenched critical curve in terms of the annealed critical curve. In addition, for the special case where the reference measure is given by a Bessel random walk, we derive the scaling limit of the annealed free energy as β , h ↓ 0 in three different regimes for the tail exponent of φ . [ABSTRACT FROM AUTHOR]

Randomly coalescing random walk in dimension HT ht . A ratio limit theorem for (sub) Markov chains on HT ht with bounded jumps. I J. Analyse Math. i , 10:117-138, 1962/63. 1963 H. Kesten. Hitting probabilities of random walks on HT ht . Math. Phys. i , 78(1):19-63, 1980/81. 1981 J. T. Cox and H. Kesten. [Extracted from the article]

We survey the published work of Harry Kesten in probability theory, with emphasis on his contributions to random walks, branching processes, percolation, and related topics. [ABSTRACT FROM AUTHOR]

We study random walks on Z d (with d ≥ 2 ) among stationary ergodic random conductances { C x , y : x , y ∈ Z d } that permit jumps of arbitrary length. Our focus is on the quenched invariance principle (QIP) which we establish by a combination of corrector methods, functional inequalities and heat-kernel technology assuming that the p-th moment of ∑ x ∈ Z d C 0 , x | x | 2 and q-th moment of 1 / C 0 , x for x neighboring the origin are finite for some p , q ≥ 1 with p - 1 + q - 1 < 2 / d . In particular, a QIP thus holds for random walks on long-range percolation graphs with connectivity exponents larger than 2d in all d ≥ 2 , provided all the nearest-neighbor edges are present. Although still limited by moment conditions, our method of proof is novel in that it avoids proving everywhere-sublinearity of the corrector. This is relevant because we show that, for long-range percolation with exponents between d + 2 and 2d, the corrector exists but fails to be sublinear everywhere. Similar examples are constructed also for nearest-neighbor, ergodic conductances in d ≥ 3 under the conditions complementary to those of the recent work of Bella and Schäffner (Ann Probab 48(1):296–316, 2020). These examples elucidate the limitations of elliptic-regularity techniques that underlie much of the recent progress on these problems. [ABSTRACT FROM AUTHOR]

Consider an infinite planar graph with uniform polynomial growth of degree d > 2 . Many examples of such graphs exhibit similar geometric and spectral properties, and it has been conjectured that this is necessary. We present a family of counterexamples. In particular, we show that for every rational d > 2 , there is a planar graph with uniform polynomial growth of degree d on which the random walk is transient, disproving a conjecture of Benjamini (Coarse Geometry and Randomness, Volume 2100 of Lecture Notes in Mathematics. Springer, Cham, 2011). By a well-known theorem of Benjamini and Schramm, such a graph cannot be a unimodular random graph. We also give examples of unimodular random planar graphs of uniform polynomial growth with unexpected properties. For instance, graphs of (almost sure) uniform polynomial growth of every rational degree d > 2 for which the speed exponent of the walk is larger than 1/d, and in which the complements of all balls are connected. This resolves negatively two questions of Benjamini and Papasoglou (Proc Am Math Soc 139(11):4105–4111, 2011). [ABSTRACT FROM AUTHOR]

We obtain sharp upper and lower bounds for the downward moderate deviations of the volume of the range of a random walk in dimension five and larger. Our results encompass two regimes: a Gaussian regime for small deviations, and a stretched exponential regime for larger deviations. In the latter regime, we show that conditioned on the moderate deviations event, the walk folds a small part of its range in a ball-like subset. Also, we provide new path properties, in dimension three as well. Besides the key role Newtonian capacity plays in this study, we introduce two original ideas, of general interest, which strengthen the approach developed in Asselah and Schapira (Sci Éc Norm Supér 50(4):755–786, 2017). [ABSTRACT FROM AUTHOR]

We consider a branching random walk on Z started by n particles at the origin, where each particle disperses according to a mean-zero random walk with bounded support and reproduces with mean number of offspring 1 + θ / n . For t ≥ 0 , we study M nt , the rightmost position reached by the branching random walk up to generation [nt]. Under certain moment assumptions on the branching law, we prove that M nt / n converges weakly to the rightmost support point of the local time of the limiting super-Brownian motion. The convergence result establishes a sharp exponential decay of the tail distribution of M nt . We also confirm that when θ > 0 , the support of the branching random walk grows in a linear speed that is identical to that of the limiting super-Brownian motion which was studied by Pinsky (Ann Probab 23(4):1748–1754, 1995). The rightmost position over all generations, M : = sup t M nt , is also shown to converge weakly to that of the limiting super-Brownian motion, whose tail is found to decay like a Gumbel distribution when θ < 0 . [ABSTRACT FROM AUTHOR]

Consider a critical branching random walk on Z d , d ≥ 1 , started with a single particle at the origin, and let L(x) be the total number of particles that ever visit a vertex x. We study the tail of L(x) under suitable conditions on the offspring distribution. In particular, our results hold if the offspring distribution has an exponential moment. [ABSTRACT FROM AUTHOR]

We establish a quenched local central limit theorem for the dynamic random conductance model on Z d only assuming ergodicity with respect to space-time shifts and a moment condition. As a key analytic ingredient we show Hölder continuity estimates for solutions to the heat equation for discrete finite difference operators in divergence form with time-dependent degenerate weights. The proof is based on De Giorgi's iteration technique. In addition, we also derive a quenched local central limit theorem for the static random conductance model on a class of random graphs with degenerate ergodic weights. [ABSTRACT FROM AUTHOR]

In this paper we prove an analogue of the Komlós–Major–Tusnády (KMT) embedding theorem for random walk bridges. The random bridges we consider are constructed through random walks with i.i.d jumps that are conditioned on the locations of their endpoints. We prove that such bridges can be strongly coupled to Brownian bridges of appropriate variance when the jumps are either continuous or integer valued under some mild technical assumptions on the jump distributions. Our arguments follow a similar dyadic scheme to KMT's original proof, but they require more refined estimates and stronger assumptions necessitated by the endpoint conditioning. In particular, our result does not follow from the KMT embedding theorem, which we illustrate via a counterexample. [ABSTRACT FROM AUTHOR]

Define (X n) on Z / q Z by X n + 1 = 2 X n + b n , where the steps b n are chosen independently at random from - 1 , 0 , + 1 . The mixing time of this random walk is known to be at most 1.02 log 2 q for almost all odd q (Chung, Diaconis, Graham in Ann Probab 15(3):1148–1165, 1987), and at least 1.004 log 2 q (Hildebrand in Proc Am Math Soc 137(4):1479–1487, 2009). We identify a constant c = 1.01136 ⋯ such that the mixing time is (c + o (1)) log 2 q for almost all odd q. In general, the mixing time of the Markov chain X n + 1 = a X n + b n modulo q, where a is a fixed positive integer and the steps b n are i.i.d. with some given distribution in Z , is related to the entropy of a corresponding self-similar Cantor-like measure (such as a Bernoulli convolution). We estimate the mixing time up to a 1 + o (1) factor whenever the entropy exceeds (log a) / 2 . [ABSTRACT FROM AUTHOR]

Let X 1 , X 2 , ... be i.i.d. copies of some real random variable X. For any deterministic ε 2 , ε 3 , ... in { 0 , 1 } , a basic algorithm introduced by H.A. Simon yields a reinforced sequence X ^ 1 , X ^ 2 , ... as follows. If ε n = 0 , then X ^ n is a uniform random sample from X ^ 1 , ... , X ^ n - 1 ; otherwise X ^ n is a new independent copy of X. The purpose of this work is to compare the scaling exponent of the usual random walk S (n) = X 1 + ⋯ + X n with that of its step reinforced version S ^ (n) = X ^ 1 + ⋯ + X ^ n . Depending on the tail of X and on asymptotic behavior of the sequence (ε n) , we show that step reinforcement may speed up the walk, or at the contrary slow it down, or also does not affect the scaling exponent at all. Our motivation partly stems from the study of random walks with memory, notably the so-called elephant random walk and its variations. [ABSTRACT FROM AUTHOR]

A reinforcement algorithm introduced by Simon (Biometrika 42(3/4):425–440, 1955) produces a sequence of uniform random variables with long range memory as follows. At each step, with a fixed probability p ∈ (0 , 1) , U ^ n + 1 is sampled uniformly from U ^ 1 , ... , U ^ n , and with complementary probability 1 - p , U ^ n + 1 is a new independent uniform variable. The Glivenko–Cantelli theorem remains valid for the reinforced empirical measure, but not the Donsker theorem. Specifically, we show that the sequence of empirical processes converges in law to a Brownian bridge only up to a constant factor when p < 1 / 2 , and that a further rescaling is needed when p > 1 / 2 and the limit is then a bridge with exchangeable increments and discontinuous paths. This is related to earlier limit theorems for correlated Bernoulli processes, the so-called elephant random walk, and more generally step reinforced random walks. [ABSTRACT FROM AUTHOR]

We prove that the simple random walk on the uniform infinite planar triangulation (UIPT) typically travels graph distance at most n 1 / 4 + o n (1) in n units of time. Together with the complementary lower bound proven by Gwynne and Miller (2017) this shows that the typical graph distance displacement of the walk after n steps is n 1 / 4 + o n (1) , as conjectured by Benjamini and Curien (Geom Funct Anal 2(2):501–531, 2013. arXiv:1202.5454). More generally, we show that the simple random walks on a certain family of random planar maps in the γ -Liouville quantum gravity (LQG) universality class for γ ∈ (0 , 2) —including spanning tree-weighted maps, bipolar-oriented maps, and mated-CRT maps—typically travels graph distance n 1 / d γ + o n (1) in n units of time, where d γ is the growth exponent for the volume of a metric ball on the map, which was shown to exist and depend only on γ by Ding and Gwynne (Commun Math Phys 374:1877–1934, 2018. arXiv:1807.01072). Since d γ > 2 , this shows that the simple random walk on each of these maps is subdiffusive. Our proofs are based on an embedding of the random planar maps under consideration into C wherein graph distance balls can be compared to Euclidean balls modulo subpolynomial errors. This embedding arises from a coupling of the given random planar map with a mated-CRT map together with the relationship of the latter map to SLE-decorated LQG. [ABSTRACT FROM AUTHOR]

We introduce and study a family of random processes on trees we call hipster random walks, special instances of which we heuristically connect to the min-plus binary trees introduced by Robin Pemantle and studied by Auffinger and Cable (Pemantle's Min-Plus Binary Tree, 2017. arXiv:1709.07849 [math.PR]), and to the critical random hierarchical lattice studied by Hambly and Jordan (Adv Appl Probab 36(3):824–838, 2004. 10.1239/aap/1093962236). We prove distributional convergence for the processes, after rescaling, by showing that their evolutions can be understood as a discrete analogues of certain convection–diffusion equations, then using a combination of coupling arguments and results from the numerical analysis literature on convergence of numerical approximations of PDEs. [ABSTRACT FROM AUTHOR]

We define a dynamical simple symmetric random walk in one dimension, and show that there almost surely exist exceptional times at which the walk tends to infinity. This is in contrast to the usual dynamical simple symmetric random walk in one dimension, for which such exceptional times are known not to exist. In fact we show that the set of exceptional times has Hausdorff dimension 1/2 almost surely, and give bounds on the rate at which the walk diverges at such times. We also show noise sensitivity of the event that our random walk is positive after n steps. In fact this event is maximally noise sensitive, in the sense that it is quantitatively noise sensitive for any sequence ε n such that n ε n → ∞ . This is again in contrast to the usual random walk, for which the corresponding event is known to be noise stable. [ABSTRACT FROM AUTHOR]

Let G be a Cayley graph of a nonamenable group with spectral radius ρ < 1 . It is known that branching random walk on G with offspring distribution μ is transient, i.e., visits the origin at most finitely often almost surely, if and only if the expected number of offspring μ ¯ satisfies μ ¯ ≤ ρ - 1 . Benjamini and Müller (Groups Geom Dyn, 6:231–247, 2012) conjectured that throughout the transient supercritical phase 1 < μ ¯ ≤ ρ - 1 , and in particular at the recurrence threshold μ ¯ = ρ - 1 , the trace of the branching random walk is tree-like in the sense that it is infinitely-ended almost surely on the event that the walk survives forever. This is essentially equivalent to the assertion that two independent copies of the branching random walk intersect at most finitely often almost surely. We prove this conjecture, along with several other related conjectures made by the same authors. A central contribution of this work is the introduction of the notion of local unimodularity, which we expect to have several further applications in the future. [ABSTRACT FROM AUTHOR]

We introduce a general technique for proving estimates for certain random planar maps which belong to the γ -Liouville quantum gravity (LQG) universality class for γ ∈ (0 , 2) . The family of random planar maps we consider are those which can be encoded by a two-dimensional random walk with i.i.d. increments via a mating-of-trees bijection, and includes the uniform infinite planar triangulation (UIPT; γ = 8 / 3 ); and planar maps weighted by the number of different spanning trees ( γ = 2 ), bipolar orientations ( γ = 4 / 3 ), or Schnyder woods ( γ = 1 ) that can be put on the map. Using our technique, we prove estimates for graph distances in the above family of random planar maps. In particular, we obtain non-trivial upper and lower bounds for the cardinality of a graph distance ball consistent with the Watabiki (Prog Theor Phys Suppl 114:1–17, 1993) prediction for the Hausdorff dimension of γ -LQG and we establish the existence of an exponent for certain distances in the map. The basic idea of our approach is to compare a given random planar map M to a mated-CRT map—a random planar map constructed from a correlated two-dimensional Brownian motion—using a strong coupling (Zaitsev in ESAIM Probab Stat 2:41–108, 1998) of the encoding walk for M and the Brownian motion used to construct the mated-CRT map. This allows us to deduce estimates for graph distances in M from the estimates for graph distances in the mated-CRT map which we proved (using continuum theory) in a previous work. In the special case when γ = 8 / 3 , we instead deduce estimates for the 8 / 3 -mated-CRT map from known results for the UIPT. The arguments of this paper do not directly use SLE/LQG, and can be read without any knowledge of these objects. [ABSTRACT FROM AUTHOR]

Let T be a supercritical Galton–Watson tree with a bounded offspring distribution that has mean μ > 1 , conditioned to survive. Let φ T be a random embedding of T into Z d according to a simple random walk step distribution. Let T p be percolation on T with parameter p, and let p c = μ - 1 be the critical percolation parameter. We consider a random walk (X n) n ≥ 1 on T p and investigate the behavior of the embedded process φ T p (X n) as n → ∞ and simultaneously, T p becomes critical, that is, p = p n ↘ p c . We show that when we scale time by n / (p n - p c) 3 and space by (p n - p c) / n , the process (φ T p (X n)) n ≥ 1 converges to a d-dimensional Brownian motion. We argue that this scaling can be seen as an interpolation between the scaling of random walk on a static random tree and the anomalous scaling of processes in critical random environments. [ABSTRACT FROM AUTHOR]