A linear-time algorithm computing the resident fitness in interacting trajectories

Friedl, Katalin and Nemkin, Viktória and Tóbiás, András József (2025) A linear-time algorithm computing the resident fitness in interacting trajectories. In: 13th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, 2025.05.26-2025.05.29, Tokyo.

Preview

Text 2502.11561v1.pdf - Draft Version Download (211kB) | Preview

Abstract

Abstract: The notion of a system of interacting trajectories was recently introduced in [13]. Such a system of [0 , 1]-valued piecewise linear trajectories arises as a scaling limit of the system of logarithmic subpopulation sizes in a certain 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 (at all times) can be computed algorithmically in O ( n) time. Our algorithm is given in terms of 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 show that even the expected number of slope changes grows only linearly in time.

Actions (login required)

Edit Item