Splitting Algorithms for Rare Events of Semimartingale Reflecting Brownian Motions

Kevin Leder, Xin Liu, Zicheng Wang

Research output: Contribution to journalArticlepeer-review


We study rare event simulations of semimartingale reflecting Brownian motions (SRBMs) in an orthant. The rare event of interest is that a d-dimensional positive recurrent SRBM enters the set {z ∈ ℝd+: ∑d k=1 zk ≥ n} before hitting a small neighborhood of the origin {z ∈ ℝd+: ∑d k=1 zk ≤ ɛ} as n →∞ with a starting point outside the two sets and of order o(n). We show that, under two regularity conditions (the Dupuis–Williams stability condition of the SRBM and the Lipschitz continuity assumption of the associated Skorokhod problem), the probability of the rare event satisfies a large deviation principle. To study the variation-al problem (VP) for the rare event in two dimensions, we adapt its exact solution from developed by Avram, Dai, and Hasenbein in 2001. In three and higher dimensions, we con-struct a novel subsolution to the VP under a further assumption that the reflection matrix of the SRBM is a nonsingular M-matrix. Based on the solution/subsolution, particle-based simulation algorithms are constructed to estimate the probability of the rare event. Our estimator is asymptotically optimal for the discretized problem in two dimensions and has exponentially superior performance over standard Monte Carlo in three and higher dimen-sions. In addition, we establish that the growth rate of the relative bias term arising from discretization is subexponential in all dimensions. Therefore, we can estimate the probability of interest with subexponential complexity growth in two dimensions. In three and higher dimensions, the computational complexity of our estimators has a strictly smaller exponential growth rate than the standard Monte Carlo estimators.

Original languageEnglish (US)
Pages (from-to)291-325
Number of pages35
JournalStochastic Systems
Issue number4
StatePublished - Dec 2021

Bibliographical note

Funding Information:
K. Leder and Z. Wang were supported in part by NSF [Grant CMMI-1552764].

Publisher Copyright:
© 2021 The Author(s).


  • Large deviation principle
  • Particle splitting algorithms
  • Rare event simulations
  • Semimartingale reflecting Brownian motions
  • Subsolutions
  • Variational problems


Dive into the research topics of 'Splitting Algorithms for Rare Events of Semimartingale Reflecting Brownian Motions'. Together they form a unique fingerprint.

Cite this