论文标题
stirling型公式，用于分布最长的子序列长度的分布
A Stirling-type formula for the distribution of the length of longest increasing subsequences
论文作者
论文摘要
在$ n $整数的随机排列中，最长增加子序列长度的离散分布与随机矩阵理论密切相关。在开创性的工作中，Baik，Deift和Johansson就GUE的大型基质极限的最大水平的分布提供了渐近学。但是，作为数值近似，这种渐近学对于小$ n $不准确，并且收敛速度较慢，猜想仅为$ n^{ - 1/3} $的顺序。在这里，我们建议基于海曼对斯特林公式的概括的不同类型的近似。这样的公式已经为$ n $的长度分布提供了几个正确的数字，$ n $的$ 20 $，但允许数值评估，并以明显的顺序$ n^{ - 2/3} $的均匀误差，$ n $，$ 10^{12} $;因此，缩小了精确值表（最多$ n = 1000 $）和随机矩阵限制之间的差距。与蒙特 - 卡洛模拟相比，Stirling-type公式更有效，更准确，可以准确地了解对随机矩阵限制的前几个有限尺寸校正项。由此，我们得出了长度的预期价值和差异的扩展，表现出比先前提出的多个术语。
The discrete distribution of the length of longest increasing subsequences in random permutations of $n$ integers is deeply related to random matrix theory. In a seminal work, Baik, Deift and Johansson provided an asymptotics in terms of the distribution of the scaled largest level of the large matrix limit of GUE. As a numerical approximation, however, this asymptotics is inaccurate for small $n$ and has a slow convergence rate, conjectured to be just of order $n^{-1/3}$. Here, we suggest a different type of approximation, based on Hayman's generalization of Stirling's formula. Such a formula gives already a couple of correct digits of the length distribution for $n$ as small as $20$ but allows numerical evaluations, with a uniform error of apparent order $n^{-2/3}$, for $n$ as large as $10^{12}$; thus closing the gap between a table of exact values (compiled for up to $n=1000$) and the random matrix limit. Being much more efficient and accurate than Monte-Carlo simulations, the Stirling-type formula allows for a precise numerical understanding of the first few finite size correction terms to the random matrix limit. From this we derive expansions of the expected value and variance of the length, exhibiting several more terms than previously put forward.
