2020/11/28 by Jean Bertoin, Bertoin, Jean · 4 citations
Computer Science · Mathematics · #05A05 #05C05 #60F05 #60G50 #Advanced Database Systems and Queries #Combinatorics (math.CO) #Data Management and Algorithms #FOS: Mathematics #Probability (math.PR) #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.2011.14069
openalex publication_date 2020/11/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A random walk with counterbalanced steps is a process of partial sums \check S(n)=\check X1+ ⋯ + \check Xn whose steps \check Xn are given recursively as follows. For each n≥ 2, with a fixed probability p, \check Xn is a new independent sample from some fixed law μ, and with complementary probability 1-p, \check Xn= -\check Xv(n) counterbalances a previous step, with v(n) a uniform random pick from \1, …, n-1\. We determine the asymptotic behavior of \check S(n) in terms of p and the first two moments of μ. Our approach relies on a coupling with a reinforcement algorithm due to H.A. Simon, and on properties of random recursive trees and Eulerian numbers, which may be of independent interest. The method can be adapted to the situation where the step distribution μ belongs to the domain of attraction of a stable law.