𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A semidefinite bound for mixing rates of Markov chains

✍ Scribed by Nabil Kahale

Publisher
John Wiley and Sons
Year
1997
Tongue
English
Weight
214 KB
Volume
11
Category
Article
ISSN
1042-9832

No coin nor oath required. For personal study only.

✦ Synopsis

We study general geometric techniques for bounding the spectral gap of a reversible Markov chain. We show that the best bound obtainable using these techniques can be computed in polynomial time via semidefinite programming, and is off by at most a factor of order log 2 n, where n is the number of states.

πŸ“œ SIMILAR VOLUMES

A more rapidly mixing Markov chain for g
A more rapidly mixing Markov chain for graph colorings
✍ Martin Dyer; Catherine Greenhill πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 351 KB

We define a new Markov chain on proper k-colorings of graphs, and relate its convergence properties to the maximum degree ⌬ of the graph. The chain is shown to have bounds on convergence time appreciably better than those for the well-known JerrumrSalas᎐Sokal chain in most circumstances. For the cas

Very rapidly mixing Markov chains for 2Ξ”
Very rapidly mixing Markov chains for 2Ξ”-colorings and for independent sets in a graph with maximum degree 4
✍ Michael Molloy πŸ“‚ Article πŸ“… 2001 πŸ› John Wiley and Sons 🌐 English βš– 140 KB πŸ‘ 1 views

We introduce a new technique for analyzing the mixing rate of Markov chains. We use it to prove that the Glauber dynamics on 2 -colorings of a graph with maximum degree mixes in O n log n time. We prove the same mixing rate for the Insert/Delete/Drag chain of Dyer and Greenhill (Random Structures A

A Multiple Binary Markov Chain Model for
A Multiple Binary Markov Chain Model for Explaining the Behaviour of Diverse Biological Phenomena
✍ D.K. Morris; G.R. Wood; W.P. Baritompa; A.G. Keen πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 260 KB πŸ‘ 2 views

The behaviour of many biological systems can be attributed to that of a large number of units, with each unit swinging between two competing states. During the past few years efforts have been made (e.g., Chung and Kennedy, 1996) to describe such discrete systems using a multiple binary Markov chain