An anti-incursion algorithm for unknown probabilistic adversaries on connected graphs

2017/01/04 by Geneson, Jesse
#05C85 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1701.01599

Abstract

A gambler moves on the vertices 1, …, n of a graph using the probability distribution p₁, …, p_n. A cop pursues the gambler on the graph, only being able to move between adjacent vertices. What is the expected number of moves that the gambler can make until the cop catches them? Komarov and Winkler proved an upper bound of approximately 1.97n for the expected capture time on any connected n-vertex graph when the cop does not know the gambler's distribution. We improve this upper bound to approximately 1.95n by modifying the cop's pursuit algorithm.

Related

• Distributed pursuit algorithms for probabilistic adversaries on\n connected graphs
• Cops vs. Gambler
• Expected capture time and throttling number for cop versus gambler
• Cops and robbers in random graphs
• Chasing robbers on random geometric graphs---an alternative approach