We consider a class of infinite critical tree-indexed random walks on $\mathbb Z$, where the motion of particles is subject to vertex reinforcement. We mainly focus on the strong reinforcement regime, where we expect the process to localize almost surely on two sites. Part of our analysis includes the study of a time-dependent generalized P\'olya urn process, where the number of draws at each step is prescribed by a sequence $(\sigma_n)_{n\ge 1}$ of arbitrary positive integers, and the probability to pick a ball of a given color is proportional to a function of the {\it number} of balls of that color. In particular for bounded sequences $(\sigma_n)_{n\ge 1}$, we recover Rubin's characterization for the fixation of one color.
A vertex-reinforced random walk steps to a neighbour with probability proportional to $1+\beta n^{a}$, where $n$ counts previous visits to that neighbour and $a\in(0,1)$ sets the memory strength. On the rooted $b$-ary tree the exponential growth of the vertex set drives the walk outward while the reinforcement pulls it back. We report a sharp condensation transition of the occupation measure at a finite $\beta_c(a,b)$: below it the occupation spreads and the range grows linearly; above it a single vertex holds an $O(1)$ fraction of the time, stable in the observation time, while the range keeps growing very slowly, at a rate better described by $\log t$ than by any power. We do not find the range to be bounded, and keep this condensation distinct from finite-range localization. Four estimators locate the same threshold, which shows no systematic drift out to $t=3\times10^{7}$. In a frozen environment the walk is reversible, with edge conductances $c_{uv}=w_{u}w_{v}$, $w_{v}=1+\beta n_{v}^{a}$, and measure $\mu_{v}\propto w_{v}\sum_{u\sim v}w_{u}$ describing the condensed core, whose neighbour coupling we test directly. Reversibility places the escape at the frontier within the branching-number criterion for biased walks on trees, predicting $\beta_c\propto b-1$; the measured lines for $b=2,3,4$ collapse under division by $b-1$ to a few percent (bootstrap). The value $a=1/2$ that governs the walk on $\mathbb{Z}$ enters only as the marginal exponent of the condensed profile. Near $\beta_c$ the occupancy is non-self-averaging and bimodal, a coexistence-type phenomenology.
We study the linear growth rate of the range of size-conditioned Branching Random Walks (BRW) when the offspring distribution $\mu$ is critical and attracted to an $\alpha$-stable law. This is done via the infinite invariant BRW introduced by Le Gall&Lin and a new criterion which relates this growth rate of the range to a notion of dimension of the underlying tree in a general way. Then, in the transient case (that is, when the range does grow linearly), we extend the notion of branching capacity to this $\alpha$-stable case. We show that it is still related to the asymptotic probability that a BRW (or its infinite version) reaches a distant set in $\mathbb Z^d$, and we estimate the $\alpha$-stable branching capacity of balls.
We study the superdiffusive behavior of random walks on the randomly oriented Manhattan lattice, i.e., the $d$-dimensional integer lattice $\mathbb{Z}^d$ where each axis-aligned line is independently assigned a random direction (forward or backward) with equal probability. The walker takes nearest-neighbor steps, choosing an axis randomly and moving along the assigned direction of that axis's line, with equal probabilities for each axis. We show that, in the critical dimension $d=3$, the diffusion coefficient of the random walk diverges in the Tauberian sense as $\sqrt{\log t}$ with a multiplicative correction $(\log\log t)^{\pm(2+\varepsilon)}$ as time $t\to\infty$. This gives an answer to a conjecture by Ledger, T\'oth and Valk\'o (2018).
In this paper, we study the random walk on the symmetric group $\mathfrak{S}_n$ generated by the conjugacy class of $k$-cycles, where $2\le k=o(n/(\log n)^4)$. We prove that the walk exhibits hitting-time mixing: at the first time when every card has been touched, the distribution is already close to equilibrium. For odd $k$, the equilibrium measure is the uniform measure on $\mathfrak{A}_n$. For even $k$, the walk first mixes to the parity mixture determined by the hitting time, and in our range this mixture is asymptotically $U_{\mathfrak{S}_n}$. Our argument combines a refined fixed-time approximation for the random $k$-cycle walk near the cutoff window with an auxiliary marking scheme inspired by Jain-Sawhney's work (arXiv:2410.23944) on random transpositions. The main new feature is a parity-compatible coupling which handles both odd and even $k$-cycles in a unified framework. We also prove a hitting-time mixing result in the opposite regime $k\ge n-o(n^{1/2})$, and formulate a conjecture for all $2\le k\le n-1$.
Chen Shang, Jiahe Shen, Jiyue Zeng et al.· 1 citation
We consider a competition between two independent random walks on a cycle of length $N$. Each vertex is claimed by the walker that visits it first, and remains claimed thereafter. We prove that if the initial distance between the walkers is $d$, then the expected number of edges whose endpoints are claimed by different walkers is of order $\ln(1+N/d).$ This confirms the logarithmic dependence on $N/d$ predicted in Gomes Jr. et al. [Coloring of a one-dimensional lattice by two independent random walkers. Physica A: Statistical Mechanics and its Applications 225.1 (1996): 81-88].
S. Chatterjee, Nadya Nabahi, Grigory Terlov· 1 citation
Mixing time bounds for Markov chains play a central role in characterizing the sample complexity of learning and inference from correlated data. While the mixing behavior of symmetric random walks on standard graph structures such as cycles, tori, and hypercubes is well understood, the impact of transition asymmetry remains less explored. In this work, we study the mixing times of lazy, asymmetric random walks on cycles, tori, and hypercubes, motivated by their relevance in practical applications. For the $n$-cycle, we develop a novel coupling construction that yields an order-wise tight upper bound $O\left(\frac{n^{2}}{p+q}\right)$, explicitly capturing the dependence on asymmetric transition probabilities $p$ and $q$. Numerical results indicate that this dependence is highly accurate. Building on this result, we derive corresponding bounds for $d$-dimensional tori. For asymmetric random walks on $n$-dimensional hypercubes, motivated by applications, we consider the problem of estimating expectations of functions that depend only on a subset $\Delta \ll n$ of coordinates. We show that the effective sample complexity improves to $O(n \log \Delta)$, compared to $O(n \log n)$ for the full chain. In all cases, our bounds recover the tightest known results for symmetric walks as special cases.
Mrudula A Mahindrakar, Hrushikesh A Kant, Avhishek Chatterjee· International Conference on...· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
