2016/10/09 by Jesse Geneson, Geneson, Jesse
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
paper · pdf · doi:10.48550/arxiv.1610.02724
openalex publication_date 2016/10/09 · 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\nprobability distribution p1, \…, pn. Multiple cops pursue the\ngambler on the graph, only being able to move between adjacent vertices. We\ninvestigate the expected capture time for the gambler against k cops as a\nfunction of n and k for three versions of the game: (1) known gambler: the\ncops know the gambler's distribution (2) unknown gambler: the cops do not know\nthe gambler's distribution (3) known changing gambler: the gambler's\ndistribution can change every turn, but the cops know all of the gambler's\ndistributions from the beginning. We show for n > k that if the cops are\nallowed to choose their initial positions before the game starts and before\nthey know the gambler's distribution(s), and if both the gambler and the cops\nplay optimally, then the expected capture time is \Θ(n/k) for the known\ngambler, the unknown gambler, and the known changing gambler.\n