We study properties of a non-Markovian random walk evolving in discrete time 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 natural series. We determine exactly the probability of finding the walker at position X at time moment l and show that this distribution converges to a Gaussian when l tends to infinity. The diffusion coefficient is, however, three times smaller than that of a conventional one-dimensional Polya walk. We formulate, as well, an auxiliary stochastic process whose distribution is identical to the distribution of the intermediate points of particle trajectories, which enables us to evaluate the probability measure of different excursions and to define the asymptotic distribution of the number of "turns" of walker trajectories.