Cop vs. gambler

DOI10.1016/J.DISC.2016.01.015MaRDI QIDQ267177zbMATH OpenOpenAlexFDO

Authors Natasha Komarov, Peter Winkler

Publication date 8 April 2016

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

cops and robberspursuit/evasion games

Mathematics Subject Classification ID

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

Abstract: We consider a variation of cop vs. robber on graph in which the robber is not restricted by the graph edges; instead, he picks a time-independent probability distribution on $V(G)$ and moves according to this fixed distribution. The cop moves from vertex to adjacent vertex with the goal of minimizing expected capture time. Players move simultaneously. We show that when the gambler's distribution is known, the expected capture time (with best play) on any connected $n$-vertex graph is exactly $n$. We also give bounds on the (generally greater) expected capture time when the gambler's distribution is unknown to the cop.

Recommendations

• Capturing the drunk robber on a graph
• Chasing a drunk robber in many classes of graphs
• The role of information in the cop-robber game
• Some remarks on cops and drunk robbers
• The capture time of a graph

Cites work

• A note on \(k\)-cop, \(l\)-robber games on graphs
• scientific article; zbMATH DE number 1789918 (Why is no real title available?)
• Hunter, Cauchy rabbit, and optimal Kakeya sets
• Maximum hitting time for random walks on graphs
• On cop-win graphs
• On the cop number of a graph
• Randomized Pursuit-Evasion in Graphs
• Search Games with Mobile and Immobile Hider
• The capture time of a graph
• The game of cops and robbers on graphs
• Vertex-to-vertex pursuit in a graph

Cited in

(3)

• Chasing a drunk robber in many classes of graphs
• Locating a robber with multiple probes
• Capturing the drunk robber on a graph

This page was built for publication: Cop vs. gambler

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