Resident Fitness Computation in Linear Time and Other Algorithmic Aspects of Interacting Trajectories

Friedl, Katalin and Nemkin, Viktória and Tóbiás, András József (2026) Resident Fitness Computation in Linear Time and Other Algorithmic Aspects of Interacting Trajectories. RANDOM STRUCTURES & ALGORITHMS, 69 (1). No. 70087. ISSN 1042-9832

Text RandomStructAlgorithms-2026-Friedl-ResidentFitnessComputationinLinearTimeandOtherAlgorithmicAspectsof.pdf - Published Version Available under License Creative Commons Attribution Non-commercial No Derivatives. Download (440kB)

Abstract

Systems of interacting trajectories were recently studied in Hermann et al. (2025). Such a system of ‐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 afterward it increases by the ultimate slope of each trajectory that reaches height 1. We show that although the interaction of trajectories may yield slope changes in total, the resident fitness function can be computed algorithmically in time. Our algorithm uses the so‐called continued lines representation of the system of interacting trajectories. In the special case of Poissonian interacting trajectories (PIT), 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.

Actions (login required)

View Item