Power laws and killed branching random walk

(3/11) A complete proof has been posted by Elie Aidekon and Yueyun Hu and Olivier Zindy. This extends the "critical case" proof by Louigi Addario-Berry and Nicolas Broutin and a subsequent refinement by Elie Aidekon and the branching Brownian motion case analyzed in Maillard.

Consider branching random walk (BRW) on the line. For simplicity take the following special setting. In generation zero there is one individual, at the origin. Each individual has two children in the next generation, and the positions of the children relative to parent are i.i.d. with some distribution X for which E \exp(aX) is finite for small a. (More generally, a random number N of children whose positions relative to parent may be dependent.)

Let R_n be the position of the rightmost individual in generation n. It is well know that

n^{-1} R_n \to c

for a computable constant c.

Now modify the process by saying that any birth at a position x < 0 is killed. This is branching random walk with killing. Call the case c < 0 subcritical and the case c = 0 critical. In either of these cases, (ultimate) extinction is certain in the "with killing" process. Write Z for the total population until extinction.

Conjecture. In the subcritical case, Z has rough power-law tail:

P(Z > z) = b^{z + o(1)} for some b > 1


while in the critical case,

E[Z] is finite but E[Z \log Z] is infinite.

The intuitive idea in the subcritical case is to consider the position R = \max_n R_n of the rightmost ever individual, and the number Z^* of descendants of that individual. There are computable constants a, d such that which imply a power-law tail for Z^*, and presumably Z has the same rough power law.

In the critical case there are some 1999 notes by Robin Pemantle giving an incomplete outline of a proof of the conjecture in the special case where X has values {-1,1} only.

History. Posed around 1998, as an offshoot of my work studying heuristic combinatorial optimization algorithms by analyzing their behavior where the objective function is tree-indexed random walk. The present setting can be regarded as a toy model for backtracking algorithms and as the 57th possible different explanation of occurence of power-law distributions.

Update (2008). The appearance of power laws in somewhat related models is discussed by Jelenkovic and Tan and by Bordenave.