Random Walks with Traversal Costs: Variance-Aware Performance Analysis and Network Optimization

Thao Le, Robbert van der Burg, Bernd Heidergott, Ines Lindner, Alessandro Zocca · 2026

Read Random Walks with Traversal Costs: Variance-Aware Performance Analysis and Network Optimization by Thao Le, Robbert van der Burg, Bernd Heidergott, Ines Lindner, Alessandro Zocca (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-26414.txt.

Description

Le and co-authors build a random walk model where moving along an edge carries its own random cost. Weighted Markovian graphs split the walk's routing rules from the edge weights it collects. That split lets cost along a path be studied apart from the path itself. The team derives closed forms for the mean and variance of weighted passage times and Kemeny constants. They apply the tools to patrol networks, where a surprise index rewards hard-to-predict routes, and to traffic under cascading failures.

Catalog record

CREATORThao Le, Robbert van der Burg, Bernd Heidergott, Ines Lindner, Alessandro Zocca
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE100772
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.26414

Browse the full library · About the Tower of Babel