  The cops and robbers game has been extensively studied under the assumption
of optimal play by both the cops and the robbers. In this paper we study the
problem in which cops are chasing a drunk robber (that is, a robber who
performs a random walk) on a graph. Our main goal is to characterize the "cost
of drunkenness." Specifically, we study the ratio of expected capture times for
the optimal version and the drunk robber one. We also examine the algorithmic
side of the problem; that is, how to compute near-optimal search schedules for
the cops. Finally, we present a preliminary investigation of the invisible
robber game and point out differences between this game and graph search.
