Efficient Simulation of Markov Chains Using Segmentation

Tim Brereton (), Ole Stenzel (), Björn Baumeier (), Denis Andrienko (), Volker Schmidt () and Dirk Kroese ()
Additional contact information
Tim Brereton: The University of Queensland
Ole Stenzel: Ulm University
Björn Baumeier: Max Planck Institute for Polymer Research
Denis Andrienko: Max Planck Institute for Polymer Research
Volker Schmidt: Ulm University
Dirk Kroese: The University of Queensland

Methodology and Computing in Applied Probability, 2014, vol. 16, issue 2, 465-484

Abstract: Abstract A methodology is proposed that is suitable for efficient simulation of continuous-time Markov chains that are nearly-completely decomposable. For such Markov chains the effort to adequately explore the state space via Crude Monte Carlo (CMC) simulation can be extremely large. The purpose of this paper is to provide a fast alternative to the standard CMC algorithm, which we call Aggregate Monte Carlo (AMC). The idea of the AMC algorithm is to reduce the jumping back and forth of the Markov chain in small subregions of the state space. We accomplish this by aggregating such problem regions into single states. We discuss two methods to identify collections of states where the Markov chain may become ‘trapped’: the stochastic watershed segmentation from image analysis, and a graph-theoretic decomposition method. As a motivating application, we consider the problem of estimating the charge carrier mobility of disordered organic semiconductors, which contain low-energy regions in which the charge carrier can quickly become stuck. It is shown that the AMC estimator for the charge carrier mobility reduces computational costs by several orders of magnitude compared to the CMC estimator.

Keywords: Markov chain; Nearly-completely decomposable; Monte Carlo; Segmentation; Watershed; Graph-theoretic decomposition; Electron transport; Mobility; Organic semiconductor; 60J22 (search for similar items in EconPapers)
Date: 2014
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s11009-013-9327-x 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:metcap:v:16:y:2014:i:2:d:10.1007_s11009-013-9327-x

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

DOI: 10.1007/s11009-013-9327-x

Access Statistics for this article

Methodology and Computing in Applied Probability is currently edited by Joseph Glaz

More articles in Methodology and Computing in Applied Probability from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().