Capturing the drunk robber on a graph

zbMATH Open1298.05224arXiv1305.4559MaRDI QIDQ406701FDOQ406701

Peter Winkler, Natasha Komarov

Publication date: 9 September 2014

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: We show that the expected time for a smart "cop" to catch a drunk "robber" on an $n$-vertex graph is at most $n+mo(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+mo(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.

Full work available at URL: https://arxiv.org/abs/1305.4559

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Chasing a drunk robber in many classes of graphs
• Some remarks on cops and drunk robbers
• Cop vs. gambler
• Cops and invisible robbers: the cost of drunkenness
• Cops and robbers in a random graph

zbMATH Keywords

random walkspursuit games on graphs

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Random walks on graphs (05C81) Games involving graphs (91A43) Positional games (pursuit and evasion, etc.) (91A24)

Cites Work

• The capture time of a graph
• On the cop number of a graph
• Vertex-to-vertex pursuit in a graph
• On cop-win graphs
• A note on \(k\)-cop, \(l\)-robber games on graphs
• Maximum hitting time for random walks on graphs
• On Cumulative Sums of Random Variables
• Projective Planes
• Collisions Among Random Walks on a Graph
• Title not available (Why is that?)
• Gibbs measures and dismantlable graphs
• Maximum diameter of regular digraphs
• A probabilistic approach to Carne's bound

Cited In (4)

• General cops and robbers games with randomness
• Chasing a drunk robber in many classes of graphs
• TIPSY COP AND DRUNKEN ROBBER: A VARIANT OF THE COP AND ROBBER GAME ON GRAPHS
• Selfish cops and passive robber: qualitative games

This page was built for publication: Capturing the drunk robber on a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q406701)