I have been reading about the topic motivated by a problem I read that asked for the first three digits of the sum of the LIS lengths in all permutations of length $n$. It is easy to see that we are really interested in the expected value of the LIS length in a random permutation of the first $n$ positive integers. A paper by Mike Phulsuksombati states $$l_n=2\sqrt{n}+cn^{1/6}+o(n^{1/6})$$ Where $c\approx-1.771088$ as a known asymptotic.

Questions: Is there a better asymptotic known? Is there a polynomial or logartihmic(in terms of $n$) time algorithm for finding $l_n$ or approximating it to a desired precision?

  • 6
    $\begingroup$ I am not sure if there is anything better than Baik-Deift-Johansson's seminal result. If there indeed is, Dan Romik's fantastic book devoted to this and more would be the place to begin. $\endgroup$ – user61318 Oct 10 '15 at 21:32
  • 5
    $\begingroup$ Dan Romik's book: The Surprising Mathematics of Longest Increasing Subsequences, Cambridge University Press, 2015. (Link to author page.) $\endgroup$ – Joseph O'Rourke Oct 11 '15 at 0:13
  • $\begingroup$ @user61318 and JosephORourke Thanks for the reference to such an interesting, recent, free book! I will update the post after giving it a read, hopefully having an answer to both questions. $\endgroup$ – chubakueno Oct 11 '15 at 1:25
  • $\begingroup$ Looking at the BDJ paper, I think one can likely make the little-o explicit (see (1.7), (1.8), and proof of 1.1 in Section 9), but I don't think it is sufficiently impressive looking to do so. But maybe I miss something. $\endgroup$ – kantelope Oct 11 '15 at 14:59

@user61318 and @JosephORourke, thanks for the advertisement for my book.

@chubakueono, as far as I know the answer to your questions are no and no. Pages 148-149 in my book have the state of the art (essentially the formula you wrote, along with some additional background) and the relevant references. However, in a broader sense much more is understood about the asymptotic formula for $l_n$ and where it comes from. The main important points as relates to your question are:

  1. The asymptotic formula for $l_n$ is closely related to a more detailed distributional limit for the random variable $L(\sigma_n)$ defined as the maximal length of an increasing subsequence in a uniformly random permutation $\sigma_n$ of order $n$. The result, known as the Baik-Deift-Johansson theorem, says that for any $t\in\mathbb{R}$, $$ \mathbb{P}\left( \frac{L(\sigma_n)-2\sqrt{n}}{n^{1/6}} \le t \right) \to F_2(t) \quad \textrm{as }n\to\infty, $$ where $F_2(t)$ is a certain probability distribution known as the Tracy-Widom distribution. $F_2(t)$ can be expressed explicitly as $$F_2(t) = \exp\left( -\int_x^\infty (x-t)q(x)^2\,dx \right), $$ where $q(x)$ is the unique solution to the Painleve II ODE $$y''(x)=2y(x)^3+xy(x)$$ with certain asymptotic boundary conditions.

  2. The constant $c$ in the asymptotic formula for $l_n=\mathbb{E}(L(\sigma_n))$ is simply the expected value of this distribution, that is $$ c = \int_{-\infty}^{\infty} x F_2'(x)\,dx. $$

  3. Proving a rate of convergence estimate in the asymptotic formula for $l_n$ would be extremely interesting (and, I suspect, difficult) and is an open problem as far as I know.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.