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

11 Citations (Scopus)


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
Issue number2
Publication statusPublished - 2014
Externally publishedYes


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


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

Cite this