BZPEER

preprint2026arXiv

Stationary hitting times on vertex-transitive graphs

We prove a refined version of the Aldous and Brown's exponential approximation of stationary hitting times. These are valid for all reversible Markov chains. We then specialise our estimates for vertex-transitive graphs, where we obtain improved bounds which depend on the growth of the graphs. The most delicate cases are when the diameter is comparable to that of low-dimensional tori. In particular, in "dimensions" less than four (up to logarithmic factors) our error terms are the square of those of Aldous and Brown. These improved bounds play a crucial role in the companion work arXiv:2202.02255 characterising the fluctuations of the cover time on vertex-transitive graphs.

preprint2022arXiv

Mean Field Behavior during the Big Bang Regime for Coalescing Random Walks

In this paper we consider coalescing random walks on a general connected graph $G=(V,E)$ . We set up a unified framework to study the leading order of the decay rate of $P_t$ , the expectation of the fraction of occupied sites at time $t$ , particularly for the `Big Bang' regime where $t\ll t_{\text{coal}}:=\mathbb{E}[\inf\{s:\text{There is only one particle at time }s\}]$ . Our results show that $P_t$ satisfies certain mean field behavior, if the graphs satisfy certain transience-like conditions. We apply this framework to two families of graphs: (1) graphs given by the configuration model with a degree distribution supported in $[3,\bar d]$ for some $\bar d\geq 3$ , and (2) finite and infinite vertex-transitive graphs. In the first case, we show that for $1 \ll t \ll |V|$ , $P_t$ decays in the order of $t^{-1}$ , and $(tP_t)^{-1}$ is approximately the probability that two particles starting from the root of the corresponding unimodular Galton-Watson tree never collide after one of them leaves the root, which is also roughly $|V|/(2t_{\text{meet}})$ , where $t_{\text{meet}}$ is the mean meeting time of two walkers. By taking the local weak limit, for the unimodular Galton-Watson tree we prove the convergence of $tP_t$ as $t\to\infty$ . For the second family of graphs, if we take a sequence of finite graphs $G_n=(V_n, E_n)$ , such that $t_{\text{meet}}=O(|V_n|)$ and the inverse of the spectral gap $t_{\text{rel}}$ is $o(|V_n|)$ , then for $t_{\text{rel}}\ll t\ll t_{\text{coal}}$ , $(tP_t)^{-1}$ is approximately the probability that two random walks never meet before time $t$ , and also $|V|/(2t_{\text{meet}})$ . In addition, we define a natural uniform transience condition, and show that it implies the above for all $1\ll t\ll t_{\text{coal}}$ . Such estimates of $tP_t$ are also obtained for all infinite transient transitive unimodular graphs, in particular, all transient transitive amenable graphs.

preprint2022arXiv

Some inequalities for reversible Markov chains and branching random walks via spectral optimization

We present results relating mixing times to the intersection time of branching random walk (BRW) in which the logarithm of the expected number of particles grows at rate of the spectral-gap $\mathrm{gap}$ . This is a finite state space analog of a critical branching process. Namely, we show that the maximal expected hitting time of a state by such a BRW is up to a universal constant larger than the $L_{\infty}$ mixing-time, whereas under transitivity the same is true for the intersection time of two independent such BRWs. Using the same methodology, we show that for a sequence of reversible Markov chains, the $L_{\infty}$ mixing-times $t_{\mathrm{mix}}^{(\infty)}$ are of smaller order than the maximal hitting times $t_{\mathrm{hit}}$ iff the product of the spectral-gap and $t_{\mathrm{hit}}$ diverges, by establishing the inequality $t_{\mathrm{mix}}^{(\infty)} \le \frac{1}{\mathrm{gap}}\log(et_{\mathrm{hit}} \cdot \mathrm{gap})$ . This resolves a conjecture of Aldous and Fill (Reversible Markov chains and random walks on graphs, Open Problem 14.12) asserting that under transitivity the condition that $t_{\mathrm{hit}} \gg \frac{1}{\mathrm{gap}}$ implies mean-field behavior for the coalescing time of coalescing random walks.

preprint2021arXiv

Cutoff for Random Walks on Upper Triangular Matrices

Consider the random Cayley graph of a finite group $G$ with respect to $k$ generators chosen uniformly at random, with $1 \ll \log k \ll \log |G|$ (ie $1 \ll k = |G|^{o(1)}$ ). A conjecture of Aldous and Diaconis (1985) asserts, for $k\gg\log|G|$ , that the random walk on this graph exhibits cutoff. When $\log k \lesssim \log\log|G|$ (ie $k = (\log |G|)^{\mathcal O(1)}$ ), the only example of a non-Abelian group for which cutoff has been established is the dihedral group. We establish cutoff (as $p\to infty$ ) for the group of $d \times d$ unit upper triangular matrices with integer entries modulo $p$ (prime), which we denote $U_{p,d}$ , for fixed $d$ or $d$ diverging sufficiently slowly. We allow $1 \ll k \lesssim \log |U_{p,d}|$ as well as $k\gg\log|U_{p,d}|$ . The cutoff time is $\max\{\log_k |U_{p,d}|, \: s_0 k\}$ , where $s_0$ is the time at which the entropy of the random walk on $\mathbb Z$ reaches $(\log |U_{p,d}^\mathrm{ab}|)/k$ , where $U_{p,d}^\mathrm{ab} \cong \mathbb Z_p^{d-1}$ is the Abelianisation of $U_{p,d}$ . When $1 \ll k \ll \log |U_{p,d}^\mathrm{ab}|$ and $d \asymp 1$ , we find the limit profile. We also prove highly related results for the $d$ -dimensional Heisenberg group over $\mathbb Z_p$ . The Aldous--Diaconis conjecture also asserts, for $k gg\log |G|$ , that the cutoff time should depend only on $k$ and $|G|$ . This was verified for all Abelian groups. Our result shows that this is not the case for $U_{p,d}$ : the cutoff time depends on $k$ , $|U_{p,d}| = p^{d(d-1)/2}$ and $|U_{p,d}^\mathrm{ab}|=p^{d-1}$ . We also show that all but $o(|U_{p,d}|)$ of the elements of $U_{p,d}$ lie at graph distance $M \pm o(M)$ from the identity, where $M$ is the minimal radius of a ball in $\mathbb Z^k$ of cardinality $|U_{p,d}^\mathrm{ab}| = p^{d-1}$ . Finally, we show that the diameter is also asymptotically $M$ when $k \gtrsim \log |U_{p,d}^\textrm{ab}|$ and $d\asymp1$ .

preprint2021arXiv

Further Results and Discussions on Random Cayley Graphs

Consider the random Cayley graph of a finite group $G$ with respect to $k$ generators chosen uniformly at random, with $1 \ll k \lesssim \log |G|$ . The results of this article supplement those in the three main papers on random Cayley graphs. The majority of the results are inspired by a `universality' conjecture of Aldous and Diaconis (1985). To start, we study the limit profile of cutoff for the simple random walk on this random graph, as well as a detailed investigation into mixing properties when $G = \mathbb Z_p^d$ with $p$ prime. We then exposit a proof of Diaconis and Saloff-Coste (1994) establishing lack of cutoff when $k \asymp 1$ . We move onto discussing material from our companion paper on matrix groups. We then study distance of a typical element of $G$ from the identity in an $L_q$ -type graph distance in the Abelian set-up. Finally, we give necessary and sufficient conditions for $k$ independent uniform elements of $G$ to generate $G$ , ie for the random Cayley graph to be connected, based on work of Pomerance (2001). The aforementioned results all hold with high probability over the random Cayley graph.

preprint2021arXiv

Supplementary Material for Random Cayley Graphs Project

This document contains supplementary material for the main articles in our Random Cayley Graphs project. We prove refined results about simple random walks on the integers and on the cycle. We are primarily interested in the entropy of these random walks at certain times and how this entropy changes when the time changes slightly. Additionally, we prove some large deviation and exit time estimates. We prove some results on the size of discrete lattice balls and how this size changes when the radius changes slightly. We do this in a general $L_q$ norm, with $q \in [1,\infty]$ . We also prove some other technical results deferred from the main papers. We hope that some of the results, particularly the simple random walk estimates, will be useful in their own right for other researchers.

preprint2021arXiv

The interchange process on high-dimensional products

We resolve a long-standing conjecture of Wilson (2004), reiterated by Oliveira (2016), asserting that the mixing-time of the unit-rate Interchange Process on the $n$ -dimensional hypercube is of order $n$ . This follows from a sharp inequality established at the level of Dirichlet forms, from which we also deduce that macroscopic cycles emerge in constant time, and that the log-Sobolev constant of the exclusion process is of order $1$ . Beyond the hypercube, our results apply to cartesian products of arbitrary graphs of fixed size, shedding light on a broad conjecture of Oliveira (2013).

preprint2020arXiv

A comparison principle for random walk on dynamical percolation

We consider the model of random walk on dynamical percolation introduced by Peres, Stauffer and Steif (2015). We obtain comparison results for this model for hitting and mixing times and for the spectral-gap and log-Sobolev constant with the corresponding quantities for simple random walk on the underlying graph $G$ , for general graphs. When $G$ is the torus $\mathbb{Z}_n^d$ , we recover the results of Peres et al. and we also extend them to the critical case. We also obtain bounds in the cases where $G$ is a transitive graph of moderate growth and also when it is the hypercube.

preprint2020arXiv

Modified log-Sobolev inequalities for strong-Rayleigh measures

We establish universal modified log-Sobolev inequalities for reversible Markov chains on the boolean lattice $\{0,1\}^n$ , under the only assumption that the invariant law $π$ satisfies a form of negative dependence known as the stochastic covering property. This condition is strictly weaker than the strong Rayleigh property, and is satisfied in particular by all determinantal measures, as well as any product measure over the set of bases of a balanced matroid. In the special case where $π$ is $k-$ homogeneous, our results imply the celebrated concentration inequality for Lipschitz functions due to Pemantle & Peres (2014). As another application, we deduce that the natural Monte-Carlo Markov Chain used to sample from $π$ has mixing time at most $kn\log\log\frac{1}{π(x)}$ when initialized in state $x$ . To the best of our knowledge, this is the first work relating negative dependence and modified log-Sobolev inequalities.

preprint2020arXiv

The exclusion process mixes (almost) faster than independent particles

Oliveira conjectured that the order of the mixing time of the exclusion process with $k$ -particles on an arbitrary $n$ -vertex graph is at most that of the mixing-time of $k$ independent particles. We verify this up to a constant factor for $d$ -regular graphs when each edge rings at rate $1/d$ in various cases: (1) when $d = Ω( \log_{n/k} n)$ , (2) when $\mathrm{gap}:=$ the spectral-gap of a single walk is $O ( 1/\log^4 n)$ and $k \ge n^{Ω(1)}$ , (3) when $k \asymp n^{a}$ for some constant $0<a<1$ . In these cases our analysis yields a probabilistic proof of a weaker version of Aldous' famous spectral-gap conjecture (resolved by Caputo et al.). We also prove a general bound of $O(\log n \log \log n / \mathrm{gap})$ , which is within a $\log \log n$ factor from Oliveira's conjecture when $k \ge n^{Ω(1)}$ . As applications we get new mixing bounds: (a) $O(\log n \log \log n)$ for expanders, (b) order $d\log (dk)$ for the hypercube $\{0,1\}^d$ , (c) order $(\mathrm{Diameter})^2 \log k$ for vertex-transitive graphs of moderate growth and for supercritical percolation on a fixed dimensional torus.

Jonathan Hermon

Research overview

Is this your work?

10 publications

Stationary hitting times on vertex-transitive graphs

Mean Field Behavior during the Big Bang Regime for Coalescing Random Walks

Some inequalities for reversible Markov chains and branching random walks via spectral optimization

Cutoff for Random Walks on Upper Triangular Matrices

Further Results and Discussions on Random Cayley Graphs

Supplementary Material for Random Cayley Graphs Project

The interchange process on high-dimensional products

A comparison principle for random walk on dynamical percolation

Modified log-Sobolev inequalities for strong-Rayleigh measures

The exclusion process mixes (almost) faster than independent particles

See the researcher in context

Building this map preview