关键词: 马氏过程, 最快混合, 边传递图, 特征值优化

Abstract:

We consider a Markov process on a connected graph, where each edge is labeled with the transition rate between the two adjacent vertices. The fastest mixing Markov process (FMMP) problem is the problem of assigning transition rates to the edges so as to maximize the second smallest eigenvalue λ₂ of the Laplacian of the weighted graph, which determines the mixing rate of the Markov process. We show that the FMMP problem always attains its optimum in the fixed-point subset of the feasible set under the automorphism group. This result can be used to reduce the number of optimization variables on graphs with symmetries. We analytically find the optimal solutions on edge-transitive graphs.

Key words: Markov process, fast mixing, edge-transitive graph, eigenvalue optimization