|
Joint Applied Math and Probability Seminar
The Fastest Mixing Markov Chains on a Graph
|
|
The problem is: given a connected graph, how should we put weights on the edges to achieve a given stationary distribution and make the spectral gap as big as possible. The metropolis algorithm and max degree construction are widely used efforts. In a joint work with Steve Boyd and Lin Ziao, we set this up as a semi-definite programming problem and show that the optimal construction can be unboundedly better. |