Autocovariance and Optimal Design for Random Walk Metropolis-Hastings Algorithm
Jingyi Zhang, James C. Spall 1 · 2025
Read Autocovariance and Optimal Design for Random Walk Metropolis-Hastings Algorithm by Jingyi Zhang, James C. Spall 1 (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-10967.txt.
Introduction
Jingyi Zhang and James Spall study the spread of guesses made by a classic sampling method that walks at random and accepts or rejects each step. The method, named for Metropolis and Hastings, is widely used to draw samples from a target spread. Most past work looked at how fast it settles, not at how its guesses vary together over time.
The authors derive new results for the single-value case with bell-shaped targets and even step proposals. In that case they also find the best proposal design. For many-value cases, they link the spread to the well-known target of about a quarter of steps accepted.
Catalog record
| CREATOR | Jingyi Zhang, James C. Spall 1 |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 40 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-10967
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Autocovariance and Optimal Design for Random Walk Metropolis-Hastings Algorithm Jingyi Zhang, James C. Spall 1 Abstract The Metropolis–Hastings algorithm has been extensively studied in the estimation and simulation literature, with most prior work focusing on convergence behavior and asymptotic theory. However, its covariance structure—an important statistical property for both theory and implementation—remains less understood. In this work, we provide new theoretical insights into the scalar case, focusing primarily on symmetric unimodal target distributions with symmetric random walk proposals, where we also establish an optimal proposal design. In addition, we derive some more general results beyond this setting. For the high-dimensional case, we relate the covariance matrix to the classical 0.23 average acceptance rate tuning criterion. I Introduction Markov chain Monte Carlo (MCMC) provides a general framework for sampling from complex distributions by constructing a Markov chain with the desired stationary distribution [ 15 ] . This approach enables efficient approximation of expectations and integrals that are otherwise analytically intractable, and it has found widespread applications in statistics, engineering, and control [ 6 ] . In particular, Monte Carlo particle filters can discretize the state space to enable efficient MAP sequence estimation via dynamic programming [ 4 ] . MCMC has also been applied to Bayesian inference for stochastic kinetic models by sampling joint posteriors of parameters and latent data [ 5 ] , and to system identification for Bayesian parameter estimation in complex dynamical models beyond the reach of traditional techniques [ 12 ] . In the control domain, particle MCMC has been applied to infer latent trajectories and nonparametric dynamics in Gaussian process state-space models [ 3 ] , MCMC has been used to generate model uncertainty sets in nonlinear dynamical systems via Hamiltonian Monte Carlo sampling of high-dimensional transfer operators [ 16 ] , and ghost sampling, an MCMC-based technique, has been introduced to efficiently simulate power disturbances conditional on rate-of-change-of-frequency violations in power systems [ 10 ] ; moreover, MCMC has also been integrated with Bernstein approximation techniques to handle non-affine and dependent chance constrained optimization problems, providing an efficient approach to high-dimensional integration [ 18 ] . The Metropolis–Hastings algorithm is one of the foundational methods in MCMC, with widespread applications in model estimation, physics, and system identification [ 6 , 2 ] . The theoretical study of MH has been extensive, with a large body of work devoted to convergence behavior and asymptotic properties of estimators [ 17 , 14 , 1 ] . An important line of research in MCMC has focused on the scaling and efficiency of Metropolis-Hastings algorithms in high-dimensional settings. For Gaussian random walk Metropolis (RWM) algorithms, the efficiency of the chain is maximized when the average acceptance rate is tuned to approximately 0.23 [ 13 ] . This “ 0.23 rule” has since become a widely used guideline for practitioners, providing a concrete and interpretable criterion for tuning proposal variances in high-dimensional problems. While convergence and asymptotics have been well developed, comparatively little is known about the covariance structure, or equivalently the autocorrelation, of the MH chain itself. MCMC methods are closely connected with statistical estimation, providing a means to approximate otherwise intractable quantities. Within this framework, the covariance structure of the samples plays a central role in determining estimation accuracy and efficiency. Further knowledge of the covariances of the samples relates strategies for variance reduction, and potentially guides practical implementation of MCMC algorithms. This work aims to address this gap. We first study the scalar case of MH with symmetric random walk proposals, focusing on symmetric unimodal target distributions. In this setting, we establish new theoretical results on the covariance structure and propose an optimal design for the proposal distribution of symmetric random walk form. In addition, we present some general results beyond this restrictive setting. For the high-dimensional case, under the same setup as Roberts and Gelman [ 13 ] , we relate the unit-lag covariance matrix to the classical 0.23 average acceptance rate criterion, providing new theoretical connections between covariance properties and established tuning principles. Before beginning the technical analysis, we emphasize that Metropolis-Hastings chains are not necessarily positively correlated. As a counterexample, consider the target density \pi(x)=\mathcal{N}(0,1) and the proposal density q(y|x)=\mathcal{N}(-cx,2) with c\in(0,1) . In this setting, proposed moves tend to push the chain in the opposite direction of the current state, so that x_{t}>0 typically leads to x_{t+1}<0 and vice versa. Since the covariance reduces to \mathrm{Cov}(X_{t},X_{t+1})=\mathbb{E}[X_{t}X_{t+1}] under the symmetry of \pi , the systematic flipping effect yields negative correlation. Both theoretical analysis and numerical evaluations confirm that the covariance is strictly negative for all c\in(0,1) . The paper is organized as follows. Section II presents the preliminary background, notation, and problem setup. Section III contains the main theoretical results. Section IV discusses the optimal proposal design. Section V provides numerical experiments to assess whether the proposed design can improve the efficiency of the Metropolis-Hastings algorithm. Section VI concludes with remarks and directions for future work. II Preliminaries Monte Carlo methods provide a general tool for estimation and simulation when analytical solutions are unavailable. MCMC extends this idea by constructing a Markov chain with the desired stationary distribution, enabling sampling from complex or high-dimensional models [ 15 , 6 ] . Within this framework, the Metropolis-Hastings (MH) algorithm stands out as a versatile and widely used scheme. In this section, we present the Metropolis-Hastings algorithm, establish the notation, and outline the problem setup. II-A Metropolis-Hastings algorithm Assume a continuous state space with probability density functions. The overall aim of MCMC methods such as Metropolis-Hastings algorithm is to generate samples from a target density of interest, say \pi(x) . The MH algorithm is defined by a proposal density q(y|x) for transitioning from state x to state y , and a target density \pi of interest. The MH algorithm accepts a proposed move with probability \alpha(x,y)=\min\!\left(1,\frac{\pi(y)q(x|y)}{\pi(x)q(y|x)}\right), and otherwise the chain remains at x . This induces a Markov transition kernel \mathcal{K}(x,y)=\alpha(x,y)q(y|x)+\delta(y-x)\big(1-r(x)\big), where \delta(\cdot) is the Dirac measure at 0 , and r(x)=\int\alpha(x,y)\,q(y|x)\,\mathrm{d}y is the overall acceptance probability at current state [ 6 ] . Under ergodicity and irreducibility assumptions, the Markov chain converges to the unique invariant distribution. Let (\mathcal{X},\mathcal{B}) denote the underlying measurable state space, with \mathcal{X} the state space and \mathcal{B} its associated \sigma -algebra, then \pi(y)=\int_{\mathcal{X}}\mathcal{K}(x,y)\,\pi(dx)\quad\pi\text{-a.s. on }(\mathcal{X},\mathcal{B}). where “ \pi -a.s.” indicates that the equality holds for all y except on a \pi -null set (i.e. almost surely). The above formulation specifies the acceptance mechanism and transition kernel in mathematical terms. For clarity, we now summarize the MH algorithm in a step-by-step procedure. Step 1. Initialization. Choose the initial state X_{0}\in\mathcal{X} and set t=0 . Step 2. Given X_{t} , generate a candidate Y according to the proposal density q(\cdot|X_{t}) . Step 3. Compute the acceptance probability \alpha(X_{t},Y)=\min\!\left(1,\frac{\pi(Y)q(X_{t}|Y)}{\pi(X_{t})q(Y|X_{t})}\right). Then set X_{t+1}=\begin{cases}Y,&\text{with probability }\alpha(X_{t},Y),\\[6.0pt] X_{t},&\text{with probability }1-\alpha(X_{t},Y).\end{cases} Increment t\leftarrow t+1 . Step 4. Repeat Steps 2-3 until the terminal iteration n is reached, yielding the chain (X_{0},\dots,X_{n}) . Our aim in this paper is to analyze the autocovariance structure of the sequence \{X_{0},X_{1},X_{2},\ldots,X_{t}\} produced by the MH algorithm. We focus on the larget t (post-“burn-in”) where the process has achieved a stationary probability distribution. II-B Notation Let X_{t} denote the current state. We