Coupling Arguments and Mixing Time

3 selectedDifficulty 8-93 unseenView topic

AdvancedNew

0 answered

3 advancedAdapts to your performance

Question 1 of 3

120sadvanced (8/10)state theorem

For a reversible Markov chain on a finite state space with stationary distribution π, the *conductance* (bottleneck ratio) is Φ_{*} = min_{S : 0 < π (S) \leq 1/2} \frac{Q ( S , S ^{c} )}{π ( S )} where Q (S, S^{c}) = \sum_{x \in S, y \in S^{c}} π (x) P (x, y) . The Cheeger inequality relates Φ_{*} to the spectral gap γ = 1 - λ_{2} how?