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

Thao Le, Robbert van der Burg, Bernd Heidergott +2

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…