Consider a game of cops and robbers on a finite graph. The robber, for reasons left to the imagination, moves entirely randomly: at each step, he moves to a randomly chosen neighbour of his current vertex. The cop's job is to catch the robber as quickly as possible:

How do we find a strategy for the cop which minimizes the expected number of steps before she catches the robber?

If I'm reading this paper correctly, the minimum expected catch time is finite even if the graph is not cop-win. *[Edit: as mentioned in the comments below, the cop and robber will never meet if they move at the same time and are in opposite parts of a bipartite graph. Provided this is not the case, I think the paper's argument can be modified to show that the expected catch time is finite. If the cop and robber take turns, there is no need for an additional assumption and the paper can be used directly. I'd be interested in either setup.]*
For example, chasing a robber around the cycle $C_n$ gives an expected catch time of $$\sum_{k=0}^\infty\ k\cdot\frac{\binom{k}{d/2}}{2^k},$$ where $d$ is the initial distance between the cop and the robber. (Since the cycle has so much symmetry, it can be shown that this strategy is the best possible.)

I'm curious as to whether, for instance, the usual optimal strategy in a cop-win graph is optimal in this sense. I'm also interested in some generalizations of this problem (by giving weights to various things). But I don't know whether the basic problem is open, trivial, or somewhere in between, so I'll ask the catch-all question:

What is known about this problem?

3more comments