Longest increasing subsequence as expectation of a simple nonlinear stochastic PDE with a low noise intensity

E. Katzav 1, S. Nechaev 2, O. Vasilyev 3, 4

Physical Review E: Statistical, Nonlinear, and Soft Matter Physics 75 (2007) 061113

We report some new observation concerning the statistics of Longest Increasing Subsequences (LIS). We show that the expectation of LIS, its variance, and apparently the full distribution function appears in statistical analysis of some simple nonlinear stochastic partial differential equation (SPDE) in the limit of very low noise intensity.

  • 1. Laboratoire de Physique Statistique de l'ENS (LPS),
    CNRS : UMR8550 – Université Paris VI - Pierre et Marie Curie – Université Paris VII - Paris Diderot – Ecole Normale Supérieure de Paris - ENS Paris
  • 2. Laboratoire de Physique Théorique et Modèles Statistiques (LPTMS),
    CNRS : UMR8626 – Université Paris XI - Paris Sud
  • 3. Max-Planck-Institut für Metallforschung,
    Max-Planck-Institut
  • 4. Institut für Theoretische und Angewandte Physik,
    Universität Stuttgart