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


Cihan O. , Akar M.

IEEE TRANSACTIONS ON AUTOMATIC CONTROL, cilt.60, ss.227-232, 2015 (SCI İndekslerine Giren Dergi) identifier identifier

  • Cilt numarası: 60 Konu: 1
  • Basım Tarihi: 2015
  • Doi Numarası: 10.1109/tac.2014.2322942
  • Dergi Adı: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
  • Sayfa Sayıları: ss.227-232

Özet

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.