Diane Hernek and Anne Condon

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-92-695
July 1992

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1992/CSD-92-695.pdf

We give tight upper and lower bounds on the expected cover time of a random walk in an undirected graph with colored edges. We show that for graphs with two colors the expected cover time is exponential, and that for three or more colors it is double exponential. In addition, we give polynomial bounds in a number of interesting special cases. We describe applications of these results to understanding the eigenvalues of products and weighted averages of matrices, and to problems on time-inhomogeneous Markov chains.

BibTeX citation:

@techreport{Hernek:CSD-92-695,
    Author = {Hernek, Diane and Condon, Anne},
    Title = {Random Walks in Colored Graphs},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1992},
    Month = {Jul},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1992/6248.html},
    Number = {UCB/CSD-92-695},
    Abstract = {We give tight upper and lower bounds on the expected cover time of a random walk in an undirected graph with colored edges. We show that for graphs with two colors the expected cover time is exponential, and that for three or more colors it is double exponential. In addition, we give polynomial bounds in a number of interesting special cases. We describe applications of these results to understanding the eigenvalues of products and weighted averages of matrices, and to problems on time-inhomogeneous Markov chains.}
}

EndNote citation:

%0 Report
%A Hernek, Diane
%A Condon, Anne
%T Random Walks in Colored Graphs
%I EECS Department, University of California, Berkeley
%D 1992
%@ UCB/CSD-92-695
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1992/6248.html
%F Hernek:CSD-92-695