Random Walks with Traversal Costs: Variance-Aware Performance Analysis and Network Optimization
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2603.26414
curl -X POST /api/v1/records/arxiv/2603.26414/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2603.26414/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'