Cops and drunken robbers

Question

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?

Answer 1

I think that I have an example where the optimal strategy for a random robber is different from the normal winning strategy.

Let me specify the graph first. We have 5 points A,B,C,D and E forming a cycle. So an edge connects A to B, and an edge connects B to C etc. points A and C are also connected by an edge. We also add a billion points connected to only D and a billion points connected to only E.

Now let me specify the position. The cop is on vertex A and the robber is on vertex D.

Now the winning strategy is for the cop to move to vertex B then If the robber moves to E then The cop moves to C and then if the robber moves back to D The cop moves to D and we are done. If then instead of moving to D the robber moves to one of the many points connected only to E the cop moves to A and now the robber must move to E and then the cop captures the robber there.

Now if the robber's moves are random The optimal strategy is for the cop to move to vertex C because the robber will with odds a billion to one move that the robber will move to one of the points adjacent only to D. Then the cop will move to D and in the next move the robber must move into D and and the cop will catch the robber after only two moves. Then if the robber moves to E the cop moves to A and again the odds are a billion to one that the robber will move to a point adjacent only to E and the cop would move To E and catch the robber. So the cop would alternate between A and C waiting for the robber to go to a point adjacent to only E or only D and this would generate and infinite series that sums to less than 3.

Now if the cop follows the normal strategy he will move to B then the robber will move to a vertex adjacent only to D and then the cop will move to C the robber will have to move to d and then the cop will move to C catching the robber in three moves. So here the winning strategy is different from the optimal winning strategy is different from the optimal random strategy.

Answer 2

Here are some recent papers on the topic:

1. Natasha Komarov, Peter Winkler, Capturing the Drunk Robber on a Graph
2. Athanasios Kehagias, Paweł Prałat: Some remarks on cops and drunk robbers
3. Athanasios Kehagias, Dieter Mitsche, Paweł Prałat: Cops and invisible robbers: The cost of drunkenness

There are also some related slides: here and here (by the OP).