Fixed-Horizon Error Rates for Array-RQMC Metropolis-Hastings
Abstract
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 𝒪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)ℓ, where ℓ is the maximum polynomial degree. For joint updates in state dimension p using p proposal uniforms, we provide a conditional 𝒪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.
Related
- Convergence of Independence Metropolis-Hastings Algorithms in High Dimensions: Iteration Lengths, Cutoff Profiles, and Diagnostic Unreliability
- Spectral Gap Inheritance for Metropolis-Hastings with Reversible Proposals
- Generalizing Metropolis-Hastings for DAG Sampling
- When Metropolis and Hastings Meet Bradley and Terry: Exact MCMC From Preference Voting
- Fixed-Time ISS for Interconnected Discrete-Time Systems, Part II: Finite-Horizon Lyapunov Functions
BibTeX
@misc{du2026fixedhorizon,
title = {{Fixed-Horizon Error Rates for Array-RQMC Metropolis-Hastings}},
author = {Jiarui Du and Josef Dick and Zexin Pan and Houying Zhu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.36431},
eprint = {2610.36431},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.36431},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Fixed-Horizon Error Rates for Array-RQMC Metropolis-Hastings
AU - Jiarui Du
AU - Josef Dick
AU - Zexin Pan
AU - Houying Zhu
PY - 2026
DA - 2026/10/27
PB - arXiv
DO - 10.48550/arxiv.2610.36431
UR - https://arxiv.org/abs/2610.36431
AB - 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 𝒪_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)^ℓ, where ℓ is the maximum polynomial degree. For joint updates in state dimension p using p proposal uniforms, we provide a conditional 𝒪_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.
ER -