Yuval Peres DLS

This week, Yuval Peres gave a Distinguished Lecture Series, which is a series of three talks for a general mathematical audience by a prominent mathematician visiting UCLA. I felt really compelled to attend these talks, since Peres seems to be working on very fundamental problems that have some interest for me. I read some of his work when I was in high school, and I was pleased to finally attend some of his lectures!

This blog post deals with the talks on Tuesday and Wednesday. I won't give a comprehensive account, because my comprehension wasn't 100%.

The first talk was about Search Games and Optimal Kakeya sets, based on joint work with Babichenko, Peretz, Sousi, and Winkler. He defined a game $G_n$ with two players "Hunter" and "Rabbit" on a cycle with $n$ vertices. At time $0$, each player chooses a position on the cycle. Then for each time step, the hunter moves to an adjacent position (or stays at the same position). The rabbit simultaneously moves to any position on the cycle. The players cannot see each other (Peres said to imagine the game is played in the dark). The game ends when Hunter and Rabbit occupy the same location.

The punchline was that the optimal winning strategies for this game can be used to construct an "optimal" Kakeya set. This Kakeya set is the union of a certain number of triangles, and has the smallest area among all such Kakeya sets with the same number of triangles. A Kakeya set is just a subset of the plane that has a unit segment in every direction. The first construction of a Kakeya set was by Besicovitch, and these sets have some importance in harmonic analysis.

But I was really fascinated by this simple game for its own interest.

For technical reasons, it is easier to consider the game $G^*_n$ which runs for $n$ timesteps, and the Hunter and Rabbit move as above. The payoff for Hunter is 1 if he's successful, 0 otherwise. To make it a zero-sum game, the payoff for Rabbit is -1 if Hunter is successful, 0 otherwise. So von Neumann proved this minimax theorem, which asserts the existence of "optimal" strategies for both players. A strategy is a rule which tells a player what move to make, each move assigned a probability depending on the situation (previous moves and information known to the player). Then von Neumann's theorem (as I understood it from the talk) says that there is a value $v$ such that $v$ is both:

• the maximum possible expected payoff for any of I's strategies, assuming that II plays optimally against that particular strategy (so the max over all strategies of I of (the min over all strategies of II of the expected payoff of running the strategies against each other))
• the minimum possible expected payoff for I for any of II's strategies, assuming that I plays optimally against that particular strategy (so $-v$ has the same role for II as $v$ had for I above).

I tried to say it in a way which I think can be easily made precise. It's very nice that you can formulate this notion of optimality, and prove that optimal strategies exist. It seems like this definition of optimality can often involve being as unpredictable as possible, because if the opponent knows your strategy, he can use that information to predict your moves and play against that. So, barring situations where for example there is a sequence of moves with no counterplay, it seems to be greatly beneficial to move around randomly.

What's the connection between $G_n$ and $G^*_n$? Peres answered this in his next slides: applying the minimax theorem to our situation, there is a value $p_n$ for the game $G^*_n$, which can be interpreted as the probability of capture under optimal play. Now we argue that in the original game $G_n$, the mean capture time in $G_n$ under optimal play is between $n/p_n$ and $2n/p_n$. The rabbit can just play his $G^*_n$ strategy for every block of time $n$, so he can ensure that the mean capture time is $\ge n/p_n$ (using linearity of expectation). The hunter can play his $G^*_n$ strategy for every other block of time $n$, using the odd blocks to move to the starting position for his next strategy. This ensures a mean capture time $\le 2n/p_n$ (again using linearity of expectation).

He then went over some sample strategies for the players, involving staying still, moving in some direction at constant speed, etc. It was amazing because he involved the audience, asking them to try to figure out different strategies. I forgot exactly what $p_n$ turned out to be: I think it was something like $n^{-1/2}$? But the optimal strategy for the hunter turned out to be going at a random speed, like I suspected. The rabbit's optimal strategy actually involved not moving around too much: I stopped taking notes here because I was struggling to keep up with his arguments at this point. Someone in the audience gave an intuitive explanation of this, but I must admit I wasn't sure about this explanation either.

I didn't know the minimax theorem before, so this talk was very eye-opening. I wonder how the proof of that theorem goes, since evidently it doesn't construct the optimal strategies (which seem to be found from methods special to the game at hand). If the argument is nice, I'll try to write a blog post about it. I wonder if these probabilistic strategies can be somehow generalized to the infinite situations that set theorists are interested in (probably just nonsense, I know!)
--------------------

The DLS on Wednesday was about random walks on groups (which seems to just be a random walk on the Cayley graph of a group, each generator has different weights). It was a bit hard to follow for me, but he proved some nice results on the blackboard bounding the expected distance in the graph between the starting point and the $n$th step of the walk (this is the rate of escape). It reminded me a lot of IST 1 class from Caltech, since a lot of inequalities I learned there were used in the talk. Unfortunately, I won't post my notes about this talk.