pith. sign in

arxiv: 2502.11561 · v3 · submitted 2025-02-17 · 💻 cs.DS · math.PR

Resident fitness computation in linear time and other algorithmic aspects of interacting trajectories

Katalin Friedl , Vikt\'oria Nemkin , Andr\'as T\'obi\'as This is my paper

Pith reviewed 2026-05-23 03:09 UTC · model grok-4.3

classification 💻 cs.DS math.PR
keywords interacting trajectoriesresident fitnesslinear time algorithmcontinued lines representationpiecewise linear functionsslope changespopulation geneticsMoran model
0
0 comments X

The pith

Resident fitness for n interacting trajectories is computable in O(n) time.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes an algorithm that computes resident fitness in linear time for systems of n piecewise linear trajectories. Resident fitness starts at 0 and adds the ultimate slope of every trajectory that reaches height 1. Although pairwise interactions can produce a quadratic number of slope changes overall, the continued lines representation lets the algorithm accumulate the needed slopes directly. The result applies to scaling limits of Moran models with mutation and selection. A Poissonian special case receives an additional linear bound on the expected number of slope changes.

Core claim

Although the interaction of n trajectories may yield Ω(n²) slope changes in total, the resident fitness function can be computed algorithmically in O(n) time using the continued lines representation of the system.

What carries the argument

The continued lines representation, which encodes the system of [0,1]-valued piecewise linear trajectories so that cumulative ultimate slopes reaching height 1 can be summed without enumerating intersections.

If this is right

  • The resident fitness function is obtained without building the full arrangement of all intersection points.
  • In the Poissonian case the expected total number of slope changes remains linear in n.
  • The same representation supports efficient handling of the underlying population-genetic scaling limits.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The linear-time result may allow direct numerical study of much larger trajectory systems than quadratic methods permit.
  • Analogous direct-computation tricks could apply to other cumulative statistics defined on the same trajectory systems.
  • The separation between quadratic geometric complexity and linear functional complexity invites similar questions for related interaction models.

Load-bearing premise

The continued lines representation must let the algorithm obtain the sum of relevant ultimate slopes by direct operations rather than by listing every slope change.

What would settle it

An explicit set of n trajectories on which any correct algorithm for resident fitness requires superlinear time in n would falsify the claim.

Figures

Figures reproduced from arXiv: 2502.11561 by Andr\'as T\'obi\'as, Katalin Friedl, Vikt\'oria Nemkin.

Figure 1
Figure 1. Figure 1: Illustration of Example 5.1 in the case A2 = A3. The smooth lines represent the true fate of the trajectories of the PIT. The dashed lines show how the zeroth (orange), second (red) and third (green) trajectory would evolve after time T1 + 1/A1 in absence of the first (blue) one. The sequential application of the heuristics suggests this evolution since the first trajectory has a killer in its future and h… view at source ↗
read the original abstract

Systems of interacting trajectories were recently studied in~\cite{HGSTW24}. Such a system of $[0,1]$-valued piecewise linear trajectories arises as a scaling limit of the system of logarithmic subpopulation sizes in a population-genetic model (more precisely, a Moran model) with mutation and selection. By definition, the resident fitness is initially 0 and afterwards it increases by the ultimate slope of each trajectory that reaches height 1. We show that although the interaction of $n$ trajectories may yield $\Omega(n^2)$ slope changes in total, the resident fitness function can be computed algorithmically in $O(n)$ time. Our algorithm uses the so-called continued lines representation of the system of interacting trajectories. In the special case of Poissonian interacting trajectories where the birth times of the trajectories form a Poisson process and the initial slopes are random and i.i.d., we provide a linear bound on the expected total number of slope changes.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper claims that although interactions among n [0,1]-valued piecewise linear trajectories can produce Ω(n²) slope changes, the resident fitness function (initially 0, then increased by the ultimate slope of each trajectory reaching height 1) can be computed in O(n) time via the continued lines representation. It further establishes a linear bound on the expected total number of slope changes in the Poissonian case (birth times a Poisson process, initial slopes i.i.d. random).

Significance. If the O(n) claim holds, the result is significant for algorithmic techniques in population-genetics models and interacting trajectories: it supplies an efficient computation that bypasses explicit enumeration of quadratic interactions. The continued-lines representation is the key enabling device, and the Poissonian expected-linear bound supplies independent supporting structure. The manuscript ships a clear algorithmic complexity result with an explicit definition of the target quantity.

minor comments (2)
  1. Abstract: the O(n) claim would be strengthened by an explicit statement of the computational model (e.g., standard RAM) in which the linear-time bound is proved.
  2. The continued-lines representation is invoked as the algorithmic engine, yet the manuscript would benefit from a short self-contained paragraph (or pseudocode snippet) showing how the representation directly yields the cumulative ultimate-slope sum without scanning all slope-change events.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, the assessment of significance, and the recommendation of minor revision. The report contains no specific major comments to address point by point.

Circularity Check

0 steps flagged

No significant circularity; algorithmic claim is independent

full rationale

The central result is an O(n)-time algorithm for resident fitness via continued lines representation, with the definition stated explicitly as the cumulative sum of ultimate slopes for trajectories reaching height 1. The model is introduced via citation to HGSTW24, but this citation is not load-bearing for the complexity bound or the algorithm itself. No self-definitional reduction, fitted input renamed as prediction, uniqueness theorem, or ansatz smuggling occurs. The Poissonian special case supplies an independent linear expectation bound. This is a standard non-circular algorithmic contribution.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on the model definition and representation from prior literature with no new free parameters, invented entities, or ad-hoc axioms introduced in the abstract.

axioms (1)
  • domain assumption Systems of [0,1]-valued piecewise linear trajectories arise as scaling limits of the Moran model with mutation and selection.
    Stated directly in the abstract as the origin of the trajectories under study.

pith-pipeline@v0.9.0 · 5703 in / 1155 out tokens · 27023 ms · 2026-05-23T03:09:35.250103+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages · 1 internal anchor

  1. [1]

    Baake , A

    E. Baake , A. González Casanova , S. Probst and A. Wakolbinger , Modelling and simulating L enski’s long-term evolution experiment, Theoret. Popul. Biol., 127 , 58--74 (2019)

    work page 2019

  2. [2]

    Blath , T

    J. Blath , T. Paul and A. Tóbiás , A stochastic adaptive dynamics model for bacterial populations with mutation, dormancy and transfer, ALEA Lat. Am. J. Probab. Math. Stat., 20 , 313–357 (2023)

    work page 2023

  3. [3]

    Boenkost , A

    F. Boenkost , A. González Casanova , C. Pokalyuk and A. Wakolbinger , Haldane’s formula in C annings models: the case of moderately strong selection, J. Math. Biol., 83:70 , 1820--1867 (2021)

    work page 2021

  4. [4]

    Boenkost , A

    F. Boenkost , A. González Casanova , C. Pokalyuk and A. Wakolbinger , Haldane’s formula in C annings models: the case of moderately weak selection, Electron.\ J.\ Probab., 26:4, 1--36 (2021)

    work page 2021

  5. [5]

    Bovier , L

    A. Bovier , L. Coquille and C. Smadi , Crossing a fitness valley as a metastable transition in a stochastic population model, Ann.\ Appl.\ Probab., 29:6 , 3541--3589 (2019)

    work page 2019

  6. [6]

    Brouard , Genetic composition of supercritical branching populations under power law mutation rates, arXiv:2309.12055 (2024)

    V. Brouard , Genetic composition of supercritical branching populations under power law mutation rates, arXiv:2309.12055 (2024)

    work page arXiv 2024

  7. [7]

    Coquille , A

    L. Coquille , A. Kraut and C. Smadi , Stochastic individual-based models with power law mutation rate on a general finite trait space, Electron.\ J.\ Probab., 26 , 1--37 (2021)

    work page 2021

  8. [8]

    Champagnat , S

    N. Champagnat , S. Méléard and V.C. Tran , Stochastic analysis of emergence of evolutionary cyclic behavior in population dynamics with transfer, Ann. Appl. Probab., 31:4, 1820--1867 (2021)

    work page 2021

  9. [9]

    Durrett and J

    R. Durrett and J. Mayberry , Traveling waves of selective sweeps, Ann. Appl. Probab., 21:2 699--744 (2011)

    work page 2011

  10. [10]

    Dembo and O

    A. Dembo and O. Zeitouni , Large Deviations Techniques and Applications\/, 2nd edition, Springer, Berlin (1998)

    work page 1998

  11. [11]

    Embrechts , C

    P. Embrechts , C. Klüppelberg and T. Mikosch , Modelling extreme events for insurance and finance, preprint, available at https://minerva.it.manchester.ac.uk/ saralees/book1.pdf (1997)

    work page 1997

  12. [12]

    Esser and A

    M. Esser and A. Kraut , Effective growth rates in a periodically changing environment: From mutation to invasion, arXiv:2310.20509, (2023)

    work page arXiv 2023

  13. [13]

    Esser and A

    M. Esser and A. Kraut , A general multi-scale description of metastable adaptive motion across fitness valleys, J. Math. Biol., 89:46 , 50 pp. (2024)

    work page 2024

  14. [14]

    Resident fitness computation in linear time and other algorithmic aspects of interacting trajectories

    K. Friedl , V. Nemkin and A. Tóbiás , A linear-time algorithm computing the resident fitness in interacting trajectories, in: N. Kakimura, A. Shioura, Y. Yokoi (editors): Proceedings of the 13th Hungarian--Japanese Symposium on Discrete Mathematics and Its Applications, pp. 469--479, see also: arXiv:2502.11561v1 (2025)

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  15. [15]

    Lenski , The fate of competing beneficial mutations in an asexual population, Genetica, 102--103:1--6 , 127--44 (1998)

    P.J.\ Gerrish and R. Lenski , The fate of competing beneficial mutations in an asexual population, Genetica, 102--103:1--6 , 127--44 (1998)

    work page 1998

  16. [16]

    Hermann , A

    F. Hermann , A. González Casanova , R. Soares dos Santos , A. Tóbiás , and A. Wakolbinger , From clonal interference to P oissonian interacting trajectories, Ann. Appl. Probab., 35:4 , 2823--2865, see also: arXiv:2407.00793 (2025)

    work page arXiv 2025

  17. [17]

    J. F. C. Kingman , Poisson Processes, Oxford University Press, New York (1993)

    work page 1993

  18. [18]

    Paul , The canonical equation of adaptive dynamics in individual-based models with power law mutation rates, arXiv:2309.02148 (2023)

    T. Paul , The canonical equation of adaptive dynamics in individual-based models with power law mutation rates, arXiv:2309.02148 (2023)

    work page arXiv 2023

  19. [19]

    Smadi , The effect of recurrent mutations on genetic diversity in a large population of varying size, Acta Appl.\ Math., 149:1 , 11--51 (2017)

    C. Smadi , The effect of recurrent mutations on genetic diversity in a large population of varying size, Acta Appl.\ Math., 149:1 , 11--51 (2017)

    work page 2017