Exact simulation for multivariate Itô diffusions

José Blanchet, Fan ZhangAdvances 2020 · DOI · arXiv

Abstract

We provide the first generic exact simulation algorithm for multivariate diffusions. Current exact sampling algorithms for diffusions require the existence of a transformation which can be used to reduce the sampling problem to the case of a constant diffusion matrix and a drift which is the gradient of some function. Such a transformation, called the Lamperti transformation, can be applied in general only in one dimension. So, completely different ideas are required for the exact sampling of generic multivariate diffusions. The development of these ideas is the main contribution of this paper. Our strategy combines techniques borrowed from the theory of rough paths, on the one hand, and multilevel Monte Carlo on the other.

Introduction

Simulating Stochastic Differential Equations (SDEs) is a cornerstone of modern computational finance, physics, and biology. Traditionally, researchers rely on discretization schemes like the Euler-Maruyama method. While effective, these methods introduce a discretization bias because they only approximate the true path of the process. "Exact simulation" seeks to eliminate this bias by sampling the state of the process at a specific time $T$ directly from its true transition distribution.

Until now, generic exact simulation was largely restricted to one-dimensional systems. The landmark Beskos-Roberts algorithm, which pioneered this field, relies on the Lamperti transformation to map an SDE into one with a constant diffusion coefficient and a gradient-form drift. In multivariate settings, the geometric conditions required for such a transformation are rarely met, creating a "multivariate curse" for exact sampling. This paper introduces a novel framework that bypasses these geometric constraints entirely.

Methodology

The authors propose a two-stage strategy to handle the complexities of multivariate diffusions without relying on the Lamperti transformation.

1. Identity Diffusion and Tolerance-Enforced Simulation (TES)

For SDEs where the diffusion matrix is the identity, the problem can be framed using Girsanov’s theorem to change the measure to a simpler Brownian motion. However, this introduces a complex likelihood ratio involving a stochastic integral. To resolve this, the authors employ Tolerance-Enforced Simulation (TES).

Rooted in rough path theory, TES allows for the "localization" of a path within a deterministic error bound $\epsilon$. Rather than calculating the exact likelihood—which is often computationally impossible—TES iteratively refines the path's precision. This refinement continues until the algorithm can definitively decide an acceptance/rejection step in a Monte Carlo framework. Essentially, one only needs to know if a value is above or below a threshold, not its exact coordinate.

2. General Multivariate Case and MLMC

For SDEs with non-constant diffusion matrices, the authors construct an unbiased estimator of the transition density. They adapt the "telescoping sum" logic from Multilevel Monte Carlo (MLMC) to create a randomized estimator. This approach effectively removes the bias inherent in local approximations by weighing a sequence of increasingly refined simulations.

3. Bernoulli Factories

Implementing acceptance-rejection sampling is challenging when the acceptance probability $p$ is only accessible via an unbiased estimator. To solve this, the authors use Bernoulli factories. These are specialized algorithms designed to produce a binary outcome (a coin flip) with probability $p$, even when $p$ is only known through an oracle that provides unbiased estimates.

Key Insights

  • The Power of Localization: The paper demonstrates that exact values of path-dependent functionals are unnecessary for exact simulation. By using TES to zoom in on a path, one can make rigorous acceptance/rejection decisions with certainty.
  • Rough Path Error Bounds: The use of rough path theory is foundational. It provides the deterministic error bounds required to guarantee that the localization process eventually terminates, ensuring the algorithm is mathematically sound.
  • Debiasing via Randomization: By combining MLMC techniques with exact sampling, the authors show how to transform a sequence of biased density approximations into a single, unbiased sample.

Theoretical Results

The paper culminates in two primary theoretical contributions:

  • Theorem 3: Establishes an exact simulation algorithm for SDEs with constant diffusion coefficients, proving that the process terminates with probability one.
  • Theorem 4: Provides the first generic exact simulation algorithm for general multivariate SDEs. This holds under specific regularity conditions, requiring the system to be three times continuously differentiable and uniformly elliptic.

These results prove that exact multivariate simulation is theoretically possible without the restrictive geometric assumptions that have limited the field for decades.

Limitations and Future Directions

Despite the theoretical breakthrough, the authors note a significant practical hurdle: the proposed algorithms have infinite expected termination time. While the algorithms are guaranteed to finish "almost surely" (with probability 1), the average runtime is mathematically infinite. This occurs because the computational cost of localizing a path near the boundaries of an acceptance region grows exponentially as the required precision increases.

Future research will focus on:

  • Rare-event simulation: Techniques to mitigate the infinite time bottleneck.
  • Controlled Bias: Investigating whether reintroducing a small, managed amount of bias could make the algorithm computationally efficient while preserving essential properties like positivity.
  • Complexity Optimization: Improving the scaling of Bernoulli factories relative to the dimensionality of the system.

Summary updated

Abstract

Abstract We provide the first generic exact simulation algorithm for multivariate diffusions. Current exact sampling algorithms for diffusions require the existence of a transformation which can be used to reduce the sampling problem to the case of a constant diffusion matrix and a drift which is the gradient of some function. Such a transformation, called the Lamperti transformation, can be applied in general only in one dimension. So, completely different ideas are required for the exact sampling of generic multivariate diffusions. The development of these ideas is the main contribution of this paper. Our strategy combines techniques borrowed from the theory of rough paths, on the one hand, and multilevel Monte Carlo on the other.
BibTeX
@inproceedings{blanchet2020exact,
  author = {José Blanchet and Fan Zhang},
  title = {{Exact simulation for multivariate Itô diffusions}},
  booktitle = {Advances},
  year = {2020},
  doi = {10.1017/apr.2020.39},
}
Figure