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

We study properties of a non-Markovian random walk X_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⁽ⁿ⁾ 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 _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.