Efficient simulation of Markov chains using segmentation

T. Brereton, O. Stenzel, B. Baumeier, D. Andrienko, V. Schmidt, D. Kroese

Research output: Contribution to journalArticleAcademicpeer-review

9 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)465-484
Number of pages20
JournalMethodology and Computing in Applied Probability
Volume16
Issue number2
DOIs
Publication statusPublished - 2014
Externally publishedYes

Keywords

  • Electron transport
  • Graph-theoretic decomposition
  • Markov chain
  • Mobility
  • Monte Carlo
  • Nearly-completely decomposable
  • Organic semiconductor
  • Segmentation
  • Watershed

Fingerprint Dive into the research topics of 'Efficient simulation of Markov chains using segmentation'. Together they form a unique fingerprint.

Cite this