Random patterns generated by random permutations of natural numbers

G. Oshanin 1, 2, R. Voituriez 1, S. Nechaev 3, O. Vasilyev 2, Florent Hivert 4

The European Physical Journal Special Topics 143 (2007) 143-157

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 induced 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 square 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 some surprising collective behavior emerging in this model.

  • 1. Laboratoire de Physique Théorique de la Matière Condensée (LPTMC),
    CNRS : UMR7600 – Université Paris VI - Pierre et Marie Curie
  • 2. Department of Inhomogeneous Condensed Matter Theory,
    Max-Planck-Institut
  • 3. Laboratoire de Physique Théorique et Modèles Statistiques (LPTMS),
    CNRS : UMR8626 – Université Paris XI - Paris Sud
  • 4. Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes (LITIS),
    Institut National des Sciences Appliquées (INSA) - Rouen – Université du Havre – Université de Rouen : EA4108