Some Problems Of Random Walks On Graphs

The random walks on finite graphs(finite Markov chains) have been widely used for designing approximation algorithms in last two decades. The efficiency of algorithms is deteminied by some inportant parameters of this random walk, for instance, the expected cover time, the expected hitting time, the mixing time, etc. In this paper, we concentrate on two parameters: the expected hitting time and mixing time. Some of main results are as follows:1. By using the algebraic method, we obtain a new formula for the expected hitting time of random walks on strong-connected and aperiodic digrahs (irreducible and aperiodic Markov chain). Prom this formula, we obtain the explicit expressions for the expected hitting times of random walks on directed de Bruijn graph, directed Kautz graph and some graphs constructed from strong regular graph, etc.2. Using the relationships between random walks on graphs (reversible Markov chains) and electrical networks, we discuss the random walks on graphs with cutpoints, and provide the explicit formulas for the expected hitting times for simple random walks on trees and unicyclic graphs.3. By solving the recurrent relations, we obtain the explicit expressions for the expected hitting times for simple random walks on several kinds of circulant graphs. As a by production, we derive some curious trigonometric identities.4. Stimulated by the mutation operator in genertic algorithm, we construct a complete weighted graph G from the n-cube. The eigenvalues and conductance of G are determined first, then we show the rapid mixing of random walk on G.