pith. sign in

arxiv: 2402.04917 · v4 · submitted 2024-02-07 · 🧮 math.PR

Time-inhomogeneous N-particle Branching Brownian Motion and the continuous random energy model

Alexandre Legrand , Pascal Maillard This is my paper

Pith reviewed 2026-05-24 03:52 UTC · model grok-4.3

classification 🧮 math.PR
keywords branching Brownian motioncontinuous random energy modelmaximal displacementBrunet-Derrida behaviorbeam searchtime-inhomogeneous processspin glass optimization
0
0 comments X

The pith

The maximal displacement of time-inhomogeneous N-particle branching Brownian motion transitions in its second-order asymptotics at the scale log N ≈ T^{1/3}.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies the N-particle branching Brownian motion in a time-inhomogeneous environment as both the time horizon T and the population size N tend to infinity. It derives the second-order term in the maximal displacement of the process and demonstrates that this term changes character when log N is comparable to T raised to the one-third power. When log N is much smaller than T to the one-third, the displacement matches the Brunet-Derrida prediction previously known only for time-homogeneous motion. These findings also quantify the performance of beam search as an optimization algorithm on the continuous random energy model near its hardness threshold.

Core claim

The maximal displacement undergoes a transition at the scale log N ≈ T^{1/3}, and recovers the Brunet-Derrida behavior when log N ≪ T^{1/3}.

What carries the argument

The link between the time-inhomogeneous N-BBM and the continuous random energy model that permits transferring results from the homogeneous setting.

If this is right

  • The second-order maximal displacement follows Brunet-Derrida asymptotics below the transition scale.
  • The efficiency of beam search on the CREM is described precisely around the algorithm hardness threshold.
  • Results hold in the joint limit where N and T go to infinity under the specified scaling regimes.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The transition scale may indicate a general feature of optimization algorithms on hierarchical spin glass models.
  • Similar scaling transitions could appear in other branching processes or front propagation models with time-dependent parameters.

Load-bearing premise

The time-inhomogeneity takes a specific form and the joint scaling of N and T satisfies conditions that connect the process to the CREM and allow use of homogeneous-case results.

What would settle it

Numerical simulation showing that the maximal displacement does not exhibit the predicted transition or second-order term when log N is around T to the one-third in the joint limit.

Figures

Figures reproduced from arXiv: 2402.04917 by Alexandre Legrand, Pascal Maillard.

Figure 1
Figure 1. Figure 1: Running maximum of simulations of time-inhomogeneous N-BBM with varying N. Parameters: T = 1000, σ(t) = 0.125+t 2 . The dashed curve corresponds to the theoretical position of the running maximum of the time-inhomogeneous BBM without selection (N = ∞), which is attained up to random O(1) fluctuations, see [20]. at most N particles, N ∈ N. At any time of a splitting event, we only keep the N particles at th… view at source ↗
Figure 2
Figure 2. Figure 2: Numerical simulations of the recentered, rescaled maximum and minimum positions max N(T) T and minN(T) T (see (2.12)) of the binary, Bernoulli N-BRW and comparison with the theoretical values. See text for details. Comparing these properties with those of the N(T)-BBM, we therefore expect the same convergence to hold for the genealogy of the N(T)-BBM in the critical regime log N ≈ T 1/3 , up to a time-chan… view at source ↗
Figure 3
Figure 3. Figure 3: The following lemma shows that the quantity m∗ T , defined in (1.11), is indeed well approximated by γ ∗,h,x T (T) when h and x are close to 1. Lemma 4.1. Let ∗ ∈ {sup,sub, crit}. Then, (4.10) lim sup (h,x)→(1,1), h>x>0 lim sup T→+∞ 1 b ∗ T [PITH_FULL_IMAGE:figures/full_fig_p021_3.png] view at source ↗
Figure 3
Figure 3. Figure 3: Illustration of the BBM between barriers, which approximates the N-BBM. In each regime, we draw the typical trajectory of a single particle that survives until time T (we do not show this rigorously, but this is the heuristic guiding our calculations). (A) In the critical regime, the trajectory resembles that of a Brownian motion constrained to remain between the space-time barriers and, moreover, in a tim… view at source ↗
Figure 4
Figure 4. Figure 4: Illustration of the strategy of a particle contributing to the lower bound for the first moment in Proposition 5.1 (super-critical case). In this figure we consider t = T and a function σ(·) increasing on [0, 1/2], decreasing on [1/2, 1]. We consider separately each time interval on which σ(·) is monotone. Let τT and hT be as in the proof of Lemma 5.2. On [τT , T /2 − τT ], we introduce an additional killi… view at source ↗
Figure 5
Figure 5. Figure 5: Illustration of the multi-type process. As in the original BBM between barriers, an uncolored individual is killed whenever it reaches γ ∗ T (·). However, when it reaches γ ∗ T (·) it is not killed but colored in red instead. Thereafter all its descendants are also colored in red, and they are killed whenever they reach one of two new barriers, γ red T (·) and γ red T (·), which are shifted-upward versions… view at source ↗
read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript studies the maximal displacement of time-inhomogeneous N-particle branching Brownian motion (N-BBM) as N and T tend jointly to infinity. It claims a second-order asymptotic for this displacement, with a transition occurring at the scale log N ≈ T^{1/3}. In the regime log N ≪ T^{1/3} the leading correction recovers the Brunet-Derrida behavior previously established for the time-homogeneous case. The results are also interpreted as describing the performance of beam search on the continuous random energy model (CREM) near its algorithmic hardness threshold.

Significance. If the claims hold, the work extends the analysis of front propagation from homogeneous to inhomogeneous branching processes and supplies a precise characterization of beam-search efficiency on hierarchical spin-glass models around the hardness threshold identified by Addario-Berry and Maillard. The joint (N,T) scaling and the explicit transition scale constitute the main technical advance.

minor comments (2)
  1. The abstract states that the time-inhomogeneity must satisfy 'technical conditions' permitting reduction to the homogeneous case, but does not indicate where these conditions are stated or verified in the manuscript.
  2. Notation for the maximal displacement (presumably denoted something like X_N(T) or M_N(T)) and the precise form of the second-order correction are not introduced in the abstract, making it difficult to locate the corresponding statements in the body.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their summary of the manuscript and for recognizing the potential significance of the joint (N,T) scaling and the explicit transition at log N ≈ T^{1/3}. The recommendation is listed as uncertain, but the report contains no specific major comments or requests for clarification. We remain available to address any additional points the referee may wish to raise.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper's central claims concern second-order asymptotics for maximal displacement in the time-inhomogeneous N-BBM, with a transition at log N ~ T^{1/3} and recovery of Brunet-Derrida behavior in a sub-regime. These rest on independent analysis of the inhomogeneous process under technical conditions that permit reduction to the CREM representation and application of prior homogeneous-case results. No equations, lemmas, or steps in the provided abstract or claim statements reduce any prediction or uniqueness statement to a fitted input, self-definition, or load-bearing self-citation chain. The reference to Addario-Berry–Maillard work supplies external support for the homogeneous baseline and CREM hardness threshold rather than circular justification for the new inhomogeneous results. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The abstract invokes the standard definition of N-BBM and the CREM from prior literature (Addario-Berry–Maillard) without introducing new free parameters or entities; all technical assumptions are inherited from that literature.

axioms (1)
  • domain assumption The time-inhomogeneous N-BBM satisfies the branching and selection rules that permit the connection to the CREM.
    Stated implicitly by the interpretation as beam search on the CREM.

pith-pipeline@v0.9.0 · 5806 in / 1310 out tokens · 25608 ms · 2026-05-24T03:52:21.713012+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

63 extracted references · 63 canonical work pages · 1 internal anchor

  1. [1]

    Addario-Berry and P

    L. Addario-Berry and P. Maillard. The algorithmic hardness threshold for continuous random energy models. Math. Stat. Learn., 2(1):77–101, 2019

    work page 2019

  2. [2]

    A¨ ıd´ ekon

    E. A¨ ıd´ ekon. Convergence in law of the minimum of a branching random walk.Ann. Probab., 41(3A):1362–1426, 2013

    work page 2013

  3. [3]

    D. Aldous. Greedy search on the binary tree with random edge-weights. Combin. Probab. Comput., 1(4):281–293, 1992

    work page 1992

  4. [4]

    D. Aldous. A metropolis-type optimization algorithm on the infinite tree. Algorithmica, 22(4):388–412, Dec 1998

    work page 1998

  5. [5]

    K. B. Athreya and P. E. Ney. Branching processes. Die Grundlehren der mathematischen Wissenschaften, Band 196. Springer-Verlag, New York-Heidelberg, 1972

    work page 1972

  6. [6]

    Activated Aging Dynamics and Effective Trap Model Description in the Random Energy Model

    M. Baity-Jesi, G. Biroli, and C. Cammarota. Activated Aging Dynamics and Effective Trap Model Description in the Random Energy Model. Journal of Statistical Mechanics: Theory and Experiment , 2018(1):013301, Jan. 2018. arXiv:1708.03268 [cond-mat]

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  7. [7]

    Ben Arous, A

    G. Ben Arous, A. Bovier, and V. Gayrard. Glauber Dynamics of the Random Energy Model. Communications in Mathematical Physics, 235(3):379–425, Apr. 2003

    work page 2003

  8. [8]

    B´ erard and J.-B

    J. B´ erard and J.-B. Gou´ er´ e. Brunet-Derrida behavior of branching-selection particle systems on the line.Comm. Math. Phys., 298(2):323–342, 2010

    work page 2010

  9. [9]

    B´ erard and J.-B

    J. B´ erard and J.-B. Gou´ er´ e. Survival probability of the branching random walk killed below a linear boundary.Electronic Journal of Probability, 16(14):396–418, 2011

    work page 2011

  10. [10]

    Berestycki, N

    J. Berestycki, N. Berestycki, and J. Schweinsberg. Survival of near-critical branching Brownian motion.Journal of Statistical Physics, 143(5):833–854, may 2011

    work page 2011

  11. [11]

    Berestycki, N

    J. Berestycki, N. Berestycki, and J. Schweinsberg. The genealogy of branching brownian motion with absorption. The Annals of Probability, 41(2), mar 2013

    work page 2013

  12. [12]

    Berestycki, N

    J. Berestycki, N. Berestycki, and J. Schweinsberg. Critical branching Brownian motion with absorption: survival probability. Probability Theory and Related Fields , 160(3-4):489–520, 2014

    work page 2014

  13. [13]

    Berestycki, N

    J. Berestycki, N. Berestycki, and J. Schweinsberg. Critical branching Brownian motion with absorption: Particle configura- tions. Annales de l’Institut Henri Poincar´ e, Probabilit´ es et Statistiques, 51(4):1215–1250, 2015

    work page 2015

  14. [14]

    S. M. Berman. Isotropic Gaussian processes on the Hilbert sphere. Ann. Probab., 8(6):1093–1106, 1980

    work page 1980

  15. [15]

    J. D. Biggins. The growth and spread of the general branching random walk. Ann. Appl. Probab., 5(4):1008–1024, 1995

    work page 1995

  16. [16]

    J. D. Biggins and A. E. Kyprianou. Measure change in multitype branching. Adv. in Appl. Probab. , 36(2):544–581, 2004

    work page 2004

  17. [17]

    Billingsley

    P. Billingsley. Convergence of probability measures. Wiley Series in Probability and Statistics: Probability and Statistics. John Wiley & Sons, Inc., New York, second edition, 1999. A Wiley-Interscience Publication

    work page 1999

  18. [18]

    R. Bisiani. Beam search. In C. S. Shapiro, editor, Encyclopedia of Artificial Intelligence , pages 56–58. John Wiley & Sons, Inc., 1987

    work page 1987

  19. [19]

    A. N. Borodin and P. Salminen. Handbook of Brownian motion—facts and formulae . Probability and its Applications. Birkh¨ auser Verlag, Basel, second edition, 2002

    work page 2002

  20. [20]

    Bovier and L

    A. Bovier and L. Hartung. Variable speed branching Brownian motion 1. Extremal processes in the weak correlation regime. Alea, 12(1):261–291, mar 2015. MAXIMAL DISPLACEMENT OF A TIME-INHOMOGENEOUS N(T)-BBM 71

    work page 2015

  21. [21]

    Bovier and I

    A. Bovier and I. Kurkova. Derrida’s generalized random energy models 2: models with continuous hierarchies. Annales de l’Institut Henri Poincare (B) Probability and Statistics , 40(4):481–495, 2004

    work page 2004

  22. [22]

    Bovier and I

    A. Bovier and I. Kurkova. Much Ado about Derrida’s GREM , pages 81–115. Springer Berlin Heidelberg, Berlin, Heidelberg, 2007

    work page 2007

  23. [23]

    M. Bramson. Convergence of solutions of the Kolmogorov equation to travelling waves. Mem. Amer. Math. Soc. , 44(285):iv+190, 1983

    work page 1983

  24. [24]

    M. D. Bramson. Maximal displacement of branching Brownian motion. Comm. Pure Appl. Math. , 31(5):531–581, 1978

    work page 1978

  25. [25]

    Brunet and B

    E. Brunet and B. Derrida. Shift in the velocity of a front due to a cutoff. Phys. Rev. E (3) , 56(3):2597–2604, 1997

    work page 1997

  26. [26]

    Brunet and B

    ´E. Brunet and B. Derrida. Microscopic models of traveling wave equations. Computer Physics Communications , 121- 122:376–381, sep 1999

    work page 1999

  27. [27]

    Brunet, B

    E. Brunet, B. Derrida, A. H. Mueller, and S. Munier. Phenomenological theory giving the full statistics of the position of fluctuating pulled fronts. Phys. Rev. E , 73:056126, May 2006

    work page 2006

  28. [28]

    B. Chauvin. Product martingales and stopping lines for branching Brownian motion. Ann. Probab., 19(3):1195–1205, 1991

    work page 1991

  29. [29]

    Derrida and P

    B. Derrida and P. Mottishaw. On the genealogy of branching random walks and of directed polymers. EPL (Europhysics Letters), 115(4):40005, Aug. 2016

    work page 2016

  30. [30]

    Derrida and D

    B. Derrida and D. Simon. The survival probability of a branching random walk in presence of an absorbing wall.Europhysics Letters (EPL), 78(6):60006, jun 2007

    work page 2007

  31. [31]

    Derrida and H

    B. Derrida and H. Spohn. Polymers on disordered trees, spin glasses, and traveling waves. Journal of Statistical Physics , 51(5):817–840, Jun 1988

    work page 1988

  32. [32]

    El Alaoui, A

    A. El Alaoui, A. Montanari, and M. Sellke. Optimization of mean-field spin glasses. The Annals of Probability , 49(6), nov 2021

    work page 2021

  33. [33]

    Fang and O

    M. Fang and O. Zeitouni. Consistent Minimal Displacement of Branching Random Walks. Electronic Communications in Probability, 15:no. 11, 106–118, mar 2010

    work page 2010

  34. [34]

    Faraud, Y

    G. Faraud, Y. Hu, and Z. Shi. Almost sure convergence for stochastically biased random walks on trees. Probability Theory and Related Fields, 154(3-4):621–660, dec 2012

    work page 2012

  35. [35]

    Gamarnik

    D. Gamarnik. The overlap gap property: A topological barrier to optimizing over random structures. Proceedings of the National Academy of Sciences of the United States of America , 118(41), 2021

    work page 2021

  36. [36]

    Gamarnik and A

    D. Gamarnik and A. Jagannath. The overlap gap property and approximate message passing algorithms for $p$-spin models. The Annals of Probability , 49(1), Jan. 2021

    work page 2021

  37. [37]

    Gantert, Y

    N. Gantert, Y. Hu, and Z. Shi. Asymptotics for the survival probability in a killed branching random walk. Annales de l’Institut Henri Poincar´ e, Probabilit´ es et Statistiques, 47(1):111 – 129, 2011

    work page 2011

  38. [38]

    Huang and M

    B. Huang and M. Sellke. Tight lipschitz hardness for optimizing mean field spin glasses. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) , pages 312–322. IEEE, 2022

    work page 2022

  39. [39]

    Huang and M

    B. Huang and M. Sellke. Algorithmic threshold for multi-species spherical spin glasses. arXiv preprint arXiv:2303.12172 , 2023

    work page arXiv 2023

  40. [40]

    Ikeda, M

    N. Ikeda, M. Nagasawa, and S. Watanabe. Branching Markov processes. I. J. Math. Kyoto Univ. , 8:233–278, 1968

    work page 1968

  41. [41]

    Ikeda, M

    N. Ikeda, M. Nagasawa, and S. Watanabe. Branching Markov processes. III. J. Math. Kyoto Univ. , 9:95–160, 1969

    work page 1969

  42. [42]

    B. Jaffuel. The critical barrier for the survival of branching random walk with absorption. Ann. Inst. Henri Poincar´ e Probab. Stat., 48(4):989–1009, 2012

    work page 2012

  43. [43]

    P. Jagers. General branching processes as Markov fields. Stochastic Process. Appl., 32(2):183–212, 1989

    work page 1989

  44. [44]

    H. Kesten. Branching Brownian motion with absorption. Stochastic Processes and their Applications , 7(1):9–47, mar 1978

    work page 1978

  45. [45]

    Klimovsky

    A. Klimovsky. High-dimensional Gaussian fields with isotropic increments seen through spin glasses. Electron. Commun. Probab., 17:no. 17, 14, 2012

    work page 2012

  46. [46]

    Lemons, C

    S. Lemons, C. L. L´ opez, R. C. Holte, and W. Ruml. Beam Search: Faster and Monotonic. Proceedings International Conference on Automated Planning and Scheduling, ICAPS , 32:222–230, 2022

    work page 2022

  47. [47]

    Maillard

    P. Maillard. Branching Brownian motion with selection . Theses, Universit´ e Pierre et Marie Curie - Paris VI, Oct. 2012

    work page 2012

  48. [48]

    Maillard

    P. Maillard. Speed and fluctuations of N-particle branching Brownian motion with spatial selection. Probab. Theory Related Fields, 166(3-4):1061–1173, 2016

    work page 2016

  49. [49]

    Maillard and J

    P. Maillard and J. Schweinsberg. Yaglom-type limit theorems for branching Brownian motion with absorption. Annales Henri Lebesgue, 5:921–985, 2022

    work page 2022

  50. [50]

    Maillard and J

    P. Maillard and J. Schweinsberg. The all-time maximum for branching Brownian motion with absorption conditioned on long-time survival. arXiv:2310.00707, page 23pp, 2023

    work page arXiv 2023

  51. [51]

    Maillard and O

    P. Maillard and O. Zeitouni. Slowdown in branching brownian motion with inhomogeneous variance. Annales de l’Institut Henri Poincar´ e, Probabilit´ es et Statistiques, 52(3), Aug 2016

    work page 2016

  52. [52]

    B. Mallein. Maximal displacement of a branching random walk in time-inhomogeneous environment. Stochastic Processes and their Applications , 125(10):3958–4019, 2015

    work page 2015

  53. [53]

    B. Mallein. Branching random walk with selection at critical rate. Bernoulli, 23(3):1784–1821, 2017

    work page 2017

  54. [54]

    H. P. McKean. Application of Brownian motion to the equation of Kolmogorov-Petrovskii-Piskunov. Comm. Pure Appl. Math., 28(3):323–331, 1975. 72 A. LEGRAND AND P. MAILLARD

    work page 1975

  55. [55]

    Montanari

    A. Montanari. Optimization of the sherrington–kirkpatrick hamiltonian. SIAM Journal on Computing , (0):FOCS19–1, 2021

    work page 2021

  56. [56]

    Nolen, J.-M

    J. Nolen, J.-M. Roquejoffre, and L. Ryzhik. Power-Like Delay in Time Inhomogeneous Fisher-KPP Equations. Communi- cations in Partial Differential Equations , 40(3):475–505, dec 2014

    work page 2014

  57. [57]

    Pemantle

    R. Pemantle. Search cost for a nearly optimal path in a binary tree. Ann. Appl. Probab., 19(4):1273–1291, 2009

    work page 2009

  58. [58]

    M. I. Roberts. Fine asymptotics for the consistent maximal displacement of branching brownian motion. Electronic Journal of Probability, 20:1–26, sep 2015

    work page 2015

  59. [59]

    T. H. Savits. The explosion problem for branching Markov process. Osaka Math. J. , 6:375–395, 1969

    work page 1969

  60. [60]

    S. Sawyer. Branching diffusion processes in population genetics. Advances in Applied Probability, 8(4):659–689, 1976

    work page 1976

  61. [61]

    M. Sellke. The threshold energy of low temperature langevin dynamics for pure spherical spin glasses, 2024

    work page 2024

  62. [62]

    D. Slepian. The one-sided barrier problem for Gaussian noise. Bell System Tech. J. , 41:463–501, 1962

    work page 1962

  63. [63]

    E. Subag. Following the ground states of full-rsb spherical spin glasses. Communications on Pure and Applied Mathematics , 74(5):1021–1044, 2021. Universite Claude Bernard Lyon 1, ICJ, CNRS UMR 5208, Ecole Centrale de Lyon, INSA Lyon, Universit ´e Jean Monnet, 43 boulevard du 11 novembre 1918, 69622 Villeurbanne Cedex, France Institut de Math´ematiques de...

    work page 2021