Branching random walks and searching in trees (10w5085)

Objectives

We have four specific goals in organizing this workshop, each of which is to gain a deeper understanding and strengthen existing results for a
question related to branching random walk and searching in trees. Below we outline these four goals and point out specific existing contributions
from the proposed invitees to research on these questions.

Recent developments for branching random walks

Very recently, Bramson and Zeitouni (2007,2008+), Addario-Berry and Reed (2008+), and Hu and Shi (2008+) have all proved related results on the position of the minimum $M_n$
and on its concentration around its mean; these results build on existing work by Biggins, Devroye, and McDiarmid, among others.
It is now clear that for a wide range of branching random walks, there are constants $alpha in mathbb{R}$ and $beta>0$ such that $M_n$
is roughly $alpha n + beta log n$ in expectation and in probability (though, as established by Hu and Shi, {em not} almost surely). Furthermore, $mathbf{P}{M_n - mathbf{E} M_n>x}$ decays
exponentially quickly in $x$.

These recent results are established using very different techniques. Bramson and Zeitouni prove their concentration result by connecting the BRW to a family of recursive equations and then studying a related Lyapunov function; Addario-Berry and Reed use a rather combinatorial argument based on the second moment method; and Hu and Shi proceed by connecting a certain exponential martingale with a distinguished path called the "spine" of the tree. There are some intriguing links between the three methods, and a deeper understanding
of these links has the potential to lead to a common strengthening of all three results. To understand these connections is the one of the four aims of the workshop.

The greedy algorithm and its variants

From the algorithmic point of view, it is natural to ask whether we can efficiently find an individual in the $n$'th generation who attains or comes close to attaining the minimum position $M_n$.
One extremely natural technique for doing finding an individual with small displacement is the following: given all the individuals seen thus far, consider the individual with the minimum displacement and explore its children.
We refer to this approach as the greedy algorithm. Aldous (1992) first analyzed this procedure, in the context of binary trees, and gave sufficient conditions for the greedy algorithm to find a path approximating
the path to $M_n$ up to a fixed error $epsilon n$ in the slope.
Aldous further made the (very natural) conjecture that the greedy algorithm stochastically optimizes the minimum position seen up to time $t$.
Surprisingly, this conjecture turns out to be false, as was shown by Stacey (1999); however, Stacey also showed that the greedy algorithm is optimal in a much weaker sense than that proposed by Aldous, and posed multiple
intriguing questions about the strongest sense in which some form of optimality holds. (It is worth mentioning the work of Karp and Pearl (1983) and McDiarmid (1992), who studied the behavior of "bounded backtracking" algorithms for finding individuals with small displacement, also using the connection with
branching random walks.)

More recently, Pemantle (2008+) has proposed a new algorithm, also of a "greedy" variety for finding individuals whose displacement is close to $M_n$; the algorithm applies in the case that the displacements are Bernoulli. Pemantle has proved (for certain "subcritical" choices of the Bernoulli parameter) that the running time of this algorithm is with high probability best possible up to $o(n)$ terms.
A key step that will be required for the analysis of the remaining cases of this algorithm is to understand branching random walks in which all particles whose displacement exceeds a fixed slope are "killed" and no longer reproduce.
Pemantle has also made an intriguing conjecture about the class of algorithms in which optimal algorithms must lie.
An extension of Aldous, Pemantle, and Stacey's results to more general displacement and offspring distributions, and an investigation of the open questions surrounding optimality, is the second of our four aims.

Finitization: applying BRW results to search trees

When using results on branching random walk to analyze (usually tree-based) data structures, one of the primary obstacles is the fact that branching random walks are usually limit objects for the data structures in question.
To apply results for BRW to the data structures themselves, one must somehow "pass from infinite to finite," and it is usually far from clear how to proceed.
For example, the expected worst-case query time is essentially determined by the finitization of the minimum displacement $M_n$. Using this fact, it is rather straightforward to bound the first-order asymptotics of the expected
worst-case query time (i.e. to "finitize" the fact that $M_n = (1+o(1))alpha n$), but understanding lower order terms can be extremely difficult. For the case of binary search trees, the link with (binary branching,
exponential displacement) branching random walks has been known since work of Biggins, Devroye, and Pittel in the 1980s. However, pinning down the lower-order behavior of worst-case query time was only
accomplished (by Reed and, later, Drmota) in 2003. A substantial part of the technical challenge in Reed's approach was dealing with the finitization, and his solution made heavy use of binary branching.
Chauvin and Drmota ( have had some success at extending Drmota's approach to more general search trees; however, a general strategy for handling this finitization remains elusive. To find one is the third aim
of the workshop.

The behavior of branching Markov chains and branching random walk in random environment

Finally, one may consider a generalization of the branching random walk model, where the displacements are given by a Markov chain (displacements along distinct edges remain independent), or where the random displacements depend on the initial position. In this case much less is known about the behavior of the system. The first-order asymptotics can be derived without much more difficulty than in branching random walks, but lower order behavior seems much
harder to handle. A common approach is to renormalize so that the first order term vanishes (i.e. so that $M_n=o(n)$) by subtracting a fixed constant from each displacement. Once this is done, even the question
of recurrence or transience is rather difficult; though at this point it is rather well understood due to work of Comets, Menshikov and Popov (1998), Machado and Popov (2000,2001,2003), Gantert and Muller (2006) and Muller (2008+).
The fourth aim of this workshop is to investigate what statements can be made about the lower order behavior of branching Markov chains and branching random walk in random environment,
along the lines of the recent developments for branching random walk.