
























We obtain upper bounds (in most cases, sharp) for the hitting times of random walks on finite undirected graphs expressed as functions of the graph's number of edges. In particular, we show that the maximum hitting time for a simple random walk on a connected graph with $m$ edges is at most $m^2$. Similar bounds are given for the settings involving arbitrary edge-weight and edge-cost functions. Upper bounds of this type are especially useful for sparse graphs.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。