Randomly shifted lattice rules for SDEs with constant diffusion: error bounds uniform in time discretization and dimension
Du Ouyang, Josef Dick, Ziyang Ye
math.NA
Nov 5, 2026 · v1
TL;DR
The main sampling-error theorems and corollary (Theorems 3.1, 3.6, 3.7, Corollary 3.3) are formalized in Lean 4, with a public repository.
Abstract
We study randomly shifted rank-1 lattice rules for computing $\mathbb{E}[g(\mathbf{X}_T)]$, where $\mathbf{X}_T$ is the terminal state of a stochastic differential equation (SDE) with constant diffusion matrix. Discretizing the SDE by the Euler–Maruyama scheme with $m$ uniform time steps turns the expectation into an integral whose dimension grows with $m$ and whose integrand has a nested composition structure; both complicate the lattice rule error analysis. We generate the Brownian path by the Brownian bridge construction and handle the nested structure using the multivariate Faà di Bruno formula and a rooted-tree expansion. Under suitable regularity and growth conditions, we prove that an $N$-point randomly shifted lattice rule with a uniformly random generating vector achieves a mean absolute sampling error of $O(N^{-1+\varepsilon})$ for every $\varepsilon\in(0,1/2)$ and every prime $N$, with the implied constant independent of $m$. To improve stability and control higher error moments, the median lattice estimator is used. The estimator takes the median of $R=2k-1$ independent lattice estimates and achieves an $L^q$ error of $O(N^{-1+\varepsilon})$ for every $1\le q<k/(1-\varepsilon)$. We further establish error bounds independent of both the state dimension and the Brownian path dimension under an additional summability condition on the columns of the diffusion matrix. Numerical experiments show that median lattice estimators converge faster than Monte Carlo estimators and remain stable as the number of time steps $m$ grows. For models satisfying the additional summability condition, stability is also observed as the state and Brownian path dimensions increase.
Problem
Expectations of functions of SDE solutions with constant diffusion are computed by Euler–Maruyama discretization. This yields high-dimensional integrals whose dimension grows with the number of time steps and whose integrands have a nested composition structure. The question is how to get quasi-Monte Carlo lattice-rule error bounds that stay uniform in the time discretization and in dimension.
Approach
Brownian paths are generated by the Brownian bridge construction. Mixed derivatives of the nested integrand are controlled with the multivariate Faà di Bruno formula and a rooted-tree expansion, giving summability estimates in weighted Gaussian function spaces. These estimates are combined with randomly shifted rank-1 lattice rules that use random generating vectors, and with a median-of-R lattice estimator. The main theorems are formalized in Lean 4.
Results
A single random lattice rule has mean absolute error O(N^{-1+ε}) for prime N, with a constant independent of the number of time steps m. The median estimator achieves the same rate in L^q for 1 ≤ q < k/(1-ε). Under a summability condition on the diffusion columns, the bounds are also independent of the state and Brownian path dimensions. Numerical experiments show faster convergence than Monte Carlo and stability as m and the dimensions grow.