pith. machine review for the scientific record. sign in

arxiv: 2605.12844 · v1 · submitted 2026-05-13 · 🧮 math.NA · cs.NA· stat.CO

Recognition: no theorem link

Walk on spheres and Array-RQMC

Art B. Owen, Valerie N. P. Ho

Authors on Pith no claims yet

Pith reviewed 2026-05-14 19:14 UTC · model grok-4.3

classification 🧮 math.NA cs.NAstat.CO
keywords Array-RQMCwalk on spheresDirichlet boundary value problemsvariance reductionSobol' indicesmean dimensionquasi-Monte Carlo
0
0 comments X

The pith

Array-RQMC sampling in the walk on spheres algorithm reduces Monte Carlo variance by factors of 57 to 2290 at sample size 2 to the 17.

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

The paper applies Array-RQMC sampling inside the walk on spheres algorithm to solve Dirichlet boundary value problems. It reports variance reductions far larger than those from a simpler RQMC version of the same algorithm. The authors introduce a column-wise mean dimension computed from Sobol' indices to isolate why the array version improves so much. This measure shows that Array-RQMC exploits higher-dimensional structure in the simulation error than ordinary Monte Carlo or single-stream RQMC. The empirical convergence rates reach between n to the -1.4 and n to the -1.8 on the tested problems.

Core claim

Array-RQMC-WOS reduces the Monte Carlo variance by factors ranging from 57-fold to 2290-fold at n=2^{17} trajectories. The variance attains empirical rates between n^{-1.4} and n^{-1.8} in the examples. A simpler RQMC-WOS algorithm reduced variance by only 1.8 to 10.7-fold on the same problems. The column-wise mean dimension of the RQMC error, defined via Sobol' indices, is much higher for Array-RQMC-WOS than for an analogous Array-MC-WOS algorithm on a gasket example.

What carries the argument

Array-RQMC sampling inside the walk on spheres algorithm, together with a column-wise mean dimension of the error computed from Sobol' indices.

If this is right

  • Array-RQMC produces superlinear empirical convergence for these path-based simulations.
  • The column-wise Sobol' mean dimension isolates the source of the variance reduction.
  • The same sampling technique can be inserted into other multi-step stochastic algorithms that simulate sphere walks.
  • Variance reduction factors will grow with the number of steps in the walk on spheres process.

Where Pith is reading between the lines

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

  • The method may transfer to other boundary-value problems that can be solved by Brownian motion paths.
  • Array structures could be tuned to raise the effective mean dimension even further in related quasi-Monte Carlo applications.
  • The observed rates suggest that Array-RQMC is capturing dependence across time steps that standard RQMC misses.

Load-bearing premise

The observed variance reductions and the higher column-wise mean dimension will continue to hold for Dirichlet problems outside the tested collection.

What would settle it

Applying Array-RQMC-WOS to a new, previously untested Dirichlet boundary value problem and measuring a variance reduction factor below 20 at n=2^{17} would falsify the scale of improvement reported.

Figures

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

Figure 1
Figure 1. Figure 1: Array-RQMC algorithm up to step k = 2. At each step, the previous states are mapped through a Hilbert curve to [0, 1) and then sorted accordingly, before advancing the chain. to yk+1 depends on yk only through zk. Then the cost function is c(yk ) =    −vol(B(zk, rk+1)) G B(zk,rk+1) d (zk, wk+1) g(wk+1), if k < τ b(z¯τ ), if k = τ 0, if k > τ. The algorithm detects k ⩾ τ by z ∈ ∂Ωε. To distinguish k > … view at source ↗
Figure 2
Figure 2. Figure 2: First four approximations of the Hilbert curve in [0 [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The apparent convergence rate for RQMC-WOS is [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗
Figure 3
Figure 3. Figure 3: Variance of the Array-RQMC-WOS, RQMC-WOS and MC-WOS [PITH_FULL_IMAGE:figures/full_fig_p012_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: MSE of the Array-RQMC-WOS, RQMC-WOS and MC-WOS esti [PITH_FULL_IMAGE:figures/full_fig_p013_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Variance and MSE of the Array-RQMC-WOS, RQMC-WOS, and [PITH_FULL_IMAGE:figures/full_fig_p014_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Variance for the dumbbell example, using Array-RQMC-WOS, [PITH_FULL_IMAGE:figures/full_fig_p016_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: MSE of MC-WOS, RQMC-WOS and Array-RQMC-WOS estimators [PITH_FULL_IMAGE:figures/full_fig_p016_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Variance curves for the Array-RQMC-WOS estimator using scrambled [PITH_FULL_IMAGE:figures/full_fig_p019_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Finally, for d = 2, we tested stratified point sets of size mk at each step k. Specifically, we used xik = (ak(i − 1) mod mk) + ∆k mk , i = 1, . . . , mk where ak is coprime with mk and ∆k ∼ U(0, 1) is a single random shift applied to all points in the RQMC point set at each step. This construction places exactly one point in each interval [j/mk,(j + 1)/mk), j = 0, . . . , mk − 1 and applies a shared shift… view at source ↗
Figure 9
Figure 9. Figure 9: Variance curves for some variants of Array-RQMC-WOS discussed in [PITH_FULL_IMAGE:figures/full_fig_p021_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Kolmogorov-Smirnov distance between pz and ˆpz averaged over 100 replicates, for 4 different starting points in the unit disk. The gray dashed line is proportional to the optimal values 1/(2n). where the effect fu depends on x only through xu ∈ [0, 1]|u| and is defined recursively by fu(x) = Z [0,1]d−|u|  f(x) − X v⊊u fv(x)  dx−u = Z [0,1]d−|u| f(x) dx−u − X v⊊u fv(x). The recursion starts with f∅, the … view at source ↗
Figure 11
Figure 11. Figure 11: Normalized and unnormalized total Sobol’ indices for the gasket [PITH_FULL_IMAGE:figures/full_fig_p028_11.png] view at source ↗
read the original 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 variance by factors ranging from $57$-fold to $2290$-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.

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.

Referee Report

3 major / 2 minor

Summary. The manuscript proposes integrating Array-RQMC sampling into the walk-on-spheres (WOS) algorithm for Dirichlet boundary-value problems. On a fixed collection of test problems it reports Monte Carlo variance reductions between 57-fold and 2290-fold at n=2^17 trajectories, together with empirical convergence rates in the range n^{-1.4} to n^{-1.8}. A simpler RQMC-WOS variant is shown to achieve only 1.8- to 10.7-fold reductions on the same examples. To account for the difference the authors define a column-wise mean dimension of the RQMC error via Sobol' indices, verify that it recovers the classical mean dimension for plain Monte Carlo and for randomized-lattice dual errors, and report a substantially higher value for Array-RQMC-WOS than for Array-MC-WOS on a gasket geometry.

Significance. If the reported variance reductions and super-linear rates prove robust outside the examined collection, the work would supply a concrete, easily implemented improvement to existing WOS solvers and a new diagnostic (column-wise mean dimension) for assessing RQMC performance on path-dependent integrands. The empirical evidence is obtained directly from Sobol' indices without fitted parameters, which is a methodological strength.

major comments (3)
  1. [§4] §4 (or the section presenting the gasket results): the claim that the newly defined column-wise mean dimension explains the observed n^{-1.4}–n^{-1.8} rates is not supported by any derivation showing how a higher value of this index produces faster-than-n^{-1} convergence; only matching with the classical mean dimension for MC and lattice rules is demonstrated.
  2. [Table 1] Table 1 (or the table of variance-reduction factors): the reported 57- to 2290-fold reductions and the associated empirical rates lack error bars or any statistical assessment of variability across independent replications, so it is impossible to judge whether the quoted rates are stable or artifacts of the particular random seeds and test geometries.
  3. [§5] §5 (discussion of generalizability): no additional domains, boundary conditions, or dimensions beyond the reported collection are examined, leaving open whether the advantage over both plain MC-WOS and the simpler RQMC-WOS of Ho & Owen persists for other Dirichlet problems.
minor comments (2)
  1. [§3.2] The notation for the column-wise mean dimension is introduced without an explicit equation number; adding a displayed equation would improve readability.
  2. [Figures 3–5] Several figure captions omit the precise value of n used for the plotted trajectories; consistency with the n=2^{17} figures in the text would help.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for their careful review and valuable comments on our manuscript. We address each of the major comments below and have made revisions where appropriate to strengthen the paper.

read point-by-point responses

  1. Referee: [§4] §4 (or the section presenting the gasket results): the claim that the newly defined column-wise mean dimension explains the observed n^{-1.4}–n^{-1.8} rates is not supported by any derivation showing how a higher value of this index produces faster-than-n^{-1} convergence; only matching with the classical mean dimension for MC and lattice rules is demonstrated.

    Authors: We agree that a rigorous derivation linking the column-wise mean dimension to the specific convergence rates is not provided in the manuscript. The column-wise mean dimension is introduced as a diagnostic tool to help explain why Array-RQMC achieves better performance than standard RQMC in this setting, building on the matching properties for MC and lattices. We have revised §4 to emphasize that this is an empirical finding supported by the Sobol' index calculations, and we have added a discussion of the heuristic reasons why a higher column-wise mean dimension might correlate with improved rates in the Array-RQMC context, citing relevant literature on effective dimension in quasi-Monte Carlo methods. A full theoretical derivation remains an open question for future research. revision: partial

  2. Referee: [Table 1] Table 1 (or the table of variance-reduction factors): the reported 57- to 2290-fold reductions and the associated empirical rates lack error bars or any statistical assessment of variability across independent replications, so it is impossible to judge whether the quoted rates are stable or artifacts of the particular random seeds and test geometries.

    Authors: The referee is correct that the original manuscript did not include error bars or replication-based variability measures. To address this, we have performed additional independent replications of the experiments and updated Table 1 to include standard errors for the variance reduction factors. We have also added error bars to the convergence rate plots and included a brief statistical assessment in the text of §4. revision: yes

  3. Referee: [§5] §5 (discussion of generalizability): no additional domains, boundary conditions, or dimensions beyond the reported collection are examined, leaving open whether the advantage over both plain MC-WOS and the simpler RQMC-WOS of Ho & Owen persists for other Dirichlet problems.

    Authors: We acknowledge that our numerical study is limited to the specific collection of test problems presented. We have expanded the discussion in §5 to better articulate the reasons why we expect the observed advantages to hold more generally, based on the structure of the WOS algorithm and the properties of Array-RQMC. However, we agree that testing on a broader set of problems would be beneficial and have noted this as an important avenue for future work. revision: partial

Circularity Check

0 steps flagged

Minor self-citation for comparison only; empirical results and new mean-dimension definition are self-contained

full rationale

The paper reports directly measured variance reduction factors (57-fold to 2290-fold) and empirical convergence rates (n^{-1.4} to n^{-1.8}) from simulations on a fixed collection of Dirichlet problems. These quantities are obtained by running the algorithms and computing sample variances; no parameter is fitted and then relabeled as a prediction. The column-wise mean dimension is explicitly introduced as a new definition based on standard Sobol' indices, with an explicit check that the definition recovers the usual mean dimension for plain Monte Carlo and for randomized-lattice dual errors. The only self-citation is to the authors' own 2026 paper on the simpler RQMC-WOS algorithm, used solely for side-by-side numerical comparison on the same test set. That citation is not load-bearing for the central claims about Array-RQMC-WOS performance or the explanatory value of the new mean-dimension measure. No step in the reported chain reduces by construction to a prior result or to a fitted quantity inside the present paper.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

No free parameters, axioms, or invented entities are stated in the abstract; the work rests on standard properties of RQMC and Sobol' indices.

pith-pipeline@v0.9.0 · 5506 in / 1080 out tokens · 29957 ms · 2026-05-14T19:14:02.795121+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

45 extracted references · 45 canonical work pages · 1 internal anchor

  1. [1]

    Bilyk, D., V. N. Temlyakov, and R. Yu (2012). Fibonacci sets and symmetrization in discrepancy theory. Journal of Complexity\/ 28\/ (1), 18--36

    work page 2012

  2. [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. [3]

    Caflisch, R. E., W. Morokoff, and A. B. Owen (1997). Valuation of mortgage backed securities using Brownian bridges to reduce effective dimension. Journal of Computational Finance\/ 1 , 27--46

    work page 1997

  4. [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. [5]

    Cools, R., F. Y. Kuo, and D. Nuyens (2006). Constructing embedded lattice rules for multivariate integration. SIAM Journal on Scientific Computing\/ 28\/ (6), 2162--2188

    work page 2006

  6. [6]

    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

  7. [7]

    DeLaurentis, J. M. and L. A. Romero (1990). A Monte Carlo method for Poisson's equation. Journal of Computational Physics\/ 90\/ (1), 123--140

    work page 1990

  8. [8]

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

    work page 2010

  9. [9]

    Gerber, M. and N. Chopin (2015). Sequential quasi monte carlo. Journal of the Royal Statistical Society Series B: Statistical Methodology\/ 77\/ (3), 509--579

    work page 2015

  10. [10]

    Griebel, M., F. Y. Kuo, and I. H. Sloan (2010). The smoothing effect of the ANOVA decomposition. Journal of Complexity\/ 26\/ (5), 523--551

    work page 2010

  11. [11]

    Halton, J. H. (1960). On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals. Numerische Mathematik\/ 2\/ (1), 84--90

    work page 1960

  12. [12]

    Hammersley, J. M. (1960). Monte Carlo methods for solving multivariable problems. Annals of the New York Academy of Sciences\/ 86\/ (3), 844--874

    work page 1960

  13. [13]

    He, Z. and A. B. Owen (2015). Extensible grids: uniform sampling on a space filling curve. Journal of the Royal Statistical Society: Series B (Statistical Methodology)\/ 78\/ (4), 917--931

    work page 2015

  14. [14]

    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

  15. [15]

    Ho, V. N. P. and A. B. Owen (2026). Randomized quasi-Monte Carlo for walk on spheres. Technical report, arXiv:2605.08483

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  16. [16]

    Jansen, M. J. W. (1999). Analysis of variance designs for model output. Computer Physics Communications\/ 117\/ (1--2), 35--43

    work page 1999

  17. [17]

    Jansen, M. J. W., W. A. H. Rossing, and R. A. Daamen (1994). Monte Carlo estimation of uncertainty contributions from several independent multivariate sources. In Predictability and nonlinear modelling in natural sciences and economics , pp.\ 334--343. Springer

    work page 1994

  18. [18]

    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

  19. [19]

    W \"a chter, and N

    Keller, A., C. W \"a chter, and N. Binder (2022). Rendering along the Hilbert curve. In Z. Botev, A. Keller, C. Lemieux, and B. Tuffin (Eds.), Advances in Modeling and Simulation: Festschrift for Pierre L'Ecuyer , pp.\ 319--332. Springer

    work page 2022

  20. [20]

    L \'e cot, C. and B. Tuffin (2004). Quasi-Monte Carlo methods for estimating transient measures of discrete time Markov chains. In Monte Carlo and Quasi-Monte Carlo Methods 2002 , pp.\ 329--343. Springer

    work page 2004

  21. [21]

    L \'e cot, and B

    L'Ecuyer, P., C. L \'e cot, and B. Tuffin (2008). A randomized quasi- M onte C arlo simulation method for M arkov chains. Operations Research\/ 56\/ (4), 958--975

    work page 2008

  22. [22]

    L'Ecuyer, P. and C. Lemieux (2000). Variance reduction via lattice rules. Management Science\/ 46\/ (9), 1214--1235

    work page 2000

  23. [23]

    Munger, C

    L'Ecuyer, P., D. Munger, C. L \'e cot, and B. Tuffin (2018). Sorting methods and convergence rates for array-rqmc: Some empirical comparisons. Mathematics and Computers in Simulation\/ 143 , 191--201

    work page 2018

  24. [24]

    Liu, R. and A. B. Owen (2006). Estimating mean dimensionality of analysis of variance decompositions. Journal of the American Statistical Association\/ 101\/ (474), 712--721

    work page 2006

  25. [25]

    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

  26. [26]

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

    work page 2022

  27. [27]

    Marsaglia, G., W. W. Tsang, and J. Wang (2003). Evaluating Kolmogorov's distribution. Journal of statistical software\/ 8 , 1--4

    work page 2003

  28. [28]

    walk on spheres

    Mascagni, M. and C.-O. Hwang (2003). -shell error analysis for “walk on spheres” algorithms. Mathematics and computers in simulation\/ 63\/ (2), 93--104

    work page 2003

  29. [29]

    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

  30. [30]

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

    work page 1998

  31. [31]

    McKay, M. D., R. J. Beckman, and W. J. Conover (1979). A comparison of three methods for selecting values of input variables in the analysis of output from a computer code. Technometrics\/ 21\/ (2), 239--45

    work page 1979

  32. [32]

    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

  33. [33]

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

    work page 1992

  34. [34]

    Owen, A. B. (1992). Orthogonal arrays for computer experiments, integration and visualization. Statistica Sinica\/ 2\/ (2), 439--452

    work page 1992

  35. [35]

    Owen, A. B. (2020). On dropping the first Sobol' point. In A. Keller (Ed.), International conference on Monte Carlo and quasi-Monte Carlo methods in scientific computing, MCQMC 2020 , pp.\ 71--86. Springer

    work page 2020

  36. [36]

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

    work page 2023

  37. [37]

    Pan, Z. and A. B. Owen (2023). The nonzero gain coefficients of Sobol' s sequences are always powers of two. Journal of Complexity\/ 75 , 101700

    work page 2023

  38. [38]

    Sagan, H. (1994). Space-filling curves . Springer Science

    work page 1994

  39. [39]

    Ratto, T

    Saltelli, A., M. Ratto, T. Andres, F. Campolongo, J. Cariboni, D. Gatelli, M. Saisana, and S. Tarantola (2008). Global sensitivity analysis: the primer . Chichester: John Wiley & Sons

    work page 2008

  40. [40]

    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

  41. [41]

    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

  42. [42]

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

    work page 1994

  43. [43]

    Sobol', I. M. (1967). Distribution of points in a cube and the approximate evaluation of integrals (in R ussian). Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki\/ 7 , 784--802

    work page 1967

  44. [44]

    Sobol', I. M. (1993). Sensitivity estimates for nonlinear mathematical models. Mathematical Modeling and Computational Experiment\/ 1 , 407--414

    work page 1993

  45. [45]

    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