Capturing the drunk robber on a graph (Q406701)

Summary: We show that the expected time for a smart ``cop'' to catch a drunk ``robber'' on an \(n\)-vertex graph is at most \(n +o(n)\). More precisely, let \(G\) be a simple, connected, undirected graph with distinguished points \(u\) and \(v\) among its \(n\) vertices. A cop begins at \(u\) and a robber at \(v\); they move alternately from vertex to adjacent vertex. The robber moves randomly, according to a simple random walk on \(G\); the cop sees all and moves as she wishes, with the object of ``capturing'' the robber -- that is, occupying the same vertex -- in least expected time. We show that the cop succeeds in expected time no more than \(n+o(n)\). Since there are graphs in which capture time is at least \(n-o(n)\), this is roughly best possible. We note also that no function of the diameter can be a bound on capture time.