Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2605.12844

Walk on spheres and Array-RQMC

Valerie N. P. Ho, Art B. Owen

Published May 13, 2026• 0 citations
arXivHTMLPDF

Abstract

We use Array-RQMC sampling in a walk on spheres (WoS) algorithm for Dirichlet boundary value problems. On a collection of problems, we find that Array-RQMC-WoS reduces the Monte Carlo MSE or variance by factors ranging from $71$-fold to $3087$-fold at $n=2^{17}$ trajectories. The variance is known to be $o(1/n)$ but attains empirical rates between $n^{-1.4}$ and $n^{-1.8}$ in our examples. A simpler RQMC-WoS algorithm studied in Ho and Owen (2026) has more theoretical support but only reduced variance by 1.8 to 10.7-fold on the same set of examples. In order to explain this improvement, we introduce a column-wise mean dimension of the RQMC error based on Sobol' indices. It matches the usual mean dimension for Monte Carlo and the mean dimension of a dual lattice error for randomized lattices. We find for a gasket example from Crane et al. (2025) that the mean dimension of Array-RQMC-WoS errors is much higher than an analogous Array-MC-WoS algorithm has. v2 replaced v1's QMCPy lattice with Korobov lattices from LatNet Builder, but left the old abstract in the meta-data v3 corrects the v2 abstract in this meta data

DOI
10.48550/arxiv.2605.12844

Related papers

Fixed-Horizon Error Rates for Array-RQMC Metropolis-Hastings

Jiarui Du, Josef Dick, Zexin Pan +1 more

This paper studies randomised quasi-Monte Carlo (RQMC) methods for Metropolis--Hastings (MH) algorithms, whose accept--reject discontinuity complicates RQMC analysis. To circumvent some of these complications, we study Array-RQMC for MH, with $N$ replicated chains evolved over a fixed time horizon $T$, where we make use of Hilbert sorting for joint multidimensional updates at each step. For one-dimensional MH and bounded-variation test functions, we prove a sampling mean squared error bound of $\mathcal O_T(N^{-4/3})$ relative to the finite-horizon expectation. For product targets, coordinatewise Array-RQMC Metropolis-within-Gibbs retains this exponent for additive marginal bounded-variation tests, with constants that may depend on dimension. With Gaussian random-walk proposals, the bounds extend to scalar and additive marginal polynomials with an additional factor $(\log N)^\ell$, where $\ell$ is the maximum polynomial degree. For joint updates in state dimension $p$ using $p$ proposal uniforms, we provide a conditional $\mathcal O_T(N^{-1-1/(p+2)})$ framework under regularity assumptions that are not verified for the joint multidimensional examples. Numerical experiments support the verified one-dimensional theory and demonstrate variance reduction for joint Hilbert-sorted updates, including Bayesian logistic regression, while illustrating the limitations of these gains as dimension increases.

arXiv:2610.36431•Oct 27, 2026•0 citations

Randomized Quasi-Monte Carlo: An Introduction for Practitioners

Pierre L’Ecuyer

We survey basic ideas and results on randomized quasi-Monte Carlo (RQMC) methods, discuss their practical aspects, and give numerical illustrations. RQMC can improve accuracy compared with standard Monte Carlo (MC) when estimating an integral interpreted as a mathematical expectation. RQMC estimators are unbiased and their variance converges at a faster rate (under certain conditions) than MC estimators, as a function of the sample size. Variants of RQMC also work for the simulation of Markov chains, for function approximation and optimization, for solving partial differential equations, etc. In this introductory survey, we look at how RQMC point sets and sequences are constructed, how we measure their uniformity, why they can work for high-dimensional integrals, and how can they work when simulating Markov chains over a large number of steps.

•Aug 14, 2016•2 citations

Empirical Bernstein and betting confidence intervals for randomized quasi-Monte Carlo

Aadit Jain, Fred J. Hickernell, Art B. Owen +1 more

Abstract Randomized quasi-Monte Carlo (RQMC) methods estimate the mean of a random variable by sampling an integrand at $n$ equidistributed points. For scrambled digital nets, the resulting variance is typically $\tilde O(n^{-\theta })$, where $\theta \in [1,3]$ depends on the smoothness of the integrand and $\tilde O$ neglects logarithmic factors. While RQMC can be far more accurate than plain Monte Carlo (MC), it remains difficult to get confidence intervals on RQMC estimates. We investigate some empirical Bernstein confidence intervals (EBCIs) and hedged betting confidence intervals (HBCIs), both from Waudby-Smith and Ramdas (2024, J. Roy. Statist. Soc. B, 86, 1–27), when the random variable of interest is subject to known bounds. When there are $N$ integrand evaluations partitioned into $R$ independent replicates of $n=N/R$ RQMC points, and the RQMC variance is $\varTheta (n^{-\theta })$, then an oracle minimizing the width of a Bennett confidence interval would choose $n =\varTheta (N^{1/(\theta +1)})$. The resulting intervals have a width $\varTheta (N^{-\theta /(\theta +1)})$. Our empirical investigations had optimal values of $n$ grow slowly with $N$, HBCI intervals that were usually narrower than the EBCI ones and optimal values of $n$ for HBCI that were equal to or smaller than the ones for the oracle.

arXiv:2504.18677•Information and Inference A Journal of the IMA•Feb 6, 2026•0 citations

A Monte Carlo method for integration of multivariate smooth functions I: Sobolev spaces

Mario Ullrich

We study a Monte Carlo algorithm that is based on a specific (randomly shifted and dilated) lattice point set. The main result of this paper is that the mean squared error for a given compactly supported, square-integrable function is bounded by $n^{-1/2}$ times the $L_2$-norm of the Fourier transform outside a region around the origin, where $n$ is the expected number of function evaluations. As corollaries we obtain the order of convergence for the Sobolev spaces $H^s_p$ with isotropic, anisotropic or mixed smoothness for all values of the parameters. This proves, in particular, that the optimal order of convergence in the latter case is $n^{-s-1/2}$ for $p\ge2$, which is, in contrast to the case of deterministic algorithms, independent of the dimension. This shows that Monte Carlo algorithms can improve the order by more than $n^{-1/2}$ for a whole class of practically important function classes. All results carry over to functions defined on the unit cube without boundary conditions.

•Apr 20, 2016•1 citation

On the Convergence Rate of Randomized Quasi--Monte Carlo for Discontinuous Functions

Zhijian He, Xiaoqun Wang

This paper studies the convergence rate of randomized quasi--Monte Carlo (RQMC) for discontinuous functions, which are often of infinite variation in the sense of Hardy and Krause. It was previously known that the root mean square error (RMSE) of RQMC is only $o(n^{-1/2})$ for discontinuous functions. For certain discontinuous functions in $d$ dimensions, we prove that the RMSE of RQMC is $O(n^{-1/2-1/(4d-2)+\epsilon})$ for any $\epsilon>0$ and arbitrary $n$. If some discontinuity boundaries are parallel to some coordinate axes, the rate can be improved to $O(n^{-1/2-1/(4d_u-2)+\epsilon})$, where $d_u$ denotes the so-called irregular dimension, that is, the number of axes which are not parallel to the discontinuity boundaries. Moreover, this paper shows that the RMSE is $O(n^{-1/2-1/(2d)})$ for certain indicator functions.

SIAM Journal on Numerical Analysis•Jan 1, 2015•27 citations

QMC integration errors and quasi-asymptotics

Ilya M. Sobol, Boris V. Shukhman

Abstract A crude Monte Carlo (MC) method allows to calculate integrals over a d-dimensional cube. As the number N of integration nodes becomes large, the rate of probable error of the MC method decreases as O ⁢ ( 1 / N ) {O(1/\sqrt{N})} . The use of quasi-random points instead of random points in the MC algorithm converts it to the quasi-Monte Carlo (QMC) method. The asymptotic error estimate of QMC integration of d-dimensional functions contains a multiplier 1 / N {1/N} . However, the multiplier ( ln ⁡ N ) d {(\ln N)^{d}} is also a part of the error estimate, which makes it virtually useless. We have proved that, in the general case, the QMC error estimate is not limited to the factor 1 / N {1/N} . However, our numerical experiments show that using quasi-random points of Sobol sequences with N = 2 m {N=2^{m}} with natural m makes the integration error approximately proportional to 1 / N {1/N} . In our numerical experiments, d ≤ 15 {d\leq 15} , and we used N ≤ 2 40 {N\leq 2^{40}} points generated by the SOBOLSEQ16384 code published in 2011. In this code, d ≤ 2 14 {d\leq 2^{14}} and N ≤ 2 63 {N\leq 2^{63}} .

Monte Carlo Methods and Applications•Jul 16, 2020•2 citations
We use Array-RQMC sampling in a walk on spheres (WoS) algorithm for Dirichlet boundary value problems. On a collection of problems, we find that Array-RQMC-WoS reduces the Monte Carlo MSE or variance by factors ranging from 717171-fold to 308730873087-fold at n=217n=2^{17}n=217 trajectories. The variance is known to be o(1/n)o(1/n)o(1/n) but attains empirical rates between n−1.4n^{-1.4}n−1.4 and n−1.8n^{-1.8}n−1.8 in our examples. A simpler RQMC-WoS algorithm studied in Ho and Owen (2026) has more theoretical support but only reduced variance by 1.8 to 10.7-fold on the same set of examples. In order to explain this improvement, we introduce a column-wise mean dimension of the RQMC error based on Sobol' indices. It matches the usual mean dimension for Monte Carlo and the mean dimension of a dual lattice error for randomized lattices. We find for a gasket example from Crane et al. (2025) that the mean dimension of Array-RQMC-WoS errors is much higher than an analogous Array-MC-WoS algorithm has. v2 replaced v1's QMCPy lattice with Korobov lattices from LatNet Builder, but left the old abstract in the meta-data v3 corrects the v2 abstract in this meta data
This paper studies randomised quasi-Monte Carlo (RQMC) methods for Metropolis--Hastings (MH) algorithms, whose accept--reject discontinuity complicates RQMC analysis. To circumvent some of these complications, we study Array-RQMC for MH, with NNN replicated chains evolved over a fixed time horizon TTT, where we make use of Hilbert sorting for joint multidimensional updates at each step. For one-dimensional MH and bounded-variation test functions, we prove a sampling mean squared error bound of OT(N−4/3)\mathcal O_T(N^{-4/3})OT​(N−4/3) relative to the finite-horizon expectation. For product targets, coordinatewise Array-RQMC Metropolis-within-Gibbs retains this exponent for additive marginal bounded-variation tests, with constants that may depend on dimension. With Gaussian random-walk proposals, the bounds extend to scalar and additive marginal polynomials with an additional factor (log⁡N)ℓ(\log N)^\ell(logN)ℓ, where ℓ\ellℓ is the maximum polynomial degree. For joint updates in state dimension ppp using ppp proposal uniforms, we provide a conditional OT(N−1−1/(p+2))\mathcal O_T(N^{-1-1/(p+2)})OT​(N−1−1/(p+2)) framework under regularity assumptions that are not verified for the joint multidimensional examples. Numerical experiments support the verified one-dimensional theory and demonstrate variance reduction for joint Hilbert-sorted updates, including Bayesian logistic regression, while illustrating the limitations of these gains as dimension increases.
We survey basic ideas and results on randomized quasi-Monte Carlo (RQMC) methods, discuss their practical aspects, and give numerical illustrations. RQMC can improve accuracy compared with standard Monte Carlo (MC) when estimating an integral interpreted as a mathematical expectation. RQMC estimators are unbiased and their variance converges at a faster rate (under certain conditions) than MC estimators, as a function of the sample size. Variants of RQMC also work for the simulation of Markov chains, for function approximation and optimization, for solving partial differential equations, etc. In this introductory survey, we look at how RQMC point sets and sequences are constructed, how we measure their uniformity, why they can work for high-dimensional integrals, and how can they work when simulating Markov chains over a large number of steps.
Abstract Randomized quasi-Monte Carlo (RQMC) methods estimate the mean of a random variable by sampling an integrand at nnn equidistributed points. For scrambled digital nets, the resulting variance is typically O~(n−θ)\tilde O(n^{-\theta })O~(n−θ), where θ∈[1,3]\theta \in [1,3]θ∈[1,3] depends on the smoothness of the integrand and O~\tilde OO~ neglects logarithmic factors. While RQMC can be far more accurate than plain Monte Carlo (MC), it remains difficult to get confidence intervals on RQMC estimates. We investigate some empirical Bernstein confidence intervals (EBCIs) and hedged betting confidence intervals (HBCIs), both from Waudby-Smith and Ramdas (2024, J. Roy. Statist. Soc. B, 86, 1–27), when the random variable of interest is subject to known bounds. When there are NNN integrand evaluations partitioned into RRR independent replicates of n=N/Rn=N/Rn=N/R RQMC points, and the RQMC variance is Θ(n−θ)\varTheta (n^{-\theta })Θ(n−θ), then an oracle minimizing the width of a Bennett confidence interval would choose n=Θ(N1/(θ+1))n =\varTheta (N^{1/(\theta +1)})n=Θ(N1/(θ+1)). The resulting intervals have a width Θ(N−θ/(θ+1))\varTheta (N^{-\theta /(\theta +1)})Θ(N−θ/(θ+1)). Our empirical investigations had optimal values of nnn grow slowly with NNN, HBCI intervals that were usually narrower than the EBCI ones and optimal values of nnn for HBCI that were equal to or smaller than the ones for the oracle.
We study a Monte Carlo algorithm that is based on a specific (randomly shifted and dilated) lattice point set. The main result of this paper is that the mean squared error for a given compactly supported, square-integrable function is bounded by n−1/2n^{-1/2}n−1/2 times the L2L_2L2​-norm of the Fourier transform outside a region around the origin, where nnn is the expected number of function evaluations. As corollaries we obtain the order of convergence for the Sobolev spaces HpsH^s_pHps​ with isotropic, anisotropic or mixed smoothness for all values of the parameters. This proves, in particular, that the optimal order of convergence in the latter case is n−s−1/2n^{-s-1/2}n−s−1/2 for p≥2p\ge2p≥2, which is, in contrast to the case of deterministic algorithms, independent of the dimension. This shows that Monte Carlo algorithms can improve the order by more than n−1/2n^{-1/2}n−1/2 for a whole class of practically important function classes. All results carry over to functions defined on the unit cube without boundary conditions.
This paper studies the convergence rate of randomized quasi--Monte Carlo (RQMC) for discontinuous functions, which are often of infinite variation in the sense of Hardy and Krause. It was previously known that the root mean square error (RMSE) of RQMC is only o(n−1/2)o(n^{-1/2})o(n−1/2) for discontinuous functions. For certain discontinuous functions in ddd dimensions, we prove that the RMSE of RQMC is O(n−1/2−1/(4d−2)+ϵ)O(n^{-1/2-1/(4d-2)+\epsilon})O(n−1/2−1/(4d−2)+ϵ) for any ϵ>0\epsilon>0ϵ>0 and arbitrary nnn. If some discontinuity boundaries are parallel to some coordinate axes, the rate can be improved to O(n−1/2−1/(4du−2)+ϵ)O(n^{-1/2-1/(4d_u-2)+\epsilon})O(n−1/2−1/(4du​−2)+ϵ), where dud_udu​ denotes the so-called irregular dimension, that is, the number of axes which are not parallel to the discontinuity boundaries. Moreover, this paper shows that the RMSE is O(n−1/2−1/(2d))O(n^{-1/2-1/(2d)})O(n−1/2−1/(2d)) for certain indicator functions.
Abstract A crude Monte Carlo (MC) method allows to calculate integrals over a d-dimensional cube. As the number N of integration nodes becomes large, the rate of probable error of the MC method decreases as O ⁢ ( 1 / N ) {O(1/\sqrt{N})} . The use of quasi-random points instead of random points in the MC algorithm converts it to the quasi-Monte Carlo (QMC) method. The asymptotic error estimate of QMC integration of d-dimensional functions contains a multiplier 1 / N {1/N} . However, the multiplier ( ln ⁡ N ) d {(\ln N)^{d}} is also a part of the error estimate, which makes it virtually useless. We have proved that, in the general case, the QMC error estimate is not limited to the factor 1 / N {1/N} . However, our numerical experiments show that using quasi-random points of Sobol sequences with N = 2 m {N=2^{m}} with natural m makes the integration error approximately proportional to 1 / N {1/N} . In our numerical experiments, d ≤ 15 {d\leq 15} , and we used N ≤ 2 40 {N\leq 2^{40}} points generated by the SOBOLSEQ16384 code published in 2011. In this code, d ≤ 2 14 {d\leq 2^{14}} and N ≤ 2 63 {N\leq 2^{63}} .