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

We study properties of a non-Markovian random walk $X_l^{(n)}$, $l =0,1,2,

…,n$,evolvingindiscretetime$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,\mathrm{.}\mathrm{.}\mathrm{.},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 \mathrm{\infty }$ it converges to a normal distribution with a smaller, compared to the conventional P'olya 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.