2003/12/31 by Gleb Oshanin, G. Oshanin, Raphaël Voituriez +1
Computer Science · Mathematics · Physics and Astronomy · #Bayesian Methods and Mixture Models #Combinatorics #Discrete mathematics #Distribution (mathematics) #Lattice (music) #Mathematical analysis #Mathematics #Permutation (music) #Physics #Random Matrices and Applications #Random permutation #Random walk #Statistics #Stochastic processes and statistical mechanics #cond-mat.stat-mech #math.PR
paper · pdf · doi:10.1088/0305-4470/37/24/002
text shortened, new results added, appearing in J. Phys. A
arxiv created 2004/05/03 · openalex publication_date 2004/06/03 · arxiv updated 2009/12/01 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/05
We study properties of a non-Markovian random walk X ( n ) l , l = 0, 1, 2, …, n , evolving in discrete time l on a one-dimensional lattice of integers, whose moves to the right or to the left are prescribed by the rise-and-descent sequences characterizing random permutations π of [ n + 1] = 1, 2, 3, …, n + 1. We determine exactly the probability of finding the end-point X n = X ( n ) n of the trajectory of such a permutation-generated random walk (PGRW) at site X , and show that in the limit n → ∞ it converges to a normal distribution with a smaller, compared to the conventional Pólya random walk, diffusion coefficient. We formulate, as well, an auxiliary stochastic process whose distribution is identical to the distribution of the intermediate points X ( n ) l , l < n , which enables us to obtain the probability measure of different excursions and to define the asymptotic distribution of the number of ‘turns’ of the PGRW trajectories.