Effect of increasing the energy gap between the two lowest energy states on the mixing time of the Metropolis algorithm

Apurv Nakade, Somenath Biswas*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

In order to understand what makes natural proteins fold rapidly, Šali, Shakhnovich and Karplus (1994) [6,7] had used the Metropolis algorithm to search for the minimum energy conformations of chains of beads in the lattice model of protein folding. Based on their computational experiments, they concluded that the Metropolis algorithm would find the minimum energy conformation of a chain of beads within an acceptable time scale if and only if there is a large gap between the energies of the minimum energy conformation and that of the second minimum. Clote (1999) [1] attempted to support this conclusion by a proof that the mixing time of the underlying Markov chain would decrease as the gap in energies of the minimum energy conformation and that of the second minimum increased. He was able to show that an upper bound on the mixing time does indeed decrease as the energy gap increases. We show in this paper that the mixing time itself, however, is a non-decreasing function of the value of the energy gap. Therefore, our result contradicts what Clote had attempted to prove.

Original languageEnglish (US)
Pages (from-to)922-927
Number of pages6
JournalInformation Processing Letters
Volume112
Issue number23
DOIs
StatePublished - Dec 15 2012
Externally publishedYes

Keywords

  • Markov chain mixing time
  • Metropolis algorithm
  • Protein folding
  • Randomized algorithms

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Fingerprint

Dive into the research topics of 'Effect of increasing the energy gap between the two lowest energy states on the mixing time of the Metropolis algorithm'. Together they form a unique fingerprint.

Cite this