Random walk generated by random permutations of {1,2,3, ..., n+1}

Abstract

We study properties of a non-Markovian random walk $X_l^{(n)}$, $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 \text{rise-and-descent} sequences characterizing random permutations $\pi$ 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\to \infty$ 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 identic to the distribution of the intermediate points $X_l^{(n)}$, $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.

text shortened, new results added, appearing in J. Phys. A

References in corpus (3)

• An Anisotropic Ballistic Deposition Model with Links to the Ulam Problem and the Tracy-Widom Distribution
• J/psi production via initial state radiation in e+ e- --> mu+ mu- gamma at an e+e- center-of-mass energy near 10.6 GeV
• Longest increasing subsequences in pattern-restricted permutations

Cited by in corpus (9)

• Frozen shuffle update for an asymmetric exclusion process on a ring
• The Statistics of the Number of Minima in a Random Energy Landscape
• Zigzag diagrams and Martin boundary
• Phase Transition in a Random Minima Model: Mean Field Theory and Exact Solution on the Bethe Lattice
• Random patterns generated by random permutations of natural numbers
• Dynamic Space Packing
• The quasispecies distribution
• A fractal set from the binary reflected Gray code
• Coherent permutations with descent statistic and the boundary problem for the graph of zigzag diagrams