Random Walks with Traversal Costs: Variance-Aware Performance Analysis and Network Optimization
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915895052337152 |
|---|---|
| author | Le, Thao van der Burg, Robbert Heidergott, Bernd Lindner, Ines Zocca, Alessandro |
| author_facet | Le, Thao van der Burg, Robbert Heidergott, Bernd Lindner, Ines Zocca, Alessandro |
| contents | We introduce weighted Markovian graphs, a random walk model that decouples the transition dynamics of a Markov chain from (random) edge weights representing the cost of traversing each edge. This decoupling allows us to study the accumulated weight along a path independently of the routing behavior. Crucially, we derive closed-form expressions for the mean and variance of weighted first passage times and weighted Kemeny constants, together with their partial derivatives with respect to both the weight and transition matrices. These results hold for both deterministic and stochastic weights with no distributional assumptions. We demonstrate the framework through two applications, highlighting the dual role of variance. In surveillance networks, we introduce the surprise index, a coefficient-of-variation metric quantifying patrol unpredictability, and show how maximizing it yields policies that are both efficient and hard to anticipate. In traffic networks subject to cascading edge failures, we develop a minimal-intervention framework that adjusts speed limits to preserve connectivity under three increasingly flexible regulatory policies. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_26414 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Random Walks with Traversal Costs: Variance-Aware Performance Analysis and Network Optimization Le, Thao van der Burg, Robbert Heidergott, Bernd Lindner, Ines Zocca, Alessandro Optimization and Control Probability We introduce weighted Markovian graphs, a random walk model that decouples the transition dynamics of a Markov chain from (random) edge weights representing the cost of traversing each edge. This decoupling allows us to study the accumulated weight along a path independently of the routing behavior. Crucially, we derive closed-form expressions for the mean and variance of weighted first passage times and weighted Kemeny constants, together with their partial derivatives with respect to both the weight and transition matrices. These results hold for both deterministic and stochastic weights with no distributional assumptions. We demonstrate the framework through two applications, highlighting the dual role of variance. In surveillance networks, we introduce the surprise index, a coefficient-of-variation metric quantifying patrol unpredictability, and show how maximizing it yields policies that are both efficient and hard to anticipate. In traffic networks subject to cascading edge failures, we develop a minimal-intervention framework that adjusts speed limits to preserve connectivity under three increasingly flexible regulatory policies. |
| title | Random Walks with Traversal Costs: Variance-Aware Performance Analysis and Network Optimization |
| topic | Optimization and Control Probability |
| url | https://arxiv.org/abs/2603.26414 |