PaperlayerView exact revision on arXiv

Source-linked AI summary

Deceptive Stochastic Patrolling via Markov Chain Lifting

Yohan John, Gilberto Diaz-Garcia, Jason R. Marden, Francesco Bullo

arXiv:2610.10903v1eess.SYcs.SYmath.OC

TL;DR

Standard stochastic patrol chains assign one state to each graph node, while this paper uses lifted chains with larger state spaces. It derives performance bounds and a weighted-graph optimization method, finding that lifted strategies cannot underperform optimized non-lifted chains and can substantially improve results on sparse graphs.

  • Problem

    Standard Markov-chain patrolling assigns one chain state to each graph node, while the paper seeks patrol strategies that can encode more complex behavior.

    Source: §I · p. 1

  • Method

    The paper lifts patrol Markov chains to larger state spaces, derives bounds and related metrics, and provides a tractable optimization procedure for travel-time-weighted graphs.

    Source: C. Contributions · p. 2

  • Results

    Optimized lifted chains cannot perform worse than optimized non-lifted chains, and numerical experiments show substantial improvement on sparse graphs.

    Source: C. Contributions · p. 2, §VIII · p. 11

  • Takeaways & Limitations

    Lifting relates the Kemeny constant to conductance for general Markov chains and can make an adversary who sees only location mis-specify the patrol state.

    Source: C. Contributions · p. 2

    The theoretical bounds are established for unweighted graphs; results on weighted graphs are empirical.

    Source: C. San Francisco Case Study · p. 10

Abstract

from arXiv · show

In this paper we propose lifted Markov Chains (MCs) as a new paradigm for deriving patrol strategies for mobile agents on an environment represented as a graph. Lifted MCs operate on a state space that can be larger than the set of nodes of the graph, and a projection operation maps the MC state to the corresponding node of the graph. We prove bounds on the performance improvement of lifted MCs over non-lifted MCs, where the performance is measured by the Kemeny constant, and show a corresponding monotonicity for the Stackelberg game capture probability and return-time entropy. These bounds yield a result of independent interest that relates the Kemeny constant and the MC conductance for general MCs. We also provide a tractable method for optimizing lifted MCs on general graphs with edge weights encoding travel times. Simulation results on randomly generated and real-world graphs verify that lifted MCs achieve substantial improvements, particularly on sparse graphs.

I. INTRODUCTION

The paper applies lifted Markov chains to stochastic graph patrolling, allowing multiple chain states to correspond to one patrol location. It develops this idea through a corridor example, prior-work comparisons, contributions, and the Markov-chain framework.

I. INTRODUCTION

  • Standard patrol chains assign one state to each graph node, whereas lifted chains allow multiple states per node to encode more complex patrol behavior.The paper motivates stochastic strategies as a way to prevent adversarial exploitation.Source: §I · p. 1

A. Running Example: Corridor Environment

  • For plift ∈ {0, 1}, the lifted path achieves K(P lift) = 7/2; for arbitrary paths with degree-proportional stationary distributions, lifted chains scale linearly while non-lifted chains scale quadratically.Source: A. Running Example: Corridor Environment · p. 1

B. Related Work

  • Against, this work optimizes stationary-preserving liftings of a given chain, adds Kemeny and return-time entropy metrics, and considers an adversary unaware of lifted states.The paper focuses on single-agent stochastic patrol strategies for small graphs; large graphs may be partitioned among agents.Source: B. Related Work · p. 2

C. Contributions

  • Lifted chains cannot perform worse than optimized non-lifted chains, and the paper relates Kemeny constant to conductance while providing a tractable optimizer for travel-time-weighted graphs.The authors also identify a deceptive effect when an adversary observes the graph but not the lifted state.Source: C. Contributions · p. 2

II. MARKOV CHAINS

  • A discrete-time chain assigns transition probabilities to graph-compatible moves, while its stationary distribution captures long-run visit shares and can encode location priorities.Source: §II · pp. 2–3

A. Metrics for Markov Chain Patrol Strategies

The paper presents three metrics for evaluating stochastic patrol chains and specifies how lifted chains relate to their original chains. These measures address movement speed, capture probability, and predictability of return times.

A. Metrics for Markov Chain Patrol Strategies

1) Kemeny Constant:

  • Kemeny constant summarizes mean first-passage times and, when minimized, favors patrol strategies that move quickly around the graph.Its mean first-passage-time matrix can be computed using the stated column-wise expression.Source: 1) Kemeny Constant · p. 3

2) Stackelberg Game Capture Probability:

  • Stackelberg game capture probability measures the patroller’s worst-case chance of reaching an attacked node within its attack duration.The patroller maximizes the minimum entry of the capture-probability matrix.Source: 2) Stackelberg Game Capture Probability · p. 3

3) Return-Time Entropy:

  • Return-time entropy evaluates how unpredictable the patroller’s return times are, since predictable absences can let an observing adversary time an attack.The paper maximizes a truncated version because the full metric has no closed form.Source: 3) Return-Time Entropy · p. 3

III. LIFTED MARKOV CHAINS

  • In this paper, lifting creates virtual copies of chain states while preserving the original stationary distribution; collapsing aggregates copy probabilities and averages transitions from copies.The aggregation uses stationary-probability weights for transitions from virtual states.Source: §III · pp. 3–4

A. Corridor Environment: Mean Capture Time

In the corridor example, empirical capture time converges to K(P) for the non-lifted chain, but not to K(P lift) for the lifted chain. The lifted Kemeny constant instead measures passage from virtual states to graph nodes and matches the lifted chain’s empirical capture time.

A. Corridor Environment: Mean Capture Time

B. Metrics for Lifted Markov Chain Patrol Strategies

  • The lifted metric definitions are constructed to equal their original counterparts when V = I_n.The set first-passage-time quantities provide the basis for defining the lifted metrics.Source: B. Metrics for Lifted Markov Chain… · p. 4

1) Lifted Kemeny Constant:

  • The lifted Kemeny constant measures reaching graph nodes from virtual states, avoiding averages over virtual-state pairs that can represent the same node.The ordinary Kemeny constant averages mean first passage times between nodes, weighted by the stationary distribution.Source: 1) Lifted Kemeny Constant · p. 4

2) Lifted Stackelberg Game Capture Probability:

The paper defines lifted capture-probability and return-time-entropy metrics for an adversary who observes graph location but not virtual state. It demonstrates improved corridor performance and establishes bounds relating optimal lifted Kemeny performance to the original chain’s conductance.

2) Lifted Stackelberg Game Capture Probability:

  • The lifted Stackelberg capture-probability metric uses set first-passage times and assumes the adversary knows graph location, but not virtual state.The patroller aims to maximize the minimum entry of the lifted capture-probability matrix.Source: 2) Lifted Stackelberg Game Capture… · pp. 4–5

3) Lifted Return-Time Entropy:

  • The lifted return-time entropy measures unpredictability of returns to each node using set return times; the expected return times match those of the non-lifted chain.At stationarity, the adversary cannot distinguish virtual copies of a node.Source: 3) Lifted Return-Time Entropy · p. 5

C. Corridor Environment: Lifted Kemeny Constant

  • At plift ∈ {0, 1}, Klift(P lift) = 47/18, compared with K(P) = 25/6; at plift = 1/2, the chains’ graph behavior is indistinguishable.For this lifted-chain structure at plift ∈ {0, 1}, the lifted Kemeny constant scales linearly with n and has a smaller constant factor than K(P lift).Source: C. Corridor Environment: Lifted Kemeny… · p. 5

A. Main Results

  • The optimal lifting has upper and lower bounds on its lifted Kemeny constant; the upper bound guarantees no degradation, while the conductance-based lower bound estimates possible improvement.The bounds depend on the given chain and apply even when that chain was optimized for a particular graph.Source: A. Main Results · p. 5
  • The paper establishes a monotonicity result for the lifted Stackelberg capture-probability and return-time-entropy metrics.The supplied result passage identifies these as metrics whose performance is to be maximized under optimal lifting.Source: A. Main Results · p. 5

B. Corridor Environment: Conductance Lower Bound

The corridor example illustrates how lifting can improve the Kemeny constant, while the proof establishes an upper bound for lifted performance and extends the argument to other metrics. The section also connects lumpability to equality between a lifted chain and its collapsed chain.

B. Corridor Environment: Conductance Lower Bound

  • For the corridor chain, the conductance bound is 3/4, while K(P) = 25/6; path-graph conductance bounds scale linearly with n, and the specified lifted chain achieves that scaling.The lifted chain uses p_lift ∈ {0, 1}.Source: B. Corridor Environment: Conductance… · p. 6

C. Upper Bound in Theorem 1

  • For lumpable lifted chains, K_lift(P_lift) = K(P), because the collapsed chain exactly reproduces their behavior.This equality supports the upper-bound argument.Source: C. Upper Bound in Theorem 1 · p. 6
  • The optimization argument establishes that the best lifted Kemeny constant is no greater than the best non-lifted value under corresponding stationary-distribution constraints.The proof compares feasible regions and uses equality between the second and third optimization problems.Source: C. Upper Bound in Theorem 1 · p. 6
  • The same argument gives corresponding monotonicity results for the lifted Stackelberg game capture probability and return-time entropy.For both metrics, lumpable lifted chains attain the same value as their collapsed chains.Source: C. Upper Bound in Theorem 1 · p. 6

D. Lower Bound in Theorem 1

The lower-bound argument uses conductance to bound the Kemeny constant of any lifting. It yields a general conductance–Kemeny relationship for irreducible Markov chains and a bound on the improvement achievable by lifting.

D. Lower Bound in Theorem 1

  • The proof uses symmetric ergodic flow across a set and its complement, together with a bound on stationary-weighted mean first-passage times.For any non-empty proper set A, Q(A, A^c) = Q(A^c, A).Source: D. Lower Bound in Theorem 1 · p. 7
  • For any irreducible MC P, [2Φ(P)]^-1 ≤ K(P), relating the Kemeny constant to conductance.The paper describes this as an analog of a known relationship for reversible MCs.Source: D. Lower Bound in Theorem 1 · p. 7
  • For a given collapsed MC P and partition V, [2Φ(P)]^-1 ≤ min_{P_lift∈L(P,V)} K(P_lift).The bound follows from optimizing over sets in the conductance argument and applies to any lifting.Source: D. Lower Bound in Theorem 1 · p. 7

V. DECEPTION VIA LIFTING

The paper shows that a naive adversary estimating a non-lifted chain from projected patrol trajectories converges to the collapsed chain. It also presents a constrained flow-based method for optimizing lifted chains.

V. DECEPTION VIA LIFTING

  • Every plug-in estimate from the projected trajectory of an irreducible lifted chain converges to the collapsed MC P.The paper identifies P as the KL-optimal aggregation and the estimate minimizing KL divergence rate to the lumped chain.Source: §V · p. 7
  • A naive adversary using a plug-in estimator arrives at P, which can lead it to underestimate the patroller’s performance.The paper notes that estimating the lifted chain directly from its graph trajectory is difficult.Source: §V · p. 7

A. Corridor Environment: Plug-In Estimate Convergence

  • In the corridor simulation, maximum-likelihood estimation of a non-lifted MC converges to P as trajectory length increases; an attack based on that estimate may leave less time than expected.The convergence plot reports medians and interquartile ranges over 50 Monte Carlo runs.Source: A. Corridor Environment: Plug-In… · p. 8, Figure 4 · p. 8

VI. OPTIMIZING LIFTED MARKOV CHAINS

  • The optimization method formulates lifted-chain design in ergodic flows, making the constraints linear, and uses projected gradient descent subject to those constraints.The constraints ensure a valid ergodic flow, irreducibility, graph compatibility, and a valid lifting.Source: §VI · p. 8

A. Travel Times

The paper extends lifted metrics to graphs whose edge weights encode travel times, including weighted return-time entropy and the Kemeny constant. It also provides a closed-form gradient for the lifted Kemeny constant with respect to ergodic flow.

A. Travel Times

  • The lifted weight matrix is W_lift = V W V^⊤, where each edge weight gives the number of time steps needed to traverse that edge.Unweighted graphs are recovered by setting all weights to one.Source: A. Travel Times · p. 8
  • The lifted Kemeny constant is extended to weighted graphs using weighted set mean first-passage times; setting all lifted weights to one recovers the unweighted form.The lifted Stackelberg game capture probability and return-time entropy can also be computed using the generalized first-passage-time recursion.Source: A. Travel Times · p. 8
  • For weighted graphs, the expected lifted weighted return time equals the expected weighted return time of the non-lifted MC for each node.This permits direct comparison of lifted and non-lifted return-time entropy metrics.Source: A. Travel Times · p. 8

B. Gradient of the Lifted Kemeny Constant

  • For fixed π, the paper gives a closed-form gradient of the lifted Kemeny constant for weighted graphs with respect to ergodic flow.The unweighted gradient is recovered by setting W_lift to an all-ones matrix.Source: B. Gradient of the Lifted Kemeny… · p. 9

VII. NUMERICAL RESULTS

Numerical experiments compare lifted and non-lifted patrol strategies on random and real-world graphs. They find improvements across the evaluated metrics, with stronger gains generally associated with sparse graphs.

A. Choosing the Partition

  • Across tested partitioning methods and lifting budgets, increasing the budget shows diminishing returns; stationary-distribution allocation is used in subsequent experiments.The experiments assign virtual states uniformly or in proportion to stationary probability, degree, betweenness centrality, or eigenvector centrality.Source: A. Choosing the Partition · p. 9, Figure 5 · p. 9

B. General Graphs and Stationary Distributions

  • On random graphs, lifting improves Kemeny, Stackelberg game capture probability, and return-time performance, with gains generally increasing as graphs become sparser.The Kemeny experiments use a lifting budget of 30 states; return-time results report percent increases in perplexity rather than entropy.Source: B. General Graphs and Stationary… · pp. 9–10, Figure 6 · p. 10

C. San Francisco Case Study

  • In San Francisco, SGCP improvements grow with graph sparsity, while Kemeny results show no clear sparsity trend because optimized chains avoid long edges.A naive trajectory-based adversary would overestimate Kemeny by 1 minute and underestimate SGCP by about 1 percentage point.Source: C. San Francisco Case Study · pp. 10–11, Table III · p. 11

D. University of Coimbra Case Study

VIII. CONCLUSION

  • The paper proposes classical Markov-chain lifting for stochastic patrol strategies and reports theoretical bounds, deceptive behavior against model-based adversaries, and substantial numerical gains on sparse graphs.Future directions include extending theory to travel times, optimizing virtual-state assignments, and developing adversary approaches.Source: §VIII · p. 11

APPENDIX

The appendix defines lumpability as the condition under which a lifted chain collapses to a Markov chain without losing the relevant behavior, then uses that condition in a proof about first-passage quantities.

A. Lumpability

  • Lumpability determines whether collapsing a lifted chain loses information; when it holds, the lumped process is a Markov chain whose transition probabilities do not depend on the starting distribution.The appendix expresses the condition as V P = P_lift V and relates it to the collapsed-chain equation.Source: A. Lumpability · p. 11
  • For the illustrated lifted chain, p_lift = 1/2 makes the chain lumpable with respect to V, and P is the resulting lumped chain.Source: A. Lumpability · p. 12

B. Proof of Lemma 3

  • The Lemma 3 proof uses lumpability to relate lifted and lumped first-passage quantities; irreducibility of the lifted chain implies irreducibility of the collapsed chain and finite mean first-passage times.Source: B. Proof of Lemma 3 · p. 12

C. Proof of Lemma 4

The appendix proves a bound using a convex sequence associated with return probabilities, then verifies that estimated transition probabilities satisfy the lifting condition.

C. Proof of Lemma 4

  • The proof expresses the inverse (I_|A| − P_A)^−1 as an infinite sum of powers of P_A, using that P_A has spectral radius below one.Source: C. Proof of Lemma 4 · p. 12
  • The Lemma 4 proof represents the relevant sum through a decreasing sequence c_k and uses its convexity to lower-bound that sum with a triangle.The triangle’s side lengths are π(A) and π(A)/Q(A, A^c), yielding the bound in Eq. (21).Source: C. Proof of Lemma 4 · p. 12

D. Proof of Proposition 8

  • The Proposition 8 proof shows that the ratio of empirical transition and visit counts yields the transition-probability condition for lifting, expressed as P = U P_lift V.Source: D. Proof of Proposition 8 · pp. 12–13

E. Proof of Lemma 9

These appendix proofs establish an identity used in the analysis and derive optimization conditions through an adjoint-state method.

E. Proof of Lemma 9

  • The Lemma 9 proof rewrites the expression using W_lift = V W V^⊤ and Q = V^⊤Q_liftV, recovering π^⊤(P ◦ W)1_n.Source: E. Proof of Lemma 9 · p. 13

F. Proof of Proposition 10

  • The Proposition 10 proof introduces Q_lift while eliminating P_lift and π_lift from the relevant equations.Source: F. Proof of Proposition 10 · p. 13
  • The proof uses an adjoint-state method: stationarity with respect to the adjoint variables gives their equations, and differentiating the Lagrangian with respect to Q_lift yields Eq. (28).Source: F. Proof of Proposition 10 · p. 13
Loading 2610.10903v1…