How to generate the tip of branching random walks evolved to large times

¹ Laboratoire de Physique de l'Écolenormale supérieure, ENS, Université PSL, CNRS, Sorbonne Université, Université de Paris - F-75005 Paris, France
² CPHT, CNRS, École polytechnique, IP Paris - F-91128 Palaiseau, France
³ Department of Physics, Columbia University - New York, NY10027, USA

^(a) eric.brunet@ens.fr
^(b) dung.le@polytechnique.edu
^(c) amh@phys.columbia.edu
^(d) stephane.munier@polytechnique.edu

Received: 27 July 2020
Accepted: 1 August 2020

Abstract

In a branching process, the number of particles increasesexponentially with time, which makes numerical simulations for large timesdifficult. In many applications, however, only the region close to the extremalparticles is relevant (the “tip”). We present a simple algorithmwhich allows to simulate a branching random walk in one dimension, keepingonly the particles that arrive within some distance of the rightmost particle ata predefined time T. The complexity of the algorithm growslinearly with T. We can furthermore choose to require that therealizations have their rightmost particle arbitrarily far on the right from itstypical position. We illustrate our algorithm by evaluating an observable forwhich no other practical method is known.