论文标题
有多少最长的子序列有多少？
How many longest increasing subsequences are there?
论文作者
论文摘要
我们研究了最长增加子序列（LIS）的熵$ s $，即不同LI的对数。我们考虑了两个序列的集合，即从有限数量的不同整数中绘制的整数和序列的随机排列。使用复杂的算法，我们能够准确计算每个给定序列的LIS数量。此外，我们不仅要测量所考虑的序列集合的平均值和差异，而且还以很高的精度对概率分布的很大一部分$ p（s）$进行采样。特别是，我们能够观察到极少数事件的尾巴，这些事件的概率小于$ 10^{-600} $。我们表明，LIS的熵的分布大约是高斯，而远端的偏差可能会在长序列的极限中消失。此外，我们提出了一个最适合我们观察到的数据的大驱动率函数。
We study the entropy $S$ of longest increasing subsequences (LIS), i.e., the logarithm of the number of distinct LIS. We consider two ensembles of sequences, namely random permutations of integers and sequences drawn i.i.d.\ from a limited number of distinct integers. Using sophisticated algorithms, we are able to exactly count the number of LIS for each given sequence. Furthermore, we are not only measuring averages and variances for the considered ensembles of sequences, but we sample very large parts of the probability distribution $p(S)$ with very high precision. Especially, we are able to observe the tails of extremely rare events which occur with probabilities smaller than $10^{-600}$. We show that the distribution of the entropy of the LIS is approximately Gaussian with deviations in the far tails, which might vanish in the limit of long sequences. Further we propose a large-deviation rate function which fits best to our observed data.
