Minima in branching random walks

By Louigi Addario-Berry, Bruce A. Reed. 2007

157 citations recorded by the source corpus.

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.

Subfields: Applied Mathematics, Mathematical Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/8de81607767a6380bde4d76c128c450fd1260f59

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

In Mathematical Physics

In Statistics and Probability

Citations in the corpus

Extreme values for two-dimensional discrete Gaussian free field (2012, unknown): “Next, let ι ∈ [2k] be the location of the maximizer of max{η τ1(i) + η (i) τ2(i) : i ∈ [2]} .”
The Seneta–Heyde scaling for the branching random walk (2011, background): “5) hold, then under P∗, 1 logn min|x|=n V (x) → (3)2 in probability; see [19], [1] or [4] for proofs under some additional assumptions.”
Asymptotics of cover times via Gaussian free fields: Bounded-degree graphs and general trees (2011, background): “Indeed, an analogue of Bramson’s result for a wide range of branching random walks was proved by Addario-Berry and Reed [1].”
Convergence in law of the minimum of a branching random walk (2013, background): “The second order was recently found separately by Hu and Shi [17], and Addario-Berry and Reed [1], and is proved to be equal to 2 lnn in probability, though there exist almost sure fluctuations (Theorem 1.”
Convergence in law of the minimum of a branching random walk (2011, background): “In [1], the authors computed the expectation of Mn to within O(1), and showed, under suitable assumptions, that the sequence of the minimum is tight around its mean.”
Convergence in Law for the Branching Random Walk Seen from Its Tip (2011, background): “Addario-Berry, L., Reed, B.: Minima in branching random walks.”
Branching random walks (2015, background): “Addario-Berry and Reed [4] also prove an analogous result for the mean of the minimal position, and obtain, moreover, an exponential tail estimate for the difference between the minimal position and its mean.”
Extrema of log-correlated random variables: Principles and Examples (2016, background): “The reader is referred to [1, 2, 24] for more details.”
Maxima of a randomized Riemann zeta function, and branching random walks (2015, background): “It has since been extended to more general branching random walks by several authors, for example, [1, 2, 11], and to log-correlated Gaussian fields see, for example, [12, 23].”
The maximum of the CUE field (2016, methodology): “H(y,z) 2 +C. 1.4. Barrier method overview. The approach we take to estimating the maximum of U is an adaptation of one developed to estimate the maximum of branching Brownian motion [Bra78] (see also [ABR09], [A¨ıd13] and [BDZ14] for the more closely related case of branching random walk). This meth”
A simple path to asymptotics for the frontier of a branching Brownian motion (2011, background): “0 P̂ ( Y 1 t , Y 2 t ∈ [1,2]|τ = s, Y 1 s = x ) P̂ ( Y 1 s ∈ dx )∣∣∣τ = s]ds ≤ ∫ 1”