Random Walks on Colored Graphs: Analysis and Applications

This thesis introduces a model of a random walk on a colored undirected graph. Such a graph has a single vertex set and k distinct sets of edges, each of which has a color. A particle begins at a designated starting vertex and an infinite color sequence C is specified. At time t the particle traverses an edge chosen uniformly at random from those edges of color C_t incident to the current vertex.The first part of this thesis addresses the extent to which an adversary, by choosing the color sequence, can affect the behavior of the random walk. In particular, we consider graphs that are covered with probability one on all infinite sequences, and study their expected cover time in the worst case over all color sequences and starting vertices. We prove tight doubly exponential upper and lower bounds for graphs with three or more colors, and exponential bounds for the special case of two-colored graphs. We obtain stronger bounds in several interesting special cases, including random and repeated sequences. These examples have applications to understanding how the entries of the stationary distributions of ergodic Markov chains scale under various elementary operations.The random walks we consider are closely related to space-bounded complexity classes and a type of interactive proof system. The second part of the thesis investigates these relationships and uses them to obtain complexity results for reachability problems in colored graphs. We also use our techniques to obtain complexity results for problems from the theory of nonhomogeneous Markov chains. We consider the problem of deciding, given a finite set cal C = C_1 , ..., C_A } of n x n stochastic matrices, whether every infinite sequence over cal C forms an ergodic Markov chain, and prove that it is PSPACE-complete. We also show that to decide whether a given finite-state channel is indecomposable is PSPACE-complete. This question is of interest in information theory where indecomposability is a necessary and sufficient condition for Shannon's theorem.

ICSI Technical Report TR-95-045

Technical Report