A note on bounding the mixing time by linear programming
When controlled with a large set of configurations (a state space of Markov chain, for example), about which little can be deduced analytically, one might attempt to estimate some of its parameters by random sampling, i.e. Monte Carlo methods. It is well known that the ability to sample states at random from a distribution close to uniform is usually sufficient to estimate the size of the state space (or its weighted analogue, the partition function). The mixing time of Markov chains on a partial order with unique minimal and maximal elements to the solution of associated linear programs is related. The author constructs the linear minimization program which has one variable per state and its solution is an upper bound on the mixing time. The proof of this theorem uses the coupling technique. Explicit solutions are obtained for the simple Markov chains on the hypercube and on the independent sets of a complete bipartite graph. As an application the author defines a new Markov chain on the down-sets (ideals) of a partial order for which this technique yields a simple proof of rapid mixing. For the entire collection see [Zbl 0898.00029].
- On the conductance of order Markov chains
- Faster random generation of linear extensions
- Mixing time for Markov chain on linear extensions
- Comparison inequalities and fastest-mixing Markov chains
- Upper Bounds on Mixing Time of Finite Markov Chains
- Using Markov-chain mixing time estimates for the analysis of ant colony optimization
This page was built for publication: A note on bounding the mixing time by linear programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4247200)
