Mathematics – Probability
Scientific paper
2011-03-22
Mathematics
Probability
24 pages, no figure
Scientific paper
In this paper we show that on bounded degree graphs and general trees the cover time of the simple random walk is asymptotically equal to the product of the number of edges and the square of the supremum of the Gaussian free field on the graph, assuming that the maximal hitting time is significantly smaller than the cover time. Previously, this was only proved for regular trees and the 2D lattice. Furthermore, for general trees, we derive exponential concentration for the cover time, which implies that the standard deviation of the cover time is bounded by the geometric mean of the cover time and the maximal hitting time.
No associations
LandOfFree
Asymptotics of cover times via Gaussian free fields: bounded-degree graphs and general trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Asymptotics of cover times via Gaussian free fields: bounded-degree graphs and general trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Asymptotics of cover times via Gaussian free fields: bounded-degree graphs and general trees will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-440437