Louigi Addario-Berry
Université McGill
20 février 2009 de 16 h 00 à 18 h 00 (heure de Montréal/HNE) Sur place
Colloque par Louigi Addario-Berry (Université McGill)
The problem is related to searching in trees. Suppose we are given a complete binary tree (a rooted tree in which the root has degree 3 and every other vertex has degree 2) with independent, identically distributed random edge weights (say copies of some random variable X). The depth d(v) of a vertex v is the number of edges on the path from v to the root. We give each vertex v the label S_v which is the sum of the edge weights on the path from v to the root. For positive integers n, we let M_n be the maximum label of any vertex at depth n, and let M^* = sup {M_n: n =0,1,...}. It is of course possible that M^* is infinity. Under suitable moment assumptions on X, it is known that there is a constant A such that M_n/n --> A almost surely and in expectation. We call the cases A>0, A=0, and A< 0 supercritical, critical, and subcritical, respectively. We derive more precise information about the expected value E(M_n) than is captured by the above "law of large numbers"-style result, and derive exponential tail bounds for M_n-E(M_n). These results are "branching random walk" analogues of results Kesten (1987) proved for branching Brownian motion. Our techniques also allow us to derive information about branching random walks in higher dimensions (with steps in R^d, d > 1). When A <= 0 it makes sense to try to find the vertex of maximum weight M* in the whole tree. One possible strategy is to only explore the subtree T_0 containing the root and consisting only of vertices of non-negative weight. With probability bounded away from zero this strategy finds the vertex of maximum weight. We derive precise information about the expected running time of this strategy. Equivalently, we derive precise information about the random variable |T_0|. In the process, we also derive rather precise information about M*. This answers two questions posed by Aldous (1997). Parts of this work are joint with Nicolas Broutin and with Bruce Reed.
Adresse
UQAM-Pavillon Sherbrooke- 200 Sherbooke o., salle SH 3420