有限图上的随机游动（即有限马尔可夫链）近一二十年来在近似算法设计的重要应用，使它受到越来越广泛的关注。这时算法的有效性大部分依赖于所设计随机游动的性能好坏，而随机游动的性能主要由它的几个重要的参数来决定，如平均首达时间，平均覆盖时间，收敛速度等。本文主要研究了有限图上随机游动的两个重要参数：平均首达时间和收敛速度。下面是本文的一些主要新结果： 1．利用代数方法给出了强连通非周期有向图上随机游动（即不可约非周期马尔可夫链）平均首达时间一个新的表达式，并利用这个表达式得到了有向de Bruijn图，有向Kautz图以及和强正则图相关的几类图上随机游动任意两点之间的平均首达时间。 2．利用无向图上随机游动（可逆马尔可夫链）和电网络之间的关系，得到了树和单圈图上简单随机游动任意两点之间的平均首达时间的表达式；同时得到了有割点图和它的子图上随机游动平均首达时间之间的关系式。 3．通过求解递推关系式，给出了几类循环图上简单随机游动任意两点之间的平均首达时间的表达式；并利用双计法得到了一些新的三角恒等式。 4．由超立方体Qn构造了一个完全赋权图G，P是G上随机游动（其背景是遗传算法中的变异算子）的转移矩阵，利用正交多项式的方法求出了P的所有特征值；并得到了G上随机游动conductance的精确值，从而证明了它的快速收敛性。