Premium
Extremal cover times for random walks on trees
Author(s) -
Brightwell Graham,
Winkler Peter
Publication year - 1990
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190140505
Subject(s) - combinatorics , mathematics , cover (algebra) , vertex (graph theory) , path (computing) , tree (set theory) , upper and lower bounds , random walk , star (game theory) , discrete mathematics , graph , statistics , computer science , mechanical engineering , mathematical analysis , engineering , programming language
Let C ν ( T ) denote the “cover time” of the tree T from the vertex v , that is, the expected number of steps before a random walk starting at v hits every vertex of T. Asymptotic lower bounds for C ν ( T ) (for T a tree on n vertices) have been obtained recently by Kahn, Linial, Nisan and Saks, and by Devroye and Sbihi; here, we obtain the exact lower bound (approximately 2 n In n ) by showing that C ν ( T ) is minimized when T is a star and v is one of its leaves. In addition, we show that the time to cover all vertices and then return to the starting point is minimized by a star (beginning at the center) and maximized by a path (beginning at one of the ends).