The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

An Isaac Newton Institute Workshop

First-Passage and Extreme Value Problems in Random Processes

Search algorithms and branching random walks on trees

28th June 2006

Author: Pemantle, R (David Rittenhouse Laboratories)

Abstract

A problem posed by Aldous is to estimate the complexity of finding a (1 - epsilon)-optimal particle in a branching random walk. This is computed in terms of the probability of existence of a trajectory staying forever above the critical drift minus epsilon. (it is known that no particle can stay above the critical drift forever). I will then discuss the computation of this probability, in a continous time (branching Brownian motion) setting, which involves estimating solutions to the KPP equation.