NB: A PDF version of this announcement (suitable for posting) is also available.

Branching Random Walks on a Graph

Peter Winkler
Bell Labs

Tuesday, February 11, 2003
1 Rockefeller, 4 pm
Tea 3:30 pm, Math Lounge

Abstract: In a simple random walk on a graph, a token steps randomly from vertex to vertex along edges of the graph. Such walks boast an elegant theory, and as a means of reaching a random vertex they have spawned an industry in applied mathematics and computer science by enabling efficient sampling and estimation. For a branching random walk we replace the token by an amoeba, which divides at each step, its children moving independently to new vertices (and soon overrunning the graph). Here memory is possible and new phenomena emerge, with some surprise consequences and connections to statistical physics. We will discuss recent results (including joint work with Graham Brightwell, London School of Economics) and some open problems.

This talk will be accessible to graduate students.