Cop vs Gambler

What is cop vs. gambler?
A variation of cop vs. robber where the robber is not restricted by the graphs edges, and instead moves accordingly to to a time-independent probability distribution. The cop moves from vertex to adjacent vertex with the goal of minimizing expected capture time; making the gamblers goal to maximize it

Things to know:
graph: connected and undirected with V(G) = {$v_{1}, v_{2},..., v_{n}$}
cop: same as original rules, can move from vertex to adjacent vertex and stay put on each turn
gambler: chooses probability distribution $p_{1}, p_{2},...,p_{n}$ on V(G). Each time t >= 0 he is at vertex $v_{i}$ with probability p
note: The gambler can pick whatever probabilities he wants as long as they sum to 1.

Conditions:
-players move simultaneously
-players move in the dark
-game continues until gambler is captured (both cop and gambler occupy the same vertex)

Vocabulary:
capture time- remains the same as cop vs. robber, that is the number of moves up to and including the capture.
gamble- the gamblers probability distribution, for example if a graph has 5 vertices labeled $v_{1}, v_{2}, v_{3},v_{4}, v_{5}$, on choice of gamble for the gambler is $p_{1}$ = .05 $p_{2}$ = .25 $p_{3}$ =.40  $p_{4}$ = .15 $p_{5}$ =.15
value of the game - expected capture time with both players playing at their best.

There are two variations of cop vs.gambler: 1) cop knows the gamble and 2)cop doesn't know the gamble. I am going to focus mainly on when the cop does know the gamble.

We know;
The cop can capture the gambler in expected time less than or equal to n on $P_{n}$
proof:
Strategy: cop moves from $v_{1}$ towards $v_{n}$ stopping when $p_{i}$ is large enough to allow it.
Now, Suppose cop is at $v_{i}$:
- let $m_{i}$ = n-i +1, be the total number of vertices "ahead" of the cop, including the one she is occupying
-let $c_{i}$ = $p_{i}+...+p_{n}$, be the sum of probabilities of vertices that are ahead
-let T_{i} be expected time from now (current position) until capture time

Claim: $T_{i} < m_{i}/c_{i}$ for all i /in {i....n} proceed by induction
when $m_{i}$=1, i = n, so the cop is at $v_{n}$, hence $C_{n} = P_{n}$ therefore
$T_{n} = 1/P_{n} = M_{n}/C_{n}$
Suppose this holds for all $m_{j}$ for j > 1, and cop has arrived at v_{i}
if $p_{i} >= c_{i}/m_{i}$ we are done since $T_{i} = i/p_{i} <= m_{i}/c_{i}$
suppose $p_{i}<c_{i}/m_{i}$ with probability $p_{i}$, the cop captures the gambler at $v_{i}$
(which takes one) and with probabiltity 1-p; she moves to vertex v_{i+1},
Now: $m_{i+1}=m_{i}-1<m$; so expected capture time from this new position is bounded by $m_{i+1}/c_{i+1}=m_{i}-1/c_{i}-p_{i}$. This yields the following inequality:
$T_{i}$ ≤ 1 + (1 − $p_i$) $m_i$−1 $c_{i}−p_{i}$
We have (for i > 1):
$p_{i} < c_{i}/ m_{i}$
⇒ $c_{i}(c_{i} − 1) < m_{i}p_{i}(c_{i} − 1)$
⇒ $c_{i}(c_{i} − m_{i}p_{i} + m_{i} − 1 + p_{i} − p_{i}) < m_{i}(c_{i} − p_{i})$
⇒ $c_{i} c_{i} − p_{i} (c_{i} − p_{i} + m_{i}(1−p_{i}) − (1−p_{i})) < m_{i }$
⇒ $c_{i} + c_{i}(1−p_{i}) c_{i} − p_{i} (m_{i} − 1) < m_{i}$
⇒ $1 + 1−p_{i} c_{i} − p_{i} (m_{i} − 1) < m_{i} c_{i}$
Therefore $T-{i} < m_{i} c_{i}$ whenever $p_{i} < c_{i} m_{i}$.

Lemma 2.1:  The cop can capture the gambler in expected time at most n on any tree of order n.

as well as:
Lemma 3.1: The cop and the gambler game played against a uniform gamble has expected capture time exactly n.

and:
Theorem 3.2: The value of the cop vs. gambler game on any connected n-vertex graph is n.

all of which I will discuss in class tomorrow.

It turns out the game value is n regardless of the graphs structure, whether the cop picks her initial position or not, or  whether the cop chooses her initial position before or after the gambler makes his strategy known.

We know a few different things about the unknown gambler (when the gamblers gamble is not known). One I found most interesting was Lemma 4.4 because it allows us to compare it directly with the known gambler.
Lemma 4.4: The cop vs. unknown gambler has expected capture time of less then 2n, on any connected n-vertex graph.
Since this is only any upper bound this does not hold true for every case but in most cases the unknown gambler is stronger compared to the known gambler.

Food for thought:
Imagine an anit-incursion program (or a program to prevent an attack) has to navigate a linked list of ports, trying to minimize the time to intercept an enemy packet as it arrives.; if the enemies' port choice is known we a get a version of the known gambler, otherwise the unknown gambler.