Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Suppose there are two or more tokens at vertices of some
fixed connected graph. Each token will, if you prod it, step
to a random neighbor. You wish to get a token to some specified
target vertex as fast as you can.
If you have to pick one token and stick with it, the problem
is easy: you compute the expected hitting time to the target
for each token, and choose the one that minimizes this quantity.
But if you're allowed to change your mind at any time, the
situation changes.
It turns out that there's still a simple way to play this game
optimally, based on a variation of a concept called the "Gittins
index." We'll present our adaptation of a proof due to Richard
Weber that this really works. All of this generalizes hugely to
arbitrary Markov chains, costs, and rewards, and now even
combinatorial constraints.
Sources: John Gittins (new book edition with Glazebrook and
Weber); papers (Dumitriu, Tetali and Winker; Janson and Peres);

new paper (Gupta, Jiang, Scully and Singla).