A data-dependent DKW inequality for regenerative Markov chains

Daniel C. Jerison · 2026

Read A data-dependent DKW inequality for regenerative Markov chains by Daniel C. Jerison (2026) 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-2606-30866.txt.

Introduction

Daniel Jerison proves a data-dependent version of the Dvoretzky-Kiefer-Wolfowitz inequality for Markov chains that regenerate. The classical inequality bounds how far an empirical distribution can sit from the true one, giving confidence bands for distribution and quantile functions. Markov chain samples are dependent, though, and Jerison's setting assumes the chain periodically restarts in distribution, which lets the sample path be cut into independent tours.

His band holds uniformly at a stated confidence level, is fully explicit, and is nearly optimal. Its leading width term is computed straight from the observed path, with no prior knowledge of how fast the chain converges; the convergence bound enters only a smaller correction term. Such empirical bounds suit chains that mix far faster in practice than theory can prove.

Catalog record

CREATORDaniel C. Jerison
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE40 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.30866

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A data-dependent DKW inequality for regenerative Markov chains Daniel C. Jerison Abstract . We prove a version of the Dvoretzky–Kiefer–Wolfowitz inequality for Markov chains with a regenerative structure. Suppose we have a regenerative Markov chain with stationary distribution π \pi . Given a functional θ \theta on the state space and a confidence level 1 − δ 1-\delta , our result provides a uniform 1 − δ 1-\delta confidence band for the CDF of θ \theta under π \pi based on the empirical CDF. By inversion, we get a 1 − δ 1-\delta confidence band for the quantile function of θ \theta under π \pi . Our bounds are fully explicit and nearly optimal. In addition, they are data-dependent in the following sense: in the formula for the width of the confidence band, the leading term can be computed directly from the sample path without any a priori information about the convergence rate of the chain. A convergence bound is required, but it contributes to the width of the confidence band only through a lower-order term. For this reason, our result is attractive for Markov chains whose convergence rate is much quicker in practice than what can be proved in theory. Data-dependent bounds of this type are called empirical concentration inequalities in the literature. Thus, our result is an empirical concentration inequality for the empirical CDF of θ \theta given the sample path. 1. Introduction This paper is concerned with explicit, nonasymptotic bounds for Markov chain Monte Carlo estimation. Suppose that (X_{t})_{t\geq 0} is a discrete time Markov chain on a state space \mathcal{X} with stationary distribution \pi . Let \theta:\mathcal{X}\to\mathbf{R} be an observable quantity of interest. The empirical distribution of \theta given the sample path (X_{0},\ldots,X_{n-1}) is \hat{\pi}_{n}(\theta\in S)=\frac{1}{n}\sum_{t=0}^{n-1}\mathbf{1}\{\theta(X_{t})\in S\},\qquad\text{for measurable $S\subseteq\mathbf{R}$}. We say that the Glivenko–Cantelli property is satisfied if the empirical cumulative distribution function of \theta converges uniformly to the cumulative distribution function of \theta under \pi : (1.1) \sup_{x\in\mathbf{R}}\left|\hat{\pi}_{n}(\theta\leq x)-\pi(\theta\leq x)\right|\to 0\qquad\text{almost surely as }n\to\infty. A DKW inequality for the Markov chain (X_{t}) is a quantitative upper bound on the supremum in ( 1.1 ) that holds with high probability. It is named after the classical inequality of Dvoretzky–Kiefer–Wolfowitz [ 7 ] , which provides the same type of bound in the case of iid data. Various authors [ 6 , 10 , 13 , 21 , 2 ] have proved DKW-type inequalities for Markov chains (or, more generally, for dependent sequences satisfying strong mixing conditions) under different assumptions. In any such result, it is necessary to have some control over the mixing properties of the chain. This is a major issue: • Many chains used in the practice of MCMC do not have theoretical convergence guarantees. • Some chains do have theoretical convergence guarantees, but only of a qualitative nature (e.g., the chain is known to be geometrically ergodic but without any explicit convergence rate). • Some chains have theoretical convergence guarantees with explicit rates, but the numerical convergence bounds are very conservative compared with the observed behavior of the chain. When dealing with a Markov chain in the third category, we might hope to get tighter estimation error bounds by feeding in information from the sample path. The main result of this paper can be stated informally as follows. Suppose that the chain (X_{t}) satisfies a certain exponential convergence bound, which is associated with constants B and \gamma (see ( 1.3 ) below). Then, for every \delta>0 , with probability at least 1-\delta we have (1.2) \sup_{x\in\mathbf{R}}\left|\hat{\pi}_{n}(\theta\leq x)-\pi(\theta\leq x)\right|\leq\frac{\log(n)}{\sqrt{n}}\cdot C_{1}(X,\delta)+\frac{\log(n)}{n}\cdot C_{2}(B,\gamma,\delta) where C_{1}(X,\delta) and C_{2}(B,\gamma,\delta) have explicit formulas and do not grow with n . The notation C_{1}(X,\delta) means that C_{1} depends on \delta and on the sample path (X_{0},\ldots,X_{n-1}) , but not on the exponential convergence bound. The notation C_{2}(B,\gamma,\delta) means that C_{2} depends on \delta and on the exponential convergence bound (but not on the sample path). See Theorem 2.1 for the fully precise statement. In ( 1.2 ), the leading term \frac{\log(n)}{\sqrt{n}}\cdot C_{1}(X,\delta) has nearly optimal dependence on n , except for the logarithmic factor. 1 1 1 To the author’s knowledge, all similar results either also have a log factor or impose an extra condition, such as uniform ergodicity, that allows the log factor to be removed. The bound in [ 2 ] has a factor of \sqrt{\log(n)} , which is slightly better than ( 1.2 ). In addition, since C_{1}(X,\delta) is fully data-dependent, its size is determined by the actual mixing properties of the Markov chain and not by the convergence bound, which may be quite conservative. The second term \frac{\log(n)}{n}\cdot C_{2}(B,\gamma,\delta) has optimal dependence on n and B,\gamma , including the logarithmic factor, as we discuss in Section 1.4 . 1.1. Regenerative chains Our results hold for Markov chains that have a regenerative structure. Let \nu be a probability measure on the state space \mathcal{X} . A \nu -regeneration time for the chain (X_{t}) is a random time T with the property that X_{T}\sim\nu , and moreover, the law of X_{T} is independent of the value of T and of the history (X_{t})_{t<T} . In other words, at time T the chain regenerates in a state drawn independently from \nu . A standard way to construct regeneration times is to identify a so-called small set . This is a subset A\subseteq\mathcal{X} together with a constant \varepsilon>0 and a probability measure \nu on \mathcal{X} such that \mathbf{P}(X_{t+1}\in\cdot\mid X_{t}=x)\geq\varepsilon\cdot\nu(\cdot)\qquad\text{for all }x\in A. The regeneration time T and the chain (X_{t}) can be defined simultaneously on the same probability space as follows. First, run the chain until it reaches A at some time \tau_{A} . Suppose that X_{\tau_{A}}=a . Flip an (\varepsilon,1-\varepsilon) coin. If the result is \varepsilon , draw X_{\tau_{A}+1} from \nu and set T=\tau_{A}+1 . Otherwise, draw X_{\tau_{A}+1} from the remainder measure \frac{1}{1-\varepsilon}[\mathbf{P}(X_{t+1}\in\cdot\mid X_{t}=a)-\varepsilon\nu(\cdot)] and keep going. Every time that the chain reaches A , flip an independent (\varepsilon,1-\varepsilon) coin; if the result is \varepsilon , jump to \nu and set the value of T accordingly. As long as the chain almost surely visits A infinitely often, eventually the coin will show \varepsilon and the random time T will be defined. It is immediate from this description that T is a \nu -regeneration time. In fact, if we restart the algorithm after every regeneration, we obtain a sequence T_{1},T_{2},\ldots of \nu -regeneration times. It will be convenient to assume that the chain is started from X_{0}\sim\nu , so that we can define T_{0}=0 . Then, the sample path (X_{t})_{t\geq 0} is partitioned into iid tours (X_{t})_{T_{k-1}\leq t<T_{k}} with the property that each tour starts at a regeneration and ends just before the next regeneration. To apply the results of this paper for a particular Markov chain (X_{t}) , it is necessary to simulate (X_{t}) and identify the regeneration times. Finding an appropriate set A and measure \nu may be quite difficult. But, once A and \nu have been chosen, identifying the regeneration times is often straightforward [ 20 , 1 ] . (In particular, it is not necessary to compute the normalizing constant for \nu .) The requirement that X_{0}\sim\nu is easily satisfied: simply run the chain until the first regeneration and discard the previous samples. Our results require

Read the complete text