English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We survey existing techniques to bound the mixing time of Markov chains. Themixing time is related to a geometric parameter called conductance which is ameasure of edge-expansion. Bounds on conductance are typically obtained by atechnique called "canonical paths" where the idea is to find a set of paths,one between every source-destination pair, such that no edge is heavilycongested. However, the canonical paths approach cannot always show rapidmixing of a rapidly mixing chain. This drawback disappears if we allow the flowbetween a pair of states to be spread along multiple paths. We prove that for alarge class of Markov chains canonical paths does capture rapid mixing.Allowing multiple paths to route the flow still does help a great deal inproofs, as illustrated by a result of Morris & Sinclair (FOCS'99) on the rapidmixing of a Markov chain for sampling 0/1 knapsack solutions.  A different approach to prove rapid mixing is "Coupling". Path Coupling is avariant discovered by Bubley & Dyer (FOCS'97) that often tremendously reducesthe complexity of designing good Couplings. We present several applications ofPath Coupling in proofs of rapid mixing. These invariably lead to much betterbounds on mixing time than known using conductance, and moreover Coupling basedproofs are typically simpler. This motivates the question of whether Couplingcan be made to work whenever the chain is rapidly mixing. This question wasanswered in the negative by Kumar & Ramesh (FOCS'99), who showed that noCoupling strategy can prove the rapid mixing of the Jerrum-Sinclair chain forsampling perfect and near-perfect matchings.

Rapidly Mixing Markov Chains: A Comparison of Techniques (A Survey)