Records, drift, and the longest increasing subsequence of biased Gaussian random walks

J. Ricardo G. Mendonça · 2026

Read Records, drift, and the longest increasing subsequence of biased Gaussian random walks by J. Ricardo G. Mendonça (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-29185.txt.

Introduction

J. Ricardo G. Mendonça simulates the longest increasing subsequence of biased Gaussian random walks, mainly studied before at zero mean. For every upward bias above one half, mean length grows linearly, from zero at the symmetric point to one at full bias. The record count is linear, fixed by Spitzer's formula, and the subsequence aligns ever closer with it as bias grows. At the symmetric point, the record skeleton collapses to a square-root scale while the subsequence follows a square-root times log regime.

Catalog record

CREATORJ. Ricardo G. Mendonça
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE40379
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.29185

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Records, drift, and the longest increasing subsequence of biased Gaussian random walks J. Ricardo G. Mendonça Abstract The longest increasing subsequence (LIS) of a random walk has so far been studied mainly for zero-mean, symmetric step increments. We numerically investigate the LIS of biased Gaussian random walks, with unit-variance increments and positive drift μ p = Φ − 1 ​ ( p ) \mu_{p}=\Phi^{-1}(p) , where p = ℙ ⁡ ( ξ > 0 ) p=\PP(\xi>0) . In contrast with the symmetric case, we find that for every fixed p > 1 / 2 p>1/2 the mean LIS length grows linearly, ⟨ L n ​ ( p ) ⟩ ∼ a ⁡ ( p ) ​ n \langle L_{n}(p)\rangle\sim a(p)n , with a ⁡ ( p ) a(p) increasing from 0 0 at p = 1 / 2 p=1/2 to 1 1 as p → 1 p\to 1 . The record count is also linear, with coefficient λ ⁡ ( p ) \lambda(p) given by Spitzer’s formula for the mean ascending ladder epoch, and the LIS becomes increasingly aligned with this record skeleton as p p grows. At the symmetric point p = 1 / 2 p=1/2 , the record skeleton collapses to the Sparre Andersen n \sqrt{n} scale, while the LIS returns to the symmetric finite-variance n ​ log ⁡ n \sqrt{n}\mkern 1.0mu\log{n} regime. Near this limit, the excess a ⁡ ( μ p ) − λ ⁡ ( μ p ) a(\mu_{p})-\lambda(\mu_{p}) vanishes more slowly than linearly in the drift, although our data do not resolve a single power law. The empirical distribution of L n L_{n} also changes across the singular point, from lognormal-like at p = 1 / 2 p=1/2 to fluctuations consistent with Gaussian behavior for every sampled p > 1 / 2 p>1/2 . I Introduction The classic longest increasing subsequence (LIS) problem, first proposed by Ulam in the early 1960s, asks for the properties of the increasing subsequences \pi_{i_{1}}<\cdots<\pi_{i_{k}} , 1\leq i_{1}<\cdots<i_{k}\leq n , of maximal length k in random n -permutations \pi ulam ; hammersley . The LIS problem for random permutations proved very rich, and its study led to developments across subjects ranging from group representation theory to random matrix theory, algebraic combinatorics, determinantal point processes, and exactly solvable models of statistical mechanics. We refer the reader to bdj99 ; aldous ; patience ; romik ; gorin for comprehensive expositions and further references. Recently, the LIS problem for random walks started also to receive attention angel ; pemantle . The LIS finds applications in the analysis of real-time data streams and large-scale correlated data liben ; gopalan2010 ; bonomi2016 ; cuzzocrea2018 . Several recent numerical studies have investigated the properties of the LIS of random walks lisjpa ; hartmann ; lispre ; fatlis ; howmany ; weakheavy . These studies confirmed the few existing rigorous results and identified candidate scaling forms for the leading asymptotic behavior of the length of the LIS of random walks for different distributions of step increments, short and heavy tailed, the possible universal properties of its full distribution function and its large deviation rate function. All results obtained so far, however, refer to the LIS of symmetric random walks. The characterization of the LIS of biased random walks remained unexplored. Biased random walks model time series with a directional trend; the LIS then probes monotone structure in a correlated, nonstationary sequence. While analytical results are not available, the relevant observables are well-defined, and a numerical investigation along the lines of the symmetric case lisjpa ; hartmann ; lispre ; fatlis ; howmany ; weakheavy offers a first step. We study the LIS of biased random walks, in which the step increments are Gaussian with unit variance and a positive mean \mu_{p} set by the bias parameter p=\PP(\xi>0)\geq 1/2 . The choice of Gaussian increments isolates the effect of asymmetry without introducing heavy-tail effects, in a setting where the symmetric case is well-understood. As we shall see, the leading asymptotic behavior of the length of the LIS is qualitatively different from the symmetric one already at vanishing asymmetry, and a notion of an asymptotic exponent in the sense of the symmetric scaling laws no longer captures the relevant mechanisms. In this case one should appeal to the theory of records of biased random walks, in which the universal Sparre Andersen behavior at p=1/2 is replaced by a linearly growing record skeleton with which the LIS aligns majumdarziff ; gms ; wbk ; msw . We find that any positive bias produces \theta(p)=1 throughout 1/2<p<1 , so the question becomes the form of the leading coefficient a(p) rather than of any exponent. This contrasts with the heavy-tailed case weakheavy , where \theta(\alpha) varies continuously with the tail index. The symmetric point p=1/2 is a singular limit of the linear regime; the data show that the small-drift lift-off a(\mu_{p})-\lambda(\mu_{p}) vanishes more slowly than linearly in \mu_{p} , so that (a(\mu_{p})-\lambda(\mu_{p}))/\mu_{p} increases as \mu_{p}\downarrow 0 ; however, the local log-log slope drifts across the sampled range and no single power law captures the behavior. The LIS distribution itself undergoes a sharp transition across this singular point: lognormal-like at p=1/2 , as reported for the symmetric case weakheavy , and consistent with Gaussian fluctuations for every sampled p>1/2 , in line with the central-limit picture applied to the extensive sum-like structure of L_{n} in the linear regime. This paper is organized as follows. In Section II we review the main facts about the LIS of symmetric random walks and the role of records, fixing notation. Section III defines the biased Gaussian walk and the observables we measure. Section IV characterizes the linear regime, reports the coefficient a(p) , identifies the record-density coefficient \lambda(p) with the known closed form msw , and documents the empirical transition in the distribution of L_{n} across p=1/2 . In Section V we interpret the gap a(p)-\lambda(p) as the LIS contribution from non-record interpolations between consecutive records of the walk. Section VI treats p=1/2 as a singular limit of the linear regime and identifies the drift crossover scale \mu_{c}(n) at which the symmetric prediction breaks down. Finally, in Section VII we summarize and discuss our results and indicate directions for further research involving distributions of infinite variance. II Background II.1 The LIS of random walks An n -step random walk is a sequence (X_{1},\dots,X_{n}) of integer or real numbers given by X_{0}=0,\quad X_{k}=X_{k-1}+\xi_{k},~1\leq k\leq n, (1) where the step increments \xi_{k} are independent and identically distributed (i. i. d.) random variables according to some probability distribution \phi(x\mkern 2.0mu|\mkern 2.0mu\bm{\beta}) . The walk positions are correlated according to \operatorname{Cov}(X_{s},X_{t})=\min(s,t)\operatorname{Var}(\xi); (2) the LIS problem for random walks differs from the permutation case because the entries of the sequence are not independent. Given a random walk (X_{1},\dots,X_{n}) , we are interested in the behavior of its longest possible strictly increasing subsequence X_{i_{1}}<\cdots<X_{i_{k}},\quad 1\leq i_{1}<\cdots<i_{k}\leq n. (3) A sequence can have more than one LIS, with different elements but the same maximal length k . Note that for continuous distributions of step increments, ties occur with probability zero, so the distinction between weakly ( X_{i_{1}}\leq\cdots\leq X_{i_{k}} ) and strictly increasing subsequences is immaterial. We therefore refer to the LIS without qualification

Read the complete text