Longest weakly increasing subsequences of discrete random walks on the integers with heavy tailed distribution of increments

This paper investigates the scaling behavior and distributional properties of the longest weakly increasing subsequences in discrete random walks with heavy-tailed increments, finding that the average length scales as $\sqrt{n}\log{n}$ for finite variance cases and as $n^\theta$ (with $\theta > 0.5$) for infinite variance cases, while the overall distribution is well-approximated by a lognormal model.

The Gist

The Big Picture: Finding the Longest "Upward" Path

Imagine you are watching a drunk person (a "random walker") stumbling along a number line. Every second, they take a step forward or backward. Sometimes they take tiny steps (1 or 2 units), but sometimes, if the distribution is "heavy-tailed," they might take a giant leap of 100 or 1,000 units in a single bound.

The researchers in this paper asked a specific question: If you look at the entire path this walker took, what is the longest sequence of steps where they never went down?

They call this the Longest Weakly Increasing Subsequence (Weak LIS).

• "Weakly" means they can stay flat (step 5, then step 5 again) or go up (step 5, then step 6). They just can't go down.
• "Subsequence" means you don't have to pick every single step; you can skip the ones where they stumbled backward, as long as the ones you do pick go up or stay level.

Think of it like a hiking trail. You want to find the longest stretch of the trail where you are either climbing up or walking on flat ground, ignoring all the times the path dips into a valley.

The Two Types of Walkers

The paper studies two main types of walkers, based on how likely they are to take giant leaps:

1. The "Normal" Walker (Finite Variance): This walker usually takes small steps. Giant leaps are extremely rare. If you watch them for a long time, their path looks like a smooth, wiggly line.
2. The "Wild" Walker (Heavy-Tailed): This walker is chaotic. While they take small steps most of the time, they have a high chance of suddenly taking a massive leap. Their path looks like a jagged, erratic scribble with huge spikes.

The researchers used a parameter called $\alpha$ (alpha) to measure how "wild" the walker is.

• Low $\alpha$ (e.g., 0.5 or 1): The walker is very wild. Giant leaps happen often.
• High $\alpha$ (e.g., 3 or 10): The walker is tame. Giant leaps are so rare they almost never happen, and the walker behaves like a standard "Simple Random Walk" (just tiny steps of 1 or -1).

The Discovery: How Fast Does the Path Grow?

The main goal was to figure out how the length of this "longest upward path" grows as the walker takes more and more steps ($n$).

1. When the Walker is Wild ($\alpha \le 2$)

The Analogy: Imagine a monkey climbing a tree that has huge, irregular branches. Because the branches are so far apart and unpredictable, the monkey can find a very long path by jumping from one high branch to another, skipping the low ones.

The Result: The length of the path grows like a power law ($n^\theta$).

• The exponent $\theta$ is greater than 0.5.
• The "wilder" the walker (lower $\alpha$), the longer the path becomes relative to the total steps.
• Key Finding: For the wildest walkers, the path length grows significantly faster than the square root of the total steps.

2. When the Walker is Tame ($\alpha \ge 2$)

The Analogy: Imagine a person walking on a flat sidewalk. They take small steps. Sometimes they step on a crack (a flat spot), sometimes they step up a curb. Because the steps are small and regular, the "longest upward path" is limited by the fact that they can't jump far.

The Result: The length of the path grows like $\sqrt{n} \times \log(n)$.

• This is the "Square Root" rule, but with a special "logarithmic bonus."
• The Surprise: The researchers found that because the walker is on integers (whole numbers like 1, 2, 3), they often land on the exact same number twice in a row (e.g., step 5, then step 5 again).
• The "Plateau" Effect: In a continuous world (where you can step 5.001), you rarely land on the exact same spot twice. But on a grid of integers, you get "plateaus." These flat spots allow the "Weak LIS" to stretch out longer than expected. It's like finding a long, flat hallway in a building; you can walk a long distance without going up or down, which counts toward your "non-decreasing" score.

The Shape of the Data: The "Lognormal" Mystery

The researchers didn't just look at the average length; they looked at the distribution of all the possible paths.

The Analogy: Imagine you have a bag of 10,000 different hiking trails. Most are medium length, a few are very short, and a few are incredibly long.

• If you plot the lengths, they don't look like a perfect bell curve (Normal distribution).
• Instead, they look like a Lognormal distribution.

What does that mean?
Think of a lognormal distribution as a "multiplicative" shape. It's very common in nature for things that grow by multiplying (like bacteria populations or compound interest). The researchers found that the length of these paths behaves as if it were the result of many small multiplicative factors, even though the math of the path is additive.

They also noticed that the "tails" of this distribution (the extremely long or short paths) are slightly "lighter" than a perfect bell curve. It's as if the universe has a safety valve that prevents the path from becoming too extreme in either direction.

Why This Matters

1. Discrete vs. Continuous: Previous studies looked at "continuous" walkers (where you can step 5.0001). This paper proves that when you force the walker to stick to whole numbers (integers), the math changes. The "plateaus" (landing on the same number twice) create a logarithmic correction that makes the path longer.
2. The "Crossover": There is a tipping point at $\alpha = 2$.
   • Below 2: The path is wild and follows a power law.
   • Above 2: The path becomes tame and follows the square-root-plus-log rule.
3. The Conjecture: The authors propose that for any random walk, the length of this longest path is likely described by a Lognormal distribution. This is a new idea that could help statisticians and computer scientists predict how long these sequences will be in data streams, financial markets, or biological sequences.

Summary in One Sentence

By simulating millions of random walkers on a number line, the authors discovered that when the walker is "wild," the longest upward path grows very fast, but when the walker is "tame," the path grows slower but gets a boost from the fact that the walker often lands on the same whole number twice, creating flat spots that extend the path.

Technical Summary

1. Problem Statement

The paper investigates the scaling behavior of the length ($L_n$) of the Longest Weakly Increasing Subsequence (weak LIS) in $n$-step discrete random walks on the integers.

• Context: While the LIS of random permutations (Ulam's problem) and continuous random walks is well-studied, the behavior of the weak LIS in discrete random walks with heavy-tailed increment distributions remains less explored.
• Specifics: The authors study symmetric random walks where step increments $X_i$ follow a heavy-tailed distribution proportional to $|k|^{-1-\alpha}$ (a discrete Pareto/Zipf distribution) for various tail indices $\alpha > 0$.
• Key Distinction: The study focuses on the difference between weak LIS (allowing equal values, $S_{i_1} \le \dots \le S_{i_L}$) and strict LIS. In discrete walks, the ability to include equal values (plateaus) significantly alters the combinatorics compared to continuous walks.
• Goal: To determine the asymptotic scaling of the sample average length $\langle L_n \rangle$ as a function of $n$ and $\alpha$, specifically distinguishing between power-law scaling ($n^\theta$) and logarithmic corrections ($\sqrt{n} \log n$).

2. Methodology

The authors employed a rigorous numerical approach combining large-scale Monte Carlo simulations with advanced statistical model selection.

• Data Generation:

  • Generated $10,000$ independent random walks for 13 different walk lengths ($n$ ranging from $10^4$ to $10^8$).
  • Tested tail indices $\alpha \in \{0.5, 1, 1.5, 2, 3, 5, 10\}$ and a Simple Random Walk (SRW, $\pm 1$ steps) for comparison.
  • Increments were generated using the method of inversion by truncation of a continuous variable to ensure the discrete heavy-tailed distribution.
  • The weak LIS length was computed using the patience sorting algorithm ($O(n \log n)$ time complexity).

• Statistical Analysis & Model Selection:

  • Exploratory Analysis: Calculated the effective local exponent $\theta_{\text{eff}}(n)$ to detect curvature in log-log plots.
  • Competing Models:
    • Model I: A unified power law with a logarithmic term: $L_n \sim n^\theta(a + b \log n)$.
    • Model II: Regime-dependent ansatz: $L_n \sim a n^\theta$ for $\alpha < 2$ and $L_n \sim \sqrt{n}(a + b \log n)$ for $\alpha \ge 2$.
  • Fitting Techniques:
    • Grid search with weighted nonlinear least squares (NLS) to minimize Residual Sum of Squares (RSS).
    • ANOVA Model Comparison: Used nested model F-tests on the full dataset (130,000 individual observations) to statistically reject or accept hypotheses (e.g., $b=0$ for pure power law vs. $b \neq 0$ for log correction).
    • Stability Analysis: Checked if fitted exponents remained constant as smaller $n$ data points were progressively removed.
  • Distributional Diagnostics: Analyzed the distribution of $L_n$ using Q-Q plots, skewness, and kurtosis to test for lognormality.

3. Key Results

A. Scaling Behavior of $\langle L_n \rangle$

The study identifies a critical transition at $\alpha = 2$ (the boundary between finite and infinite variance):

1. Finite Variance Regime ($\alpha \ge 2$) and SRW:

   • The scaling follows $\langle L_n \rangle \sim \sqrt{n}(a + b \log n)$.
   • The exponent is rigorously $\theta = 1/2$.
   • The logarithmic correction is significant and robust. The coefficient $b$ increases with $\alpha$, matching the SRW behavior at high $\alpha$.
   • Significance: This confirms that for discrete walks with finite variance, the "plateaus" created by integer steps allow weak LIS to exploit equal values, introducing a $\log n$ factor not present in the rigorous lower bounds for continuous walks.

2. Infinite Variance Regime ($\alpha < 2$):

   • The scaling follows a pure power law $\langle L_n \rangle \sim a n^\theta$.
   • The exponent $\theta$ varies with $\alpha$:
     • $\alpha = 1/2$: $\theta \approx 0.73$ (with caution due to finite-size effects).
     • $\alpha = 1$: $\theta \approx 0.685$.
     • $\alpha = 1.5$: $\theta \approx 0.640$.
   • As $\alpha \to 2$, $\theta$ approaches $0.5$.
   • Note: For $\alpha = 3/2$, a transitional behavior was observed where a logarithmic correction begins to emerge, suggesting a crossover region.

B. Distribution of $L_n$

• Lognormality: The distribution of $L_n$ is well-approximated by a lognormal distribution for all $\alpha$ and $n$ studied.
• Deviations: The tails of the distribution are slightly lighter than a perfect lognormal (negative excess kurtosis), but the approximation is excellent for $\alpha \ge 1$.
• Variance: For $\alpha \ge 1$, the variance of $\log L_n$ is approximately constant (homoscedastic), validating the use of log-scale regression. For $\alpha = 0.5$, variance increases with $n$.

C. Model Validation

• ANOVA Tests:
  • For $\alpha < 2$, the hypothesis of no logarithmic correction ($b=0$) could not be rejected for $\alpha=0.5$ and $\alpha=1$, confirming the pure power law.
  • For $\alpha \ge 2$, the hypothesis that $\theta = 1/2$ exactly ($\delta=0$) was formally rejected by ANOVA due to high statistical power, but the estimated deviation ($\hat{\delta} \approx 0.03$) was identified as a finite-size bias caused by the slow convergence of the $\log n$ term, not a true change in the asymptotic exponent.

4. Significance and Contributions

1. Resolution of Scaling Forms: The paper provides objective statistical evidence (via ANOVA and stability analysis) to resolve the ambiguity in previous literature regarding whether the scaling is $n^\theta$ or $\sqrt{n} \log n$. It definitively separates the regimes based on the tail index $\alpha$.
2. Discreteness Effect: It highlights that the logarithmic correction in the finite-variance regime is an intrinsic property of discrete random walks (due to the existence of plateaus/ties), contrasting with continuous walks where such ties occur with probability zero. This suggests previous observations of log-corrections in continuous simulations may have been artifacts of floating-point discretization.
3. Heavy-Tailed Behavior: It extends the understanding of LIS to discrete heavy-tailed walks, confirming that the exponent $\theta$ varies continuously with the tail index $\alpha$ in the infinite variance regime, bounded by rigorous theoretical limits ($\theta < 0.815$).
4. Distributional Insight: The finding that $L_n$ follows a lognormal distribution (even for heavy-tailed increments) is a significant empirical observation, though a rigorous theoretical derivation remains an open problem.
5. Methodological Framework: The authors introduce a robust framework combining exploratory plots, weighted NLS, and ANOVA model comparison, which can be applied to other problems involving scaling laws and model selection in stochastic processes.

Conclusion

The paper establishes that the longest weakly increasing subsequence of discrete random walks exhibits a phase transition in scaling behavior at $\alpha=2$. For heavy tails ($\alpha < 2$), the length scales as a pure power law $n^\theta$ with a varying exponent. For finite variance ($\alpha \ge 2$), it scales as $\sqrt{n} \log n$. The results underscore the profound impact of the discrete nature of the walk on the combinatorial structure of increasing subsequences.