Random walks on colored graphs. (English) Zbl 0792.05123
Summary: 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 describe 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.
MSC:
| 05C80 | Random graphs (graph-theoretic aspects) |
| 60G50 | Sums of independent random variables; random walks |
| 05C15 | Coloring of graphs and hypergraphs |
Keywords:
random walks; undirected graphs; colored edges; cover time; dominant eigenvectors; stochastic matrices; time-inhomogeneous Markov chainsReferences:
| [1] | R. Aleliunas R. Karp R. Lipton L. Lovász C. Rackoff Random walks, universal traversal sequences, and the complexity of maze problems Proc. 20th Symposium on Foundations of Computer Science 218 223 1979 |
| [2] | Alon, Eigenvalues and expanders, Combinatorica 6 (2) pp 83– (1986) · Zbl 0661.05053 |
| [3] | S. Arora C. Lund R. Motwani M. Sudan M. Szegedy Proof verification and hardness of approximation problems Proc. 33rd Symposium on Foundations of Computer Science 14 23 1992 · Zbl 0977.68539 |
| [4] | Blackwell, Proof of Shannon’s transmission theorem for finite-state indecomposable channels, Ann. Math. Stat. 29 pp 1209– (1958) · Zbl 0096.10901 |
| [5] | Broder, Bounds on the cover time, J. Theor. Probab. 2 (1) pp 101– (1989) |
| [6] | Condon, Space-bounded probabilistic game automata, JACM 38 (2) pp 472– (1991) · Zbl 0799.68095 |
| [7] | A. Condon R. Lipton On the complexity of space-bounded interactive proofs Proc. 30th Symposium on Foundations of Computer Science 462 467 1989 |
| [8] | Dwork, Finite state verifiers I: The power of interaction, In JACM 39 (4) pp 800– (1992) · Zbl 0799.68099 |
| [9] | Göbel, Random walks on graphs, Stochast. Process. Appl. 2 pp 311– (1974) |
| [10] | N. Immerman Nondeterministic space is closed under complement Proc. Conference on Structure in Complexity Theory 112 115 1988 |
| [11] | M. Jerrum A. Sinclair Conductance and the rapid mixing property for Markov chains Proc. 20th ACM Symposium on Theory of Computing 235 244 1988 |
| [12] | M. Mihail Conductance and convergence of expanders Proc. 30th Symposium on Foundations of Computer Science 526 531 1989 |
| [13] | Paz, Definite and quasi-definite sets of stochastic matrices, Am. Math. Soc. Proc. 16 (4) pp 634– (1965) · Zbl 0149.13404 |
| [14] | Savitch, Relationships between nondeterministic and deterministic tape complexities, J. Comput. Syst. Sci. 4 (2) pp 177– (1970) · Zbl 0188.33502 |
| [15] | Seneta, Non-negative Matrices and Markov Chains (1981) · Zbl 1099.60004 · doi:10.1007/0-387-32792-4 |
| [16] | R. Szelepcsényi The method of forcing for nondeterministic automata Bull. Eur. Assoc. Theor. Comput. Sci. 96 100 1987 · Zbl 0664.68082 |
| [17] | Wolfowitz, Products of indecomposable, aperiodic, stochastic matrices, Am. Math. Soc. Proc. 14 pp 733– (1963) · Zbl 0116.35001 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
