{
  "id": "2402.04917",
  "version": "v1",
  "published": "2024-02-07T14:43:48.000Z",
  "updated": "2024-02-07T14:43:48.000Z",
  "title": "Maximal displacement of a time-inhomogeneous N(T)-particles branching Brownian motion",
  "authors": [
    "Alexandre Legrand",
    "Pascal Maillard"
  ],
  "comment": "72 pages, 3 figures",
  "categories": [
    "math.PR"
  ],
  "abstract": "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-02-07T14:43:48.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60J80",
      "68Q17",
      "82C21",
      "60J70",
      "92D25",
      "60K35"
    ],
    "keywords": [
      "beam search algorithm",
      "derridas random energy model",
      "maximal displacement behaves",
      "continuous random energy model",
      "particles branching brownian motion"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 72,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}