Resident fitness computation in linear time and other algorithmic aspects of interacting trajectories
This work provides an efficient algorithm for a key quantity in a population-genetic model, addressing a computational bottleneck for large n.
The paper shows that the resident fitness function in a system of interacting trajectories can be computed in O(n) time despite Ω(n^2) slope changes, using a continued lines representation. For Poissonian trajectories, it provides a linear bound on expected slope changes.
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 $Ω(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.