Randomized Search of Graphs in Log Space and Probabilistic Computation

Reingold has shown that L = SL, that s-t connectivity in a poly-mixing digraph is complete for promise-RL, and that s-t connectivity for a poly-mixing out-regular digraph with known stationary distribution is in L. Several properties that bound the mixing times of random walks on digraphs have been identified, including the digraph conductance and the digraph spectral expansion. However, rapidly mixing digraphs can still have exponential cover time, thus it is important to specifically identify structural properties of digraphs that effect cover times. We examine the complexity of random walks on a basic parameterized family of unbalanced digraphs called Strong Chains (which model weakly symmetric logspace computations), and a special family of Strong Chains called Harps. We show that the worst case hitting times of Strong Chain families vary smoothly with the number of asymmetric vertices and identify the necessary condition for non-polynomial cover time. This analysis also yields bounds on the cover times of general digraphs. Next we relate random walks on graphs to the random walks that arise in Monte Carlo methods applied to optimization problems. We introduce the notion of the asymmetric states of Markov chains and use this definition to obtain some results about Markov chains. We also obtain some results on the mixing times for Markov Chain Monte Carlo Methods. Finally, we consider the question of whether a single long random walk or many short walks is a better strategy for exploration. These are walks which reset to the start after a fixed number of steps. We exhibit digraph families for which a few short walks are far superior to a single long walk. We introduce an iterative deepening random search. We use this strategy estimate the cover time for poly-mixing subgraphs. Finally we discuss complexity theoretic implications and future work