Premium
Random walks on colored graphs
Author(s) -
Condon Anne,
Hernek Diane
Publication year - 1994
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240050204
Subject(s) - random walk , colored , combinatorics , markov chain , mathematics , cover (algebra) , random walker algorithm , eigenvalues and eigenvectors , exponential function , discrete mathematics , random graph , sequence (biology) , indifference graph , upper and lower bounds , graph , statistics , mechanical engineering , mathematical analysis , materials science , physics , quantum mechanics , biology , engineering , composite material , genetics
We initiate a study of random walks on undirected graphs with colored edges. In our model, a sequence of colors is specified before the walk begins, and it dictates the color of edge to be followed at each step. We give tight upper and lower bounds on the expected cover time of a random walk on an undirected graph with colored edges. We show that, in general, graphs with two colors have exponential expected cover time, and graphs with three or more colors have doubly‐exponential expected cover time. We also give polynomial bounds on the expected cover time in a number of interesting special cases. We described applications of our results to understanding the dominant eigenvectors of products and weighted averages of stochastic matrices, and to problems on time‐inhomogeneous Markov chains. © 1994 John Wiley & Sons, Inc.