Search

Consider a branching random walk on Z in discrete time. Denote by Ln(k) the number of particles at site k ∈ Z at time n ∈ N0. By the profile of the branching random walk (at time n) we mean the function k → Ln(k). We establish the following asymptotic expansion of Ln(k), as n→∞: e-Φ(0)nLn(k) = e-1/2x2 n(k)√ 2πΦ (0)n Σr j=0 Fj (xn(k))/nj/2 +o(n -r+1/2 ) a.s., where r ∈ N0 is arbitrary, Φ(β) = logΣk∈Z eβkEL1(k) is the cumulant generating function of the intensity of the branching random walk and xn(k) = k -Φ (0)n/√Φ'' (0)n . The expansion is valid uniformly in k ∈ Z with probability 1 and the Fj's are polynomials whose random coefficients can be expressed through the derivatives of Φ and the derivatives of the limit of the Biggins martingale at 0. Using exponential tilting, we also establish more general expansions covering the whole range of the branching random walk except its extreme values. As an application of this expansion for r = 0, 1, 2 we recover in a unified way a number of known results and establish several new limit theorems. In particular, we study the a.s. behavior of the individual occupation numbers Ln(kn), where kn ∈ Z depends on n in some regular way. We also prove a.s. limit theorems for the mode argmaxk∈Z Ln(k) and the height maxk∈Z Ln(k) of the profile. The asymptotic behavior of these quantities depends on whether the drift parameter Φ'(0) is integer, non-integer rational, or irrational. Applications of our results to profiles of random trees including binary search trees and random recursive trees will be given in a separate paper. [ABSTRACT FROM AUTHOR]