You are here

[Video] Yuval Peres, Principal Researcher and Theory Group Manager at Microsoft Research

Friday, May 17, 2013 - 2:30pm
DEM 004

Search games and Optimal Kakeya Sets

Yuval Peres, Principal Researcher and Theory Group Manager at Microsoft Research

 

A planar set that contains a unit segment in every direction is called a Kakeya set. These sets have been studied intensively in geometric measure theory and harmonic analysis since the work of Besicovich (1928); we find a new connection to game theory and probability. A hunter and a rabbit move on an n-vertex cycle without seeing each other until they meet. At each step, the hunter moves to a neighboring vertex or stays in place, while the rabbit is free to jump to any node. Thus they are engaged in a zero sum game, where the payoff is the capture time. We show that every rabbit strategy yields a Kakeya set; the optimal rabbit strategy is based on a discretized Cauchy random walk, and it yields a Kakeya set K consisting of 4n triangles, that has minimal area among such Kakeya sets. Passing to the scaling limit yields a simple construction of a random Kakeya set with zero area from two Brownian motions. (Talk based on joint work with Y. Babichenko, R. Peretz, P. Sousi and P. Winkler).

Event Type: 
Event Subcalendar: 
Share