(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
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:
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.