边传递图上的最快混合马氏过程

摘要

考虑加权连通图上的简单连续时间马氏过程,每条边上赋权为马氏过程的转移速率,使得马氏过程混合时间最短的赋权问题称之为最快混合马氏过程问题(FMMP).我们证明FMMP在图自同构群的不变点集合中取到最优,并且在边传递图中解析地得到了最优解.%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 λ2 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.