arxiv: 2605.08483 · v1 · submitted 2026-05-08 · 🧮 math.NA · cs.NA· stat.CO

Recognition: no theorem link

Randomized quasi-Monte Carlo for walk on spheres

Art B. Owen, Valerie N. P. Ho

Authors on Pith no claims yet

Pith reviewed 2026-05-12 01:35 UTC · model grok-4.3

classification 🧮 math.NA cs.NAstat.CO

keywords randomized quasi-Monte Carlowalk on spheresDirichlet problemsvariance reductionharmonic functionsMonte Carlo methodsnumerical integrationboundary value problems

0 comments

The pith

Randomized quasi-Monte Carlo in walk-on-spheres yields variance decay slightly better than Monte Carlo for Dirichlet problems.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines the use of randomized quasi-Monte Carlo sampling inside walk-on-spheres algorithms for boundary value problems with Dirichlet conditions. For two-dimensional harmonic functions the integrands become periodic indicator functions on the torus, and the authors establish conditions under which the boundaries have the required Minkowski content to invoke existing variance theory. In five numerical examples covering both two and three dimensions as well as problems with source terms, four RQMC schemes all produced sampling variances that fell slightly faster than the Monte Carlo benchmark. The median rate was better than n to the power of minus 1.1, and variance was reduced by factors between 1.8 and 10.7 at the largest sample size. These gains matter because they let practitioners reach a given accuracy level with substantially fewer random walks when solving elliptic partial differential equations.

Core claim

When randomized quasi-Monte Carlo replaces ordinary Monte Carlo inside the walk-on-spheres procedure, the variance of the estimator for the solution of the Dirichlet problem decreases with the number n of points at a rate slightly better than n to the minus one. Across four RQMC methods and five test problems the median observed rate exceeded O(n to the minus 1.1), while the variance reduction relative to plain Monte Carlo ranged from 1.8 to 10.7 at n equal to 2 to the 17. The improvement is seen both for purely harmonic functions in two dimensions and for three-dimensional problems that include nonzero source functions.

What carries the argument

The key machinery is the walk-on-spheres representation of the Dirichlet solution as an expectation that, after suitable randomization, produces a periodic indicator function on the torus whose boundary satisfies a Minkowski-content condition allowing application of discrepancy-based variance bounds.

If this is right

Variance reduction factors of 2 to 11 mean that target accuracy can be reached with far fewer sample paths.
The Minkowski-content condition on region boundaries permits the use of existing RQMC error analysis for these periodic integrands.
The lack of dominance by any one RQMC method indicates that several constructions are viable in practice.
The same improvement appears in three-dimensional settings and with source terms, showing the technique is not limited to simple harmonic cases.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Similar RQMC substitutions could accelerate other Monte Carlo algorithms for PDEs that rely on sphere or ball sampling.
If the boundary regularity condition can be verified for irregular domains, the method would extend to more realistic geometries arising in applications.
Computational savings from the variance reduction could make high-resolution simulations of diffusion processes more feasible on modest hardware.
The results suggest examining whether multilevel or other variance-reduction combinations with RQMC yield additive benefits.

Load-bearing premise

The boundaries of the integration regions must have finite (k-1)-dimensional Minkowski content so that the variance bounds derived by He and Wang apply without additional error terms.

What would settle it

A new example satisfying the periodic-indicator and Minkowski-content assumptions but exhibiting variance decay no better than O(n to the minus one) would show that the reported improvement does not hold in general.

Figures

Figures reproduced from arXiv: 2605.08483 by Art B. Owen, Valerie N. P. Ho.

**Figure 1.** Figure 1: In this problem u(z) is the temperature of the gasket at z ∈ Ω. The purpose of the head gasket is to avoid any leakage of oil or coolant from the combustion engine into the cylinders where combustion occurs. Leaks are more likely to occur where the gasket is hotter. They are interested in approximating the solution to the BVP with ∆u(z) = 0 for z ∈ Ω ◦ and boundary values u(z) = X r∈{coolant, outer, oil, o… view at source ↗

**Figure 1.** Figure 1: Cylinder head gasket domain. The domain Ω is the interior of the [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗

**Figure 2.** Figure 2: Variance of the standard WOS estimator at [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗

**Figure 3.** Figure 3: The curve A is a circular arc. Together with the shown rays it defines 4 open regions of R 2 on which rA is analytic. Ramamurthy (1998) which uses parameterized arcs. We write our real analytic arc as A = {ϕ(t) | 0 ⩽ t ⩽ 1} and we assume that ϕ ′ (t) ̸= 0 at any t ∈ [0, 1]. With this parameterization, we define an internal curve A◦ = ϕ((0, 1)) and endpoints a = ϕ(0) and b = ϕ(1). Then rA(z) = min ra(z), rA… view at source ↗

**Figure 4.** Figure 4: This figure illustrates a portion of the proof of Theorem 10 for [PITH_FULL_IMAGE:figures/full_fig_p022_4.png] view at source ↗

**Figure 5.** Figure 5: MSE of the WOS estimator for the unit disk example, starting at [PITH_FULL_IMAGE:figures/full_fig_p025_5.png] view at source ↗

**Figure 6.** Figure 6: MSE of the standard WOS estimator for the major circular sector [PITH_FULL_IMAGE:figures/full_fig_p026_6.png] view at source ↗

**Figure 7.** Figure 7: Dumbbell-shaped domain with parameters R = 1, L = 1.5 and w = 0.4. The starting point z0 = (0.5, 0) used in our experiments is marked with a red cross. Using MC and RQMC samples, we get the results presented in [PITH_FULL_IMAGE:figures/full_fig_p027_7.png] view at source ↗

**Figure 8.** Figure 8: Variance of the WOS estimator for the dumbbell example, started [PITH_FULL_IMAGE:figures/full_fig_p028_8.png] view at source ↗

**Figure 9.** Figure 9: MSE of the standard WOS estimator for the unit ball example, for [PITH_FULL_IMAGE:figures/full_fig_p029_9.png] view at source ↗

read the original abstract

We investigate the use of randomized quasi-Monte Carlo (RQMC) in walk on spheres algorithms to solve boundary value problems for functions with Dirichlet boundary conditions in $\mathbb{R}^d$. For harmonic functions with $d=2$, the integrands of interest are periodic indicator functions over regions $\Theta$ in the torus $\mathbb{T}^k$. We give conditions for $\partial\Theta$ to have $k-1$ dimensional Minkowski content which allows us to use results of He and Wang (2015). The RQMC estimates involve multiple values of $k$. We see sampling variances decreasing with the number $n$ of sample points at slightly better than Monte Carlo rates. The median variance rate in $4$ RQMC methods over $5$ worked examples, including some with $d=3$ and some with nonzero source functions, was slightly better than $O(n^{-1.1})$. The variance reduction factors ranged from $1.8$ to $10.7$ at $n=2^{17}$. None of the four RQMC methods dominated the others.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

RQMC inside walk-on-spheres gives modest empirical variance gains over MC but the supporting theory only covers the 2D harmonic cases they tested.

read the letter

The paper combines randomized quasi-Monte Carlo with walk-on-spheres for Dirichlet problems. The central observation is that four RQMC schemes produced variance rates slightly better than O(n^{-1}) across five examples, with reduction factors between 1.8 and 10.7 at n=2^17. None of the RQMC variants stood out as clearly best. They also state explicit conditions on the Minkowski content of the boundary of the integration region so that He and Wang's results apply to the periodic indicator integrands that appear in the two-dimensional harmonic setting. That combination and the concrete variance numbers are new. The geometric conditions are written out plainly and the experiments are described enough that someone could re-run them. The work stays within its stated scope and does not overclaim the size of the improvement. The main limitation is that the theory is tied to periodic indicators on the torus, yet the reported examples include three-dimensional domains and Poisson problems with nonzero sources. In those cases the integrand is no longer a simple periodic indicator, so the Minkowski-content hypothesis does not transfer directly and the paper supplies no separate verification for the test geometries. The variance figures are given without error bars or details on how the five examples were selected, which leaves the median rate of slightly better than n^{-1.1} harder to interpret. This is useful reading for people already running walk-on-spheres codes who want a small, low-effort accuracy boost. It is not a breakthrough but the empirical comparison is honest and the conditions are stated clearly enough to be checked. I would send it to referees; the practical evidence is worth a specialist look even with the gap between the stated theory and the full set of experiments.

Referee Report

3 major / 2 minor

Summary. The paper investigates the use of randomized quasi-Monte Carlo (RQMC) within walk-on-spheres algorithms for Dirichlet boundary value problems in R^d. For the d=2 harmonic case it states conditions under which the boundary of the region Θ in the torus T^k has finite (k-1)-dimensional Minkowski content, allowing application of variance bounds from He and Wang (2015). Empirical tests on five examples (including d=3 problems and cases with nonzero source terms) report that four RQMC variants produce sampling variances that decay at rates slightly better than O(n^{-1.1}), with variance reduction factors ranging from 1.8 to 10.7 at n=2^{17}; no single method dominates.

Significance. If the reported rates prove robust and reproducible, the work supplies practical evidence that RQMC can deliver modest but consistent variance reduction over plain Monte Carlo in a widely used PDE solver. The explicit geometric conditions offered for the d=2 case form a useful link to existing QMC theory. The multi-example comparison across dimensions and source terms provides concrete implementation guidance, though the absence of verification for the key assumption in the full test suite limits the strength of the theoretical backing.

major comments (3)

[theoretical justification for periodic indicators] The section stating the Minkowski-content conditions for ∂Θ (immediately preceding the citation of He and Wang (2015)) gives the general hypothesis but supplies no analytic or numerical verification that any of the five concrete Θ satisfy it. This is load-bearing for the d=3 and nonzero-source experiments, where the integrands are no longer simple periodic indicators, so the cited variance bounds do not automatically apply.
[numerical experiments] Numerical results section: the median variance rate “slightly better than O(n^{-1.1})” and the reduction-factor range 1.8–10.7 are reported without error bars, without description of the regression procedure used to extract the rates, and without any account of how the five examples were chosen. These omissions make it impossible to assess whether the observed improvement is statistically reliable or merely an artifact of the particular test set.
[methodology] Algorithmic description: the four RQMC variants are compared but the precise randomization schemes, the mapping from the torus samples to the walk-on-spheres steps, and the handling of the source term (when present) are not specified in sufficient detail for independent reproduction or for confirming that the same sampling strategy is used across all examples.

minor comments (2)

[abstract] Abstract: the four RQMC methods are referred to only by number; naming them (e.g., “randomized Sobol’, scrambled Halton, …”) would improve immediate readability.
[preliminaries] Notation: the dimension k of the torus is introduced without an explicit relation to the spatial dimension d; a short clarifying sentence would prevent confusion when k varies across examples.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We address each major comment below and describe the revisions we will make to improve clarity, reproducibility, and the scope of the theoretical claims.

read point-by-point responses

Referee: The section stating the Minkowski-content conditions for ∂Θ (immediately preceding the citation of He and Wang (2015)) gives the general hypothesis but supplies no analytic or numerical verification that any of the five concrete Θ satisfy it. This is load-bearing for the d=3 and nonzero-source experiments, where the integrands are no longer simple periodic indicators, so the cited variance bounds do not automatically apply.

Authors: We agree that the Minkowski-content conditions and the variance bounds of He and Wang (2015) apply directly only to the d=2 harmonic cases with periodic indicator integrands. The d=3 and nonzero-source results are presented as empirical observations. In revision we will (i) state the limited scope of the cited bounds explicitly, (ii) add numerical checks confirming finite (k-1)-dimensional Minkowski content for the two d=2 examples, and (iii) note that the theoretical guarantees do not extend to the remaining experiments. revision: yes
Referee: Numerical results section: the median variance rate “slightly better than O(n^{-1.1})” and the reduction-factor range 1.8–10.7 are reported without error bars, without description of the regression procedure used to extract the rates, and without any account of how the five examples were chosen. These omissions make it impossible to assess whether the observed improvement is statistically reliable or merely an artifact of the particular test set.

Authors: We will augment the numerical section with (a) error bars obtained from 100 independent replications of each RQMC estimator, (b) a description of the ordinary-least-squares regression performed on log-log plots over n = 2^10 to 2^17, and (c) a brief rationale for the choice of the five examples (covering harmonic/non-harmonic problems in d=2 and d=3). These additions will allow readers to evaluate the statistical reliability of the reported rates. revision: yes
Referee: Algorithmic description: the four RQMC variants are compared but the precise randomization schemes, the mapping from the torus samples to the walk-on-spheres steps, and the handling of the source term (when present) are not specified in sufficient detail for independent reproduction or for confirming that the same sampling strategy is used across all examples.

Authors: We will expand the algorithmic section to specify (i) the exact randomization (random shifts for lattice rules, digital shifts for digital nets), (ii) the coordinate-wise mapping from torus points to the sequence of sphere radii and centers in the walk-on-spheres iteration, and (iii) the explicit integrand modification used when a nonzero source term is present. These details will be given uniformly for all five examples. revision: yes

Circularity Check

0 steps flagged

No circularity: empirical rates computed directly from simulations; external theorem applied under stated conditions

full rationale

The paper's central results are Monte Carlo variance estimates obtained by running the described RQMC algorithms on five concrete examples. These rates are reported as direct simulation outputs (median slightly better than O(n^{-1.1}), reduction factors 1.8-10.7 at n=2^17) and do not reduce, by any equation in the manuscript, to quantities fitted from the same data or to a self-citation chain. The invocation of He and Wang (2015) occurs only after the authors explicitly state the Minkowski-content hypothesis for the d=2 harmonic case; the hypothesis is not derived from the present work and the citation is external. For the d=3 and nonzero-source examples the paper makes no theoretical claim and relies solely on the empirical numbers. No self-definitional, fitted-input, or ansatz-smuggling steps appear.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central empirical claims rest on the assumption that the integration domains satisfy a Minkowski-content condition so that He and Wang (2015) theory applies; no free parameters or new entities are introduced.

axioms (1)

domain assumption ∂Θ has (k-1)-dimensional Minkowski content for the relevant regions Θ
Invoked to justify use of He and Wang (2015) results on the discrepancy of the integrands.

pith-pipeline@v0.9.0 · 5489 in / 1309 out tokens · 35080 ms · 2026-05-12T01:35:12.690276+00:00 · methodology

discussion (0)

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Walk on spheres and Array-RQMC
math.NA 2026-05 unverdicted novelty 7.0

Array-RQMC-WOS cuts Monte Carlo variance by 57-2290 times with empirical rates n^{-1.4} to n^{-1.8} and introduces a column-wise mean dimension to explain the gain.

Reference graph

Works this paper leans on

36 extracted references · 36 canonical work pages · cited by 1 Pith paper

[1]

Basu, S. and S. Prasad (2023). A connection between cut locus, T hom space and M orse-- B ott functions. Algebraic & Geometric Topology\/ 23\/ (9), 4185--4233

work page 2023
[2]

Binder, I. and M. Braverman (2012). The rate of convergence of the walk on spheres algorithm. Geometric and Functional Analysis\/ 22\/ (3), 558--587

work page 2012
[3]

Choi, H. I., S. W. Choi, and H. P. Moon (1997). Mathematical theory of medial axis transform. Pacific Journal of Mathematics\/ 181\/ (1), 57--88

work page 1997
[4]

Choi, S.-C. T., F. J. Hickernell, M. McCourt, J. Rathinavel, and A. G. Sorokin (2026). QMCPy : A Q uasi- M onte C arlo P ython L ibrary

work page 2026
[5]

Gkioulekas, B

Crane, K., I. Gkioulekas, B. Miller, and R. Sawhney (2025). Walk on spheres in one weekend. https://brickisland.net/wos-one-weekend/. Online tutorial, accessed April 2026

work page 2025
[6]

Faber, M

Czekanski, M., B. Faber, M. Fairborn, A. Wright, and D. Bindel (2024). Walking on spheres and talking to neighbors: Variance reduction for Laplace's equation. Technical report, arXiv:2404.17692

work page arXiv 2024
[7]

Dick, J. and F. Pillichshammer (2010). Digital sequences, discrepancy and quasi- Monte Carlo integration . Cambridge: Cambridge University Press

work page 2010
[8]

Dudek, E. and K. Holly (1994). Nonlinear orthogonal projection. Annales Polonici Mathematici\/ 59\/ (1), 1--31

work page 1994
[9]

Evans, L. C. and R. F. Gariepy (2015). Measure Theory and Fine Properties of Functions\/ (Revised ed.). Textbooks in Mathematics. Boca Raton, FL: CRC Press

work page 2015
[10]

Fang, K.-T. and Y. Wang (1994). Number Theoretic Methods in Statistics . Chapman & Hall

work page 1994
[11]

Farouki, R. T. and R. Ramamurthy (1998). Degenerate point/curve and curve/curve bisectors arising in medial axis computations for planar domains with curved boundaries. Computer Aided Geometric Design\/ 15\/ (6), 615--635

work page 1998
[12]

Federer, H. (1969). Geometric measure theory . Berlin: Springer-Verlag

work page 1969
[13]

Foote, R. L. (1984). Regularity of the distance function. Proceedings of the American Mathematical Society\/ 92\/ (1), 153--155

work page 1984
[14]

Guillemin, V. and A. Pollack (1974). Differential topology . Englewood Cliffs, NJ: Prentice-Hall

work page 1974
[15]

He, Z. and X. Wang (2015). On the convergence rate of randomized quasi- Monte Carlo for discontinuous functions. SIAM Journal on Numerical Analysis\/ 53\/ (5), 2488--2503

work page 2015
[16]

Joe, S. and F. Y. Kuo (2008). Constructing Sobol' sequences with better two-dimensional projections. SIAM Journal on Scientific Computing\/ 30\/ (5), 2635--2654

work page 2008
[17]

Krantz, S. G. and H. R. Parks (1999). The geometry of domains in space . New York: Springer Science & Business Media

work page 1999
[18]

Lee, J. M. (2013). Introduction to Smooth Manifolds\/ (Second ed.). New York: Springer

work page 2013
[19]

Leobacher, G. and A. Steinicke (2021). Existence, uniqueness and regularity of the projection onto differentiable manifolds. Annals of global analysis and geometry\/ 60\/ (3), 559--587

work page 2021
[20]

Lundberg, E. and K. Ramachandran (2019). A note on the critical points of the torsion function. Technical report, arxiv:1907.08376v1

work page arXiv 2019
[21]

Magnanini, R. and G. Poggesi (2022). The location of hot spots and other extremal points. Mathematische Annalen\/ 384\/ (1), 1--39

work page 2022
[22]

W alk O n S pheres

Mascagni, M. and C.-O. Hwang (2003). -shell error analysis for “ W alk O n S pheres” algorithms. Mathematics and computers in simulation\/ 63\/ (2), 93--104

work page 2003
[23]

Karaivanova, and C.-O

Mascagni, M., A. Karaivanova, and C.-O. Hwang (2004). Quasi- Monte Carlo methods for elliptic BVP s. In Monte Carlo and Quasi-Monte Carlo Methods 2002: Proceedings of a Conference held at the National University of Singapore, Republic of Singapore, November 25--28, 2002 , pp.\ 345--355. Springer

work page 2004
[24]

Matou s ek, J. (1998). On the L ^2 --discrepancy for anchored boxes. Journal of Complexity\/ 14 , 527--556

work page 1998
[25]

Mattila, P. (1999). Geometry of sets and measures in Euclidean spaces : fractals and rectifiability . Number 44. Cambridge, MA: Cambridge University Press

work page 1999
[26]

Muller, M. E. (1956). Some continuous Monte Carlo methods for the Dirichlet problem. The Annals of Mathematical Statistics\/ 27\/ (3), 569--589

work page 1956
[27]

Niederreiter, H. (1992). Random Number Generation and Quasi- Monte Carlo Methods . Philadelphia, PA: S.I.A.M

work page 1992
[28]

Owen, A. B. (2005). Multidimensional variation for quasi- Monte Carlo . In J. Fan and G. Li (Eds.), International Conference on Statistics in honour of Professor Kai-Tai Fang's 65th birthday

work page 2005
[29]

Owen, A. B. (2023). Practical Quasi-Monte Carlo Integration . https://artowen.su.domains/mc/practicalqmc.pdf

work page 2023
[30]

Owen, A. B. and Z. Pan (2024). Gain coefficients for scrambled Halton points. SIAM Journal on Numerical Analysis\/ 62\/ (3), 1021--1038

work page 2024
[31]

Owen, A. B. and D. Rudolf (2021). A strong law of large numbers for scrambled net integration. SIAM Review\/ 63\/ (2), 360--372

work page 2021
[32]

Sabelfeld, K. K. (1991). Monte Carlo methods in boundary value problems . Berlin: Springer-Verlag

work page 1991
[33]

Sawhney, R. and K. Crane (2020). Monte Carlo geometry processing: A grid-free approach to PDE -based methods on volumetric domains. ACM Transactions on Graphics\/ 39\/ (4)

work page 2020
[34]

Miller, I

Sawhney, R., B. Miller, I. Gkioulekas, and K. Crane (2023). Walk on stars: A grid-free Monte Carlo method for PDE s with Neumann boundary conditions. Technical report, arXiv:2302.11815

work page arXiv 2023
[35]

Sloan, I. H. and S. Joe (1994). Lattice Methods for Multiple Integration . Oxford: Oxford Science Publications

work page 1994
[36]

Morrical, S

Wu, L., N. Morrical, S. P. Bangaru, R. Sawhney, S. Zhao, C. Wyman, R. Ramamoorthi, and A. Lefohn (2025). Unbiased differential visibility using fixed-step walk-on-spherical-caps and closest silhouettes. ACM Transactions on Graphics (TOG)\/ 44\/ (4), 1--16

work page 2025