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](http://dx.doi.org/10.1109/SFCS.1979.34) 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?
> 
> 
> 



Cops and drunken robbers
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.


