Time-inhomogeneous N-particle Branching Brownian Motion and the continuous random energy model
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914459409186816 |
|---|---|
| author | Legrand, Alexandre Maillard, Pascal |
| author_facet | Legrand, Alexandre Maillard, Pascal |
| contents | The $N$-particle branching Brownian motion ($N$-BBM) is a branching Markov process which describes the evolution of a population of particles undergoing reproduction and selection. It has attracted a lot of interest due to its relations to the study of front propagation phenomena on the one hand, and to (hierarchical) physical $p$-spin models on the other hand, among which the continuous random energy model (CREM). This paper investigates the asymptotic displacement of the $N$-BBM in a time-inhomogeneous setting, and when the time horizon $T$ and the number of particles $N$ jointly tend to infinity. We estimate the maximal displacement of the process up to the second order, and show that the latter undergoes a transition at the scale $\log N\approx T^{1/3}$. In particular when $\log N\ll T^{1/3}$ we recover the Brunet-Derrida behavior which was proven in a time-homogeneous setting and for $T\to+\infty$ then $N\to+\infty$. Furthermore, our results can also be interpreted from the perspective of algorithmic optimisation on some spin glass models, since the time-inhomogeneous $N$-BBM can be seen as the realization of an optimization procedure called beam search on the aforementioned CREM. The CREM has been proven by L. Addario-Berry and the second author to undergo an algorithm hardness threshold phenomenon, and the results of the present paper describe precisely the efficiency of the beam search algorithm around that threshold. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_04917 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Time-inhomogeneous N-particle Branching Brownian Motion and the continuous random energy model Legrand, Alexandre Maillard, Pascal Probability 60J80, 68Q17, 82C21 (Primary) 60J70, 92D25, 60K35 (Secondary) The $N$-particle branching Brownian motion ($N$-BBM) is a branching Markov process which describes the evolution of a population of particles undergoing reproduction and selection. It has attracted a lot of interest due to its relations to the study of front propagation phenomena on the one hand, and to (hierarchical) physical $p$-spin models on the other hand, among which the continuous random energy model (CREM). This paper investigates the asymptotic displacement of the $N$-BBM in a time-inhomogeneous setting, and when the time horizon $T$ and the number of particles $N$ jointly tend to infinity. We estimate the maximal displacement of the process up to the second order, and show that the latter undergoes a transition at the scale $\log N\approx T^{1/3}$. In particular when $\log N\ll T^{1/3}$ we recover the Brunet-Derrida behavior which was proven in a time-homogeneous setting and for $T\to+\infty$ then $N\to+\infty$. Furthermore, our results can also be interpreted from the perspective of algorithmic optimisation on some spin glass models, since the time-inhomogeneous $N$-BBM can be seen as the realization of an optimization procedure called beam search on the aforementioned CREM. The CREM has been proven by L. Addario-Berry and the second author to undergo an algorithm hardness threshold phenomenon, and the results of the present paper describe precisely the efficiency of the beam search algorithm around that threshold. |
| title | Time-inhomogeneous N-particle Branching Brownian Motion and the continuous random energy model |
| topic | Probability 60J80, 68Q17, 82C21 (Primary) 60J70, 92D25, 60K35 (Secondary) |
| url | https://arxiv.org/abs/2402.04917 |