Random patterns generated by random permutations of natural numbers
Physique Théorique de la Matière Condensée (UMR 7600), Université Pierre et Marie Curie – Paris 6, 4 place Jussieu, 75252 Paris, France
2 Department of Inhomogeneous Condensed Matter Theory, Max-Planck-Institute für Metallforschung, Heisenbergstrasse 3, 0569 Stuttgart, Germany
3 LPTMS, Université Paris Sud, 91405 Orsay Cedex, France
4 LITIS/LIFAR, Université de Rouen, 76801 Saint Étienne du Rouvray, France
We survey recent results on some one- and two-dimensional patterns generated by random permutations of natural numbers. In the first part, we discuss properties of random walks, evolving on a one-dimensional regular lattice in discrete time n, whose moves to the right or to the left are prescribed by the rise-and-descent sequence associated with a given random permutation. We determine exactly the probability of finding the trajectory of such a permutation-generated random walk at site X at time n, obtain the probability measure of different excursions and define the asymptotic distribution of the number of “U-turns" of the trajectories - permutation “peaks" and “through". In the second part, we focus on some statistical properties of surfaces obtained by randomly placing natural numbers 1,2,3, ...,L on sites of a 1d or 2d lattices containing L sites. We calculate the distribution function of the number of local “peaks" - sites the number at which is larger than the numbers appearing at nearest-neighboring sites - and discuss surprising collective behavior emerging in this model.
© EDP Sciences, Springer-Verlag, 2007