Geometric bounds on the fastest mixing Markov chain
Geometric bounds on the fastest mixing Markov chain
Abstract In the Fastest Mixing Markov Chain problem, we are given a graph $$G = (V, E)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>G</mml:mi> <mml:mo>=</mml:mo> <mml:mo>(</mml:mo> <mml:mi>V</mml:mi> <mml:mo>,</mml:mo> <mml:mi>E</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> and desire the discrete-time Markov chain with smallest mixing time $$\tau $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>τ</mml:mi> </mml:math> subject to having equilibrium distribution …