Fastest Mixing Reversible Markov Chains on Graphs With Degree Proportional Stationary Distributions

In this technical note, we study two semi-definite programming (SDP) methods of assigning transition probabilities to a Markov chain in order to optimize its mixing rate. In the first SDP formulation, there is a single transition probability parameter to be optimized (the holding probability of vertices) which leads to easier and faster computation as opposed to the more general reversible Markov chain formulation corresponding to a stationary distribution that is proportional to the degree of vertices. By deriving exact analytical results, it is shown that both the single parameter and the degree proportional reversible FMMC formulations tend to yield better results than the symmetric SDP formulation for some well-known graphs.