{"id":"arxiv/2603.26414","url":"https://arxiv.org/abs/2603.26414","tags":["math.OC","math.PR"],"score":0,"title":"Random Walks with Traversal Costs: Variance-Aware Performance Analysis and Network Optimization","domain":"math.OC","source":"arxiv","authors":["Thao Le","Robbert van der Burg","Bernd Heidergott","Ines Lindner","Alessandro Zocca"],"reviews":0,"subject":"math.OC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-03-27","reactions":{}}