An arXiv preprint offers a more direct analysis of a randomized quasi-Monte Carlo method for numerical integration, a way of estimating integrals from sampled points. For the functions covered by the theorem, it bounds the expected squared integration error, meaning the average squared gap between the estimate and the target integral, by a dimension-dependent soft-O factor times the square of a smoothed-out variation measure, divided by n-squared. Soft-O notation signals that some logarithmic and dimension-dependent details remain hidden. The result is a mathematical guarantee, not an empirical error estimate or a reported application.
The guarantee has a narrow target
The theorem applies to square-integrable functions on the d-dimensional unit cube, provided their smoothed-out variation, called sigmaSO in the paper, is finite. The analysis concerns a mathematical integration problem rather than an empirical participant sample. The algorithm takes n-squared independent, uniformly distributed points, partitions them into n output sets, and puts n points in each set. Its stated running-time bound is soft-O in n-squared.
How the point set is thinned
Before the thinning begins, the procedure applies a uniformly random shift. It then repeatedly assigns balanced signs and retains the points whose sign is 1, continuing for a logarithmic number of steps tied to n. The final estimate is the average of f over the output set. The design combines an initial point collection with repeated reductions to produce the sets used for integration.
The balancing step controls fluctuation
The balancing step uses a self-balancing walk and a procedure called TripletWalk, which sign vectors so their combined signed sum has a small sub-Gaussian norm. In ordinary language, sub-Gaussian control describes how tightly the analysis limits large fluctuations in that sum. At every thinning step, the signed sum over the current set has sub-Gaussian control at a scale of order a logarithm of n raised to d/2, where d is the dimension.
A proof built from simple pieces
The proof changes focus from the full function to its building blocks. It expands f in normalized Haar functions and writes the integration error as a sum in which each Haar coefficient is multiplied by the error of its corresponding basis function. This separates the basis-function errors before they are combined into the error for f.
One measure, two descriptions
The central bridge is a second description of smoothed-out variation. For any square-integrable function, the squared Haar-Besov seminorm, the paper's Haar-based measure of variation, becomes comparable above and below with the square of sigmaSO when averaged over uniformly random shifts. The comparison allows constants that depend on dimension. In reader terms, the shift-averaged Haar quantity and sigmaSO track the same scale.
A frequency-by-frequency check
An appendix gives a more detailed comparison in the one-dimensional smooth-periodic setting. It says the Bansal-Jiang endpoint-increment form, the shift-averaged Haar-Besov form, and sigmaSO characterize the same function space. For a nonzero one-dimensional Fourier frequency, the squared Haar-Besov seminorm of the associated Fourier character has order equal to the absolute frequency magnitude. That is an analytic scaling statement, not a measured estimate.
Separating slow and fast variation
To complete the error analysis, the proof splits the Haar expansion at a cutoff. For a fixed shift, the expected squared error from the low-frequency part is bounded by a dimension-dependent logarithmic factor times its Haar-Besov energy divided by n-squared. The high-frequency part is bounded by the same kind of logarithmic factor divided by an unspecified polynomial in n, multiplied by its high-frequency Haar-Besov energy. The supplied analysis does not give the hidden constants, the exact cutoff implementation, or the polynomial factor.
Paper data and sources
Original title: A Simpler Analysis of the Bansal-Jiang Quasi Monte-Carlo Algorithm via Haar Wavelets
Authors: Jiaheng Cheng, Agastya Vibhuti Jha, Haotian Jiang
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-28
DOI: Not available
Original paper · Full text