Unbiased Sampling of Multidimensional Partial Differential Equations with Random Coefficients

José Blanchet, Fengpei Li, Xiaoou LiarXiv 2018 · DOI · arXiv

Abstract

We construct an unbiased estimator for function value evaluated at the solution of a partial differential equation with random coefficients. We show that the variance and expected computational cost of our estimator are finite and our estimator is unsensitive to the problem dimension so that it can be applied in problems across various disciplines. For the error analysis, we connect the parabolic partial differential equations with the expectations of stochastic differential equations and perform rough path estimation.

Introduction

Parabolic partial differential equations (PDEs), such as the heat equation, are fundamental in fields ranging from finance (option pricing) to physics (thermal conductivity) and geology (fluid flow in porous media). In practice, the coefficients of these equations—like the drift $\mu(x)$ or diffusion $\sigma(x)$—are often uncertain or heterogeneous, leading researchers to model them as random fields.

Solving these "random PDEs" is notoriously difficult for two primary reasons:

  1. The Curse of Dimensionality: Traditional numerical methods like Finite Element Methods (FEM) require grids that grow exponentially with the number of dimensions ($d$).
  2. Bias vs. Variance: Standard Monte Carlo methods for these problems are typically biased because they rely on discretizing the underlying stochastic processes. Previous attempts to create unbiased estimators often suffered from infinite variance in dimensions higher than $d=3$, making them impractical for complex real-world systems.

Methodology

The authors construct a random variable $W$ that serves as an unbiased estimator for the expected value of a functional of the PDE solution. Their approach integrates several sophisticated techniques:

  • Feynman-Kac Formula: They transform the PDE problem into an equivalent problem of calculating expectations over paths of a Stochastic Differential Equation (SDE).
  • Antithetic Multilevel Monte Carlo (MLMC): Building on work by Giles and Szpruch, they use a hierarchy of discretization levels. The "antithetic" part ensures that the difference between a fine grid and a coarse grid has very low variance, which is crucial for efficiency.
  • Randomization for Bias Removal: They employ a "debiasing" trick (the Rhee-Glynn estimator) where the discretization level itself is chosen randomly. This turns a biased limit into an unbiased sum with finite expected computational cost.
  • Rough Path Theory: This is the paper's core technical innovation. Standard error analysis usually relies on Gronwall’s inequality, which fails when the drift coefficient is itself a random field. The authors use rough path estimates to provide "path-by-path" error bounds, proving that their estimator has finite variance even under random coefficients.
Algorithm 3: The UNBIASED_Z procedure for generating unbiased estimators.

The implementation of this approach is formalized in Algorithm 3, which details the UNBIASED_Z procedure. This algorithm generates the unbiased estimator by sampling from a geometric distribution to determine the discretization level and then computing the corresponding path increments.

Key Results and Insights

The paper validates the estimator using synthetic benchmarks, including an Ornstein-Uhlenbeck process and a complex multidimensional SDE where the drift $\mu(x)$ is a random field defined by a trigonometric series expansion.

Theoretical and Empirical Success

The authors rigorously prove that their estimator $W$ is unbiased ($E[W] = \nu$), has finite variance ($Var(W) < \infty$), and has finite expected computational cost. In simulations, the proposed estimator correctly converged to the true mean, while standard Monte Carlo methods showed significant, non-overlapping bias. For example, in a complex SDE test, the 95% confidence interval for the standard MC was $[0.5189, 0.5255]$, while the unbiased estimator correctly identified the interval as $[0.4610, 0.4656]$.

Dimensionality Independence

A significant finding is that the convergence rate of this Monte Carlo procedure is $O(n^{-1/2})$ for any dimension $d$. While the constants might grow with $d$, the fundamental scaling does not, effectively "beating" the curse of dimensionality.

Practical Utility of Rough Paths

Rough path theory, often viewed as abstract pure mathematics, is shown here to have practical utility in numerical analysis. It allows for handling the "roughness" of random coefficients where traditional Lipschitz-based tools break down. Furthermore, because the estimator is unbiased and has finite variance, it is highly parallel-friendly, allowing for implementation across massive parallel computing architectures with zero communication overhead.

Limitations and Future Work

While promising, the current approach has some limitations:

  • Deterministic Diffusion: The current proof assumes the diffusion coefficient $\sigma(x)$ is deterministic. Extending this to random $\sigma(x)$ is suggested but not fully detailed.
  • Coefficient Regularity: The random field $\mu(x)$ must satisfy certain regularity conditions (e.g., being twice continuously differentiable).
  • Computational Constants: Although the rate of convergence is independent of dimension, the constant factors still depend on $d$, presenting an opportunity for future optimization.

Summary updated

Abstract

We construct an unbiased estimator for function value evaluated at the solution of a partial differential equation with random coefficients. We show that the variance and expected computational cost of our estimator are finite and our estimator is unsensitive to the problem dimension so that it can be applied in problems across various disciplines. For the error analysis, we connect the parabolic partial differential equations with the expectations of stochastic differential equations and perform rough path estimation.
BibTeX
@misc{blanchet2018unbiased,
  author = {José Blanchet and Fengpei Li and Xiaoou Li},
  title = {{Unbiased Sampling of Multidimensional Partial Differential Equations with Random Coefficients}},
  year = {2018},
  eprint = {1806.03362},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1806.03362},
}
Figure