Records, range, and longest increasing subsequences of random walks

Abstract

The problem of the longest increasing subsequence (LIS) is to find an increasing subsequence of maximum length of a given finite sequence of elements drawn from a partially ordered set. The most classic problem of this kind is to determine the LIS of a random permutation. The complete resolution of this problem combined various approaches from different areas of mathematics and physics, culminating with the exact determination of the complete distribution function of the length of the LIS as the Tracy-Widom distribution for the largest eigenvalue of a Gaussian unitary ensemble. Recently, another version of the LIS problem has been posed: what is the behavior of the LIS of a random walk? Only a few results have been obtained about this problem so far. The goal of this project is to investigate in detail the LIS of random walks through a combination of numerical simulations and analytical approaches. We believe that this problem is representative of a whole family of problems involving correlated random variables for which there are many applications. Specifically, we intend (i) to investigate the scaling law of the length of the LIS of random walks with heavy-tailed step increments, (ii) to investigate the structure of the records and the range of random walks on Z, which can be considered as a proxy to the LIS in these cases, and (iii) to explore possible connections between the LIS problem for random walks and exactly integrable interacting particle systems, since there is, to date, no microscopic or hydrodynamic model to describe that quantity. (AU)