Minima in branching random walks

Louigi Addario-Berry Bruce Reed 1, 2
2 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : Given a branching random walk, let $M_n$ be the minimum position of any member of the $n$th generation. We calculate $\\mathbfEM_n$ to within O(1) and prove exponential tail bounds for $\\mathbfP{|M_n-\\mathbfEM_n|>x}$, under quite general conditions on the branching random walk. In particular, together with work by Bramson [Z. Wahrsch. Verw. Gebiete 45 (1978) 89―108], our results fully characterize the possible behavior of $\\mathbf EM_n$ when the branching random walk has bounded branching and step size.
Type de document :
Article dans une revue
Annals of Probability, Institute of Mathematical Statistics, 2009, 37, pp.1044―1079
Liste complète des métadonnées

https://hal.inria.fr/hal-00795281
Contributeur : Alain Monteil <>
Soumis le : mercredi 27 février 2013 - 17:16:25
Dernière modification le : jeudi 28 février 2013 - 09:53:27

Identifiants

  • HAL Id : hal-00795281, version 1

Collections

Citation

Louigi Addario-Berry, Bruce Reed. Minima in branching random walks. Annals of Probability, Institute of Mathematical Statistics, 2009, 37, pp.1044―1079. <hal-00795281>

Partager

Métriques

Consultations de la notice

132