Large deviations of the length of the longest increasing subsequence of random permutations and random walks
Large deviations of the length of the longest increasing subsequence of random permutations and random walks
复制标题
DOI：
10.1103/physreve.99.042104
复制
发表时间：
2019-04-02
影响因子：
2.4
通讯作者：
Hartmann, Alexander K.
中科院分区：
文献类型：
--
作者：
Boerjes, Joern;Schawe, Hendrik;Hartmann, Alexander K.
我们以数值方式研究随机排列和一维随机游走的最长递增子序列 (LIS) 的长度分布。使用复杂的大偏差算法，我们能够获得分布的很大一部分，特别是还覆盖小于 10(-1000) 的概率。这使我们能够验证随机排列的 LIS 的长度、速率函数的分析已知渐近性，甚至整个 Tracy-Widom 分布。我们观察到，在比典型部分更大的部分中，该限制分布的收敛速度相当快。对于随机游走的 LIS 的长度 L，我们不知道任何分析结果。我们测试了提出的缩放定律，并观察尾部收敛到崩溃以增加系统规模。此外，我们获得了两个尾部速率函数的前导行为的估计。
We study numerically the length distribution of the longest increasing subsequence (LIS) for random permutations and one-dimensional random walks. Using sophisticated large-deviation algorithms, we are able to obtain very large parts of the distribution, especially also covering probabilities smaller than 10(-1000). This enables us to verify for the length of the LIS of random permutations the analytically known asymptotics of the rate function and even the whole Tracy-Widom distribution. We observe a rather fast convergence in the larger than typical part to this limiting distribution. For the length L of LIS of random walks no analytical results are known to us. We test a proposed scaling law and observe convergence of the tails into a collapse for increasing system size. Further, we obtain estimates for the leading-order behavior of the rate functions in both tails.