2016/10/09 by Jesse Geneson, Geneson, Jesse · 1 citation
Computer Science · Social Sciences · #05C85 #Adversarial Robustness in Machine Learning #Crime, Illicit Activities, and Governance #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Spam and Phishing Detection #Terrorism, Counterterrorism, and Political Violence #cs.DM #msc:05C85
paper · pdf · doi:10.48550/arxiv.1610.02724
7 pages
arxiv created 2016/10/09 · openalex publication_date 2016/10/09 · arxiv updated 2016/10/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A gambler moves between the vertices 1, …, n of a graph using the probability distribution p1, …, pn. Multiple cops pursue the gambler on the graph, only being able to move between adjacent vertices. We investigate the expected capture time for the gambler against k cops as a function of n and k for three versions of the game: (1) known gambler: the cops know the gambler's distribution (2) unknown gambler: the cops do not know the gambler's distribution (3) known changing gambler: the gambler's distribution can change every turn, but the cops know all of the gambler's distributions from the beginning. We show for n > k that if the cops are allowed to choose their initial positions before the game starts and before they know the gambler's distribution(s), and if both the gambler and the cops play optimally, then the expected capture time is Θ(n/k) for the known gambler, the unknown gambler, and the known changing gambler.