Research

Abstract: Under suitable moment assumptions, we show that a genuinely d-dimensional step-reinforced random walk undergoes a phase transition between recurrence and transience in dimensions d = 1, 2, and that it is transient for all reinforcement parameters in dimensions d ≥ 3, which solves a conjecture of Bertoin. 

Abstract: We consider a two-elephant walking model in which the elephants interact dynamically. At each time step, each elephant determines its next move randomly based on its partner’s past movements. We show that the asymptotic behavior of the elephants mainly depends on the product of their reinforcement parameters. In various regimes, we establish the law of large numbers and the central limit theorem. Our proofs are based on a connection to the random recursive trees and employ martingale methods.

Abstract: We prove a conjecture by Bertoin that the multidimensional elephant random walk on Z^d is transient in dimensions d ≥ 3. We show that it undergoes a phase transition in dimensions d = 1, 2, between recurrence and transience at p = (2d+1)/(4d). 

Abstract: We consider weakly reinforced Pólya urns on a countable graph of uniformly bounded degree. The vertices have positive bounded firing rates, which need not be bounded away from zero. For every reinforcement exponent α∈[0,1) and every deterministic choice of finite positive initial weights, the normalized edge weights converge almost surely, coordinate-wise, to a deterministic vector independent of the initial weights. We identify this vector as the unique non-vanishing equilibrium of the limiting equation. This proves the homogenization conjecture of Couzinié and Hirsch, including its formulation for non-uniform firing rates in the MATRIX open-problems report. The main step is a Liouville theorem for the limiting equation, established by a logarithmic-norm comparison of complete solutions using the row-sum balance at each vertex

Abstract: We prove that the planar balanced excited random walk M(2,1,2) is recurrent. This walk takes a horizontal simple random walk step on its first departure from each vertex and a planar simple random walk step on every later departure. Moreover, the number of distinct vertices visited before time n, multiplied by (\log n)/n, converges to \pi almost surely and in every L^p, 1\le p<\infty, the same limit as for the planar simple random walk. More generally, we prove recurrence of balanced excited random walks in spatially inhomogeneous cookie environments whenever the total positive and negative cookie strengths at each vertex are bounded by constants A, B with A+B<1+1/(2\pi +1).

Abstract: We study cover times on discrete tori and ranges on Z^d for elephant random walks with memory parameter p\in[0,1). In dimension one there is a phase transition at p=3/4. Away from criticality we determine the exact first-order asymptotics of the mean cover time, while at p=3/4 the mean is of order L^2/\sqrt{\log L}, a factor \sqrt{\log L} larger than the natural fluctuation scale L^2/\log L. We identify the limiting distribution under each of the three natural fluctuation normalizations. In dimensions d\geq2, for every fixed p<1, the cover time has the same order as for simple random walk, in expectation and with high probability. The leading constants also agree when p<(2d+1)/(4d), and at equality when d\geq3. For the range on Z^d, we prove L^1 convergence to the simple random walk asymptotics when d=2 and p<5/8, and for every p<1 when d\geq3. Finally, we give a cover-time upper bound for generalized step-reinforced random walks on finite groups in terms of a conditional L^\infty mixing profile.

Abstract: We study the mixing time of a non-Markovian process, the step-reinforced random walk (SRRW) on a finite group. This process differs from a classical random walk in that at each integer time, with probability α the next step is chosen uniformly from the previous steps of the walk. We prove that the distribution of the SRRW converges to the uniform distribution exponentially fast if the walk is irreducible and aperiodic. When the step distribution is either symmetric, a class function, or has an atom at the identity, we relate the mixing time of the SRRW to the spectral gap and the mixing time of the underlying walk. For the reinforced (lazy) simple random walk on L-cycles, we show that the mixing time undergoes a phase transition at α = 1/2 and the reinforcement reduces the mixing time to order L^{1/\alpha} for α >1/2. On the d-dimensional hypercube, the reinforcement slows down mixing, and the SRRW exhibits cutoff as d\to\infty at time d\log(d)/[F(α)(1-α)], with an O(d) window for each fixed \alpha \in (0,1), where F(\cdot) is a hypergeometric function. 

Abstract: The step-reinforced random walk (SRRW) either repeats a uniformly chosen past step or takes a fresh independent step. We consider a generalized SRRW on groups, where the selected past step is transformed by a random map. The transformations are independent of the fresh steps but may be dependent on one another.

For every reinforcement parameter α<1, we obtain upper bounds on transition probabilities in terms of the geometry of the group. On R^d, a non-singular step distribution yields bounds of order n^{-d/2} for balls of any fixed radius, uniformly over their centers and without any moment assumption, and hence transience for d ≥ 3. On finitely generated groups, we give bounds in terms of the isoperimetric profile. We also prove exponential decay for the elephant random walk on every nonamenable Cayley graph with a finite symmetric generating set and every memory parameter p<1. In particular, this answers a question of Mukherjee for Cayley trees.

Abstract: A gambler starts with fortune x and unit bet, doubling the target bet after wins and halving it after losses, with actual bets capped by the current fortune. Rounds are won independently with probability p \in (0,1). We prove that the survival probability f(x,p) is positive exactly when x>2 and p<1/2. For fixed x>2, f(x,\cdot) is strictly decreasing and real analytic on (0,1/2): playing a more favourable game lowers the chance of surviving it. For fixed p\in(0,1/2), f(\cdot,p) is strictly increasing and singular continuous on [2,\infty). We give an explicit global Hölder exponent and determine the pointwise exponent at x=2. An exact finite computation shows that the optimal global exponent is strictly smaller than the boundary exponent for p<1/2 sufficiently close to 1/2. We also give the complete phase diagram for unequal multipliers. 

Abstract: For the interacting urn model with polynomial reinforcement, it has been conjectured that almost surely one color monopolizes all the urns if the interaction parameter p > 0. We disprove the conjecture. For the case p = 1, we give a sufficient condition for monopoly, which improves a result obtained by Launay. 

Abstract: We introduce the continuous-time vertex-reinforced random walk (cVRRW) as a continuous-time version of the vertex-reinforced random walk (VRRW). On a complete-like graph Kd ∪ ∂Kd, we show that the cVRRW a.s. spends finite time on leaves and equal time on each of the non-leaf vertices up to a convergent error term. For the VRRW, we provide estimates on the rate of convergence of the empirical occupation measure, which, in particular, verifies a conjecture by Limic and Volkov that the true convergence rate is of order n^{-1/(d−1)}.