pith. sign in

arxiv: 1902.05860 · v3 · pith:FVWC6NZ2new · submitted 2019-02-10 · 💻 cs.DM · math.CO· math.PR

Expected capture time and throttling number for cop versus gambler

classification 💻 cs.DM math.COmath.PR
keywords gamblercaptureexpectedtimegamenumberversusdistribution
0
0 comments X
read the original abstract

We bound expected capture time and throttling number for the cop versus gambler game on a connected graph with $n$ vertices, a variant of the cop versus robber game that is played in darkness, where the adversary hops between vertices using a fixed probability distribution. The paper that originally defined the cop versus gambler game focused on two versions, a known gambler whose distribution the cop knows, and an unknown gambler whose distribution is secret. We define a new version of the gambler where the cop makes a fixed number of observations before the lights go out and the game begins. We show that the strategy that gives the best possible expected capture time of $n$ for the known gambler can also be used to achieve nearly the same expected capture time against the observed gambler when the cop makes a sufficiently large number of observations. We also show that even with only a single observation, the cop is able to achieve an expected capture time of approximately $1.5n$, which is much lower than the expected capture time of the best known strategy against the unknown gambler (approximately $1.95n$).

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.