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

Cihan O., Akar M.

IEEE TRANSACTIONS ON AUTOMATIC CONTROL, cilt.60, sa.1, ss.227-232, 2015 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 60 Sayı: 1
  • Basım Tarihi: 2015
  • Doi Numarası: 10.1109/tac.2014.2322942
  • Dergi Adı: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.227-232
  • Anahtar Kelimeler: Fastest mixing, Markov chains, second largest eigenvalue modulus, DOUBLY STOCHASTIC MATRICES
  • Marmara Üniversitesi Adresli: Hayır

Ö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.