On Playing Golf with Two Balls

We analyze and solve a game in which a player chooses which of several Markov chains to advance, with the object of minimizing the expected time (or cost) for one of the chains to reach a target state. The solution entails computing (in polynomial time) a function gamma-a variety of "Gittins index"-on the states of the individual chains, the minimization of which produces an optimal strategy. It turns out that gamma is a useful cousin of the "expected hitting time" of a Markov chain, but is defined even, for example, for random walks on infinite graphs. We derive the basic properties of gamma and consider its values in some natural situations.