# Statistically efficient thinning of a Markov chain sampler

arXiv: https://arxiv.org/abs/1510.07727 · HTML: https://mlsanity.com/paper/1510.07727/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Oct 2015.

## Built on by (most cited first, 8 of 8)

- [Kernel Thinning](https://mlsanity.com/paper/2105.05842/) (2021)
- [Generalized Kernel Thinning](https://mlsanity.com/paper/2110.01593/) (2021)
- [A Survey of Monte Carlo Methods for Parameter Estimation](https://mlsanity.com/paper/2107.11820/) (2021)
- [Distribution Compression in Near-linear Time](https://mlsanity.com/paper/2111.07941/) (2021)
- [Weighted quantization using MMD: From mean field to mean shift via gradient flows](https://mlsanity.com/paper/2502.10600/) (2025)
- [Efficient and Accurate Explanation Estimation with Distribution Compression](https://mlsanity.com/paper/2406.18334/) (2024)
- [Local and Mixing-Based Algorithms for Gaussian Graphical Model Selection from Glauber Dynamics](https://mlsanity.com/paper/2412.18594/) (2024)
- [Unbiased Derivative Estimation for Stationary Mean of Parameterized Markov chains](https://mlsanity.com/paper/2606.11487/) (2026)

## Abstract (arXiv)

It is common to subsample Markov chain output to reduce the storage burden. Geyer (1992) shows that discarding k-1 out of every k observations will not improve statistical efficiency, as quantified through variance in a given computational budget. That observation is often taken to mean that thinning MCMC output cannot improve statistical efficiency. Here we suppose that it costs one unit of time to advance a Markov chain and then θ>0 units of time to compute a sampled quantity of interest. For a thinned process, that cost θ is incurred less often, so it can be advanced through more stages. Here we provide examples to show that thinning will improve statistical efficiency if θ is large and the sample autocorrelations decay slowly enough. If the lag ℓ≥1 autocorrelations of a scalar measurement satisfy ρℓ≥ρℓ+1≥0, then there is always a θ<∞ at which thinning becomes more efficient for averages of that scalar. Many sample autocorrelation functions resemble first order AR(1) processes with ρℓ =ρ|ℓ| for some -1<ρ<1. For an AR(1) process it is possible to compute the most efficient subsampling frequency k. The optimal k grows rapidly as ρ increases towards 1. The resulting efficiency gain depends primarily on θ, not ρ. Taking k=1 (no thinning) is optimal when ρ≤0. For ρ>0 it is optimal if and only if θ ≤ (1-ρ)2/(2ρ). This efficiency gain never exceeds 1+θ. This paper also gives efficiency bounds for autocorrelations bounded between those of two AR(1) processes.