Algorithms for improving efficiency of discrete Markov chains

Nabanita Mukherjee (), George Casella () and Kshitij Khare ()
Additional contact information
Nabanita Mukherjee: Duke University
George Casella: University of Florida
Kshitij Khare: University of Florida

Indian Journal of Pure and Applied Mathematics, 2017, vol. 48, issue 4, 495-511

Abstract: Abstract Sampling from an intractable probability distribution is a common and important problem in scientific computing. A popular approach to solve this problem is to construct a Markov chain which converges to the desired probability distribution, and run this Markov chain to obtain an approximate sample. In this paper, we provide two methods to improve the performance of a given discrete reversible Markov chain. These methods require the knowledge of the stationary distribution only up to a normalizing constant. Each of these methods produces a reversible Markov chain which has the same stationary distribution as the original chain, and dominates the original chain in the ordering introduced by Peskun [11]. We illustrate these methods on two Markov chains, one connected to hidden Markov models and one connected to card shuffling. We also prove a result which shows that the Metropolis-Hastings algorithm preserves the Peskun ordering for Markov transition matrices.

Keywords: Markov chain Monte Carlo; Peskun ordering; Metropolis-Hastings algorithm; asymptotic efficiency (search for similar items in EconPapers)
Date: 2017
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s13226-017-0242-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:indpam:v:48:y:2017:i:4:d:10.1007_s13226-017-0242-7

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/13226

DOI: 10.1007/s13226-017-0242-7

Access Statistics for this article

Indian Journal of Pure and Applied Mathematics is currently edited by Nidhi Chandhoke

More articles in Indian Journal of Pure and Applied Mathematics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().