CS Theory Colloquium: David Aldous (UC Berkeley)
Speaker: David Aldous
Date: Friday, February 24th, 2023
Time: 1:00 PM
Location: LSB 1001
Host: Eric Vigoda
Title: From Euler to Stellaris: New Variants of Random Walks
Abstract:
This is a non-technical talk, intended to be appropriate for undergraduates.
Random walks, either in $d$-dimensional space or on a graph, have been studied in theoretical and applied probability for over a century. But new variants arise constantly, and I will describe three projects, on each of which I have collaborated with undergraduate researchers.
(1) Perhaps the oldest theorem in graph theory is Euler's theorem on the existence of tours that use each edge of a directed graph exactly once. What is the behavior of a random such tour?
(2) For a finite graph linking vertices in the plane, one can move along edges at unit speed using the NUV algorithm, that is always move toward the Nearest Unvisited Vertex. How long does this take to visit every vertex?
(3) "4X games", exemplified by the Civilization series and Stellaris, are a genre of complex strategy computer games. Consider a hugely oversimplified game that captures the essence of the first stages (eXplore, eXpand) of such games. Your agent starts at a vertex on a 600-vertex graph. You can move along edges at unit speed, and every vertex you visit is added to your growing empire. But other players are doing this at the same time, and you cannot visit a vertex in their empires. Also, you don't see the whole graph, only the neighborhood of where you've visited. Eventually every vertex is taken into some player's empire, and the goal is to have the largest empire.
Problem: what is a good strategy for deciding where to move next?
The NUV strategy is simple to describe and implement. Intuitively it is clear that a human player will beat an NUV opponent, but can one describe an explicit strategy that does so?
Bio:
David Aldous was Professor in the Statistics Dept at U.C. Berkeley, 1979--2018. He received his Ph.D. from Cambridge University in 1977. He is the author of "Probability Approximations via the Poisson Clumping Heuristic" and (with Jim Fill) of a notorious unfinished online work "Reversible Markov Chains and Random Walks on Graphs". His research in mathematical probability has covered weak convergence, exchangeability, Markov chain mixing times, continuum random trees, stochastic coalescence and spatial random networks. A central theme has been the study of large finite random structures, obtaining asymptotic behavior as the size tends to infinity via consideration of some suitable infinite random structure. He has recently become interested in articulating critically what mathematical probability says about the real world.
He is a Fellow of the Royal Society, and a foreign associate of the National Academy of Sciences.