Step‑Reinforced Random Walks: From Mixing to Cover Times

Speaker: 秦硕（北京雁栖湖应用数学研究院）

Title: Step‑Reinforced Random Walks: From Mixing to Cover Times

Inviter: 随机分析中心

Language: English

Time & Venue: 2026年9月18日11:00–12:00 南楼613 

Abstract: A step‑reinforced random walk either repeats a uniformly chosen past increment or samples a fresh one. This simple rule creates long‑range dependence and generally makes the position process non‑Markovian. I will explain how a random recursive forest representation separates fresh randomness from memory, providing a common framework for mixing, transition probabilities, and covering. On finite groups, it yields exponential convergence to equilibrium; finer analysis reveals a phase transition and speedup on odd cycles, but a slowdown with cutoff on high‑dimensional hypercubes. On infinite groups, the same representation, combined with evolving sets, gives heat‑kernel bounds. Restarting the argument after stopping times then yields conditional estimates for elephant random walks, viewed as generalized step‑reinforced walks. On discrete tori in dimensions d ≥ 2, their cover times have the same order as those of simple random walk, while in dimension one reinforcement produces a phase transition and a separation between typical and mean scales.