A numerical investigation into the scaling behavior of the longest increasing subsequences of the symmetric ultra-fat tailed random walk

Abstract

The longest increasing subsequence (LIS) of a sequence of correlated random variables is a basic quantity with potential applications that has started to receive proper attention only recently. Here we investigate the behavior of the length of the LIS of the so-called symmetric ultra-fat tailed random walk, introduced earlier in an abstract setting in the mathematical literature. After explicit constructing the ultra-fat tailed random walk, we found numerically that the expected length $L_n$ of its LIS scales with the length $n$ of the walk like $⟨L_n⟩\sim n^{0.716}$, indicating that, indeed, as far as the behavior of the LIS is concerned the ultra-fat tailed distribution can be thought of as equivalent to a very heavy tailed $\alpha$-stable distribution. We also found that the distribution of $L_n$ seems to be universal, in agreement with results obtained for other heavy tailed random walks.

arXiv commentA brief report on the LIS of ultra-fat tailed random walks, the construction of which may be of independent interest. Accepted for publication in Physics Letters A (2020)

References in corpus (8)

• More rigorous results on the Kauffman-Levin model of evolution
• Large deviations of the length of the longest increasing subsequence of random permutations and random walks
• Increasing subsequences of random walks
• How many longest increasing subsequences are there?
• Empirical scaling of the length of the longest increasing subsequences of random walks
• Asymptotic behavior of the length of the longest increasing subsequences of random walks
• Results and conjectures on a toy model of depinning
• Pemantle's min-plus binary tree

Cited by in corpus (2)

• Finite-depth scaling and an exact Bernoulli-leaf identity for the min-plus process on the binary tree
• Longest weakly increasing subsequences of discrete random walks on the integers with heavy tailed distribution of increments