# Random Walks in Colored Graphs

### Diane Hernek and Anne Condon

###
EECS Department

University of California, Berkeley

Technical Report No. UCB/CSD-92-695

July 1992

### http://www.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://www.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://www.eecs.berkeley.edu/Pubs/TechRpts/1992/6248.html %F Hernek:CSD-92-695