Maximal displacement of a time-inhomogeneous N(T)-particles branching Brownian motion

Alexandre Legrand, Pascal Maillard

Published 2024-02-07Version 1

The $N$-particles branching Brownian motion ($N$-BBM) is a branching Markov process which describes the evolution of a population of particles undergoing reproduction and selection. It shares many properties with the $N$-particles branching random walk ($N$-BRW), which itself is strongly related to physical $p$-spin models, or to Derrida's Random Energy Model. The $N$-BRW can also be seen as the realization of an optimization algorithm over hierarchical data, which is often called beam search. More precisely, the maximal displacement of the $N$-BRW (or $N$-BBM) can be seen as the output of the beam search algorithm; and the population size $N$ is the ``width'' of the beam, and (almost) matches the computational complexity of the algorithm. In this paper, we investigate the maximal displacement at time $T$ of an $N$-BBM, where $N=N(T)$ is picked arbitrarily depending on $T$ and the diffusion of the process $\sigma(\cdot)$ is inhomogeneous in time. We prove the existence of a transition in the second order of the maximal displacement when $\log N(T)$ is of order $T^{1/3}$. When $\log N(T)\ll T^{1/3}$, the maximal displacement behaves according to the Brunet-Derrida correction which has already been studied for $N$ a large constant and for $\sigma$ constant. When $\log N(T)\gg T^{1/3}$, the output of the algorithm (i.e. the maximal displacement) is subject to two phenomena: on the one hand it begins to grow very slowly (logarithmically) in terms of the complexity $N$; and on the other hand its dependency in the time-inhomogeneity $\sigma(\cdot)$ becomes more intricate. The transition at $\log N(T)\approx T^{1/3}$ can be interpreted as an ``efficiency ceiling'' in the output of the beam search algorithm, which extends previous results from Addario-Berry and Maillard regarding an algorithm hardness threshold for optimization over the Continuous Random Energy Model.