Deceptive Stochastic Patrolling via Markov Chain Lifting
Abstract
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.
Related
- Memory-Dependent Interval Markov Chain Abstractions of Stochastic Dynamics
- Markov chain Monte Carlo for predictively oriented posteriors
- Geometric approximation for the number of returns of a transient Markov chain to its origin
- A Markov Chain Approach to Modeling Rugby Union
- Markov Chain Convergence in Kernel-Induced Geometry
BibTeX
@misc{john2026deceptive,
title = {{Deceptive Stochastic Patrolling via Markov Chain Lifting}},
author = {Yohan John and Gilberto Diaz-Garcia and Jason R. Marden and Francesco Bullo},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.10903},
eprint = {2610.10903},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.10903},
}
RIS
TY - UNPB
TI - Deceptive Stochastic Patrolling via Markov Chain Lifting
AU - Yohan John
AU - Gilberto Diaz-Garcia
AU - Jason R. Marden
AU - Francesco Bullo
PY - 2026
DA - 2026/10/07
PB - arXiv
DO - 10.48550/arxiv.2610.10903
UR - https://arxiv.org/abs/2610.10903
AB - 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.
ER -