Introduction
Volume computation is a classical problem at the intersection of computational geometry, randomized algorithms, and approximate counting [12 , 17 , 22 , 9 ] . The challenge is to yield an estimate V ^ \widehat{V} V of the volume Vol ( K ) \operatorname{Vol}(K) Vol ( K ) of a convex body K ⊂ R n K \subset\mathbb{R}^{n} K ⊂ R n , when we have only sampling access to it. Exact volume computation is #P-hard even for a single polytope [12 , 17 ] . Thus, we retreat to randomized algorithms, and aim to yield an estimate V ^ \widehat{V} V that is an ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) -approximation of Vol ( K ) \operatorname{Vol}(K) Vol ( K ) , i.e.,
Pr [ ( 1 − ε ) Vol ( K ) ≤ V ^ ≤ ( 1 + ε ) Vol ( K ) ] ≥ 1 − δ , \Pr\left[(1-\varepsilon)\operatorname{Vol}(K) \le\widehat{V} \le(1+\varepsilon)\operatorname{Vol}(K)\right] \ge1-\delta, Pr [ ( 1 − ε ) Vol ( K ) ≤ V ≤ ( 1 + ε ) Vol ( K ) ] ≥ 1 − δ ,
for some ε > 0 \varepsilon> 0 ε > 0 and δ ∈ ( 0 , 1 ] \delta\in(0,1] δ ∈ ( 0 , 1 ] . In this direction, a celebrated line of work beginning with Dyer, Frieze, and Kannan [ [11 ] established polynomial-time randomized approximation algorithms for convex bodies. A unifying theme across this extensive line of work is the central role of random walks and Markov Chain Monte Carlo (MCMC) methods. Specifically, rapidly mixing random walks have emerged as the predominant algorithmic paradigm for both volume approximation and approximately uniform sampling from high-dimensional convex bodies. These developments have led to powerful techniques based on geometric random walks, approximate sampling, and rapidly mixing Markov chains. Most notably, the recent work of Cousins and Vempala [ [9 ] solves ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) -approximate volume computation of ( r , R ) (r,R) ( r , R ) -fat convex body1 in O ( n 3 R 2 / r 2 ) O(n^{3}R^{2}/r^{2}) O ( n 3 R 2 / r 2 ) by expanding upon the idea of generating sequences of interpolating convex bodies via resorting to Gaussian distributions: a technique referred to as Gaussian cooling.
In this paper, we take a step further, and study how to efficiently estimate the volume of a union of convex bodies with provable guarantees.
Problem 1 ((ε , δ \varepsilon,\delta ε , δ )-Union Volume Estimation). Given M M M convex bodies K 1 , … , K M ⊂ R n K_{1},\ldots,K_{M} \subset\mathbb{R}^{n} K 1 , … , K M ⊂ R n yield an estimate of the volume of their union
V : = Vol ( ⋃ i = 1 M K i ) V := \operatorname{Vol}\left(\bigcup_{i=1}^{M} K_i\right) V := Vol ( i = 1 ⋃ M K i ) within a multiplicative factor of 1 ± ε 1 \pm\varepsilon 1 ± ε , with probability at least 1 − δ 1-\delta 1 − δ .
Estimating the volume of a union of convex bodies presents additional difficulties. While each individual body is convex, their union need not be, and substantial overlaps can make the sum of the individual volumes a poor estimate of the volume of their union.
For discrete convex bodies, the Union Volume Estimation problem manifests to the enumeration of union size. Randomized approximation algorithms for union size, beginning with the classical work of Karp and Luby [ [15 ] , provide a natural framework for addressing this problem. Subsequent works [16 , 28 , 39 , 6 ] have extended this framework to realistic implementations with approximate size enumeration and sampling oracles. Thus, our central challenge is not proving only the existence of an efficient approximation algorithm, rather understanding which oracle guarantees suffice to provably solve the Union Volume Estimation problem, and how these guarantees can be realized efficiently for general convex bodies.
Motivations. Beyond its theoretical significance, the Union Volume Estimation problem naturally arises in automated reasoning and probabilistic verification [30 ] . If the convex bodies are axis-parallel hypercubes, the Union Volume Estimation reduces to the Klee’s measure problem, which was first proposed by Klee [ [18 ] in one dimension. Its multidimensional version is specifically useful for DNF (Disjunctive Normal Forms) counting and has been addressed by Meel et al. [ [29 ] , when one has access to ‘exact’ sampling and size enumeration oracles for each hypercube (known as a Delphic set). But the algorithms used in practice are deployed with approximate samplers [39 ] .
In a similar spirit, the satisfying assignments of a formula in Satisfiability Modulo Theories over Linear Real Arithmetic (SMT-LRA) can be represented as a union of convex polytopes. Estimating the volume of this union provides quantitative information about the space of satisfying assignments, with applications to reasoning about continuous systems. The recent work by Shaw et al. [ [38 ] introduced an algorithm for estimating the volume of regions represented by SMT-LRA formulas. The algorithm builds on randomized union-size estimation and demonstrates impressive empirical performance, significantly improving upon earlier approaches on the benchmarks considered. Their implementation uses, in the background, the volume and sampling oracles with sound theoretical guarantees assumed in their analysis. However none of these guarantees are retained in practice. In practice, the volume estimators (such as, discretize-and-count, Gaussian cooling [9 ] ) and geometric random walks (in particular, Hit-and-Run [25 ] )- run only up to a fixed walk length, since the walk lengths required by the theoretical guarantees are prohibitively long. Although these are natural and computationally effective choices, they do not satisfy the assumptions used in the analysis. This exposes a theory-to-practice gap in the Union Volume Estimation problem, which is not unique to the work of [38 ] but rather exhibited by any Union Volume Estimation algorithm using approximate samplers.
We aim to understand and algorithmically close this gap for general convex bodies that include all the aforementioned problems as special cases. To this end, we ask the following three questions.
Does an Union Volume Estimation algorithm with an approximate sampler and a PAC volume computation oracle fail to be ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) -approximate for certain sets of convex bodies?
Can we design a generic and efficient algorithmic framework that can incorporate the errors of the volume computation and approximate sampling oracles to provably yield an ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) -union volume estimate?
Can this algorithmic framework be computationally efficient, i.e. what are the time and sample complexities of this algorithmic framework when instantiated with well-known and computationally-efficient approximate volume computation algorithms, like Gaussian cooling, and approximate samplers, like Hit-and-Run?
Overview of the Contributions
By addressing the aforementioned questions, our work establishes a generic framework and the necessary properties of sampling and volume computation oracles to ensure the reliability of Union Volume Estimation algorithms when the idealized volume and uniform sampling oracles are replaced by computationally efficient approximations. The contributions are fivefold.
(C1) Characterizing the limitations due to efficient but approximate samplers
We investigate the efficiency-correctness dilemma encountered by the Union Volume Estimation algorithms. First, we show that the approximate sampling guarantees for each convex body in terms of TV-distance does not suffice to control the total error accumulated over the union of convex bodies (Theorem 3). TV-distance based guarantees control the overall discrepancy between two distributions, but do not ensure that their probability densities are multiplicatively close at every point. In Union Volume Estimation, the locations of sampled points matter crucially: samples lying in overlapping regions between multiple bodies are treated differently from those lying in regions belonging to only one body. Consequently, distributional errors may interact with the geometry of the input in ways that are not captured by the TV distance. Motivated by this geometric insight, we construct the sunflower family (Lemma 4), where every convex body is of same size with a common overlapping region and individual petals, and show that any Union Volume Estimation algorithm with TV-distance close sampler would fail to be correct in this sunflower family.
A Tail-sensitive Distance for Approximate Samplers
Instead of TV-distance close approximate samplers, if we focus on only using ℓ ∞ \ell_{\infty} ℓ ∞ -close approximate samplers, we can design correct Union Volume Estimation algorithm but that becomes too restrictive as most of the efficient samplers are not provably ℓ ∞ \ell_{\infty} ℓ ∞ -close (e.g. Hit-and-Run, Ball walk [14 ] , Billiard walk [34 ] ). We propose a new ( η , β ) (\eta,\beta) ( η , β ) -closeness measure to measure divergence between two distributions.
Definition 1 (( η , β ) ( \eta,\beta) ( η , β ) -closeness). Given a probability space ( S , π ) (S,\pi) ( S , π ) , and a distribution D \mathcal{D} D which is absolutely continuous with respect to the base measure π \pi π , let h : = d D d π h := \frac{\mathrm{d}\mathcal{D}}{\mathrm{d}\pi} h := d π d D denote its relative density. We call D \mathcal{D} D to be ( η , β ) (\eta,\beta) ( η , β ) -close to π \pi π , if we have
π ( B a d η ) ≤ β and D ( B a d η ) ≤ 2 β , where B a d η : = { x ∈ S : ∣ h ( x ) − 1 ∣ > η } , \pi(\mathrm{Bad}_{\eta}) \le\beta\text{ and } \mathcal{D}(\mathrm{Bad}_{\eta}) \le2\beta, \text{ where } \mathrm{Bad}_{\eta} := \{x \in S : |h(x)-1| > \eta\}, π ( Bad η ) ≤ β and D ( Bad η ) ≤ 2 β , where Bad η := { x ∈ S : ∣ h ( x ) − 1∣ > η } , for some ( η , β ) ∈ [ 0 , 1 ] 2 (\eta,\beta) \in[0,1]^2 ( η , β ) ∈ [ 0 , 1 ] 2 .
( 0 , 0 ) (0,0) ( 0 , 0 ) -closeness implies the distribution is exactly uniform, except possibly on a measure zero subset. The ( η , β ) (\eta,\beta) ( η , β ) -tailed samplers are the approximate samplers that generate samples exhibiting empirical distributions differing from uniform distribution by β \beta β , i.e. the support mass with ℓ ∞ \ell_{\infty} ℓ ∞ distance more than η \eta η . Informally, the ( η , β ) (\eta,\beta) ( η , β ) -tailed sampler produces samples whose density is multiplicatively close to the uniform density on a majority fraction of the set. Outside of this region (hereby referred as the exceptional region ), we have no information as to how the density behaves.
We prove that Hit-and-Run, which is known to be an efficient approximate sampler, yields ( η , β ) (\eta,\beta) ( η , β ) -close samples to uniform for any ( r , R ) (r,R) ( r , R ) -fat convex body in polynomial number of steps.
Lemma 1 (( η , β ) ( \eta,\beta) ( η , β ) -closeness of Hit-and-Run Samples, Informal version of Theorem 6). For any 1 > β , η > 0 1 > \beta,\eta> 0 1 > β , η > 0 , if Hit-and-Run is run on a ( r , R ) (r,R) ( r , R ) -fat convex body K ⊂ R n K \subset\mathbb{R}^n K ⊂ R n starting from any boundary point, we have π K ( B a d t , η ) ≤ β \pi_K(\mathrm{Bad}_{t,\eta}) \le\beta π K ( Bad t , η ) ≤ β if
t = ω ( poly ( n , R r , log 1 β , log 1 η ) ) . t = \omega\left(\operatorname{poly}\left(n,\frac{R}{r},\log\frac{1}{\beta},\log\frac{1}{\eta}\right)\right). t = ω ( poly ( n , r R , log β 1 , log η 1 ) ) . Here, π K \pi_K π K denotes the uniform distribution over K K K . Moreover, D t ( B a d t , η ) ≤ 2 β \mathcal{D}_t(\mathrm{Bad}_{t,\eta}) \le2\beta D t ( Bad t , η ) ≤ 2 β , i.e., a point sampled from D t \mathcal{D}_t D t has density ( 1 ± η ) (1 \pm\eta) ( 1 ± η ) close to that of π \pi π with probability at least 1 − 2 β 1-2\beta 1 − 2 β .
Designing a correct and efficient framework for Union Volume Estimation
Now, we propose a provably correct algorithmic framework, Alpona , for Union Volume Estimation that access two oracles: (i) a PAC (Probably Approximately Correct) volume estimator for each convex body, and (ii) an ( η , β ) (\eta,\beta) ( η , β ) -tailed sampler. Under appropriate choices of the oracle parameters, Alpona returns a multiplicative approximation to the union volume with high probability.
Theorem 2 (Informal version of Theorem 7). Let K 1 , … , K M ⊂ R n K_1,\ldots,K_M \subset\mathbb{R}^n K 1 , … , K M ⊂ R n be convex bodies satisfying the geometric assumptions required by the PAC volume estimation and approximate sampling oracles. For every ε , δ ∈ ( 0 , 1 ) \varepsilon,\delta\in(0,1) ε , δ ∈ ( 0 , 1 ) , there is a randomized algorithm Alpona that, using PAC volume estimators and ( η , β ) (\eta,\beta) ( η , β ) -tailed samplers, outputs an estimate V ^ \widehat{V} V satisfying
Pr [ ( 1 − ε ) V ≤ V ^ ≤ ( 1 + ε ) V ] ≥ 1 − δ , \Pr\left[(1-\varepsilon)V \le\widehat{V} \le(1+\varepsilon)V\right] \ge1-\delta, Pr [ ( 1 − ε ) V ≤ V ≤ ( 1 + ε ) V ] ≥ 1 − δ , where V : = Vol ( ⋃ i = 1 M K i ) V := \operatorname{Vol}\left(\bigcup_{i=1}^{M} K_i\right) V := Vol ( ⋃ i = 1 M K i ) . Alpona requires O ( M ) O(M) O ( M ) calls to the PAC volume estimation oracle and O ~ ( M / ε 2 ) \widetilde{O}(M/\varepsilon^2) O ( M / ε 2 ) calls to ( η , β ) (\eta,\beta) ( η , β ) -tailed samplers.
The algorithm is a adaptive sampling based algorithm that aims to retain a Poisson number of representative points from each body proportional to its estimated volume. The main technical challenge is to analyse the interaction between three sources of uncertainty: errors in volume estimation, non-uniformity in the sampling distributions, and adaptive changes in the sampling intensity. Our analysis separates the regions where the sampling density is approximately uniform from the exceptional regions where this guarantee may fail. The former contribute a controlled approximation to the union volume, while the contribution from the latter is bounded using their small measure and sampling probability. Together with concentration arguments for the sampling procedure, this establishes the correctness guarantee.
Connecting geometric sampling guarantees to implementable algorithms
Finally, we propose a practically efficient instantiation of Alpona with Hit-and-Run as ( η , β ) (\eta,\beta) ( η , β ) -tailed approximate sampler and Gaussian cooling as the PAC volume estimator. We show that space and time complexity of this algorithm are
O ~ ( n ε 2 log M δ ) , and O ~ ( M max { n 3 , n 2 ( R / r ) 2 } ε 2 ) . \widetilde{O}\left(\frac{n}{\varepsilon^2}\log\frac{M}{\delta}\right),\text{ and }\widetilde{O}\left(M\frac{\max\left\{n^3,n^2(R/r)^2\right\}}{\varepsilon^2}\right). O ( ε 2 n log δ M ) , and O ( M ε 2 max { n 3 , n 2 ( R / r ) 2 } ) .
The resulting complexity analysis separates the number of oracle calls made by the main algorithm from the cost of implementing each oracle. This distinction is important: the number of bodies affects both the number of operations and the accuracy parameters required by the subroutines, while the geometry of each body influences the complexity of the individual approximate volume computation and sampling queries. Thus, the analysis provides a quantitative connection between the desired approximation guarantee, the number of convex bodies, their geometric parameters, and the computational resources required by the implementation.
In this process, we derive in Theorem 21 an improved walk length that Hit-and-Run needs to take to generate an ( η , β ) (\eta,\beta) ( η , β ) -close sample is O ~ ( n 3 R 2 r 2 ) \widetilde{O}\left(n^3\frac{R^2}{r^2}\right) O ( n 3 r 2 R 2 ) from O ~ ( n 4 R 2 r 2 ) \widetilde{O}\left(n^4\frac{R^2}{r^2}\right) O ( n 4 r 2 R 2 ) [Lovász and Vempala, 2006]. The proof passes through two geometric claims:
For any 0 < η , β < 1 0<\eta,\beta<1 0 < η , β < 1 , Hit-and-Run taking at least
1 + n 2 + O ( n log ( 32 R / d ) + log ( 1 / ( η 2 β ) ) γ H R ) 1+\frac{n}{2}+O\left(\frac{n\log(32R/d)+\log(1/(\eta^2\beta))}{\gamma_{\mathrm{HR}}}\right) 1 + 2 n + O ( γ HR n log ( 32 R / d ) + log ( 1/ ( η 2 β )) )
suffices to guarantee that π ( B a d t , η ) ≤ β \pi(\mathrm{Bad}_{t,\eta})\le\beta π ( Bad t , η ) ≤ β and D t ( B a d t , η ) ≤ 2 β \mathcal{D}_t(\mathrm{Bad}_{t,\eta})\le2\beta D t ( Bad t , η ) ≤ 2 β , where γ H R \gamma_{\mathrm{HR}} γ HR is the spectral gap for Hit-and-Run.
We show contraction of Hit-and-Run’s sampling operator P P P for functions f f f with mean 0 0 0 :
∥ P s f ∥ L 2 ( π ) ≤ e − γ H R s ∥ f ∥ 2 , \left\|P^s f\right\|_{L_2(\pi)} \le e^{-\gamma_{\mathrm{HR}}s}\|f\|_2, ∥ P s f ∥ L 2 ( π ) ≤ e − γ HR s ∥ f ∥ 2 ,
for s > 1 + n 2 s>1+\frac{n}{2} s > 1 + 2 n .
(C5) Bounded Frequency Streams. Till now, we have worked with a pre-fixed number of convex bodies M M M . But we can adapt Alpona further to streams of convex bodies with bounded frequency. Here, a bounded frequency stream of convex bodies means that each point of the union of these bodies has a bounded frequency 1 ≤ τ ≤ M 1 \le\tau\le M 1 ≤ τ ≤ M . In this case, we show Theorem 23 that time and space complexities of Alpona will be dependent on the frequency τ \tau τ instead of M M M .
Organisation. Rest of the paper is organised as follows: in § 2 , we demonstrate and highlight the weakness in sampling from distributions with only TV-control. In § 3 , we propose the notion of tail-controlled distributions and discuss its properties. The paper’s algorithmic contribution is described in § 4 , which also includes a short discussion on the related works. Correctness of the algorithm and it’s complexity requirements are discussed in § 5 and in § 6 respectively. We cover the special case of sparse streams in § 7 . We finally conclude in § 8 .
From Worst-Case Sampling Guarantees to Practical Performance
Estimating the volume of a union of convex bodies from approximate samples presents a subtle difficulty: a small sampling error for each body need not translate into a small error for the union. We first demonstrate this limitation through a sunflower construction. We then examine its relevance to the practical algorithm of Shaw et al. [ [38 ] . Although adversarial sampling errors can cause substantial failures, the practical performance of their algorithm is often considerably better than this pessimistic scenario suggests. Understanding this discrepancy motivates our study of more informative sampling guarantees.
A Fundamental Limitation of Approximate Sampling
Suppose an estimator has sampling-oracle access to convex bodies K 1 , … , K M K_1,\ldots,K_M K 1 , … , K M . Denote by π i \pi_i π i the uniform distribution on K i K_i K i . For each i i i , the oracle returns independent samples from a distribution D i D_i D i satisfying ∥ D i − π i ∥ 1 ≤ θ \lVert D_i-\pi_i\rVert_1 \le\theta ∥ D i − π i ∥ 1 ≤ θ . We ask whether this assumption alone suffices for reliable estimation of the union volume. The following theorem gives a negative answer in the sampling-only oracle model. Here, ∥ ⋅ ∥ 1 \lVert\cdot\rVert_1 ∥ ⋅ ∥ 1 denotes the ℓ 1 \ell_1 ℓ 1 distance between probability distributions, which is twice their TV distance.
Theorem 3 (Limitations of approximate sampling). Fix ε , θ ∈ ( 0 , 1 ) \varepsilon,\theta\in(0,1) ε , θ ∈ ( 0 , 1 ) , and let A \mathcal{A} A be any randomized algorithm whose access to the input convex bodies is restricted to the following oracles:
∥ D i − π i ∥ 1 ≤ θ . \lVert D_i-\pi_i\rVert_1 \le\theta. ∥ D i − π i ∥ 1 ≤ θ . Then there exists an instance consisting of K = O ε ( 1 / θ ) K = O_{\varepsilon}(1/\theta) K = O ε ( 1/ θ ) convex bodies, together with oracles satisfying the above guarantees, on which A \mathcal{A} A fails to return a ( 1 ± ε ) (1\pm\varepsilon) ( 1 ± ε ) -approximation to the volume of their union with probability at least 1 / 2 1/2 1/2 .
Proof. Let a = θ / ( 2 − θ ) ∈ ( 0 , 1 ) a = \theta/(2-\theta) \in(0,1) a = θ / ( 2 − θ ) ∈ ( 0 , 1 ) . By Lemma 4 (proved later), there exist M M M convex bodies K 1 , … , K M ⊆ R M − 1 K_1,\ldots,K_M \subseteq\mathbb{R}^{M-1} K 1 , … , K M ⊆ R M − 1 forming a sunflower family with common core K ∩ K_{\cap} K ∩ and pairwise disjoint petals C 1 , … , C M C_1,\ldots,C_M C 1 , … , C M , such that
K i : = K ∩ ⊔ C i , Vol ( C i ) : = a Vol ( K ∩ ) . K_i := K_{\cap} \sqcup C_i,\qquad\operatorname{Vol}(C_i) := a\operatorname{Vol}(K_{\cap}). K i := K ∩ ⊔ C i , Vol ( C i ) := a Vol ( K ∩ ) .
Write V ∩ = Vol ( K ∩ ) > 0 V_{\cap} = \operatorname{Vol}(K_{\cap}) > 0 V ∩ = Vol ( K ∩ ) > 0 .
For each i i i , define the sampling distribution D i = π K ∩ D_i = \pi_{K_{\cap}} D i = π K ∩ . Thus, the sampler returns uniformly random points from the common core K ∩ K_{\cap} K ∩ and never samples from the petals. Then:
∥ D i − π i ∥ 1 = ∫ K ∩ ∣ 1 V ∩ − 1 ( 1 + a ) V ∩ ∣ d x + ∫ C i d x ( 1 + a ) V ∩ = 2 a 1 + a = θ . \lVert D_i-\pi_i\rVert_1 = \int_{K_{\cap}}\left|\frac{1}{V_{\cap}}-\frac{1}{(1+a)V_{\cap}}\right|\,dx+\int_{C_i}\frac{dx}{(1+a)V_{\cap}}
= \frac{2a}{1+a}=\theta. ∥ D i − π i ∥ 1 = ∫ K ∩ V ∩ 1 − ( 1 + a ) V ∩ 1 d x + ∫ C i ( 1 + a ) V ∩ d x = 1 + a 2 a = θ .
Hence, every sampling oracle satisfies the required ℓ 1 \ell_1 ℓ 1 -accuracy guarantee, despite completely ignoring its petal.
Next, let the volume oracle for every body return the value V ∩ V_{\cap} V ∩ . This is a valid ( 1 ± θ ) (1\pm\theta) ( 1 ± θ ) -factor approximation of the corresponding volumes since
( 1 − θ ) Vol ( K i ) = ( 1 − θ ) ( 1 + a ) V ∩ = 2 ( 1 − θ ) 2 − θ V ∩ ≤ V ∩ ≤ ( 1 + θ ) Vol ( K i ) . (1-\theta)\operatorname{Vol}(K_i)=(1-\theta)(1+a)V_{\cap}
=\frac{2(1-\theta)}{2-\theta}V_{\cap}\leq V_{\cap}\leq(1+\theta)\operatorname{Vol}(K_i). ( 1 − θ ) Vol ( K i ) = ( 1 − θ ) ( 1 + a ) V ∩ = 2 − θ 2 ( 1 − θ ) V ∩ ≤ V ∩ ≤ ( 1 + θ ) Vol ( K i ) .
Now consider a second instance consisting of M M M identical copies of the core K ∩ K_{\cap} K ∩ , each equipped with an exact uniform sampling oracle and an exact volume oracle returning V ∩ V_{\cap} V ∩ .
The two instances are indistinguishable to A \mathcal{A} A : in both cases, every sampling oracle returns independent uniform samples from K ∩ K_{\cap} K ∩ , and every volume oracle returns V ∩ V_{\cap} V ∩ . Consequently, the complete oracle transcripts, and hence, the output distributions of A \mathcal{A} A are identical on the two instances, regardless of the number of adaptive oracle queries.
However, the union volumes of the two instances differ. For the second instance, the union volume is V 0 = V ∩ V_0=V_{\cap} V 0 = V ∩ , whereas for the sunflower instance,
V 1 = V ∩ + ∑ i = 1 M Vol ( C i ) = V ∩ ( 1 + M a ) . V_1=V_{\cap}+\sum_{i=1}^{M}\operatorname{Vol}(C_i)=V_{\cap}(1+Ma). V 1 = V ∩ + i = 1 ∑ M Vol ( C i ) = V ∩ ( 1 + M a ) .
Choose an integer M M M satisfying
M > 2 ε ( 1 − ε ) a = 2 ε ( 2 − θ ) ( 1 − ε ) θ . M>\frac{2\varepsilon}{(1-\varepsilon)a}=\frac{2\varepsilon(2-\theta)}{(1-\varepsilon)\theta}. M > ( 1 − ε ) a 2 ε = ( 1 − ε ) θ 2 ε ( 2 − θ ) .
Then,
( 1 − ε ) V 1 > ( 1 + ε ) V 0 , (1-\varepsilon)V_1>(1+\varepsilon)V_0, ( 1 − ε ) V 1 > ( 1 + ε ) V 0 ,
so the intervals of valid ( 1 ± ε ) (1\pm\varepsilon) ( 1 ± ε ) -approximations to V 0 V_0 V 0 and V 1 V_1 V 1 are disjoint.
Since A \mathcal{A} A has identical output distributions on the two instances, the sum of its success probabilities on these instances is at most one. Therefore, A \mathcal{A} A must fail with probability at least 1 / 2 1/2 1/2 on at least one of them.
Finally, for every fixed ε \varepsilon ε , the above choice of M M M satisfies M = O ε ( 1 / θ ) M=O_{\varepsilon}(1/\theta) M = O ε ( 1/ θ ) , completing the proof. □ \square □
Now, we construct a specific family of convex bodies, namely sunflower families, where the union volume estimator A \mathcal{A} A fails to yield an ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) -estimate.
Lemma 4 (Existence of convex sunflower families). For every integer M ≥ 2 M \ge2 M ≥ 2 and every a ∈ ( 0 , 1 ) a \in(0,1) a ∈ ( 0 , 1 ) , there exist M M M full-dimensional convex polytopes K 1 , … , K M ⊆ R M − 1 K_1,\ldots,K_M \subseteq\mathbb{R}^{M-1} K 1 , … , K M ⊆ R M − 1 and a convex body K K K of positive volume such that, writing C i : = K i ∖ K C_i := K_i \setminus K C i := K i ∖ K , we have
K i = K ∪ C i , Vol ( C i ) = a Vol ( K ) for every i ∈ [ M ] , K_i = K \cup C_i,\qquad\operatorname{Vol}(C_i) = a\operatorname{Vol}(K)\quad\text{for every }i \in[M], K i = K ∪ C i , Vol ( C i ) = a Vol ( K ) for every i ∈ [ M ] , and the petals C 1 , … , C M C_1,\ldots,C_M C 1 , … , C M are pairwise disjoint.
Proof. Let n : = M − 1 n := M - 1 n := M − 1 , and let K ⊆ R n K \subseteq\mathbb{R}^n K ⊆ R n be a regular n n n -dimensional simplex with vertices v 1 , … , v M v_1,\ldots,v_M v 1 , … , v M . For each i ∈ [ M ] i \in[M] i ∈ [ M ] , let F i F_i F i be the facet opposite to v i v_i v i , and let z i z_i z i denote the centroid of F i F_i F i . By symmetry, the segment joining v i v_i v i to z i z_i z i is perpendicular to F i F_i F i , and its length h > 0 h > 0 h > 0 is independent of i i i . Let us define
w i : = z i + a ( z i − v i ) w_i := z_i + a(z_i-v_i) w i := z i + a ( z i − v i ) and
K i : = conv ( K ∪ { w i } ) . K_i := \operatorname{conv}(K \cup\{w_i\}). K i := conv ( K ∪ { w i }) . We claim that K i K_i K i is obtained by attaching the pyramid
P i : = conv ( F i ∪ { w i } ) P_i := \operatorname{conv}(F_i \cup\{w_i\}) P i := conv ( F i ∪ { w i }) to K K K along the facet F i F_i F i . To see this, consider the barycentric coordinates of w i w_i w i with respect to v 1 , … , v M v_1,\ldots,v_M v 1 , … , v M . Since
z i = 1 M − 1 ∑ j ≠ i v j z_i = \frac{1}{M-1}\sum_{j\ne i}v_j z i = M − 1 1 j = i ∑ v j we have
w i = − a v i + 1 + a M − 1 ∑ j ≠ i v j . w_i = -av_i + \frac{1+a}{M-1}\sum_{j\ne i}v_j. w i = − a v i + M − 1 1 + a j = i ∑ v j . Thus, the barycentric coordinate corresponding to v i v_i v i is negative, whereas all the remaining coordinates are positive. Consequently, w i w_i w i lies strictly beyond F i F_i F i but satisfies all the other facet-defining inequalities of K K K . It follows that
K i = K ∪ P i , K ∩ P i = F i . K_i = K \cup P_i,\qquad K \cap P_i = F_i. K i = K ∪ P i , K ∩ P i = F i . Moreover, every point of P i ∖ K P_i \setminus K P i ∖ K violates the facet inequality corresponding to F i F_i F i , while satisfying all the other facet inequalities. Hence
( P i ∖ K ) ∩ ( P j ∖ K ) = ∅ for i ≠ j . (P_i \setminus K) \cap(P_j \setminus K) = \varnothing\qquad\text{for }i \ne j. ( P i ∖ K ) ∩ ( P j ∖ K ) = ∅ for i = j . It remains to verify the volumes. Let A A A denote the common ( n − 1 ) (n-1) ( n − 1 ) -dimensional volume of the facets of K K K . Since K K K has altitude h h h over each facet,
Vol ( K ) = A h n . \operatorname{Vol}(K) = \frac{Ah}{n}. Vol ( K ) = n A h . The pyramid P i P_i P i has base F i F_i F i and altitude a h ah ah , giving
Vol ( P i ) = A ( a h ) n = a Vol ( K ) . \operatorname{Vol}(P_i) = \frac{A(ah)}{n} = a\operatorname{Vol}(K). Vol ( P i ) = n A ( ah ) = a Vol ( K ) . Taking C i = P i ∖ K C_i = P_i \setminus K C i = P i ∖ K , we obtain
Vol ( C i ) = a Vol ( K ) \operatorname{Vol}(C_i) = a\operatorname{Vol}(K) Vol ( C i ) = a Vol ( K ) for every i ∈ [ M ] i \in[M] i ∈ [ M ] . Since the petals are pairwise disjoint, the desired sunflower family follows.
Beyond Worst-Case Sampling Guarantees
While the preceding theorem establishes that any algorithm A \mathcal{A} A can fail on a worst-case instance involving only O ( 1 / θ ) O(1/\theta) O ( 1/ θ ) convex bodies, practical algorithms often perform considerably well. This discrepancy raises a natural question: is this limitation inherent to approximate sampling, or does it arise from the overly pessimistic assumptions underlying the worst-case analysis? To understand this discrepancy, we take a closer look at the behavior of practical sampling procedures.
The lower bound via sunflower construction relies on highly adversarial samplers that sample uniformly from a common core while completely ignoring the remaining regions of the bodies. However, practical geometric samplers, such as those based on Hit-and-Run random walks, need not exhibit such extreme behavior. Instead, we expect their sampling distributions to be much closer to uniform over most of the body, with significant deviations potentially concentrated in regions that are harder to explore. In particular, rather than assuming only an ℓ 1 \ell_1 ℓ 1 -distance guarantee, it may be more appropriate to seek a multiplicative ℓ ∞ \ell_\infty ℓ ∞ guarantee over a large portion of the body.
More precisely, for a convex body K i K_i K i with uniform density π i \pi_i π i , we seek a measurable good region G i ⊆ K i G_i \subseteq K_i G i ⊆ K i satisfying
Vol ( K i ∖ G i ) ≤ β i Vol ( K i ) , \operatorname{Vol}(K_i \setminus G_i) \leq\beta_i \operatorname{Vol}(K_i), Vol ( K i ∖ G i ) ≤ β i Vol ( K i ) ,
such that the sampling distribution D i D_i D i satisfies
( 1 − η i ) π i ( x ) ≤ D i ( x ) ≤ ( 1 + η i ) π i ( x ) for almost every x ∈ G i . (1-\eta_i)\pi_i(x) \leq D_i(x) \leq(1+\eta_i)\pi_i(x) \qquad\text{for almost every } x \in G_i. ( 1 − η i ) π i ( x ) ≤ D i ( x ) ≤ ( 1 + η i ) π i ( x ) for almost every x ∈ G i .
Here, η i \eta_i η i measures the multiplicative distortion of the sampling density over the good region, while β i \beta_i β i measures the relative volume of the exceptional region. This provides a more refined description of sampling quality than a global ℓ 1 \ell_1 ℓ 1 -distance bound.
A second important consideration is the geometry of the underlying convex bodies. The accuracy of a practical sampler is influenced by how easily it can explore different regions of the body, which in turn depends on its geometric conditioning. In particular, the ratio R i / r i R_i/r_i R i / r i , where R i R_i R i and r i r_i r i are the radii of suitable enclosing and enclosed balls, can affect the convergence of random-walk-based samplers. Poorly conditioned bodies, with large R i / r i R_i/r_i R i / r i , may contain long or thin regions that are more difficult to explore accurately.
These observations suggest two complementary ways to understand and potentially overcome the pessimism of the worst-case bound. One possibility is to require more accurate samplers as the number of bodies grows. Indeed, the sunflower construction suggests that an ℓ 1 \ell_1 ℓ 1 -accuracy of order O ( ε / m ) O(\varepsilon/m) O ( ε / m ) is a natural conservative target for controlling the accumulation of sampling errors. However, achieving such accuracy may significantly increase the computational cost.
An alternative is to exploit the more favorable behavior of practical samplers by incorporating multiplicative approximation guarantees over large good regions, together with geometric information about the bodies. Such guarantees may provide a more realistic characterization of sampling quality without requiring uniformly stringent ℓ 1 \ell_1 ℓ 1 -accuracy.
The Gap between Worst-case Guarantees and in Practice
The algorithm of Shaw et al. [ [38 ] , namely ttc, provides a useful case study. It estimates volumes of regions represented by SMT-LRA formulas, building on the Delphic-set framework for union-size estimation Meel et al. [ [29 ] . At a high level, ttc combines approximate individual-volume estimates with samples from the constituent convex bodies. Its adaptive, Poisson-based representative-sampling procedure maintains a bounded bucket of sampled points and adjusts the sampling rate as the bodies are processed. The theoretical analysis requires sufficiently accurate sampling oracles; its practical implementation uses geometric random walks, notably Hit-and-Run, with much shorter walks than conservative worst-case mixing analyses may prescribe.
Despite this compromise, ttc exhibits strong empirical performance on previously considered benchmarks. This raises the following genuine question: what are the properties of a benchmark that influence the corresponding empirical performances? We investigate this question by proposing two families of geometric benchmarks, designed to stress the samplers in the backend, but in different ways:
Boxes benchmark. Each instance is a union of axis-aligned boxes. By varying their widths, we control the geometric aspect ratio max i R i / r i \max_i R_i/r_i max i R i / r i , where R i R_i R i and r i r_i r i denote circumscribed and inscribed radii. Thin bodies can make accurate sampling more challenging.
Sunflower benchmark. Each instance consists of M M M convex bodies arranged around a common core. Increasing M M M creates more distinct petal regions, making it possible for sampling biases to accumulate across bodies.
We constructed 26 boxes instances and 20 sunflower instances. Figure 1 illustrates representative examples.
Figure 1. Illustrations of Boxes and Sunflower Family Benchmarks.
Observed estimation errors. For each benchmark, we run ttc with Hit-and-Run walk length fixed at 1000 n 1000n 1000 n , following the implementation of Shaw et al. [ [38 ] . We measure relative error ∣ V ^ − V ∣ / V |\widehat{V}-V|/V ∣ V − V ∣/ V , where V V V is the true union volume. As shown in Figure 2 , error tends to increase with the aspect ratio in the boxes benchmark and with the number of petals in the sunflower benchmark. On some instances, the observed error exceeds the target 0.2. Thus, a walk length fixed independently of the input geometry cannot be assumed sufficient for every instance.
Figure 2. Observed relative error of the volume estimate returned by ttc on each benchmark, with the Hit-and-Run walk length fixed to 1000 n 1000n 1000 n , where n n n is the dimension of the instance. The shaded region marks the target relative error of at most 0.2. The boxes benchmarks are arranged in increasing order of max i R i / r i \max_i R_i/r_i max i R i / r i with median reported for benchmarks with same max i R i / r i \max_i R_i/r_i max i R i / r i , and the sunflower benchmarks in increasing order of number of bodies M M M .
Crucially, however, these failures do not mean that the extreme sunflower samplers accurately model the usual behavior of Hit-and-Run. The lower bound allows a sampler to ignore every petal completely, whereas practical random walks may explore such regions imperfectly but still with appreciable probability. The experiments therefore support a more nuanced conclusion: the theoretical vulnerability is real, yet the worst-case ℓ 1 \ell_1 ℓ 1 model can be far more pessimistic than the behavior of the sampler actually used by ttc.
Towards Geometry-aware, Multiplicative Sampling Guarantees
The lesson is not that approximate sampling is inherently unsuitable for union-volume estimation, nor that the empirical success of ttc supplies a correctness guarantee. Rather, ℓ 1 \ell_1 ℓ 1 closeness alone fails to distinguish between benign sampling errors and errors concentrated in precisely those regions that matter most to the union. A useful theory should capture additional properties of practical samplers and translate them into guarantees for the final volume estimate.
This leads to the question driving our work:
Can we exploit multiplicative near-uniformity on a large good region, together with quantitative control of the exceptional region, to obtain provable union-volume estimates?
We seek guarantees that explicitly account for the number of bodies and their geometric conditioning, rather than treating all samplers within a given ℓ 1 \ell_1 ℓ 1 ball as equally representative of practice. The experiments above test precisely these two sources of difficulty: accumulation as m m m grows and deterioration of sampling quality as R / r R/r R / r grows.
Tail-Controlled Approximate Sampling
The preceding section shows that small sampling error for each convex body need not translate into a reliable estimate of their union volume: errors concentrated in geometrically significant regions may accumulate across bodies. Requiring multiplicative closeness to uniformity everywhere would rule out this behavior, but is stronger than what the analysis needs. We instead allow the sampling density to deviate arbitrarily on a small exceptional region (which are essentially tails of this distribution, hence the term Tail-Controlled ), while controlling its multiplicative distortion elsewhere. We first formalize this guarantee, compare it with standard ℓ 1 \ell_1 ℓ 1 and ℓ ∞ \ell_\infty ℓ ∞ notions, and then discuss its realization through Hit-and-Run.
Almost-ℓ ∞ \ell_\infty ℓ ∞ closeness
Let ( S , F , π ) (S,\mathcal{F},\pi) ( S , F , π ) be a probability space and let D \mathcal{D} D be another probability distribution on S S S , absolutely continuous with respect to π \pi π . Write
h ( x ) : = d D d π ( x ) h(x) := \frac{\mathrm{d}\mathcal{D}}{\mathrm{d}\pi}(x) h ( x ) := d π d D ( x )
for the relative density of D \mathcal{D} D with respect to π \pi π .
For η ∈ ( 0 , 1 ) \eta\in(0,1) η ∈ ( 0 , 1 ) , define the exceptional region
Bad η ( D , π ) : = { x ∈ S : ∣ h ( x ) − 1 ∣ > η } . (1) \operatorname{Bad}_{\eta}(\mathcal{D},\pi) := \{x \in S : |h(x)-1| > \eta\}. \tag*{(1)} Bad η ( D , π ) := { x ∈ S : ∣ h ( x ) − 1∣ > η } . (1)
Outside this region, the sampling distribution satisfies
1 − η ≤ h ( x ) ≤ 1 + η . 1-\eta\le h(x) \le1+\eta. 1 − η ≤ h ( x ) ≤ 1 + η .
Thus, h h h is multiplicatively close to 1 outside Bad η ( D , π ) \operatorname{Bad}_{\eta}(\mathcal{D},\pi) Bad η ( D , π ) .
Definition 2 ((η , β \eta,\beta η , β )-almost-ℓ ∞ \ell_\infty ℓ ∞ closeness). For η , β ∈ ( 0 , 1 ) \eta,\beta\in(0,1) η , β ∈ ( 0 , 1 ) , we say that D \mathcal{D} D is ( η , β ) (\eta,\beta) ( η , β ) -almost-ℓ ∞ \ell_\infty ℓ ∞ -close to π \pi π if
π ( Bad η ( D , π ) ) ≤ β and D ( Bad η ( D , π ) ) ≤ 2 β . \pi(\operatorname{Bad}_{\eta}(\mathcal{D},\pi)) \le\beta
\qquad\text{and}\qquad
\mathcal{D}(\operatorname{Bad}_{\eta}(\mathcal{D},\pi)) \le2\beta. π ( Bad η ( D , π )) ≤ β and D ( Bad η ( D , π )) ≤ 2 β . When it is clear from context, we shall defer to D \mathcal{D} D simply as a distribution which is ( η , β ) (\eta,\beta) ( η , β ) -close to π \pi π .
The two parameters capture distinct aspects of sampling accuracy. The parameter η \eta η bounds the multiplicative distortion of the density outside the exceptional region, while β \beta β controls the size of this exceptional region.
In particular, if G = S ∖ Bad η ( D , π ) G = S \setminus\operatorname{Bad}_{\eta}(\mathcal{D},\pi) G = S ∖ Bad η ( D , π ) , then for every measurable A ⊆ G A \subseteq G A ⊆ G ,
( 1 − η ) π ( A ) ≤ D ( A ) ≤ ( 1 + η ) π ( A ) . (1-\eta)\pi(A) \le\mathcal{D}(A) \le(1+\eta)\pi(A). ( 1 − η ) π ( A ) ≤ D ( A ) ≤ ( 1 + η ) π ( A ) .
No pointwise density guarantee is imposed on the exceptional region, but its probability mass is controlled, under both the target distribution and the sampling distribution.
Relevance to union-volume estimation. Consider convex bodies K 1 , … , K M ⊆ R n K_1,\ldots,K_M \subseteq\mathbb{R}^n K 1 , … , K M ⊆ R n . Let π i \pi_i π i denote the uniform distribution on K i K_i K i , and suppose the sampling distribution D i \mathcal{D}_i D i is ( η , β ) (\eta,\beta) ( η , β ) -almost-ℓ ∞ \ell_\infty ℓ ∞ -close to π i \pi_i π i .
Write B i = Bad η ( D i , π i ) B_i = \operatorname{Bad}_{\eta}(\mathcal{D}_i,\pi_i) B i = Bad η ( D i , π i ) . Since π i \pi_i π i is uniform on K i K_i K i ,
Vol ( B i ) ≤ β Vol ( K i ) . \operatorname{Vol}(B_i) \le\beta\operatorname{Vol}(K_i). Vol ( B i ) ≤ β Vol ( K i ) .
Consequently,
Vol ( ⋃ i = 1 M B i ) ≤ β ∑ i = 1 M Vol ( K i ) ≤ M β V , \operatorname{Vol}\left(\bigcup_{i=1}^{M} B_i\right)
\le\beta\sum_{i=1}^{M}\operatorname{Vol}(K_i)
\le M\beta V, Vol ( i = 1 ⋃ M B i ) ≤ β i = 1 ∑ M Vol ( K i ) ≤ M β V ,
where
V = Vol ( ⋃ i = 1 M K i ) . V = \operatorname{Vol}\left(\bigcup_{i=1}^{M} K_i\right). V = Vol ( i = 1 ⋃ M K i ) .
Thus, the natural parameter regime for an ε \varepsilon ε -relative approximation is η = Θ ( ε ) \eta= \Theta(\varepsilon) η = Θ ( ε ) and β = Θ ( ε / M ) \beta= \Theta(\varepsilon/M) β = Θ ( ε / M ) , with sufficiently small absolute constants. The latter makes the exceptional regions occupy at most an O ( ε ) O(\varepsilon) O ( ε ) fraction of the union, while the former bounds the multiplicative distortion on their complements. For constant ε \varepsilon ε , these become η = Θ ( 1 ) \eta= \Theta(1) η = Θ ( 1 ) and β = Θ ( 1 / M ) \beta= \Theta(1/M) β = Θ ( 1/ M ) .
These observations motivate the sampling guarantees used by our algorithm. The formal correctness analysis, including the effect of approximate individual-volume estimates, is given in § 5 .
Obtaining Tail-Controlled Guarantees for Hit-and-Run
We now turn to the question of whether the almost-ℓ ∞ \ell_\infty ℓ ∞ guarantees required by our framework can be realized efficiently using geometric random walks. We focus on the classical Hit-and-Run algorithm [25 ] , a widely used Markov chain Monte Carlo method for approximately uniform sampling from convex bodies.
Let K ⊆ R n K \subseteq\mathbb{R}^n K ⊆ R n be a convex body, and let π \pi π denote the uniform distribution on K K K . Starting from a point x 0 ∈ K x_0 \in K x 0 ∈ K , Hit-and-Run generates a Markov chain ( X t ) t ≥ 0 (X_t)_{t\geq0} ( X t ) t ≥ 0 as follows. At each step, it chooses a direction u \mathbf{u} u uniformly at random from the unit sphere S n − 1 \mathbb{S}^{n-1} S n − 1 and selects X t + 1 X_{t+1} X t + 1 uniformly from the chord
C K ( X t , u ) : = K ∩ { X t + s u : s ∈ R } . C_K(X_t,\mathbf{u}) := K \cap\{X_t + s\mathbf{u} : s \in\mathbb{R}\}. C K ( X t , u ) := K ∩ { X t + s u : s ∈ R } .
Let D t D_t D t denote the distribution of X t X_t X t . The uniform distribution π \pi π is stationary for this chain, and classical mixing-time results establish rapid convergence to π \pi π under suitable geometric and initialization assumptions.
Our interest, however, is in obtaining the particular sampling guarantee required for union-volume estimation. In view of the discussion in Section B.1, the central question is the following:
Question 1. For η = Θ ( ε ) \eta= \Theta(\varepsilon) η = Θ ( ε ) and β = Θ ( ε / M ) \beta= \Theta(\varepsilon/M) β = Θ ( ε / M ) , how many Hit-and-Run steps suffice to ensure that D t D_t D t is ( η , β ) (\eta,\beta) ( η , β ) -almost-ℓ ∞ \ell_\infty ℓ ∞ -close to π \pi π ?
Suppose that K K K contains a Euclidean ball of radius r r r and is contained in a Euclidean ball of radius R R R . Assume further that the initial point x 0 x_0 x 0 is at distance at least d 0 > 0 d_0 > 0 d 0 > 0 from the boundary of K K K .
Corollary 5 (Tail-controlled Hit-and-Run). Under the preceding assumptions, Hit-and-Run produces an ( η , β ) (\eta,\beta) ( η , β ) -almost-ℓ ∞ \ell_\infty ℓ ∞ -close distribution to π \pi π after
O ( n 3 R 2 r 2 log ( R d 0 η β ) ) \mathcal{O}\left(n^3 \frac{R^2}{r^2}\log\left(\frac{R}{d_0\eta\beta}\right)\right) O ( n 3 r 2 R 2 log ( d 0 η β R ) ) steps.
This is a consequence of the mixing property of Hit-and-Run [Lovász and Vempala, 2006]. Although this establishes that the desired sampling guarantee can be achieved in polynomial time, the argument proceeds through the substantially stronger requirement of η β \eta\beta η β -ℓ 1 \ell_1 ℓ 1 closeness. As discussed in the preceding subsection, such accuracy is sufficient but not necessary for almost-ℓ ∞ \ell_\infty ℓ ∞ closeness. This raises the natural question of whether the desired guarantee can be obtained with a smaller number of random-walk steps.
We somewhat address this question through a refined analysis of Hit-and-Run, obtaining the following improved bound.
Theorem 6 (Improved tail-controlled Hit-and-Run, informal). Under the geometric and initialization assumptions of our analysis, Hit-and-Run produces an ( η , β ) (\eta,\beta) ( η , β ) -almost-ℓ ∞ \ell_\infty ℓ ∞ -close distribution to π \pi π after
t = O ( n 2 R 2 r 2 [ n log R d 0 + log 1 η β ] ) t = \mathcal{O}\left(n^2 \frac{R^2}{r^2}\left[n\log\frac{R}{d_0}+\log\frac{1}{\eta\beta}\right]\right) t = O ( n 2 r 2 R 2 [ n log d 0 R + log η β 1 ] ) steps.
In particular, for the parameter regime relevant to union-volume estimation, namely η = Θ ( ϵ ) \eta= \Theta(\epsilon) η = Θ ( ϵ ) and β = Θ ( ϵ / M ) \beta= \Theta(\epsilon/M) β = Θ ( ϵ / M ) , this yields
t = O ( n 2 R 2 r 2 [ n log R d 0 + log M ϵ ] ) . t = O\left(n^2\frac{R^2}{r^2}\left[n\log\frac{R}{d_0}+\log\frac{M}{\epsilon}\right]\right). t = O ( n 2 r 2 R 2 [ n log d 0 R + log ϵ M ] ) .
Thus, our analysis improves the dependence on the sampling-accuracy parameters relative to the preceding TV-based bound, while retaining the almost-ℓ ∞ \ell_\infty ℓ ∞ guarantee required by Alpona. The formal statement, proof, and resulting complexity bounds are presented in § 6 .
In fact, we believe even this dependency is not optimal. Heuristically, the factor of log ( M / ϵ ) \log(M/\epsilon) log ( M / ϵ ) should not have a dependency of n 2 n^2 n 2 in front of it. We conjecture that it is possible to get a bound of order
t = O ( n 2 R 2 r 2 [ n log n R 2 d 0 r + log 1 η ] ) + O ( R r log 1 β ) . t = O\left(n^2\frac{R^2}{r^2}\left[n\log\frac{nR^2}{d_0r}+\log\frac{1}{\eta}\right]\right)+O\left(\frac{R}{r}\log\frac{1}{\beta}\right). t = O ( n 2 r 2 R 2 [ n log d 0 r n R 2 + log η 1 ] ) + O ( r R log β 1 ) .
which, with η = Θ ( ϵ ) \eta= \Theta(\epsilon) η = Θ ( ϵ ) and β = Θ ( ϵ / M ) \beta= \Theta(\epsilon/M) β = Θ ( ϵ / M ) yields
t = O ( n 2 R 2 r 2 [ n log n R 2 d 0 r + log 1 ϵ ] ) + O ( R r log M ϵ ) . t = O\left(n^2\frac{R^2}{r^2}\left[n\log\frac{nR^2}{d_0r}+\log\frac{1}{\epsilon}\right]\right)+O\left(\frac{R}{r}\log\frac{M}{\epsilon}\right). t = O ( n 2 r 2 R 2 [ n log d 0 r n R 2 + log ϵ 1 ] ) + O ( r R log ϵ M ) .
We elaborate on this conjecture later in § 8 .
Algorithmic Framework:
Using the notion of tail-controlled sampling, we develop the algorithm Alpona that estimates the volume of union of convex bodies. The analysis of the algorithm is done in the next section.
Overview and intuition
We are given a collection { K 1 , … , K M } \{K_1,\ldots,K_M\} { K 1 , … , K M } of convex bodies in R n \mathbb{R}^n R n and wish to estimate the volume of their union, i.e. solve Problem 1. We assume that all the bodies, K i K_i K i 's, are subsets of Ω \Omega Ω , where Ω \Omega Ω is a compact measurable subset of R n \mathbb{R}^n R n with volume ∣ Ω ∣ |\Omega| ∣Ω∣ .
The guiding idea is to maintain a multiset X \mathcal{X} X of representative points at a common sampling intensity p ∈ ( 0 , 1 ) p \in(0,1) p ∈ ( 0 , 1 ) . Here, intensity quantifies the contribution made to the random quantity ∣ X ∣ |\mathcal{X}| ∣ X ∣ by each representative point. Ideally, a measurable region of volume v v v would contribute a Poisson number of representatives with mean p v pv p v . If this property holds for the union, then ∣ X ∣ / p |\mathcal{X}|/p ∣ X ∣/ p acts a natural estimator of the union-volume.
The first challenge is accounting for the overlaps . While processing a body K i K_i K i from a given arbitrary ordering of the convex bodies, we remove from X \mathcal{X} X every point lying in K i K_i K i before adding new samples from that body. In this way, the representatives retained at the end correspond to disjoint portions of the union, determined by the last body in the chosen ordering that contains each point. To obtain intensity p p p per unit volume in K i K_i K i , one would ideally draw N i ∼ Pois ( p Vol ( K i ) ) N_i \sim\operatorname{Pois}(p\operatorname{Vol}(K_i)) N i ∼ Pois ( p Vol ( K i )) , and then choose N i N_i N i independent points uniformly from K i K_i K i .
The second challenge is to keep the total number of retained samples ∣ X ∣ |\mathcal{X}| ∣ X ∣ bounded . Whenever the proposed insertion of new samples exceeds a threshold, we independently retain each existing point with probability 1 / 2 1/2 1/2 and replace p p p by p / 2 p/2 p /2 . Accordingly, we reduce the proposed sample size from N i N_i N i to Binomial ( N i , 1 / 2 ) \operatorname{Binomial}(N_i,1/2) Binomial ( N i , 1/2 ) . This ensures the thinning property of Poisson random variables: at a fixed intensity, independently thinning a Poisson sample X X X via Binomial ( X , 1 / 2 ) \operatorname{Binomial}(X,1/2) Binomial ( X , 1/2 ) produces a Poisson sample at half the intensity.
There is, however, a more fundamental challenge: the ideal sampling process cannot be implemented exactly with the available efficient algorithms. Neither can we sample points uniformly, nor do we have the ability to do an exact computation of the volume. For each convex body K i K_i K i , we have only a PAC estimate V ~ i \widetilde{V}_i V i of Vol ( K i ) \operatorname{Vol}(K_i) Vol ( K i ) , and each generated point follows a distribution D i D_i D i that is ( η , β ) (\eta,\beta) ( η , β ) -close to the uniform distribution π K i \pi_{K_i} π K i .
These two approximations affect different aspects of the final sample set over the union. To see this, let us denote h i : = d D i d π K i h_i := \frac{\mathrm{d}D_i}{\mathrm{d}\pi_{K_i}} h i := d π K i d D i to be the Radon-Nikodym derivative. For a measurable set A ⊆ K i A \subseteq K_i A ⊆ K i , the expected number of newly generated points in A A A , at a fixed intensity p p p and conditional on V ~ i \widetilde{V}_i V i , is
p V ~ i D i ( A ) = p V ~ i Vol ( K i ) ∫ A h i ( x ) d x . p\widetilde{V}_i D_i(A) = p\frac{\widetilde{V}_i}{\operatorname{Vol}(K_i)}\int_A h_i(x)\,\mathrm{d}x. p V i D i ( A ) = p Vol ( K i ) V i ∫ A h i ( x ) d x .
Thus, the volume-estimation error changes the overall scale of the sampling intensity, whereas the sampling error changes its spatial distribution . Even if the total number of generated points is close to the ideal count, they may be distributed unevenly among overlapping and non-overlapping portions of the bodies. This matters because the algorithm removes points according to their locations, not merely their number.
Let us look back to the particular case of Sunflower families. Note that the key reason for ineffectiveness of TV-close samplers was this sampling bias. It might happen, that the provided samplers are heavily biased towards the overlapping portions, rather than the portions which are unique to the convex bodies. Thus, points from overlapping portions are sampled; only to be thrown out later, leaving no trace of the convex body from which it was sampled. And hence it causes a major collapse in the point sampling based framework for volume estimation.
The almost-ℓ ∞ \ell_\infty ℓ ∞ guarantee gives a useful way to separate these effects. Outside the exceptional set B a d η \mathrm{Bad}_\eta Bad η defined in Definition 2, the density ratio h i h_i h i lies between 1 − η 1-\eta 1 − η and 1 + η 1+\eta 1 + η . Hence, on this good portion of a body, the local sampling intensity differs from the ideal intensity by controlled multiplicative factors, provided the volume estimate is accurate. Since the exceptional portion cannot be treated pointwise in the same way; its contribution must be bounded via the bounds on the exceptional region, which we obtain from the definition of almost-ℓ ∞ \ell_\infty ℓ ∞ close sampling. We explain these guarantees with the oracles below and quantify their effect in the correctness proof.
Finally, the sampling intensity p p p is reduced adaptively, depending on the points already retained and the proposed Poisson counts. Although Poisson thinning explains the operation at a fixed rate, the analysis must also justify concentration for the resulting adaptive procedure.
The algorithmic framework Alpona is described next in details, while its correctness and oracle efficiency are established later in § 5 .
Volume and Sampling Oracles
The algorithm Alpona uses a couple of oracles deployed as subroutines, and the guarantees and implementation of them are crucial both for the analysis of correctness and the overall complexity analysis of Alpona. Let us first describe the guarantees given by the subroutines. We will analysis the implementation and analysis of these subroutines later.
I. PAC Volume Estimation. The subroutine ComputeVolume takes a convex body K ⊆ R n K \subseteq\mathbb{R}^n K ⊆ R n , its geometric parameters ( r , R ) (r,R) ( r , R ) , and accuracy parameters ( κ , δ v ) (\kappa,\delta_v) ( κ , δ v ) . It returns an estimate V ~ \widetilde{V} V satisfying
Pr [ ( 1 − κ ) Vol ( K ) ≤ V ~ ≤ ( 1 + κ ) Vol ( K ) ] ≥ 1 − δ v . \Pr\left[(1-\kappa)\operatorname{Vol}(K) \leq\widetilde{V} \leq(1+\kappa)\operatorname{Vol}(K)\right] \geq1-\delta_v. Pr [ ( 1 − κ ) Vol ( K ) ≤ V ≤ ( 1 + κ ) Vol ( K ) ] ≥ 1 − δ v .
We use the volume-estimation algorithms discussed in Cousins and Vempala [ [9 ] . Their implementation and resource requirements are treated separately in the complexity analysis.
II. ( η , β ) (\eta,\beta) ( η , β ) -almost Uniform Point Sampling. The subroutine GenerateSamples takes a convex body K ⊆ R n K \subseteq\mathbb{R}^{n} K ⊆ R n , its geometric parameters ( r , R ) (r,R) ( r , R ) , and parameters ( η , β ) (\eta,\beta) ( η , β ) . Each invocation produces an independent point in K K K according to a distribution D \mathcal{D} D satisfying the ( η , β ) (\eta,\beta) ( η , β ) -almost-ℓ ∞ \ell_{\infty} ℓ ∞ -uniform guarantee of Definition 2. Such sampling guarantees can be realised using suitable implementations of Hit-and-Run (ref. § 6.2.2 ).
The Main Algorithm:
We assume that each body K i K_i K i is ( r , R ) (r,R) ( r , R ) -fat convex body, that is, it contains an sphere of radius at most r > 0 r>0 r > 0 and is circumscribed by a sphere of radius at least R ≥ r > 0 R\ge r>0 R ≥ r > 0 . The algorithm Alpona takes the number of bodies M M M , approximation parameters ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) , and the geometric specifications ( r , R ) (r,R) ( r , R ) as input. It maintains a multiset X \mathcal{X} X of sampled points and a common sampling intensity p p p . The threshold threshold and the accuracy parameters of the two subroutines are fixed as functions of the input parameters.
Algorithm 1 Alpona( ε , δ , M , r , R ) (\varepsilon,\delta,M,r,R) ( ε , δ , M , r , R )
Initialise threshold ← ⌈ 576 ε 2 log 16 M δ ⌉ \leftarrow\left\lceil\frac{576}{\varepsilon^2}\log\frac{16M}{\delta}\right\rceil ← ⌈ ε 2 576 log δ 16 M ⌉
Initialise p ← 1 p\leftarrow1 p ← 1
Initialise multiset X ← ∅ \mathcal{X}\leftarrow\varnothing X ← ∅
Set parameters: κ = ε 32 , δ v = δ 4 M , η = ε 32 , β = ε 32 M \kappa=\frac{\varepsilon}{32},\delta_v=\frac{\delta}{4M},\eta=\frac{\varepsilon}{32},\beta=\frac{\varepsilon}{32M} κ = 32 ε , δ v = 4 M δ , η = 32 ε , β = 32 M ε
for i = 1 i=1 i = 1 to M M M do
for all x ∈ X x\in\mathcal{X} x ∈ X do
If x ∈ K i x\in K_i x ∈ K i , remove all copies of x x x from X \mathcal{X} X
Query V ~ i ← ComputeVolume ( K i , κ , δ v , r , R ) \widetilde{V}_i\leftarrow\operatorname{ComputeVolume}(K_i,\kappa,\delta_v,r,R) V i ← ComputeVolume ( K i , κ , δ v , r , R )
Draw N i ∼ Pois ( V ~ i ⋅ p ) N_i\sim\operatorname{Pois}(\widetilde{V}_i\cdot p) N i ∼ Pois ( V i ⋅ p )
while ( ∣ X ∣ + N i > threshold ) (|\mathcal{X}|+N_i>\texttt{threshold}) ( ∣ X ∣ + N i > threshold ) do
For each y ∈ X y\in\mathcal{X} y ∈ X , throw y y y from X \mathcal{X} X with probability 1 / 2 1/2 1/2
N i ← Binomial ( N i , 1 / 2 ) N_i\leftarrow\operatorname{Binomial}(N_i,1/2) N i ← Binomial ( N i , 1/2 ) and p ← p / 2 p\leftarrow p/2 p ← p /2
for j = 1 j=1 j = 1 to N i N_i N i do
Query z ← GenerateSamples ( K i , η , β , r , R ) z\leftarrow\operatorname{GenerateSamples}(K_i,\eta,\beta,r,R) z ← GenerateSamples ( K i , η , β , r , R )
X ← X ∪ { z } \mathcal{X}\leftarrow\mathcal{X}\cup\{z\} X ← X ∪ { z }
return ∣ X ∣ / p |\mathcal{X}|/p ∣ X ∣/ p
In lines 1–4, the algorithm sets the storage threshold threshold, initializes the common sampling intensity p p p to 1 1 1 , and starts with an empty multi-set X \mathcal{X} X , that would contain the samples from the union of bodies seen so far. It also fixes the accuracy and confidence parameters for the volume and sampling subroutines. The choices of these parameters are justified in the analysis.
Inside the for loop (lines 5–15), the multi-set X \mathcal{X} X is updated according to the bodies K 1 K_1 K 1 to K M K_M K M . For each body K i K_i K i , the algorithm firstly (in lines 6–7) removes every occurrence in X \mathcal{X} X whose location belongs to K i K_i K i . Thus, if a point belongs to several bodies, all the previous occurrence of the point does not have any influence on its inclusion in X \mathcal{X} X , suggesting that every measurable subset of the union is processed by the algorithm exactly once (during it’s last occurrence in the ordering). The resulting last-occurrence decomposition of the union is formalized in the correctness proof.
In line 8, Alpona computes the PAC estimate V ~ i \widetilde{V}_i V i . In line 9, it draws N i ∼ Pois ( p V ~ i ) N_i\sim\operatorname{Pois}(p\widetilde{V}_i) N i ∼ Pois ( p V i ) , i.e., the number of representatives from K i K_i K i that would be added to X \mathcal{X} X so that each point in the union ( K 1 ∪ ⋯ ∪ K i ) (K_1\cup\cdots\cup K_i) ( K 1 ∪ ⋯ ∪ K i ) is equally represented. Since V ~ i \widetilde{V}_i V i is an estimate, the intended number of representatives is proportional to the estimated volume , rather than the unknown true volume. This distinction, together with the non-uniformity of the generated points, is explicitly accounted for in the correctness proof.
If inserting N i N_i N i new points would exceed threshold, the algorithm independently retains each occurrence already in X \mathcal{X} X with probability 1 / 2 1/2 1/2 and halves p p p (lines 10–12), and appropriately reduces the estimated number of points to be sampled from K i K_i K i and resamples the points in X \mathcal{X} X . The loop continues until the proposed count fits within the storage threshold. Once the count fits, Alpona (in lines 13–15) makes N i N_i N i independent calls to GenerateSamples and inserts the resulting points into X \mathcal{X} X . The points follow the almost-ℓ ∞ \ell_\infty ℓ ∞ -uniform sampling distribution described above, rather than an exactly uniform distribution.
After all bodies have been processed, the algorithm returns ∣ X ∣ / p |\mathcal{X}|/p ∣ X ∣/ p . Informally, ∣ X ∣ |\mathcal{X}| ∣ X ∣ is the number of retained representatives at the final sampling intensity p p p , and division by p p p rescales the count into a volume estimate. Proving that this estimate is accurate despite approximate subroutines and adaptive halving is the subject of the next section.
Relation to the Existing Union Volume Estimation Algorithms
While randomized polynomial-time approximation algorithms for estimating the volume of convex bodies are well established [11 , 22 , 9 ] , extending these techniques to non-convex regions presents additional challenges. In particular, a union of convex bodies need not be convex, and the geometric properties underlying efficient random-walk-based volume estimation may no longer hold. An important special case is Klee’s Measure Problem, which asks for the volume of a union of axis-parallel boxes and has been extensively studied in computational geometry.
The classical framework of Karp et al. [ [16 ] provides randomized approximation algorithms for unions using size, uniform-sampling, and membership oracles. Bringmann and Friedrich [ [5 ] extended this approach to unions of high-dimensional geometric objects, including general convex bodies and settings with approximate oracles. In a different computational model, Meel et al. [ [29 , 30 ] developed space-efficient algorithms for estimating unions of implicitly represented sets, introducing the framework of Delphic sets and its approximate-oracle generalization. Their results yield efficient algorithms for discrete versions of Klee’s Measure Problem and were subsequently improved by Nandi et al. [ [32 ] . More recently, Bringmann et al. [ [7 ] established an Ω ( M / ε 2 ) \Omega(M/\varepsilon^2) Ω ( M / ε 2 ) lower bound for general oracle-based union-volume estimation, matching the classical query complexity, and obtained faster algorithms for Klee’s Measure Problem by exploiting the geometric structure of axis-parallel boxes.
Our algorithm, Alpona, addresses a complementary aspect of this problem. Unlike the algorithms for Delphic sets, which operate over a discrete universe, Alpona works directly with continuous convex bodies, without discretizing the underlying space. Moreover, while the oracle-based framework of Bringmann and Friedrich [ [5 ] already permits oracles which may be unrealistic, our emphasis is on the guarantees required when these oracles are implemented using randomized volume-estimation procedures and geometric random walks. In particular, Alpona uses PAC volume estimates and almost-ℓ ∞ \ell_\infty ℓ ∞ -uniform samples, together with Poissonization and adaptive thinning, to control the combined effects of approximation errors and overlapping regions. Thus, rather than improving the general oracle-query lower bound, our contribution is an end-to-end analysis of a sampling-based algorithm using concrete approximate geometric primitives.
Correctness Proof of Alpona
In this section, we formally state and prove the guarantees offered by the algorithm Alpona. The proof proceeds by first showing that almost all of this volume is contained in regions where the sampler behaves approximately uniformly, and then showing that the algorithm accurately estimates the volume of these regions.
Theorem 7 (Correctness and oracle efficiency of Alpona). Given input parameters ( ε , δ , M , r , R ) (\varepsilon, \delta, M, r, R) ( ε , δ , M , r , R ) and a collection { K 1 , … , K M } \{K_1,\ldots,K_M\} { K 1 , … , K M } of M M M many ( r , R ) (r,R) ( r , R ) -fat convex bodies, the algorithm Alpona yields an ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) -correct Union Volume Estimation, i.e., it returns a value V ~ \widetilde{V} V such that
( 1 − ε ) Vol ( ⋃ i = 1 M K i ) ≤ V ~ ≤ ( 1 + ε ) Vol ( ⋃ i = 1 M K i ) (1-\varepsilon)\operatorname{Vol}\left(\bigcup_{i=1}^{M}K_i\right) \le\widetilde{V} \le(1+\varepsilon)\operatorname{Vol}\left(\bigcup_{i=1}^{M}K_i\right) ( 1 − ε ) Vol ( i = 1 ⋃ M K i ) ≤ V ≤ ( 1 + ε ) Vol ( i = 1 ⋃ M K i ) with probability at least 1 − δ 1-\delta 1 − δ , with O ( M ) O(M) O ( M ) many calls to the PAC volume computation oracle and O ( M ε 2 log M δ ) O\left(\frac{M}{\varepsilon^2}\log\frac{M}{\delta}\right) O ( ε 2 M log δ M ) many calls to the ( η , β ) (\eta,\beta) ( η , β ) -tailed sampler oracle.
Overview of the Proof
We write F 0 : = Vol ( ⋃ j = 1 M K j ) F_0 := \operatorname{Vol}(\bigcup_{j=1}^{M} K_j) F 0 := Vol ( ⋃ j = 1 M K j ) for the volume of the union. Since the algorithm Alpona is a random process, it makes sense to talk about it’s output from the perspective of distributions. For simplicity of the proof, we consider a variant Alpona-modified of the main algorithm. Note that in Alpona-modified, we are assuming that we know the quantity 1 / F 0 1/F_0 1/ F 0 beforehand; and that the only difference between Alpona and Alpona-modified is in line 10. If p ∗ p_* p ∗ denotes the value of p p p at the end of Alpona, the event where p ∗ > 1 / F 0 p_* > 1/F_0 p ∗ > 1/ F 0 should correspond to runs of Alpona-modified with the same output. Thus, we consider an event Failp r o b _{\mathrm{prob}} prob where p p p falls too low.
Our first claim (Claim 8 ) informally tells us that as long as we are capable of proving that Failp r o b _{\mathrm{prob}} prob occurs with very low probability, the output distributions of Alpona and Alpona-modified are very close to each other w.r.t Total Variation distance. As a consequence, if we are able to prove a correctness guarantee upon Alpona-modified, that should give us a correctness guarantee on Alpona as well (after accounting for this TV-distance between the two distributions). Our objective moving forward, will therefore be upon trying to prove the correctness of Alpona-modified.
Recall the good and bad regions associated with the sampler GenerateSamples, as defined in § 4.2 . In particular, Bad j \operatorname{Bad}_j Bad j denotes the bad region of K j K_j K j , and Good j : = K j ∖ Bad j \operatorname{Good}_j := K_j \setminus\operatorname{Bad}_j Good j := K j ∖ Bad j its good region. To avoid counting overlapping regions multiple times, we assign each point in the union to the last body (in the fixed processing order) that contains it. Formally, we define
K ^ j : = K j ∖ ⋃ i > j K i . \widehat{K}_j := K_j \setminus\bigcup_{i>j} K_i. K j := K j ∖ i > j ⋃ K i .
These unique sections K ^ j \widehat{K}_j K j are pairwise disjoint and their union is precisely the union of the convex bodies. We write K ^ j ∖ Bad j \widehat{K}_j \setminus\operatorname{Bad}_j K j ∖ Bad j and K ^ j ∩ Bad j \widehat{K}_j \cap\operatorname{Bad}_j K j ∩ Bad j for the good and bad parts of K ^ j \widehat{K}_j K j , respectively. The first step of the proof is to show that the total volume of the good parts,
F 0 ′ : = Vol ( ⋃ j ( K ^ j ∖ Bad j ) ) = ∑ j Vol ( K ^ j ∖ Bad j ) , (2) F'_0 := \operatorname{Vol}\left(\bigcup_j(\widehat{K}_j \setminus\operatorname{Bad}_j)\right) = \sum_j \operatorname{Vol}(\widehat{K}_j \setminus\operatorname{Bad}_j), \tag*{(2)} F 0 ′ := Vol ( j ⋃ ( K j ∖ Bad j ) ) = j ∑ Vol ( K j ∖ Bad j ) , (2)
is close to F 0 F_0 F 0 . This is established in Claim 9 . Consequently, it suffices to show that the output of the algorithm is a sufficiently accurate estimate of $F'_0`.
To analyse the output, we partition the surviving samples according to whether they originate from the good or bad parts of the corresponding bodies. Let p f i n a l p_{\mathrm{final}} p final denote the sampling intensity at the end of a run of Alpona-modified. Let E s t g o o d \mathrm{Est}_{\mathrm{good}} Est good and E s t b a d \mathrm{Est}_{\mathrm{bad}} Est bad denote the respective numbers of such samples. Thus, whenever the algorithm returns a numerical estimate,
∣ X ∣ = E s t g o o d + E s t b a d , O u t = E s t g o o d + E s t b a d p f i n a l . |\mathcal{X}| = \mathrm{Est}_{\mathrm{good}} + \mathrm{Est}_{\mathrm{bad}}, \qquad\mathrm{Out} = \frac{\mathrm{Est}_{\mathrm{good}} + \mathrm{Est}_{\mathrm{bad}}}{p_{\mathrm{final}}}. ∣ X ∣ = Est good + Est bad , Out = p final Est good + Est bad .
We show that E s t g o o d / p f i n a l \mathrm{Est}_{\mathrm{good}}/p_{\mathrm{final}} Est good / p final is concentrated around F 0 ′ F'_0 F 0 ′ , while E s t b a d / p f i n a l \mathrm{Est}_{\mathrm{bad}}/p_{\mathrm{final}} Est bad / p final contributes only a small additive error. Together, these establish that O u t \mathrm{Out} Out approximates F 0 F_0 F 0 .
The analysis must account for four possible sources of failure: an inaccurate estimate returned by the volume oracle (F a i l v o l \mathbf{Fail}_{\mathrm{vol}} Fail vol ), a significant deviation in the number of good samples (F a i l g o o d \mathbf{Fail}_{\mathrm{good}} Fail good ), and an excessive number of bad samples (F a i l b a d \mathbf{Fail}_{\mathrm{bad}} Fail bad ). In Claim 10 , we show that the algorithm succeeds whenever none of these events occurs. The remainder of the proof bounds the probabilities of these four events individually and combines the bounds using a union bound to obtain the desired correctness guarantee.
Proof of Theorem 7 . First, we prove Claim 8 to show that the TV-distance between the output distributions of Alpona and Alpona-modified is at most δ 4 \frac{\delta}{4} 4 δ . Then, we are left to prove that Alpona-modified is an ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) -Union Volume Estimation algorithm with probability at most 3 δ 4 \frac{3\delta}{4} 4 3 δ .
In this context, we prove Claim 10 , i.e., the event where the algorithm Alpona-modified results in a failure can be decomposed into three events: F a i l v o l \mathbf{Fail}_{\mathrm{vol}} Fail vol due to the approximation errors of PAC volume estimator, F a i l g o o d \mathbf{Fail}_{\mathrm{good}} Fail good due to deviations of the ‘good’ sample counts, and F a i l b a d \mathbf{Fail}_{\mathrm{bad}} Fail bad due to the ‘bad’ samples.
In the next subsections, we bound each of their probabilities of occurrence:
We prove in Claim 11 that P [ F a i l v o l ] < δ 4 \mathbb{P}[\mathbf{Fail}_{\mathrm{vol}}] < \frac{\delta}{4} P [ Fail vol ] < 4 δ .
We prove in Claim 17 that P [ F a i l g o o d ] < δ 4 \mathbb{P}[\mathbf{Fail}_{\mathrm{good}}] < \frac{\delta}{4} P [ Fail good ] < 4 δ .
We prove in Claim 20 that P [ F a i l b a d ] < δ 4 \mathbb{P}[\mathbf{Fail}_{\mathrm{bad}}] < \frac{\delta}{4} P [ Fail bad ] < 4 δ .
Combining the three above inequalities tells us that the random process Alpona-modified outputs a value outside the range [ ( 1 − ε ) F 0 , ( 1 + ε ) F 0 ] [(1-\varepsilon)F_0,(1+\varepsilon)F_0] [( 1 − ε ) F 0 , ( 1 + ε ) F 0 ] is at most 3 δ 4 \frac{3\delta}{4} 4 3 δ .
By Lemma 30 , then we can conclude that the probability of Alpona not yielding a value in the range [ ( 1 − ε ) F 0 , ( 1 + ε ) F 0 ] [(1-\varepsilon)F_0,(1+\varepsilon)F_0] [( 1 − ε ) F 0 , ( 1 + ε ) F 0 ] is at most:
3 δ 4 + δ 4 = δ , \frac{3\delta}{4}+\frac{\delta}{4}=\delta, 4 3 δ + 4 δ = δ ,
as desired. □
Now, we are going to formally introduce Alpona-modified, and prove the claims corresponding to Alpona-modified in the next sections.
Alpona-modified: A Technical Modification for Analysis
For simplicity in proving correctness, we define a modified version of Alpona below strictly for the purpose of analysis. As one can note the key distinction between the two algorithms is the inclusion of the clause p ≥ 1 / F 0 p \ge1/F_0 p ≥ 1/ F 0 . Notably in this version of the algorithm there is no strict upper bound on ∣ X ∣ |\mathcal{X}| ∣ X ∣ , because of which we can make observations as demonstrated in Lemma 13 , something we could not do for Alpona itself because in the original algorithm there is an implicit upper bound X < threshold \mathcal{X}<\texttt{threshold} X < threshold .
Consider the event Fail p r o b _{\mathrm{prob}} prob , where the value of the sampling intensity in Alpona decreases below 1 / F 0 1/F_0 1/ F 0 . If the Fail p r o b _{\mathrm{prob}} prob event does not occur, then the two algorithms are essentially the same; and thus must output the same quantity. In other words, the only situation where the output distributions of the two algorithms would differ is when Fail p r o b _{\mathrm{prob}} prob would occur. This intuition is presented formally below.
Algorithm 2 Alpona-modified($\varepsilon,\delta,M,r,R$)
1: Initialise threshold $\leftarrow \left\lceil \frac{576}{\varepsilon^2}\log\frac{16M}{\delta}\right\rceil$
2: Initialise $p\leftarrow 1$
3: Initialise multiset $\mathcal{X}\leftarrow\varnothing$
4: Set parameters: $\kappa=\frac{\varepsilon}{32},\delta_v=\frac{\delta}{4M},\eta=\frac{\varepsilon}{32},\beta=\frac{\varepsilon}{32M}$
5: for $i=1$ to $M$ do
6: for all $x\in\mathcal{X}$ do
7: If $x\in K_i$, remove all copies of $x$ from $\mathcal{X}$
8: Query $\widetilde{V}_i\leftarrow\operatorname{ComputeVolume}(K_i,\kappa,\delta_v,r,R)$
9: Draw $N_i\sim\operatorname{Pois}(\widetilde{V}_i\cdot p)$
10: while $(|\mathcal{X}|+N_i>\text{threshold})$ and $(p\ge 1/F_0)$ do
11: For each $y\in\mathcal{X}$, throw $y$ from $\mathcal{X}$ with probability $1/2$
12: $N_i\leftarrow\operatorname{Binomial}(N_i,1/2)$ and $p\leftarrow p/2$
13: for $j=1$ to $N_i$ do
14: Query $z\leftarrow\operatorname{GenerateSamples}(K_i,\eta,\beta,r,R)$
15: $\mathcal{X}\leftarrow\mathcal{X}\cup\{z\}$
16: return $|\mathcal{X}|/p$
Claim 8 (Closeness of Alpona and Alpona-modified). The total variation distance between the output distribution of the two algorithms Alpona and Alpona-modified is upper bounded by Pr ( F a i l p r o b ) \Pr(\mathrm{Fail}_{\mathrm{prob}}) Pr ( Fail prob ) .
Proof. Couple the two executions of Alpona and Alpona-modified from shared randomness. Let O O O and O m o d O_{\mathrm{mod}} O mod denotes their respective outputs. During this coupled execution Alpona differs from Alpona-modified when the condition of p ≥ 1 / F 0 p\ge1/F_0 p ≥ 1/ F 0 in line 10 prevents Alpona-modified from performing one more halving that Alpona performs. By the coupling inequality (Lemma 29 ), therefore the total variation distance is upper bounded by:
Pr ( O ≠ O m o d ) ≤ Pr ( p ≤ 1 / F 0 ) ≤ Pr ( p f i n a l ≤ 1 / F 0 ) = Pr ( F a i l p r o b ) . \Pr(O\ne O_{\mathrm{mod}})\le\Pr(p\le1/F_0)\le\Pr(p_{\mathrm{final}}\le1/F_0)=\Pr(\mathrm{Fail}_{\mathrm{prob}}). Pr ( O = O mod ) ≤ Pr ( p ≤ 1/ F 0 ) ≤ Pr ( p final ≤ 1/ F 0 ) = Pr ( Fail prob ) .
This completes the proof of the claim.
Since each of run Alpona which results in the final sampling intensity decreasing below 1 / F 0 1/F_0 1/ F 0 corresponds to a run of Alpona-modified resulting in the sampling intensity decreasing below 1 / F 0 1/F_0 1/ F 0 , moving forward we can equivalently consider Fail p r o b _{\mathrm{prob}} prob to be the event where the sampling intensity of Alpona-modified at the end of a run falls below 1 / F 0 1/F_0 1/ F 0 .
Step I. The Decomposition of Failure of Alpona-modified
As explained in the previous section, our current strategy is to prove the correctness of Alpona-modified. We proceed along the lines described in § 5.1 ; firstly we shall formally reduce the problem of estimating F 0 F_0 F 0 into the problem of estimating F 0 ′ F'_0 F 0 ′ . We do this by strictly upper-bounding the mass stored in exceptional regions of each convex body.
Claim 9 (Equivalence of F 0 F_0 F 0 and F 0 ′ F'_0 F 0 ′ ). Referring to notations defined previously (2) , we have:
( 1 − β ) F 0 = ( 1 − ε 32 ) F 0 ≤ F 0 ′ ≤ F 0 . (1-\beta)F_0=\left(1-\frac{\varepsilon}{32}\right)F_0\le F'_0\le F_0. ( 1 − β ) F 0 = ( 1 − 32 ε ) F 0 ≤ F 0 ′ ≤ F 0 . If the output of the algorithm is in the range O u t ∈ ( 1 ± 15 ε 16 ) F 0 ′ \mathrm{Out}\in\left(1\pm\frac{15\varepsilon}{16}\right)F'_0 Out ∈ ( 1 ± 16 15 ε ) F 0 ′ , we will have O u t ∈ ( 1 ± ε ) F 0 \mathrm{Out}\in(1\pm\varepsilon)F_0 Out ∈ ( 1 ± ε ) F 0 .
Proof. Observe that we can write F 0 F_0 F 0 as a sum of Vol ( K ^ j ) \operatorname{Vol}(\widehat{K}_j) Vol ( K j ) , since the union of all the sets can be viewed as a disjoint union of the unique sections. We can further break down each Vol ( K ^ j ) \operatorname{Vol}(\widehat{K}_j) Vol ( K j ) into a sum of volumes of good and bad sections, and bound the volume of bad sections by the guarantees of almost-ℓ ∞ \ell_\infty ℓ ∞ sampling.
F 0 = ∑ j = 1 M Vol ( K ^ j ) = ∑ j = 1 M Vol ( K ^ j ∖ Bad j ) + Vol ( K ^ j ∩ Bad j ) ≤ F 0 ′ + ∑ j = 1 M Vol ( Bad j ) ≤ F 0 ′ + β F 0 M = F 0 ′ + ε 32 F 0 . \begin{aligned}
F_0&=\sum_{j=1}^{M}\operatorname{Vol}(\widehat{K}_j)
=\sum_{j=1}^{M}\operatorname{Vol}(\widehat{K}_j\setminus\operatorname{Bad}_j)+\operatorname{Vol}(\widehat{K}_j\cap\operatorname{Bad}_j)\\
&\le F'_0+\sum_{j=1}^{M}\operatorname{Vol}(\operatorname{Bad}_j)\\
&\le F'_0+\beta F_0M=F'_0+\frac{\varepsilon}{32}F_0.
\end{aligned} F 0 = j = 1 ∑ M Vol ( K j ) = j = 1 ∑ M Vol ( K j ∖ Bad j ) + Vol ( K j ∩ Bad j ) ≤ F 0 ′ + j = 1 ∑ M Vol ( Bad j ) ≤ F 0 ′ + β F 0 M = F 0 ′ + 32 ε F 0 . The second part is simple algebraic manipulation. Note that by default we have ( 1 + 15 ε 16 ) F 0 ′ ≤ ( 1 + ε ) F 0 \left(1+\frac{15\varepsilon}{16}\right)F'_0\le(1+\varepsilon)F_0 ( 1 + 16 15 ε ) F 0 ′ ≤ ( 1 + ε ) F 0 . For the other direction, we apply the above obtained lower bound on F 0 ′ F'_0 F 0 ′ .
( 1 − 15 ε 16 ) F 0 ′ ≥ ( 1 − 15 ε 16 ε ) ( 1 − ε 32 ) F 0 ≥ ( 1 − ε ) F 0 . \left(1-\frac{15\varepsilon}{16}\right)F'_0\ge\left(1-\frac{15\varepsilon}{16}\varepsilon\right)\left(1-\frac{\varepsilon}{32}\right)F_0\ge(1-\varepsilon)F_0. ( 1 − 16 15 ε ) F 0 ′ ≥ ( 1 − 16 15 ε ε ) ( 1 − 32 ε ) F 0 ≥ ( 1 − ε ) F 0 .
Claim 10 (Decomposition of Failure). The event where a run of Alpona-modified results in a failure, i.e. the output distribution of Alpona-modified returns a value outside ( 1 ± ε ) F 0 (1\pm\varepsilon)F_0 ( 1 ± ε ) F 0 is contained in the union of the following events:
Fail v o l _{\mathrm{vol}} vol := At least one ComputeVolume query returns an incorrect estimate of the volume.
Fail g o o d _{\mathrm{good}} good := The ComputeVolume queries are all correct, and we have p f i n a l ≥ 1 / F 0 p_{\mathrm{final}}\ge1/F_0 p final ≥ 1/ F 0 , but E s t g o o d \mathrm{Est}_{\mathrm{good}} Est good does not lie in ( 1 ± 15 ε 32 ) p f i n a l F 0 ′ \left(1\pm\frac{15\varepsilon}{32}\right)p_{\mathrm{final}}F'_0 ( 1 ± 32 15 ε ) p final F 0 ′ .
Fail b a d _{\mathrm{bad}} bad := The ComputeVolume queries are all correct, and we have p f i n a l ≥ 1 / F 0 p_{\mathrm{final}}\ge1/F_0 p final ≥ 1/ F 0 , but E s t b a d \mathrm{Est}_{\mathrm{bad}} Est bad takes a value larger than 15 32 ε p f i n a l F 0 ′ \frac{15}{32}\varepsilon p_{\mathrm{final}}F'_0 32 15 ε p final F 0 ′ .
Proof. Observe that if a run of Alpona-modified belongs to the intersection of complements of the above mentioned events, then O u t = E s t g o o d + E s t b a d p f i n a l ∈ ( 1 ± 15 ε 16 ) F 0 ′ \mathrm{Out}=\frac{\mathrm{Est}_{\mathrm{good}}+\mathrm{Est}_{\mathrm{bad}}}{p_{\mathrm{final}}}\in\left(1\pm\frac{15\varepsilon}{16}\right)F'_0 Out = p final Est good + Est bad ∈ ( 1 ± 16 15 ε ) F 0 ′ by adding the bounds for E s t g o o d \mathrm{Est}_{\mathrm{good}} Est good and E s t b a d \mathrm{Est}_{\mathrm{bad}} Est bad . By Claim 9 , it would therefore suggest the algorithm has resulted in a success. Thus the failure event must be contained within the union of the above four events.
Rest of the subsections are structured as follows. A section each is dedicated to bounding the probability of each of the events mentioned in the above claim. Through these series of steps, we shall prove that all the four above mentioned events can occur with probability at most δ / 4 \delta/4 δ /4 , and thus by a Union bound argument we give a concrete proof to Theorem 7 at the end of this section.
Step II. Bounding Error due to Volume Computation
We first consider the event of failure due to volume computation. This event is relatively easy to bound; because the volume oracle can output incorrect estimates in any of the M M M many queries, so a simple application of union bound should restrict the probability of F a i l v o l \mathrm{Fail}_{\mathrm{vol}} Fail vol . This intuition is formalised below.
Claim 11 (Bounding Error due to Volume Computation). Consider the event F a i l v o l \mathrm{Fail}_{\mathrm{vol}} Fail vol , where at least one of the ComputeVolume queries does not return a κ \kappa κ -factor approximation to the corresponding volume. Then P [ F a i l v o l ] < δ 4 \mathbb{P}[\mathrm{Fail}_{\mathrm{vol}}] < \frac{\delta}{4} P [ Fail vol ] < 4 δ .
Proof. The probability that a single ComputeVolume query does not return a κ \kappa κ -factor approximation to the corresponding volume is bounded at most by δ v \delta_v δ v . By applying union bound over the M M M many queries and substituting the values for κ \kappa κ and δ v \delta_v δ v , we get P [ F a i l v o l ] < δ 4 M ⋅ M = δ 4 \mathbb{P}[\mathrm{Fail}_{\mathrm{vol}}] < \frac{\delta}{4M} \cdot M = \frac{\delta}{4} P [ Fail vol ] < 4 M δ ⋅ M = 4 δ .
Conditioning on the volume queries. Since the volume queries use randomness independent of the sampling randomness, from now on we fix an outcome of all the volume queries in which every query returns an accurate estimate. Thus for each j j j , we have V ~ j ∈ ( 1 ± ε 32 ) Vol ( K j ) \widetilde{V}_j \in\left(1 \pm\frac{\varepsilon}{32}\right)\operatorname{Vol}(K_j) V j ∈ ( 1 ± 32 ε ) Vol ( K j ) , where V ~ j \widetilde{V}_j V j denotes output of the ComputeVolume query done on K j K_j K j .
Step III. Bounding Error due to Low Intensity of Points
Restricting the volume computation error beforehand allows us to be more lax moving forward, as we don’t have to needlessly worry abound the cases where volume computation might go wrong. To prove F a i l p r o b \mathrm{Fail}_{\mathrm{prob}} Fail prob however, we need to do a bit more work. We start by better explaining the behaviour of the random quantity ∣ X ∣ |\mathcal{X}| ∣ X ∣ .
Let X j X_j X j denote the number of surviving samples belonging to K ^ j \widehat{K}_j K j . Using this notation, we can say ∑ j X j \sum_j X_j ∑ j X j is precisely equal to ∣ X ∣ |\mathcal{X}| ∣ X ∣ , as it represents all the surviving samples. Recall the definitions defined earlier; D j D_j D j represents the sampling distribution, corresponding to the GenerateSamples query on K j K_j K j . The quantity D j ( K ^ j ) ⋅ Vol ( K j ) D_j(\widehat{K}_j)\cdot\operatorname{Vol}(K_j) D j ( K j ) ⋅ Vol ( K j ) reflects the relative mass stored in the region K ^ j \widehat{K}_j K j w.r.t the distribution D j D_j D j . The following lemma informally tells us that the random variables X j X_j X j are mutually independent, and each X j X_j X j follows a Poisson distribution of intensity proportional to the relative mass of K ^ j \widehat{K}_j K j .
Lemma 12 (Properties of X j X_j X j ). The random variables ⟨ X j : 1 ≤ j ≤ M ⟩ \langle X_j : 1 \le j \le M\rangle ⟨ X j : 1 ≤ j ≤ M ⟩ are mutually independent, and for each j ∈ [ M ] j \in[M] j ∈ [ M ] , we have:
X j ∼ Pois ( p f i n a l V ~ j D j ( K ^ j ) ) . X_j \sim\operatorname{Pois}(p_{\mathrm{final}}\widetilde{V}_jD_j(\widehat{K}_j)). X j ∼ Pois ( p final V j D j ( K j )) .
Proof. When the body K j K_j K j gets processed, we draw N j ∼ Pois ( p V ~ j ) N_j \sim\operatorname{Pois}(p\widetilde{V}_j) N j ∼ Pois ( p V j ) many samples from it, where the p p p gets adjusted and decreased to p f i n a l p_{\mathrm{final}} p final over the course of the algorithm. Now consider the measurable partition of K j K_j K j into two parts: K ^ j \widehat{K}_j K j and K j \ K ^ j K_j\backslash\widehat{K}_j K j \ K j . Recall Lemma 26 , since we are drawing from a distribution D j D_j D j on K j K_j K j , the random variable X j X_j X j signifying number of surviving samples from K ^ j \widehat{K}_j K j would follow: X j ∼ Pois ( p f i n a l V ~ j D j ( K ^ j ) ) X_j \sim\operatorname{Pois}(p_{\mathrm{final}}\widetilde{V}_jD_j(\widehat{K}_j)) X j ∼ Pois ( p final V j D j ( K j )) . Additionally, since the value of the random quantity X j X_j X j depend only upon the fresh randomness of the GenerateSamples queries done while processing K j K_j K j , the obtained random quantities ⟨ X j : j ∈ [ M ] ⟩ \langle X_j : j \in[M]\rangle ⟨ X j : j ∈ [ M ]⟩ would therefore be independent.
Lemma 13 (Properties of Λ \Lambda Λ ). Define Λ : = ∑ j V ~ j D j ( K ^ j ) \Lambda:= \sum_j \widetilde{V}_jD_j(\widehat{K}_j) Λ := ∑ j V j D j ( K j ) . Then ∣ X ∣ ∼ Pois ( p f i n a l Λ ) |\mathcal{X}| \sim\operatorname{Pois}(p_{\mathrm{final}}\Lambda) ∣ X ∣ ∼ Pois ( p final Λ ) , and
Λ < ( 1 + ε 7 ) F 0 ′ . \Lambda< \left(1+\frac{\varepsilon}{7}\right)F'_0. Λ < ( 1 + 7 ε ) F 0 ′ .
Proof. As the random variable ∣ X ∣ |\mathcal{X}| ∣ X ∣ can be written as a sum ∑ j X j \sum_j X_j ∑ j X j of independent Poisson random variables, by the additivity property of Poisson distributions (Lemma 25 ) we get the first statement. To prove the bound on Λ \Lambda Λ , we would need to better analyse the relative mass D j ( K ^ j ) D_j(\widehat{K}_j) D j ( K j ) . Recall that π j \pi_j π j represents the uniform distribution over K j K_j K j .
D j ( K ^ j ) = D j ( K ^ j ∖ B a d j ) + D j ( K ^ j ∩ B a d j ) ≤ ( 1 + η ) π j ( K ^ j ∖ B a d j ) + D j ( B a d j ) . (3) \begin{aligned}
D_j(\widehat{K}_j)=D_j(\widehat{K}_j\setminus\mathrm{Bad}_j)+D_j(\widehat{K}_j\cap\mathrm{Bad}_j) \\
&\leq(1+\eta)\pi_j(\widehat{K}_j\setminus\mathrm{Bad}_j)+D_j(\mathrm{Bad}_j). \tag*{(3)}
\end{aligned} D j ( K j ) = D j ( K j ∖ Bad j ) + D j ( K j ∩ Bad j ) ≤ ( 1 + η ) π j ( K j ∖ Bad j ) + D j ( Bad j ) . (3)
Multiplying the above equation by V ~ j \widetilde{V}_j V j , the left side of the above equation becomes the expression for Λ \Lambda Λ . For handling the right side, we bound V ~ j ≤ ( 1 + κ ) Vol ( K j ) \widetilde{V}_j\leq(1+\kappa)\operatorname{Vol}(K_j) V j ≤ ( 1 + κ ) Vol ( K j ) , as mentioned earlier (5.2.2). First term of the right side is easier to handle because we are bounding the good region of K ^ j \widehat{K}_j K j .
∑ j V ~ j ( 1 + η ) π j ( K ^ j ∖ B a d j ) ≤ ∑ j ( 1 + η ) ( 1 + κ ) Vol ( K j ) π j ( K ^ j ∖ B a d j ) = ( 1 + ε 32 ) ( 1 + ε 32 ) ∑ j Vol ( K ^ j ∖ B a d j ) ≤ ( 1 + ε 15 ) ∑ j Vol ( K ^ j ∖ B a d j ) = ( 1 + ε 15 ) F 0 ′ . (4) \begin{aligned}
\sum_j\widetilde{V}_j(1+\eta)\pi_j(\widehat{K}_j\setminus\mathrm{Bad}_j)\leq\sum_j(1+\eta)(1+\kappa)\operatorname{Vol}(K_j)\pi_j(\widehat{K}_j\setminus\mathrm{Bad}_j) \\
&=\left(1+\frac{\varepsilon}{32}\right)\left(1+\frac{\varepsilon}{32}\right)\sum_j\operatorname{Vol}(\widehat{K}_j\setminus\mathrm{Bad}_j) \\
&\leq\left(1+\frac{\varepsilon}{15}\right)\sum_j\operatorname{Vol}(\widehat{K}_j\setminus\mathrm{Bad}_j)=\left(1+\frac{\varepsilon}{15}\right)F'_0. \tag*{(4)}
\end{aligned} j ∑ V j ( 1 + η ) π j ( K j ∖ Bad j ) ≤ j ∑ ( 1 + η ) ( 1 + κ ) Vol ( K j ) π j ( K j ∖ Bad j ) = ( 1 + 32 ε ) ( 1 + 32 ε ) j ∑ Vol ( K j ∖ Bad j ) ≤ ( 1 + 15 ε ) j ∑ Vol ( K j ∖ Bad j ) = ( 1 + 15 ε ) F 0 ′ . (4)
The last equality follows from Equation (2) . For bounding the second term, we shall use the tail control guarantee of D j D_j D j .
∑ j V ~ j D j ( B a d j ) ≤ ∑ j ( 1 + κ ) Vol ( K j ) ⋅ 2 β \sum_j\widetilde{V}_jD_j(\mathrm{Bad}_j)\leq\sum_j(1+\kappa)\operatorname{Vol}(K_j)\cdot2\beta j ∑ V j D j ( Bad j ) ≤ j ∑ ( 1 + κ ) Vol ( K j ) ⋅ 2 β
≤ 2 ( 1 + ε 32 ) ε 32 M M F 0 \leq2\left(1+\frac{\varepsilon}{32}\right)\frac{\varepsilon}{32M}MF_0 ≤ 2 ( 1 + 32 ε ) 32 M ε M F 0
≤ 2 ( 1 + ε 32 ) ε 32 F 0 ′ 1 − ε / 32 < ε 15 F 0 ′ . (5) \leq2\left(1+\frac{\varepsilon}{32}\right)\frac{\varepsilon}{32}\frac{F'_0}{1-\varepsilon/32}<\frac{\varepsilon}{15}F'_0. \tag*{(5)} ≤ 2 ( 1 + 32 ε ) 32 ε 1 − ε /32 F 0 ′ < 15 ε F 0 ′ . (5)
The bound on F 0 F_0 F 0 is obtained from Claim 9 . Adding up the two different bounds, we get:
Λ ≤ ( 1 + ε 15 ) F 0 ′ + ε 15 F 0 ′ < ( 1 + ε 7 ) F 0 ′ . \Lambda\leq\left(1+\frac{\varepsilon}{15}\right)F'_0+\frac{\varepsilon}{15}F'_0<\left(1+\frac{\varepsilon}{7}\right)F'_0. Λ ≤ ( 1 + 15 ε ) F 0 ′ + 15 ε F 0 ′ < ( 1 + 7 ε ) F 0 ′ .
In the same spirit as above, consider the quantity Λ ( s ) : = ∑ j = 1 s V ~ j D j ( K ^ j ) \Lambda_{(s)}:=\sum_{j=1}^{s}\widetilde{V}_jD_j(\widehat{K}_j) Λ ( s ) := ∑ j = 1 s V j D j ( K j ) for any index s ∈ [ M ] s\in[M] s ∈ [ M ] . Observe that if p ← p s p\leftarrow p_s p ← p s is the sampling intensity and X ( s ) \mathcal{X}_{(s)} X ( s ) represents state of the bucket just after processing K s K_s K s , then by the same idea as Lemma 13 , we can say that
∣ X ( s ) ∣ ∼ Pois ( p s Λ ( s ) ) ∀ s ∈ [ M ] . |\mathcal{X}_{(s)}|\sim\operatorname{Pois}(p_s\Lambda_{(s)})\qquad\forall s\in[M]. ∣ X ( s ) ∣ ∼ Pois ( p s Λ ( s ) ) ∀ s ∈ [ M ] .
Claim 14 (Bounding Probability of Failp r o b _{\mathrm{prob}} prob ). Consider the event Fail p r o b _{\mathrm{prob}} prob , where the value p f i n a l p_{\mathrm{final}} p final falls lower than 1 / F 0 1/F_0 1/ F 0 . Then P [ F a i l p r o b ] < δ / 4 \mathbb{P}[\mathrm{Fail}_{\mathrm{prob}}]<\delta/4 P [ Fail prob ] < δ /4 .
Proof. Observe that by the bound obtained in Lemma 13 , we can say that:
2 Λ t h r e s h o l d < 2 ( 1 + ε / 7 ) t h r e s h o l d F 0 ′ ≤ F 0 . \frac{2\Lambda}{\mathrm{threshold}}<\frac{2(1+\varepsilon/7)}{\mathrm{threshold}}F'_0\leq F_0. threshold 2Λ < threshold 2 ( 1 + ε /7 ) F 0 ′ ≤ F 0 . Define the quantity L : = ⌈ log 2 2 Λ t h r e s h o l d ⌉ \mathcal{L}:=\left\lceil\log_2\frac{2\Lambda}{\mathrm{threshold}}\right\rceil L := ⌈ log 2 threshold 2Λ ⌉ . By this observation, we can say that L ≤ log 2 F 0 \mathcal{L}\leq\log_2F_0 L ≤ log 2 F 0 , which implies 2 − L ≥ 1 / F 0 2^{-\mathcal{L}}\geq1/F_0 2 − L ≥ 1/ F 0 . This would mean the event where p p p falls below 1 / F 0 1/F_0 1/ F 0 is contained as a subset
inside the event where p p p falls below 2 − L 2^{-\mathcal{L}} 2 − L . Our strategy will be therefore to bound the probability of this latter event.
Since the value of p p p can decrease below the above specified threshold while processing any of the M M M many convex bodies; we will need to make sure that this event can collectively happen during any of the M M M many situations with low probability. To do so, we isolate the event where p p p falls below the threshold after processing K s K_s K s for each s s s , individually bound these events and apply an union bound argument to finish the proof.
Define L ( s ) : = ⌈ log 2 2 Λ ( s ) t h r e s h o l d ⌉ \mathcal{L}_{(s)} := \left\lceil\log_2 \frac{2\Lambda_{(s)}}{\mathit{threshold}} \right\rceil L ( s ) := ⌈ log 2 threshold 2 Λ ( s ) ⌉ . By definition, we know that Λ ( s ) ≤ Λ \Lambda_{(s)} \leq\Lambda Λ ( s ) ≤ Λ for each s ∈ [ M ] s \in[M] s ∈ [ M ] . This would mean 2 − L ( s ) ≥ 2 − L 2^{-\mathcal{L}_{(s)}} \geq2^{-\mathcal{L}} 2 − L ( s ) ≥ 2 − L . Thus the event where p p p falls below 2 − L 2^{-\mathcal{L}} 2 − L after processing K s K_s K s ; is a subset of the event where p p p falls below 2 − L ( s ) 2^{-\mathcal{L}_{(s)}} 2 − L ( s ) after processing K s K_s K s . Therefore the event F a i l p r o b \mathbf{Fail}_{\mathrm{prob}} Fail prob is contained in the union of the following events.
F a i l p r o b ( s ) : = { p falls below 2 − L ( s ) after processing K s } ∀ s ∈ [ M ] . \mathbf{Fail}_{\mathrm{prob}}^{(s)} := \{p\text{ falls below }2^{-\mathcal{L}_{(s)}}\text{ after processing }K_s\}
\qquad\forall s \in[M]. Fail prob ( s ) := { p falls below 2 − L ( s ) after processing K s } ∀ s ∈ [ M ] .
By definition of L ( s ) \mathcal{L}_{(s)} L ( s ) , we obtain the following inequalities, which will be helpful in proving the claim. Our strategy moving forward, will be to individually bound the probability of these events, and then continue with our union bound strategy.
E [ ∣ X ( s ) ∣ ] = 2 − L ( s ) Λ ( s ) ≤ t h r e s h o l d 2 Λ ( s ) Λ ( s ) ≤ t h r e s h o l d 2 (6) \mathbb{E}[|\mathcal{X}_{(s)}|] = 2^{-\mathcal{L}_{(s)}}\Lambda_{(s)} \leq\frac{\mathit{threshold}}{2\Lambda_{(s)}}\Lambda_{(s)} \leq\frac{\mathit{threshold}}{2} \tag*{(6)} E [ ∣ X ( s ) ∣ ] = 2 − L ( s ) Λ ( s ) ≤ 2 Λ ( s ) threshold Λ ( s ) ≤ 2 threshold (6)
E [ ∣ X ( s ) ∣ ] ≥ 1 2 t h r e s h o l d 2 Λ ( s ) Λ ( s ) = t h r e s h o l d 4 (7) \mathbb{E}[|\mathcal{X}_{(s)}|] \geq\frac{1}{2}\frac{\mathit{threshold}}{2\Lambda_{(s)}}\Lambda_{(s)} = \frac{\mathit{threshold}}{4} \tag*{(7)} E [ ∣ X ( s ) ∣ ] ≥ 2 1 2 Λ ( s ) threshold Λ ( s ) = 4 threshold (7)
The value of p p p decreased below 2 − L ( s ) 2^{-\mathcal{L}_{(s)}} 2 − L ( s ) when processing K s K_s K s suggests that setting p ← 2 − L ( s ) p \leftarrow2^{-\mathcal{L}_{(s)}} p ← 2 − L ( s ) when processing K s K_s K s would cause the bucket to spill over. Since ∣ X ( s ) ∣ |\mathcal{X}_{(s)}| ∣ X ( s ) ∣ follows a Poisson distribution, an application of Chernoff bounds (Lemma 28) gives us the following.
P [ F a i l p r o b ( s ) ] = P [ ∣ X ( s ) ∣ > t h r e s h o l d : p ← 2 − L ( s ) ] ≤ P [ ∣ X ( s ) ∣ > 2 ⋅ E [ ∣ X ( s ) ∣ ] : p ← 2 − L ( s ) ] (by 6) ≤ exp ( − 1 2 ⋅ 2 E [ ∣ X ( s ) ∣ ] ) ≤ exp ( − t h r e s h o l d 16 ) < δ 4 M (by 7) \begin{aligned}
\mathbb{P}\left[\mathbf{Fail}_{\mathrm{prob}}^{(s)}\right] = \mathbb{P}\left[|\mathcal{X}_{(s)}| > \mathit{threshold}:p \leftarrow2^{-\mathcal{L}_{(s)}}\right] \\
&\leq\mathbb{P}\left[|\mathcal{X}_{(s)}| > 2\cdot\mathbb{E}[|\mathcal{X}_{(s)}|]:p \leftarrow2^{-\mathcal{L}_{(s)}}\right]\qquad\text{(by 6)} \\
&\leq\exp\left(-\frac{1}{2\cdot2}\mathbb{E}[|\mathcal{X}_{(s)}|]\right) \leq\exp\left(-\frac{\mathit{threshold}}{16}\right) < \frac{\delta}{4M}\qquad\text{(by 7)}
\end{aligned} P [ Fail prob ( s ) ] = P [ ∣ X ( s ) ∣ > threshold : p ← 2 − L ( s ) ] ≤ P [ ∣ X ( s ) ∣ > 2 ⋅ E [ ∣ X ( s ) ∣ ] : p ← 2 − L ( s ) ] (by 6) ≤ exp ( − 2 ⋅ 2 1 E [ ∣ X ( s ) ∣ ] ) ≤ exp ( − 16 threshold ) < 4 M δ (by 7)
Since the probability of p p p falling below 2 − L 2^{-\mathcal{L}} 2 − L when processing K s K_s K s is bounded by δ 4 M \frac{\delta}{4M} 4 M δ , this means the probability of p p p falling below 1 F 0 \frac{1}{F_0} F 0 1 is also bounded by δ 4 M \frac{\delta}{4M} 4 M δ , and this holds for each s ∈ [ M ] s \in[M] s ∈ [ M ] . By application of Union bound, that means p p p can fall below 1 F 0 \frac{1}{F_0} F 0 1 at any point during the algorithm, with probability at most δ 4 \frac{\delta}{4} 4 δ , as claimed. □
Conditioning on the high probability events. In the above proof, not only have we proved that p p p cannot fall below 1 / F 0 1/F_0 1/ F 0 with high probability; we have also established the value of p p p falling below 2 − L 2^{-\mathcal{L}} 2 − L itself is a low probability event. Thus, moving forward we shall condition all the other events on the event where p f i n a l p_{\mathrm{final}} p final stays above 2 − L 2^{-\mathcal{L}} 2 − L . Because in situations where we would need a control over p f i n a l p_{\mathrm{final}} p final , we could simply break those events into two sub-events: one where p f i n a l ≥ 2 − L p_{\mathrm{final}} \geq2^{-\mathcal{L}} p final ≥ 2 − L , and one where that does not happen. As the latter is already addressed above, we do not need to do so again.
Step IV. Bounding F a i l g o o d \mathbf{Fail}_{\mathrm{good}} Fail good : Deviations of the ‘Good’ Samples’ Count
In this section, we focus on the F a i l g o o d \mathbf{Fail}_{\mathrm{good}} Fail good event. If we manage to bound the probability of this event; that would tell us that the quantity E s t g o o d \mathsf{Est}_{\mathrm{good}} Est good would be a good estimation of F 0 ′ F'_0 F 0 ′ , which is one step closer to proving that the entire estimate itself will be a good estimate of F 0 ′ F'_0 F 0 ′ . The structure of proof will follow a structure similar to the proof of Claim 14. We open with formally defining the random quantity Est g o o d \operatorname{Est}_{\mathrm{good}} Est good , and break it into a sum of independent random variables. Using the conditioning of low-probability as mentioned in the previous section, combined with probabilistic tools such as concentration techniques and union bounds, we offer a bound for F 0 ′ F'_0 F 0 ′ .
Recall that Est g o o d \operatorname{Est}_{\mathrm{good}} Est good denotes the number of surviving samples from all the good sections. We can decompose this random quantity into a sum of M M M many random variables as follows: let Y j Y_j Y j denote the number of samples from K ^ j \ Bad j \widehat{K}_j\backslash\operatorname{Bad}_j K j \ Bad j for each j ∈ [ M ] j \in[M] j ∈ [ M ] . Using this notation, we can say that ∑ j Y j \sum_j Y_j ∑ j Y j is precisely equal to Est g o o d \operatorname{Est}_{\mathrm{good}} Est good .
Lemma 15 (Properties of Y j Y_j Y j ). The random variables ⟨ Y j : 1 ≤ j ≤ M ⟩ \langle Y_j : 1 \le j \le M\rangle ⟨ Y j : 1 ≤ j ≤ M ⟩ are mutually independent, and for each j ∈ [ M ] j \in[M] j ∈ [ M ] , we have:
Y j ∼ Pois ( p f i n a l V ~ j D j ( K ^ j \ Bad j ) ) . Y_j \sim\operatorname{Pois}\left(p_{\mathrm{final}}\widetilde{V}_j\mathcal{D}_j\left(\widehat{K}_j\backslash\operatorname{Bad}_j\right)\right). Y j ∼ Pois ( p final V j D j ( K j \ Bad j ) ) .
Proof. Recall the proof of Lemma 12 . Since K ^ j \ Bad j \widehat{K}_j\backslash\operatorname{Bad}_j K j \ Bad j is a measurable subset of K j K_j K j , again by Lemma 26 the random variable Y j Y_j Y j signifying number of surviving samples from K ^ j \ Bad j \widehat{K}_j\backslash\operatorname{Bad}_j K j \ Bad j would follow: Y j ∼ Pois ( p f i n a l V ~ j D ( K ^ j \ Bad j ) ) Y_j \sim\operatorname{Pois}\left(p_{\mathrm{final}}\widetilde{V}_j\mathcal{D}\left(\widehat{K}_j\backslash\operatorname{Bad}_j\right)\right) Y j ∼ Pois ( p final V j D ( K j \ Bad j ) ) as claimed. Independence of Y j Y_j Y j ’s follow once again since we use mutually independent sources of randomness for obtaining each Y j Y_j Y j .
Using the Poisson properties of Y j Y_j Y j we can better characterize the quantity Est g o o d \operatorname{Est}_{\mathrm{good}} Est good , and additionally we bound it’s expectation in the following lemma.
Lemma 16 (Properties of Est g o o d \operatorname{Est}_{\mathrm{good}} Est good ). Define Λ Y : = ∑ j V ~ j D j ( K ^ j \ Bad j ) \Lambda^Y := \sum_j \widetilde{V}_j\mathcal{D}_j(\widehat{K}_j\backslash\operatorname{Bad}_j) Λ Y := ∑ j V j D j ( K j \ Bad j ) . Then Est g o o d ∼ Pois ( p f i n a l Λ Y ) \operatorname{Est}_{\mathrm{good}} \sim\operatorname{Pois}(p_{\mathrm{final}}\Lambda^Y) Est good ∼ Pois ( p final Λ Y ) . Further, the quantity Λ Y \Lambda^Y Λ Y follows the following inequalities:
( 1 − ε 15 ) F 0 ′ ≤ Λ Y ≤ ( 1 + ε 15 ) F 0 ′ (1-\frac{\varepsilon}{15})F'_0 \le\Lambda^Y \le(1+\frac{\varepsilon}{15})F'_0 ( 1 − 15 ε ) F 0 ′ ≤ Λ Y ≤ ( 1 + 15 ε ) F 0 ′ .
Λ Y ≥ Λ 2 \Lambda^Y \ge\frac{\Lambda}{2} Λ Y ≥ 2 Λ .
[ ( 1 − ε 8 ) Λ Y , ( 1 + ε 8 ) Λ Y ] ⊂ [ ( 1 − 15 32 ε ) F 0 ′ , ( 1 + 15 32 ε ) F 0 ′ ] \left[(1-\frac{\varepsilon}{8})\Lambda^Y,(1+\frac{\varepsilon}{8})\Lambda^Y\right] \subset\left[(1-\frac{15}{32}\varepsilon)F'_0,(1+\frac{15}{32}\varepsilon)F'_0\right] [ ( 1 − 8 ε ) Λ Y , ( 1 + 8 ε ) Λ Y ] ⊂ [ ( 1 − 32 15 ε ) F 0 ′ , ( 1 + 32 15 ε ) F 0 ′ ] .
Proof. The Poisson property of Est g o o d \operatorname{Est}_{\mathrm{good}} Est good follows from the additivity property of Poisson random variables (Lemma 25 ). To prove the first inequality, observe that the upper bound can be obtained from the equation obtained earlier (4) . For the lower bound, we operate similarly, using the η \eta η -closeness combined with the lower bound on V ~ j \widetilde{V}_j V j (Section 5.2.2).
Λ Y ≤ ∑ j V ~ j ( 1 + η ) π j ( K ^ j \ Bad j ) ≤ ( 1 + ε 15 ) F 0 ′ \Lambda^Y \le\sum_j \widetilde{V}_j(1+\eta)\pi_j(\widehat{K}_j\backslash\operatorname{Bad}_j) \le\left(1+\frac{\varepsilon}{15}\right)F'_0 Λ Y ≤ j ∑ V j ( 1 + η ) π j ( K j \ Bad j ) ≤ ( 1 + 15 ε ) F 0 ′
Λ Y ≥ ∑ j V ~ j ( 1 − η ) π j ( K ^ j \ Bad j ) ≤ ( 1 − ε 15 ) F 0 ′ \Lambda^Y \ge\sum_j \widetilde{V}_j(1-\eta)\pi_j(\widehat{K}_j\backslash\operatorname{Bad}_j) \le\left(1-\frac{\varepsilon}{15}\right)F'_0 Λ Y ≥ j ∑ V j ( 1 − η ) π j ( K j \ Bad j ) ≤ ( 1 − 15 ε ) F 0 ′
For the bound between Λ Y \Lambda^Y Λ Y and Λ \Lambda Λ , we combine the inequalities obtained in Lemma 13 , in conjunction with the bounds we just proved.
Λ ≤ Λ Y + ∑ j V ~ j D j ( K ^ j ∩ Bad j ) < Λ Y + ε 15 F 0 ′ < 2 Λ Y \Lambda\le\Lambda^Y+\sum_j \widetilde{V}_j\mathcal{D}_j(\widehat{K}_j\cap\operatorname{Bad}_j)<\Lambda^Y+\frac{\varepsilon}{15}F'_0<2\Lambda^Y Λ ≤ Λ Y + j ∑ V j D j ( K j ∩ Bad j ) < Λ Y + 15 ε F 0 ′ < 2 Λ Y
where the last inequality follows due to the obtained lower bound on Λ Y \Lambda^Y Λ Y , as we know ε 15 < 1 − ε 15 \frac{\varepsilon}{15}<1-\frac{\varepsilon}{15} 15 ε < 1 − 15 ε . The third result follows directly from Lemma 16 .
Claim 17 (Bounding Probability of Failgood). Consider the event Failgood, where:
E s t g o o d ∉ [ ( 1 − 15 32 ε ) p f i n a l F 0 ′ , ( 1 + 15 32 ε ) p f i n a l F 0 ′ ] . \mathrm{Est}_{\mathrm{good}} \notin\left[\left(1-\frac{15}{32}\varepsilon\right)p_{\mathrm{final}}F'_0,\left(1+\frac{15}{32}\varepsilon\right)p_{\mathrm{final}}F'_0\right]. Est good ∈ / [ ( 1 − 32 15 ε ) p final F 0 ′ , ( 1 + 32 15 ε ) p final F 0 ′ ] . Then P [ F a i l g o o d ] < δ 4 \mathbb{P}[\mathrm{Fail}_{\mathrm{good}}] < \frac{\delta}{4} P [ Fail good ] < 4 δ .
Proof. Since the definition of F a i l g o o d \mathrm{Fail}_{\mathrm{good}} Fail good is dependent upon the random quantity p f i n a l p_{\mathrm{final}} p final , we need to apply an union bound over all the possible values of p f i n a l p_{\mathrm{final}} p final , which we know to be all the values 2 − t 2^{-t} 2 − t , where t t t is any non-negative integer at most L \mathcal{L} L . (The reasoning is the conditioned, mentioned previously in Section 5.2.3). Our strategy will therefore be to prove the claim for each of these possible values of p f i n a l p_{\mathrm{final}} p final , and then tie all of these bounds together via an union bound argument.
Say p f i n a l ← 2 − t p_{\mathrm{final}} \leftarrow2^{-t} p final ← 2 − t for some non-negative integer, at most L \mathcal{L} L . Since we know E s t g o o d \mathrm{Est}_{\mathrm{good}} Est good to follow a Poisson distribution, an application of Chernoff bounds give us the following.
P [ F a i l g o o d : p f i n a l ← 2 − t ] ≤ P [ E s t g o o d ∉ ( 1 ± ε 8 ) p f i n a l Λ Y : p f i n a l ← 2 − t ] \mathbb{P}[\mathrm{Fail}_{\mathrm{good}}:p_{\mathrm{final}}\leftarrow2^{-t}]
\leq\mathbb{P}\left[\mathrm{Est}_{\mathrm{good}}\notin\left(1\pm\frac{\varepsilon}{8}\right)p_{\mathrm{final}}\Lambda^{Y}:p_{\mathrm{final}}\leftarrow2^{-t}\right] P [ Fail good : p final ← 2 − t ] ≤ P [ Est good ∈ / ( 1 ± 8 ε ) p final Λ Y : p final ← 2 − t ]
(by Lemma 16 )
≤ 2 exp ( − ε 2 16 ( 8 + ε ) 2 − t Λ Y ) = 2 exp ( − ε 2 16 ( 8 + ε ) 2 − L Λ Y ⋅ 2 L − t ) \leq2\exp\left(-\frac{\varepsilon^2}{16(8+\varepsilon)}2^{-t}\Lambda^{Y}\right)
=2\exp\left(-\frac{\varepsilon^2}{16(8+\varepsilon)}2^{-\mathcal{L}}\Lambda^{Y}\cdot2^{\mathcal{L}-t}\right) ≤ 2 exp ( − 16 ( 8 + ε ) ε 2 2 − t Λ Y ) = 2 exp ( − 16 ( 8 + ε ) ε 2 2 − L Λ Y ⋅ 2 L − t )
≤ 2 exp ( − ε 2 16 ( 8 + ε ) t h r e s h o l d Λ 2 Λ ⋅ 2 L − t ) \leq2\exp\left(-\frac{\varepsilon^2}{16(8+\varepsilon)}\frac{\mathit{threshold}\,\Lambda}{2\Lambda}\cdot2^{\mathcal{L}-t}\right) ≤ 2 exp ( − 16 ( 8 + ε ) ε 2 2Λ threshold Λ ⋅ 2 L − t )
(by Item 2)
= 2 exp ( − ε 2 t h r e s h o l d 64 ( 8 + ε ) ⋅ 2 L − t ) . =2\exp\left(-\frac{\varepsilon^2\mathit{threshold}}{64(8+\varepsilon)}\cdot2^{\mathcal{L}-t}\right). = 2 exp ( − 64 ( 8 + ε ) ε 2 threshold ⋅ 2 L − t ) .
Denote the quantity c : = ε 2 t h r e s h o l d 64 ( 8 + ε ) c:=\frac{\varepsilon^2\mathit{threshold}}{64(8+\varepsilon)} c := 64 ( 8 + ε ) ε 2 threshold . Note that by substituting the value of t h r e s h o l d \mathit{threshold} threshold , we shall obtain c ≥ ln 2 c\geq\ln2 c ≥ ln 2 , i.e. e − c < 1 e^{-c}<1 e − c < 1 . Additionally we will also have c > ln 16 M δ c>\ln\frac{16M}{\delta} c > ln δ 16 M . All that remains for us to apply union bound over the above bounds for each possible value of t t t .
P [ F a i l g o o d ] ≤ ∑ t = 0 L P [ F a i l g o o d : p f i n a l ← 2 − t ] = ∑ t = 0 L 2 exp ( − c ⋅ 2 L − t ) ≤ ∑ s = 0 L 2 exp ( − c ⋅ 2 s ) (substitute s ← L − t ) \begin{aligned}
\mathbb{P}[\mathrm{Fail}_{\mathrm{good}}]
\leq\sum_{t=0}^{\mathcal{L}}\mathbb{P}[\mathrm{Fail}_{\mathrm{good}}:p_{\mathrm{final}}\leftarrow2^{-t}]
=\sum_{t=0}^{\mathcal{L}}2\exp\left(-c\cdot2^{\mathcal{L}-t}\right) \\
&\leq\sum_{s=0}^{\mathcal{L}}2\exp\left(-c\cdot2^s\right)
\qquad\text{(substitute }s\leftarrow\mathcal{L}-t\text{)}
\end{aligned} P [ Fail good ] ≤ t = 0 ∑ L P [ Fail good : p final ← 2 − t ] = t = 0 ∑ L 2 exp ( − c ⋅ 2 L − t ) ≤ s = 0 ∑ L 2 exp ( − c ⋅ 2 s ) (substitute s ← L − t )
≤ 2 ∑ s = 0 L ( e − c ) 2 s < 2 ∑ u ≥ 1 ( e − c ) u (well defined since e − c < 1 ) \leq2\sum_{s=0}^{\mathcal{L}}\left(e^{-c}\right)^{2^s}
<2\sum_{u\geq1}\left(e^{-c}\right)^u
\qquad\text{(well defined since }e^{-c}<1\text{)} ≤ 2 s = 0 ∑ L ( e − c ) 2 s < 2 u ≥ 1 ∑ ( e − c ) u (well defined since e − c < 1 )
≤ 2 exp ( − c ) ∑ u ≥ 0 exp ( − c ) u = 2 e − c 1 − e − c < 4 exp ( − c ) ≤ δ 4 M < δ 4 . \begin{aligned}
\leq2\exp(-c)\sum_{u\geq0}\exp(-c)^u
=\frac{2e^{-c}}{1-e^{-c}} \\
&<4\exp(-c)\leq\frac{\delta}{4M}<\frac{\delta}{4}.
\end{aligned} ≤ 2 exp ( − c ) u ≥ 0 ∑ exp ( − c ) u = 1 − e − c 2 e − c < 4 exp ( − c ) ≤ 4 M δ < 4 δ .
Step V. Bounding Failbad: Contribution of the ‘Bad’ Samples
We continue our routine of better understanding the contribution to the net estimate coming from the exceptional regions. Recall that E s t b a d \mathrm{Est}_{\mathrm{bad}} Est bad denotes the number of surviving samples from all the bad sections. We again decompose this random quantity into a sum of M M M many random variables as follows: let Z j Z_j Z j denote the number of samples from K ^ j ∩ B a d j \widehat{K}_j\cap\mathrm{Bad}_j K j ∩ Bad j for each j ∈ [ M ] j\in[M] j ∈ [ M ] . Using this notation, we can say that ∑ j Z j \sum_j Z_j ∑ j Z j is precisely equal to E s t b a d \mathrm{Est}_{\mathrm{bad}} Est bad .
Lemma 18 (Properties of Z j Z_j Z j ). The random variables ⟨ Z j : 1 ≤ j ≤ M ⟩ \langle Z_j : 1 \le j \le M\rangle ⟨ Z j : 1 ≤ j ≤ M ⟩ are mutually independent, and for each j ∈ [ M ] j \in[M] j ∈ [ M ] , we have:
Z j ∼ Pois ( p f i n a l V ~ j D j ( K ^ j ∩ B a d j ) ) . Z_j \sim\operatorname{Pois}\left(p_{\mathrm{final}}\widetilde{V}_j\mathcal{D}_j\left(\widehat{K}_j \cap\mathrm{Bad}_j\right)\right). Z j ∼ Pois ( p final V j D j ( K j ∩ Bad j ) ) . Proof. Follows the same structure as Lemma 15 , since K ^ j ∩ B a d j \widehat{K}_j \cap\mathrm{Bad}_j K j ∩ Bad j is a measurable subset of K j K_j K j .
Lemma 19 (Properties of E s t b a d \mathrm{Est}_{\mathrm{bad}} Est bad ). Define Λ Z : = ∑ j V ~ j D j ( K ^ j ∩ B a d j ) \Lambda^Z := \sum_j \widetilde{V}_j\mathcal{D}_j(\widehat{K}_j \cap\mathrm{Bad}_j) Λ Z := ∑ j V j D j ( K j ∩ Bad j ) . Then E s t b a d ∼ Pois ( p f i n a l Λ Z ) \mathrm{Est}_{\mathrm{bad}} \sim\operatorname{Pois}(p_{\mathrm{final}}\Lambda^Z) Est bad ∼ Pois ( p final Λ Z ) . Further, the quantity Λ Z \Lambda^Z Λ Z obeys the following inequalities:
Λ Z ≤ ε 15 F 0 ′ \Lambda^Z \le\frac{\varepsilon}{15}F'_0 Λ Z ≤ 15 ε F 0 ′ .
( 1 + ε 8 ) Λ Z ≤ 15 32 ε F 0 ′ \left(1+\frac{\varepsilon}{8}\right)\Lambda^Z \le\frac{15}{32}\varepsilon F'_0 ( 1 + 8 ε ) Λ Z ≤ 32 15 ε F 0 ′ .
Proof. Follow along the argument of Lemma 16 to obtain the Poisson properties of E s t b a d \mathrm{Est}_{\mathrm{bad}} Est bad . The inequalities have also been proved previously: the first one has been proved in Equation (5) , and the second one can be obtained by substituting the upper bound for Λ Z \Lambda^Z Λ Z in the left side expression.
Claim 20 (Bounding Probability of F a i l b a d \mathrm{Fail}_{\mathrm{bad}} Fail bad ). Consider the event F a i l b a d \mathrm{Fail}_{\mathrm{bad}} Fail bad , where the quantity E s t b a d \mathrm{Est}_{\mathrm{bad}} Est bad takes a value larger than 15 32 ε p f i n a l F 0 ′ \frac{15}{32}\varepsilon p_{\mathrm{final}}F'_0 32 15 ε p final F 0 ′ . Then P [ F a i l b a d ] < δ 4 \mathbb{P}[\mathrm{Fail}_{\mathrm{bad}}] < \frac{\delta}{4} P [ Fail bad ] < 4 δ .
Proof. Following the proof structure of Claim 17 , we would like to apply an union bound argument by individually bounding the probability of F a i l b a d \mathrm{Fail}_{\mathrm{bad}} Fail bad conditioned under each of the possible values for p f i n a l p_{\mathrm{final}} p final .
Fix a value of p ← 2 − t p \leftarrow2^{-t} p ← 2 − t , where t t t is a non-negative integer at most L \mathcal{L} L . We shall apply Chernoff bounds, with an additional layer of Poisson additivity (Lemma 25 ) applied beforehand. We replace E s t b a d \mathrm{Est}_{\mathrm{bad}} Est bad , which follows Pois ( p f i n a l Λ Z ) \operatorname{Pois}(p_{\mathrm{final}}\Lambda^Z) Pois ( p final Λ Z ) , by a random variable W ∼ Pois ( p f i n a l ε 15 F 0 ′ ) W \sim\operatorname{Pois}\left(p_{\mathrm{final}}\frac{\varepsilon}{15}F'_0\right) W ∼ Pois ( p final 15 ε F 0 ′ ) . The monotonicity bound is applicable here, since we have proved that Λ Z ≤ ε 15 F 0 ′ \Lambda^Z \le\frac{\varepsilon}{15}F'_0 Λ Z ≤ 15 ε F 0 ′ above (Lemma 19 ).
P [ F a i l b a d : p f i n a l ← 2 − t ] = P [ E s t b a d > 15 32 ε p f i n a l F 0 ′ : p f i n a l ← 2 − t ] ≤ P [ W > 15 2 32 E [ W ] : W ∼ Pois ( 2 − t ε 15 F 0 ′ ) ] ≤ P [ W > 7 E [ W ] : W ∼ Pois ( 2 − t ε 15 F 0 ′ ) ] ≤ exp ( − 6 2 2 ⋅ 7 2 − t ε 15 F 0 ′ ) = exp ( − 6 ε 35 2 − t F 0 ′ ) ≤ exp ( − 6 ε t h r e s h o l d 35 F 0 ′ 2 Λ ⋅ 2 L − t ) ≤ exp ( − 3 ε t h r e s h o l d 35 1 1 + ε / 7 ⋅ 2 L − t ) (by xref‘Lemma 13‘) ≤ exp ( − d ⋅ 2 L − t ) , \begin{aligned}
\mathbb{P}\left[\mathrm{Fail}_{\mathrm{bad}} : p_{\mathrm{final}} \leftarrow2^{-t}\right]
&= \mathbb{P}\left[\mathrm{Est}_{\mathrm{bad}} > \frac{15}{32}\varepsilon p_{\mathrm{final}}F'_0 : p_{\mathrm{final}} \leftarrow2^{-t}\right] \\
&\le\mathbb{P}\left[W > \frac{15^2}{32}\mathbb{E}[W] : W \sim\operatorname{Pois}\left(2^{-t}\frac{\varepsilon}{15}F'_0\right)\right] \\
&\le\mathbb{P}\left[W > 7\mathbb{E}[W] : W \sim\operatorname{Pois}\left(2^{-t}\frac{\varepsilon}{15}F'_0\right)\right] \\
&\le\exp\left(-\frac{6^2}{2\cdot7}2^{-t}\frac{\varepsilon}{15}F'_0\right)
= \exp\left(-\frac{6\varepsilon}{35}2^{-t}F'_0\right) \\
&\le\exp\left(-\frac{6\varepsilon\,\mathrm{threshold}}{35}\frac{F'_0}{2\Lambda}\cdot2^{\mathcal{L}-t}\right) \\
&\le\exp\left(-\frac{3\varepsilon\,\mathrm{threshold}}{35}\frac{1}{1+\varepsilon/7}\cdot2^{\mathcal{L}-t}\right)
\qquad\text{(by {xref}`Lemma 13`)} \\
&\le\exp\left(-d\cdot2^{\mathcal{L}-t}\right),
\end{aligned} P [ Fail bad : p final ← 2 − t ] = P [ Est bad > 32 15 ε p final F 0 ′ : p final ← 2 − t ] ≤ P [ W > 32 1 5 2 E [ W ] : W ∼ Pois ( 2 − t 15 ε F 0 ′ ) ] ≤ P [ W > 7 E [ W ] : W ∼ Pois ( 2 − t 15 ε F 0 ′ ) ] ≤ exp ( − 2 ⋅ 7 6 2 2 − t 15 ε F 0 ′ ) = exp ( − 35 6 ε 2 − t F 0 ′ ) ≤ exp ( − 35 6 ε threshold 2Λ F 0 ′ ⋅ 2 L − t ) ≤ exp ( − 35 3 ε threshold 1 + ε /7 1 ⋅ 2 L − t ) (by xref ‘Lemma 13‘) ≤ exp ( − d ⋅ 2 L − t ) , where d : = 3 ε t h r e s h o l d 5 ( ε + 7 ) d := \frac{3\varepsilon\,\mathrm{threshold}}{5(\varepsilon+7)} d := 5 ( ε + 7 ) 3 ε threshold . Again by the choice of value for t h r e s h o l d \mathrm{threshold} threshold , we have d ≥ ln 2 d \ge\ln2 d ≥ ln 2 , i.e. e − d < 1 e^{-d} < 1 e − d < 1 . Additionally we will also have d ≥ ln 8 δ d \ge\ln\frac{8}{\delta} d ≥ ln δ 8 . We use an union bound argument, similar to the one used
in Claim 17 .
P [ F a i l b a d ] ≤ ∑ t = 0 L P [ F a i l b a d : p f i n a l ← 2 − t ] ≤ exp ( − d ⋅ 2 L − t ) ≤ ∑ s = 0 L exp ( − d ⋅ 2 s ) = ∑ s = 0 L ( e − d ) 2 s (substituting s ← L − t ) < ∑ u ≥ 1 ( e − d ) u ≤ e − d ∑ u ≥ 0 ( e − d ) s = e − d 1 − e − d < 2 exp ( − d ) < δ 4 . \begin{aligned}
\mathbb{P}[\mathrm{Failbad}] \le\sum_{t=0}^{\mathcal{L}} \mathbb{P}[\mathrm{Failbad}: p_{\mathrm{final}} \leftarrow2^{-t}] \le\exp\left(-d \cdot2^{\mathcal{L}-t}\right) \\
&\le\sum_{s=0}^{\mathcal{L}} \exp(-d \cdot2^s) = \sum_{s=0}^{\mathcal{L}} \left(e^{-d}\right)^{2^s}
\qquad\text{(substituting }s \leftarrow\mathcal{L}-t\text{)} \\
&< \sum_{u\ge1} \left(e^{-d}\right)^u \\
&\le e^{-d}\sum_{u\ge0}\left(e^{-d}\right)^s = \frac{e^{-d}}{1-e^{-d}} \\
&< 2\exp(-d)<\frac{\delta}{4}.
\end{aligned} P [ Failbad ] ≤ t = 0 ∑ L P [ Failbad : p final ← 2 − t ] ≤ exp ( − d ⋅ 2 L − t ) ≤ s = 0 ∑ L exp ( − d ⋅ 2 s ) = s = 0 ∑ L ( e − d ) 2 s (substituting s ← L − t ) < u ≥ 1 ∑ ( e − d ) u ≤ e − d u ≥ 0 ∑ ( e − d ) s = 1 − e − d e − d < 2 exp ( − d ) < 4 δ .
Time and Space Complexities of Alpona
In this section, we analyze the costs of the volume-estimation and point-sampling oracles and then combine them with the operations of Algorithm 1. Throughout, time complexity denotes the number of calls to the membership oracles of the convex bodies, each counted at unit cost. The layout of the section is as follows. We first derive the complexity of Alpona as a function of the complexities of volume-estimation and point-sampling oracles (§ 6.1 ). In subsequent subsections, we instantiate the oracles with their actual complexities (§ 6.2.1 and § 6.2.2 ), combine them to obtain the complexity of Alpona under this instantiation (§ 6.2 ). And finally discuss the main ideas behind our improved walk length for Hit-and-Run (§ 6.3 ).
With the above in mind, we let T v o l T_{\mathrm{vol}} T vol , S v o l S_{\mathrm{vol}} S vol denote the time and auxiliary space of one invocation of ComputeVolume, respectively, and T s a m p T_{\mathrm{samp}} T samp , S s a m p S_{\mathrm{samp}} S samp denote the time and auxiliary space of one invocation of GenerateSamples, respectively.
Generic Complexity of Alpona
We deduce the complexity of Alpona by segregating the algorithm’s workflow in the following four essential components.
Removal. Recall that the algorithm maintains at most t h r e s h o l d = ⌈ 576 ε 2 log 16 M δ ⌉ \mathrm{threshold}=\left\lceil\frac{576}{\varepsilon^2}\log\frac{16M}{\delta}\right\rceil threshold = ⌈ ε 2 576 log δ 16 M ⌉ points in X \mathcal{X} X . In each of its M M M iterations, the removal step (Line 7 of Algorithm 1) tests at most t h r e s h o l d \mathrm{threshold} threshold stored points for membership in the current body. Hence all removal steps together require O ( M ⋅ t h r e s h o l d ) O(M\cdot\mathrm{threshold}) O ( M ⋅ threshold ) membership queries.
Volume Estimation. For the volume-estimation step (Line 8), the algorithm invokes ComputeVolume once for each of the M M M bodies, with parameters ε 32 \frac{\varepsilon}{32} 32 ε and δ 4 M \frac{\delta}{4M} 4 M δ . Consequently, the total time invested by Alpona towards for volume estimation is
O ( M T v o l ( ε 32 , δ 4 M , n , r , R ) ) . O\left(MT_{\mathrm{vol}}\left(\frac{\varepsilon}{32},\frac{\delta}{4M},n,r,R\right)\right). O ( M T vol ( 32 ε , 4 M δ , n , r , R ) ) .
Halving. Each execution of the halving step (Lines 10–12) examines at most threshold stored points and requires O ( threshold ) O(\texttt{threshold}) O ( threshold ) operations. By the bound on the event F a i l p r o b \mathrm{Fail}_{\mathrm{prob}} Fail prob in the correctness analysis, with probability at least 1 − δ / 4 1-\delta/4 1 − δ /4 (Claim 14) the total number of halvings is at most log F 0 \log F_0 log F 0 . Thus, on this event, their total cost is O ( threshold ⋅ log F 0 ) O(\texttt{threshold}\cdot\log F_0) O ( threshold ⋅ log F 0 ) .
Sampling. Finally, at most threshold points are inserted during any one iteration (Lines 13–15), so the algorithm makes at most M ⋅ threshold M\cdot\texttt{threshold} M ⋅ threshold calls to G e n e r a t e S a m p l e s \mathrm{GenerateSamples} GenerateSamples in total, with parameters ε 32 , ε 32 M \frac{\varepsilon}{32},\frac{\varepsilon}{32M} 32 ε , 32 M ε . Therefore the total time invested by Alpona towards for volume estimation is
O ( M ⋅ threshold ⋅ T s a m p ( ε 32 , ε 32 M , n , r , R ) ) . O\left(M\cdot\texttt{threshold}\cdot T_{\mathrm{samp}}\left(\frac{\varepsilon}{32},\frac{\varepsilon}{32M},n,r,R\right)\right). O ( M ⋅ threshold ⋅ T samp ( 32 ε , 32 M ε , n , r , R ) ) .
Total time complexity. Combining all these contributions, with probability at least 1 − δ / 4 1-\delta/4 1 − δ /4 , the total running time is
O ( M ⋅ threshold + threshold ⋅ log F 0 + M ⋅ T v o l ( ε 32 , δ 4 M , n , r , R ) + M ⋅ threshold ⋅ T s a m p ( ε 32 , ε 32 M , n , r , R ) ) . (8) O\left(M\cdot\texttt{threshold}+\texttt{threshold}\cdot\log F_0+M\cdot T_{\mathrm{vol}}\left(\frac{\varepsilon}{32},\frac{\delta}{4M},n,r,R\right)
+M\cdot\texttt{threshold}\cdot T_{\mathrm{samp}}\left(\frac{\varepsilon}{32},\frac{\varepsilon}{32M},n,r,R\right)\right). \tag*{(8)} O ( M ⋅ threshold + threshold ⋅ log F 0 + M ⋅ T vol ( 32 ε , 4 M δ , n , r , R ) + M ⋅ threshold ⋅ T samp ( 32 ε , 32 M ε , n , r , R ) ) . (8)
Recall from Lines 1–2 of Algorithm 1 that
threshold = ⌈ 576 ε 2 log 16 M δ ⌉ and F 0 ≤ ∣ Ω ∣ , \texttt{threshold}=\left\lceil\frac{576}{\varepsilon^2}\log\frac{16M}{\delta}\right\rceil
\qquad\text{and}\qquad
F_0\leq|\Omega|, threshold = ⌈ ε 2 576 log δ 16 M ⌉ and F 0 ≤ ∣Ω∣ ,
where each convex body K i K_i K i is assumed to be a subset of Ω ⊆ R n \Omega\subseteq\mathbb{R}^n Ω ⊆ R n . Since T s a m p ≥ 1 T_{\mathrm{samp}}\geq1 T samp ≥ 1 , the term M ⋅ threshold M\cdot\texttt{threshold} M ⋅ threshold is dominated by M ⋅ threshold ⋅ T s a m p M\cdot\texttt{threshold}\cdot T_{\mathrm{samp}} M ⋅ threshold ⋅ T samp . Substituting these values in Equation (8) and collecting the terms that contain threshold, the total running time of Alpona is
O ( 1 ε 2 log M δ ⋅ [ log ∣ Ω ∣ + M ⋅ T s a m p ( ε 32 , ε 32 M , n , r , R ) ] + M ⋅ T v o l ( ε 32 , δ 4 M , n , r , R ) ) . O\left(\frac{1}{\varepsilon^2}\log\frac{M}{\delta}\cdot\left[\log|\Omega|+M\cdot T_{\mathrm{samp}}\left(\frac{\varepsilon}{32},\frac{\varepsilon}{32M},n,r,R\right)\right]+M\cdot T_{\mathrm{vol}}\left(\frac{\varepsilon}{32},\frac{\delta}{4M},n,r,R\right)\right). O ( ε 2 1 log δ M ⋅ [ log ∣Ω∣ + M ⋅ T samp ( 32 ε , 32 M ε , n , r , R ) ] + M ⋅ T vol ( 32 ε , 4 M δ , n , r , R ) ) .
Space complexity. For space, the bucket contains at most threshold points of R n \mathbb{R}^n R n , and hence occupies O ( n ⋅ threshold ) O(n\cdot\texttt{threshold}) O ( n ⋅ threshold ) real-coordinate storage locations. The volume and sampling oracles are called sequentially, so their workspaces may be reused. The overall auxiliary space is therefore
O ( S v o l ( δ 4 M , n ) + S s a m p + n ε 2 log M δ ) . O\left(S_{\mathrm{vol}}\left(\frac{\delta}{4M},n\right)+S_{\mathrm{samp}}+\frac{n}{\varepsilon^2}\log\frac{M}{\delta}\right). O ( S vol ( 4 M δ , n ) + S samp + ε 2 n log δ M ) .
real words.
Complexity of a Practical Instantiation of
First, we derive the time and space complexities for each of the PAC volume estimation and approximate sampling oracles, namely Gaussian cooling and Hit-and-Run used to instantiate Alpona. Then, we derive the final time and space complexity for this instantiation.
Complexity of the PAC Volume Estimation Oracle: Gaussian Cooling
We instantiate C o m p u t e V o l u m e \mathrm{ComputeVolume} ComputeVolume with the Gaussian-cooling approach of Cousins and Vempala [ [9 ] , under the geometric normalization assumed for our ( r , R ) (r,R) ( r , R ) -fat bodies. The implementation requires the appropriate interior-point and radius information.
Time complexity. By [9 Theorem 1.1] , ComputeVolume returns a ( 1 ± κ ) (1 \pm\kappa) ( 1 ± κ ) -approximation with probability at least 1 − δ v 1-\delta_v 1 − δ v , using
T v o l ( κ , δ v , n , r , R ) = O ( max { n 3 , n 2 ( R / r ) 2 } κ 2 log 2 n log 2 1 κ log 2 n κ log 1 δ v ) (9) T_{\mathrm{vol}}(\kappa,\delta_v,n,r,R)=O\left(\frac{\max\{n^3,n^2(R/r)^2\}}{\kappa^2}\log^2 n\log^2\frac{1}{\kappa}\log^2\frac{n}{\kappa}\log\frac{1}{\delta_v}\right) \tag*{(9)} T vol ( κ , δ v , n , r , R ) = O ( κ 2 max { n 3 , n 2 ( R / r ) 2 } log 2 n log 2 κ 1 log 2 κ n log δ v 1 ) (9)
membership-oracle queries.
Space complexity. For the space bound, observe that the next temperature in Step 2(b) of [9 ] , Figure 1 can be computed before generating the points in Step 2(a). We generate these points one at a time, retaining the current point of the walk, and update the sum in Step 2(c) as each point is generated. We also update the product in Step 3 after each cooling phase. Thus each run uses O ( n ) O(n) O ( n ) real words. Running the confidence-boosting repetitions sequentially and storing their final estimates therefore gives
S v o l ( δ v , n ) = O ( n + log 1 δ v ) S_{\mathrm{vol}}(\delta_v,n)=O\left(n+\log\frac{1}{\delta_v}\right) S vol ( δ v , n ) = O ( n + log δ v 1 )
real words.
Complexity of the Approximate Point Sampling Oracle: Hit-and-Run
We instantiate GenerateSamples using Hit-and-Run, started from an interior point x 0 x_0 x 0 at distance d 0 = dist ( x 0 , ∂ K ) > 0 d_0=\operatorname{dist}(x_0,\partial K)>0 d 0 = dist ( x 0 , ∂ K ) > 0 from the boundary.
Space complexity. Let us show what S s a m p S_{\mathrm{samp}} S samp is first. A walk retains only its current point, direction, proposed point, and a few scalars, so it is just O ( n ) O(n) O ( n ) real words.
Time complexity. Now we move on to T s a m p T_{\mathrm{samp}} T samp . First, we recall the almost-ℓ ∞ \ell_\infty ℓ ∞ guarantee and the mixing result that determine the number of steps required. Note that the algorithm uses S = K S=K S = K , a convex body, and the conditions2
π K ( Bad η ) ≤ β , D K ( Bad η ) ≤ 2 β . (10) \pi_K(\operatorname{Bad}_{\eta})\le\beta,\qquad D_K(\operatorname{Bad}_{\eta})\le2\beta. \tag*{(10)} π K ( Bad η ) ≤ β , D K ( Bad η ) ≤ 2 β . (10)
along with the following parameter assignments in line 4:
η = ε 32 , β = ε 32 M . (11) \eta=\frac{\varepsilon}{32},\qquad\beta=\frac{\varepsilon}{32M}. \tag*{(11)} η = 32 ε , β = 32 M ε . (11)
Here, Bad η = Bad t , η \operatorname{Bad}_{\eta}=\operatorname{Bad}_{t,\eta} Bad η = Bad t , η denotes the exceptional set of the distribution D t D_t D t after t t t Hit-and-Run steps. We drop t t t when it is clear from the context. We now present three bounds on t t t .
(i) The LV bound. Thus, we retrieve the sufficient bound (we call this the LV bound) on the number of mixing step as follows:
t > 10 11 n 3 ( R r ) 2 [ log 2 R d 0 + 2 log 32 ε + log M ] . (12) t>10^{11}n^3\left(\frac{R}{r}\right)^2\left[\log\frac{2R}{d_0}+2\log\frac{32}{\varepsilon}+\log M\right]. \tag*{(12)} t > 1 0 11 n 3 ( r R ) 2 [ log d 0 2 R + 2 log ε 32 + log M ] . (12)
(ii) The KV bound. Now, for our required values of η \eta η and β \beta β , the LV bound carries a factor n 3 n^3 n 3 in the accuracy and stream-length terms. The most natural question then is,
can we improve their dependence on the dimension?
The spectral-gap bound of Kook and Vempala gives us a way to investigate this. Let us first see what follows directly from their result. We show in Section C.4 that using the spectral-gap bound of Kook and Vempala [20 Theorem 1.1] , combined with the convex-domain diameter bound [31 Theorem 5.10] and truncation of the first-step density3 , we can get the sufficient point-start bound (we call this the KV bound)
t ≥ 1 + O ( n 3 ( R r ) 2 [ log 32 R d 0 + log 32 ε + log M ] ) . (13) t \ge1 + O\left(n^3\left(\frac{R}{r}\right)^2\left[\log\frac{32R}{d_0}+\log\frac{32}{\varepsilon}+\log M\right]\right). \tag*{(13)} t ≥ 1 + O ( n 3 ( r R ) 2 [ log d 0 32 R + log ε 32 + log M ] ) . (13)
Note that this also gives both bounds in Equation (10) .
(iii) Our bound. It turns out that the KV bound still gives the same complexity bounds of our algorithm for our parameters as the LV bound (see comparison below). In Section C, we show that for our choice of parameters for η \eta η and β \beta β , we can obtain the following better bound by doing a more careful analysis of the whole walk.
Theorem 21 (Bound on the Walk length for the Sampling Subroutine of Alpona). With η = ε 32 \eta= \frac{\varepsilon}{32} η = 32 ε and β = ε 32 M \beta= \frac{\varepsilon}{32M} β = 32 M ε , both bounds in Equation (10) can be obtained in
t = 1 + ⌊ n / 2 ⌋ + O ( n 2 ( R r ) 2 [ n log 32 R d 0 + log 32 ε + log M ] ) (14) t = 1 + \lfloor n/2 \rfloor+ O\left(n^2\left(\frac{R}{r}\right)^2\left[n\log\frac{32R}{d_0}+\log\frac{32}{\varepsilon}+\log M\right]\right) \tag*{(14)} t = 1 + ⌊ n /2 ⌋ + O ( n 2 ( r R ) 2 [ n log d 0 32 R + log ε 32 + log M ] ) (14) Hit and Run steps.
We describe the technical challenges and new techniques developed to prove this result in § 6.3 .
Final Time and Space Complexity for Union Volume Estimation
We now substitute the subroutine costs of § 6.2.1 and § 6.2.2 into Equation (8) . By substituting the LV bound for T s a m p T_{\mathrm{samp}} T samp and using Equation (9) for T v o l T_{\mathrm{vol}} T vol in Equation (8) we get the following running time for Alpona:
O ( 1 ε 2 log M δ ⋅ [ log ∣ Ω ∣ + M ⋅ n 3 ( R / r ) 2 [ log 2 R d 0 + log 32 ε + log M ] + M ⋅ max { n 3 , n 2 ( R / r ) 2 } ε 2 log 2 n log 2 32 ε log 2 32 n ε log 4 M δ ] ) . O\left(\frac{1}{\varepsilon^2}\log\frac{M}{\delta}\cdot\left[\log|\Omega|+M\cdot n^3(R/r)^2\left[\log\frac{2R}{d_0}+\log\frac{32}{\varepsilon}+\log M\right]+M\cdot\frac{\max\{n^3,n^2(R/r)^2\}}{\varepsilon^2}\log^2 n\log^2\frac{32}{\varepsilon}\log^2\frac{32n}{\varepsilon}\log\frac{4M}{\delta}\right]\right). O ( ε 2 1 log δ M ⋅ [ log ∣Ω∣ + M ⋅ n 3 ( R / r ) 2 [ log d 0 2 R + log ε 32 + log M ] + M ⋅ ε 2 max { n 3 , n 2 ( R / r ) 2 } log 2 n log 2 ε 32 log 2 ε 32 n log δ 4 M ] ) .
Plugging in the KV bound instead, we get the time complexity to be
O ( 1 ε 2 log M δ ⋅ [ log ∣ Ω ∣ + M n 3 ( R / r ) 2 [ log 32 R d 0 + log 32 ε + log M ] + M ⋅ max { n 3 , n 2 ( R / r ) 2 } ε 2 log 2 n log 2 32 ε log 2 32 n ε log 4 M δ ] ) \mathcal{O}\left(\frac{1}{\varepsilon^2}\log\frac{M}{\delta}\cdot\left[\log|\Omega|+Mn^3(R/r)^2\left[\log\frac{32R}{d_0}+\log\frac{32}{\varepsilon}+\log M\right]+M\cdot\frac{\max\{n^3,n^2(R/r)^2\}}{\varepsilon^2}\log^2 n\log^2\frac{32}{\varepsilon}\log^2\frac{32n}{\varepsilon}\log\frac{4M}{\delta}\right]\right) O ( ε 2 1 log δ M ⋅ [ log ∣Ω∣ + M n 3 ( R / r ) 2 [ log d 0 32 R + log ε 32 + log M ] + M ⋅ ε 2 max { n 3 , n 2 ( R / r ) 2 } log 2 n log 2 ε 32 log 2 ε 32 n log δ 4 M ] )
Finally, substituting the walk length of Theorem 21 back into the complexity calculations, this gives us a runtime requirement of:
O ( 1 ε 2 log M δ ⋅ [ log ∣ Ω ∣ + M n + M n 2 ( R / r ) 2 ] [ n log 32 R d 0 + log 32 ε + log M ] + M ⋅ max { n 3 , n 2 ( R / r ) 2 } ε 2 log 2 n log 2 32 ε log 2 32 n ε log 4 M δ ) \mathcal{O}\left(\frac{1}{\varepsilon^2}\log\frac{M}{\delta}\cdot\left[\log|\Omega|+Mn+Mn^2(R/r)^2\right]\left[n\log\frac{32R}{d_0}+\log\frac{32}{\varepsilon}+\log M\right]+M\cdot\frac{\max\{n^3,n^2(R/r)^2\}}{\varepsilon^2}\log^2 n\log^2\frac{32}{\varepsilon}\log^2\frac{32n}{\varepsilon}\log\frac{4M}{\delta}\right) O ( ε 2 1 log δ M ⋅ [ log ∣Ω∣ + M n + M n 2 ( R / r ) 2 ] [ n log d 0 32 R + log ε 32 + log M ] + M ⋅ ε 2 max { n 3 , n 2 ( R / r ) 2 } log 2 n log 2 ε 32 log 2 ε 32 n log δ 4 M )
Overall complexity. Instantiating ComputeVolume and GenerateSamples with the algorithm from [9 ] and Hit-and-Run respectively, and using the better walk length bound from Theorem 21, we can now state a concrete space and time complexity for Alpona. We also replace some multiplicative constants inside logs with additive ones.
Time Complexity:
O ( 1 ε 2 log M δ ⋅ ( log ∣ Ω ∣ + M n 2 ( R / r ) 2 [ n log 1 + R d 0 + log 1 ε + log M ] + M ⋅ max { n 3 , n 2 ( R / r ) 2 } ε 2 log 2 n log 2 1 ε log 2 1 + n ε log M δ ) \mathcal{O}(\frac{1}{\varepsilon^2}\log\frac{M}{\delta}\cdot(\log|\Omega|+Mn^2(R/r)^2[n\log\frac{1+R}{d_0}+\log\frac{1}{\varepsilon}+\log M]+M\cdot\frac{\max\{n^3,n^2(R/r)^2\}}{\varepsilon^2}\log^2 n\log^2\frac{1}{\varepsilon}\log^2\frac{1+n}{\varepsilon}\log\frac{M}{\delta}) O ( ε 2 1 log δ M ⋅ ( log ∣Ω∣ + M n 2 ( R / r ) 2 [ n log d 0 1 + R + log ε 1 + log M ] + M ⋅ ε 2 max { n 3 , n 2 ( R / r ) 2 } log 2 n log 2 ε 1 log 2 ε 1 + n log δ M )
Space Complexity:
O ( n ε 2 log M δ + log 4 M δ ) real words \mathcal{O}\left(\frac{n}{\varepsilon^2}\log\frac{M}{\delta}+\log\frac{4M}{\delta}\right)\ \text{real words} O ( ε 2 n log δ M + log δ 4 M ) real words
Improved runtime of Alpona using Theorem 21 : Let us see what improvements this gives for the running time of Alpona. Suppose R / r R/r R / r and R / d 0 R/d_0 R / d 0 are both O ( 1 ) O(1) O ( 1 ) , and fix ε \varepsilon ε , δ \delta δ . Since we are using the volume computation algorithm of Cousins and Vempala [2018, Theorem 1.1], note that after rescaling the inball to have radius one, the constant aspect ratio gives the second-moment bound required by their theorem. Then with the parameters above, its cost is
T v o l = O ( n 3 log 4 n log M ) . T_{\mathrm{vol}}=\mathcal{O}\left(n^3\log^4 n\log M\right). T vol = O ( n 3 log 4 n log M ) .
Then both the LV bound in Equation (12) and the KV bound in Equation (13) give a total running-time bound of
O ( M [ n 3 log 4 n log M + n 3 ( log M ) 2 ] ) . \mathcal{O}\left(M\left[n^3\log^4 n\log M+n^3(\log M)^2\right]\right). O ( M [ n 3 log 4 n log M + n 3 ( log M ) 2 ] ) .
while our result via Equation (14) gives
O ( M [ n 3 log 4 n log M + n 3 log M + n 2 ( log M ) 2 ] ) . \mathcal{O}\left(M\left[n^3\log^4 n\log M+n^3\log M+n^2(\log M)^2\right]\right). O ( M [ n 3 log 4 n log M + n 3 log M + n 2 ( log M ) 2 ] ) .
The first term in each bound is the common volume computation cost. Let us now make the improvement a little more concrete. Whenever
log M ≥ n log 4 n \log M \ge n\log^{4} n log M ≥ n log 4 n
these bounds simplify to
O ( M n 3 ( log M ) 2 ) and O ( M n 2 ( log M ) 2 ) O\left(Mn^{3}(\log M)^{2}\right) \qquad\text{and} \qquad O\left(Mn^{2}(\log M)^{2}\right) O ( M n 3 ( log M ) 2 ) and O ( M n 2 ( log M ) 2 )
respectively. More concretely, for M = e n 2 M=e^{n^{2}} M = e n 2 , we get the following comparison.
Table 1. Comparison table when the stream length is M = e n 2 M=e^{n^{2}} M = e n 2 .
Thus, in this regime, the improvement in the sampling bound gives a factor of order n n n in the total running-time bound for Alpona.
Discussion on The Improved Walk Length of Hit-and-Run (Theorem 21)
In this subsection, we talk a little about the result of Theorem 21 , its main proof ideas, and some interesting results that go into it (all a bit heuristically). This result and the proof techniques (specifically the construction and use of the explicit radial vector field) may be independently useful to the Hit and Run community.
For the sake of exposition, we ignore the functional analytical details about domains and constants here.
As we show in the appendix, the result of Theorem 21 follows from two results:
For any 0 < η , β < 1 0<\eta,\beta<1 0 < η , β < 1 taking at least
1 + n / 2 + O ( n log ( 32 R / d ) + log ( 1 / ( n 2 β ) ) γ H R ) 1+n/2+O\left(\frac{n\log(32R/d)+\log(1/(n^{2}\beta))}{\gamma_{\mathrm{HR}}}\right) 1 + n /2 + O ( γ HR n log ( 32 R / d ) + log ( 1/ ( n 2 β )) )
suffices to guarantee that π ( B a d t , η ) ≤ β \pi(\mathrm{Bad}_{t,\eta})\le\beta π ( Bad t , η ) ≤ β and D t ( B a d t , η ) ≤ 2 β D_t(\mathrm{Bad}_{t,\eta})\le2\beta D t ( Bad t , η ) ≤ 2 β .
A lower bound on γ H R \gamma_{\mathrm{HR}} γ HR and contraction of the Hit and Run operator P P P , namely for functions f f f with mean 0 0 0 ,
∥ P s f ∥ L 2 ( π ) ≤ e − γ H R s ∥ f ∥ 2 \lVert P^{s}f\rVert_{L^{2}(\pi)}\le e^{-\gamma_{\mathrm{HR}}s}\lVert f\rVert_{2} ∥ P s f ∥ L 2 ( π ) ≤ e − γ HR s ∥ f ∥ 2
Let us talk first about item (2). This can be proven in a myriad of ways, one of them provided by (a corollary of) [20 Theorem 1.1] . We give a different geometric proof for it using an explicit radial vector field construction. The idea is (after some technicalities) to consider a scaled copy C C C of the body such that C C C has half the volume of K K K . After some technicalities, we define a radial vector field which satisfies
∫ K f d π − 2 ∫ 2 − 1 / n K f d π = − 2 ∫ K F ⋅ ∇ f d π \int_{K} f\,\mathrm{d}\pi-2\int_{2^{-1/n}K}f\,\mathrm{d}\pi=-2\int_{K}F\cdot\nabla f\,\mathrm{d}\pi ∫ K f d π − 2 ∫ 2 − 1/ n K f d π = − 2 ∫ K F ⋅ ∇ f d π
This comes out from the fact that scaling moves the points in the original body and the field F F F says what the combined flow through each point is. In particular, our particular F F F can be viewed as the accumulated mass flow (up to a factor of 2) across a “shell”, generated by the scaling itself. In effect, this gives
E π C f − E π K f ⏟ change in the average = 2 ∫ K F ⋅ ∇ f d π K \underbrace{\mathbb{E}_{\pi_C}f-\mathbb{E}_{\pi_K}f}_{\text{change in the average}}=2\int_K F\cdot\nabla f\,d\pi_K change in the average E π C f − E π K f = 2 ∫ K F ⋅ ∇ f d π K
Geometrically, the change is the amount of mass passing through each location, multiplied by how much f f f changes there. We then use the estimate ∥ F ( x ) ∥ ≲ ( R / r ) dist ( x , ∂ K ) \lVert F(x)\rVert\lesssim(R/r)\operatorname{dist}(x,\partial K) ∥ F ( x )∥ ≲ ( R / r ) dist ( x , ∂ K ) (which we build inside the vector field definition by decaying it suitably), which gives the “flux” term the desired weight (heuristically, across a surface just beneath the boundary, we only need to carry the mass lying in the thin shell outside that surface. As that shell becomes thinner, there is less mass to carry.). The smaller copy stays at depth ≳ r / n \gtrsim r/n ≳ r / n , so its Cheeger’s inequality controls the remaining error by a gradient bound similar to that in [20 Theorem 3.1] .
In contrast, their proof compares a function with its values after moving points slightly towards the centre
f ( x ) − f ( ( 1 − 1 2 n ) x ) = ∫ 1 − 1 / ( 2 n ) 1 x ⋅ ∇ f ( t x ) d t . f(x)-f\left(\left(1-\frac{1}{2n}\right)x\right)=\int_{1-1/(2n)}^{1}x\cdot\nabla f(tx)\,dt. f ( x ) − f ( ( 1 − 2 n 1 ) x ) = ∫ 1 − 1/ ( 2 n ) 1 x ⋅ ∇ f ( t x ) d t .
Then they average over x x x , turning the radial integral into a weighted gradient bound (weights being the distance from the boundary, which appears because a location very close to the boundary can belong to only a small range of the radial segments. Its gradient therefore receives a small weight.), while the contracted copy has depth at least r / ( 2 n ) r/(2n) r / ( 2 n ) . They then use the ordinary Poincare inequality on this copy to control the remaining error [20 proof of Theorem 3.1] .
Now item (1) and this is much more interesting. To prove this, we do two things (again):
1.1. First use a few steps of Hit and Run to make the density square-integrable.
1.2. Then use the remaining steps to reduce its (squared) error by spectral contraction (that is, item (2)).
We then show that item (1.2) suffices to get the π ( B a d t , η ) ≤ β \pi(\mathrm{Bad}_{t,\eta})\le\beta π ( Bad t , η ) ≤ β and D t ( B a d t , η ) ≤ 2 β D_t(\mathrm{Bad}_{t,\eta})\le2\beta D t ( Bad t , η ) ≤ 2 β guarantees. Once done, all that remains is to prove item (1.1). To the best of our knowledge, we have not found this in the literature and looks like a very interesting result.
The idea for item (1.1) is as follows. For a point start, the density is singular at the starting point x 0 x_0 x 0 , and the singularity is captured by the term ∣ y − x 0 ∣ 1 − n \lvert y-x_0\rvert^{1-n} ∣ y − x 0 ∣ 1 − n , where y y y is some other point (from standard Hit and Run theory, see [Lovász and Vempala, 2006, equation (5)]). We follow this singularity near x 0 x_0 x 0 through the initial steps and keep track of it inside the fixed ball U = B ( x 0 , d / 2 ) U=B(x_0,d/2) U = B ( x 0 , d /2 ) . Suppressing constants and scale factors, we follow the progression (ignoring the part outside U U U which we can bound)
∣ y − x 0 ∣ 1 − n → ∣ y − x 0 ∣ 2 − n → ∣ y − x 0 ∣ 3 − n → ⋯ \lvert y-x_0\rvert^{1-n}\to\lvert y-x_0\rvert^{2-n}\to\lvert y-x_0\rvert^{3-n}\to\cdots ∣ y − x 0 ∣ 1 − n → ∣ y − x 0 ∣ 2 − n → ∣ y − x 0 ∣ 3 − n → ⋯
Now let q q q be a small distance scale. To reach y y y , we average over possible intermediate points x x x . Points at that scale occupy volume of order q n q^n q n . Combining them gives
q s − n ⏟ old spike × q 1 − n ⏟ transition kernel × q n ⏟ volume of intermediate points = q s + 1 − n \underbrace{q^{s-n}}_{\text{old spike}}\times\underbrace{q^{1-n}}_{\text{transition kernel}}\times\underbrace{q^n}_{\text{volume of intermediate points}}=q^{s+1-n} old spike q s − n × transition kernel q 1 − n × volume of intermediate points q n = q s + 1 − n
This is essentially what we formally do in the proof. This helps us because a spike of order q j − n q^{j-n} q j − n has squared integral near x 0 x_0 x 0 behaving like
∫ 0 d / 2 q 2 ( j − n ) ⏟ squared density × q n − 1 d q ⏟ volume of a thin shell = ∫ 0 d / 2 q 2 j − n − 1 d q \int_0^{d/2}\underbrace{q^{2(j-n)}}_{\text{squared density}}\times\underbrace{q^{n-1}\,dq}_{\text{volume of a thin shell}}=\int_0^{d/2}q^{2j-n-1}\,dq ∫ 0 d /2 squared density q 2 ( j − n ) × volume of a thin shell q n − 1 d q = ∫ 0 d /2 q 2 j − n − 1 d q
This becomes finite precisely when 2 j > n 2j > n 2 j > n , predicting that ⌊ n / 2 ⌋ + 1 \lfloor n/2 \rfloor+ 1 ⌊ n /2 ⌋ + 1 should suffice for getting a square-integrable density. In fact, we show that we get
χ 2 ( D t ∥ π ) ≤ ( 32 R d ) n e − 2 γ H R ( t − ⌊ n / 2 ⌋ − 1 ) \chi^2(\mathcal{D}_t\Vert\pi) \le\left(\frac{32R}{d}\right)^n e^{-2\gamma H_R(t-\lfloor n/2\rfloor-1)} χ 2 ( D t ∥ π ) ≤ ( d 32 R ) n e − 2 γ H R ( t − ⌊ n /2 ⌋ − 1 )
Choosing the remaining walk length so that this is at most η 2 / β \eta^2/\beta η 2 / β gives both sampling guarantees and recovers our required bound.
So the first few steps spread out the mass near x 0 x_0 x 0 , weakening the singularity (the spike) until the squared density has a finite integral. This is what is known as regularization . What happens if we do not do this regularization? Well, if we kept bounding every subsequent density by the original singularity of the first-step bound, namely q 1 − n q^{1-n} q 1 − n , the same calculation would give
∫ 0 d / 2 q 2 ( 1 − n ) ⏟ squared first-step bound q n − 1 d q ⏟ volume of a thin shell = ∫ 0 d / 2 q 1 − n d q \int_0^{d/2} \underbrace{q^{2(1-n)}}_{\text{squared first-step bound}}\underbrace{q^{n-1}\,dq}_{\text{volume of a thin shell}}
=
\int_0^{d/2}q^{1-n}\,dq ∫ 0 d /2 squared first-step bound q 2 ( 1 − n ) volume of a thin shell q n − 1 d q = ∫ 0 d /2 q 1 − n d q
which diverges for n ≥ 2 n \ge2 n ≥ 2 . The walk would still regularise though, but that estimate would never give us a finite L 2 L^2 L 2 norm. Another approach is to separate off the first-step mass inside a small ball around x 0 x_0 x 0 , and bound the density outside this ball. We would then control the contribution from inside using its small probability. The ball must be chosen small enough for our required η , β \eta,\beta η , β , so these parameters enter the resulting density bound. By following the weakening spike as above, we obtain a finite bound for the whole density after about n / 2 n/2 n /2 steps, with this initial number of steps depending only on the dimension. The detailed proof is in Appendix § 11 .
A Special Case: Bounded Frequency Streams
In this section, we consider a special case of the union volume estimation. Observe that in full generality, each K j K_j K j can intersect with every other convex body in the collection. This type of input is slightly inefficient for the algorithm to process, as it would mean elements from the intersection region, if drawn, would get thrown out repeatedly, and our strategy of storing samples from the unique sections would not be achieved. This is why we considered the special case, where each point of the union has a bounded frequency. This special case of bounded frequency sets has been studied extensively, particularly in the streaming literature (ref. McGregor et al. [2021], Ben-Eliezer et al. [2022], Swartworth et al. [2026]). We formally define the setup below.
Definition 3 (τ \tau τ -bounded Frequence Streams). A stream of convex bodies K : = ⟨ K j ⊂ R n : j ∈ [ M ] ⟩ \mathcal{K} := \langle K_j \subset\mathbb{R}^n : j \in[M]\rangle K := ⟨ K j ⊂ R n : j ∈ [ M ]⟩ , has frequency at most τ \tau τ if every point x ∈ R n x \in\mathbb{R}^n x ∈ R n lies in at most τ \tau τ of the bodies K j K_j K j , i.e.
∑ j = 1 M 1 K j ( x ) ≤ τ 1 ∪ j K j ( x ) ∀ x ∈ R n . \sum_{j=1}^{M}\mathbf{1}_{K_j}(x) \le\tau\mathbf{1}_{\cup_j K_j}(x)\ \forall\ x \in\mathbb{R}^n. j = 1 ∑ M 1 K j ( x ) ≤ τ 1 ∪ j K j ( x ) ∀ x ∈ R n . By definition, we shall always have 1 ≤ τ ≤ M 1 \le\tau\le M 1 ≤ τ ≤ M .
Lemma 22 (Connecting Union Volume and Frequency). For a stream K \mathcal{K} K of frequency at most τ \tau τ , we have:
∑ j Vol ( K j ) ≤ τ F 0 . (15) \sum_j \operatorname{Vol}(K_j) \le\tau F_0. \tag*{(15)} j ∑ Vol ( K j ) ≤ τ F 0 . (15)
Proof. In the finite setting, observe that if each element can appear in at most τ \tau τ many different sets, then the sum of sizes of all the sets can contain τ \tau τ many copies of each distinct element. Hence the sum of their sizes will be bounded by τ \tau τ times the union size. This intuition is mathematically described below.
∑ j Vol ( K j ) = ∑ j ∫ R n 1 K j ( x ) d x ≤ ∫ R n τ ⋅ 1 ∪ j K j ( x ) d x = τ F 0 . \sum_j \operatorname{Vol}(K_j) = \sum_j \int_{\mathbb{R}^n} 1_{K_j}(x)\mathrm{d}x \le\int_{\mathbb{R}^n} \tau\cdot1_{\cup_j K_j}(x)\mathrm{d}x = \tau F_0. j ∑ Vol ( K j ) = j ∑ ∫ R n 1 K j ( x ) d x ≤ ∫ R n τ ⋅ 1 ∪ j K j ( x ) d x = τ F 0 .
Theorem 23 (Correctness of Alpona for Bounded Frequency Streams). Suppose that Alpona takes as input, a collection of convex bodies with frequency at most τ \tau τ , and suppose τ \tau τ is known to the algorithm beforehand. If we run Alpona with β ← ε 32 τ \beta\leftarrow\frac{\varepsilon}{32\tau} β ← 32 τ ε and keep all the other parameters unchanged, then with probability at least 1 − δ 1-\delta 1 − δ the output lies in the range ( 1 ± ε ) F 0 (1\pm\varepsilon)F_0 ( 1 ± ε ) F 0 .
Proof. The quantity ∑ j Vol ( K j ) \sum_j \operatorname{Vol}(K_j) ∑ j Vol ( K j ) is used in exactly two cases, and in the following argument we shall show that the above chosen value for β \beta β suffices.
In the proof of Claim 9 , where if we apply the bound Equation (15) and substitute the chosen value of β \beta β , we get the same output saying F 0 ′ ≥ ( 1 − ε 32 ) F 0 F'_0 \ge(1-\frac{\varepsilon}{32})F_0 F 0 ′ ≥ ( 1 − 32 ε ) F 0 . Thus we continue our agenda of proving a 15 ε 16 \frac{15\varepsilon}{16} 16 15 ε -factor estimation of F 0 ′ F'_0 F 0 ′ .
The second place where this modification affects us is in the proof of Lemma 13 , where we try to bound D j ( K ^ j ) D_j(\widehat{K}_j) D j ( K j ) , and the term D j ( Bad j ) D_j(\operatorname{Bad}_j) D j ( Bad j ) comes up. To be precise, the quantity we bound is:
∑ j D j ( Bad j ) V ~ j ≤ 2 ( 1 + κ ) β ∑ j Vol ( K j ) ≤ 2 ( 1 + ε 32 ) ε 32 τ ⋅ τ F 0 . \sum_j D_j(\operatorname{Bad}_j)\widetilde{V}_j \le2(1+\kappa)\beta\sum_j \operatorname{Vol}(K_j) \le2\left(1+\frac{\varepsilon}{32}\right)\frac{\varepsilon}{32\tau}\cdot\tau F_0. j ∑ D j ( Bad j ) V j ≤ 2 ( 1 + κ ) β j ∑ Vol ( K j ) ≤ 2 ( 1 + 32 ε ) 32 τ ε ⋅ τ F 0 .
Plugging in the values for κ \kappa κ and bounding F 0 F_0 F 0 by F 0 ′ ( 1 − ε 32 ) \frac{F'_0}{(1-\frac{\varepsilon}{32})} ( 1 − 32 ε ) F 0 ′ , we shall get the same bound as obtained in Equation (5) .
Since the two intermediate assertions which require the value of β \beta β and a bound on ∑ j Vol ( K j ) \sum_j \operatorname{Vol}(K_j) ∑ j Vol ( K j ) remain unchanged, the proof follows through.
Observe that our proof of the general theorem simply requires τ \tau τ to be set to M M M . But this does not, however, rid us of the factor M M M as we require it regardless when applying the union bound argument to bound the probability of Fail p r o b \operatorname{Fail}_{\mathrm{prob}} Fail prob , as demonstrated in Claim 14.
Discussions and Future Work
We studied union-volume estimation with approximate volume and sampling oracles. Our sunflower construction shows that sampling-based union-volume estimators can fail when their samplers provide only a fixed per-body total-variation guarantee. Such samplers can miss a small portion of each body even when these portions taken together may account for a substantial fraction of the union. This leads to a large error in the volume estimate.
We addressed this issue through a new concept of tail-controlled samplers , whose density is multiplicatively close to uniform outside an exceptional region of small uniform measure. Our algorithm, Alpona, uses such tail-controlled samplers with PAC volume estimates to return an ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) -approximation of the union volume. Its analysis bounds the contribution of the bad samples from the exceptional region, while accounting for errors in the individual volume estimates. Along the way, Alpona also bypasses the discretization step of the earlier work of Shaw et al. [ [38 ] , thereby improving the complexity.
Finally, we proved that Hit-and-Run provides the required tail control from an interior point start. This leads to a concrete implementation of Alpona with Hit-and-Run as the sampling subroutine. We also give a slightly better analysis of Hit and Run that improves the dimension dependence of the accuracy and stream-length terms in the walk-length bound from n 3 n^3 n 3 to n 2 n^2 n 2 .
The significance of this investigation extends beyond union-volume estimation. Our work illustrates how theoretical analysis can identify the limitations of an existing implementation, determine the approximation guarantees that are actually required, and develop algorithms whose correctness can be established using realizable computational primitives, such as, Alpona with Hit-and-Run. More broadly, we view this as a step toward bridging the gap between idealized randomized algorithms and their practical implementations: using theoretical analysis not merely to justify an abstract algorithm, but to understand and improve algorithms that have already demonstrated empirical promise.
Future Work
Our ( η , β ) (\eta, \beta) ( η , β ) -notion is a first step towards capturing the geometric behavior of approximate samplers, with substantial scope for refinement. It separates local density accuracy from exceptional mass, but does not directly describe how sampling errors are distributed across the body. A promising direction is to develop a geometric sampling guarantee that relates the exceptional region to a sub-Gaussian tail within the convex body. Establishing these guarantees for practical samplers such as Ball Walk or Hit-and-Run could help explain why relatively short walks often suffice in implementations, providing a stronger theoretical basis for their empirical success and potentially yielding less conservative sampling requirements for union-volume estimation.
Heuristics suggest that the dependence on the stream length can be improved further at a slight cost of the geometric term. We conjecture the following strengthening of our Hit and Run analysis:
Conjecture. With η = ε 32 \eta= \frac{\varepsilon}{32} η = 32 ε and β = ε 32 M \beta= \frac{\varepsilon}{32M} β = 32 M ε , both bounds in Equation (10) can be obtained after t t t steps, where
t = 1 + n + O ( n 2 ( R r ) 2 [ n log n R 2 d 0 r + log 1 ε ] ) + O ( ( R r ) log M ε ) t = 1 + n + O\left(n^2\left(\frac{R}{r}\right)^2\left[n\log\frac{nR^2}{d_0r}+\log\frac{1}{\varepsilon}\right]\right) + O\left(\left(\frac{R}{r}\right)\log\frac{M}{\varepsilon}\right) t = 1 + n + O ( n 2 ( r R ) 2 [ n log d 0 r n R 2 + log ε 1 ] ) + O ( ( r R ) log ε M )
This would remove the dependence on the dimension from the term attached to the stream length M M M . In words, this conjecture says that after paying the geometric and accuracy costs, making the exceptional region progressively smaller should be much cheaper than what we have now.
We also believe the dependence on log M \log M log M is not optimal and can possibly be pushed down to log log M \log\log M log log M with possibly worse factors of R / r R/r R / r .4 This would require a different geometric analysis of the Hit and Run Markov chain’s tail bounds.
AI Disclosure. No generative AI or AI-assisted tools were used in the conception of research ideas or the development of proofs. Their use was limited exclusively to assistance with basic writing, grammatical corrections, and language polishing of the manuscript.
Additional Related Work on Point Sampling
Although sampling from log-concave distributions is #P-Hard, a long line of research has been devoted to designing randomized approximate samplers for log-concave distributions. These algorithms generate samples whose distribution is ε \varepsilon ε -close (in total variation distance) to a target log-concave distribution π \pi π supported on a convex body K ⊆ R n K \subseteq\mathbb{R}^{n} K ⊆ R n .
The initial approaches towards this direction used grid walk on a discretization of the log-concave function on the assumption that the function is sufficiently smooth (e.g. Lipschitz continuous) [2 ] . This large polytime dependence on the dimension n n n was soon brought down to O ∗ ( n 2 R 2 / r 2 ) O^{*}(n^{2}R^{2}/r^{2}) O ∗ ( n 2 R 2 / r 2 ) queries to the membership oracle by ball walk [14 ] . The idea of ball walk is to propose a point sampled uniformly from a ball of small radius around the current point, and accept the proposal if does not leave the body. Starting from W W W -warm distribution, the Ball walk was later analyzed [24 ] to have a query complexity of O ∗ ( W 4 ε 4 ⋅ n 2 R 2 r 2 log W ε ) O^{*}\left(\frac{W^{4}}{\varepsilon^{4}}\cdot\frac{n^{2}R^{2}}{r^{2}}\log\frac{W}{\varepsilon}\right) O ∗ ( ε 4 W 4 ⋅ r 2 n 2 R 2 log ε W ) where W W W is the warmness of the starting distribution with respect to the target.
Another style of algorithm, namely Hit-and-Run was showed to mix as fast as the Ball-walk . Lovász and Vempala [2006, Theorem1.1] showed the dependence on W W W to be polylogarithmic for Hit-and-Run: O ( n 2 R 2 r 2 log 2 n W R ε r log 3 W ε ) O\left(\frac{n^{2}R^{2}}{r^{2}}\log^{2}\frac{nWR}{\varepsilon r}\log^{3}\frac{W}{\varepsilon}\right) O ( r 2 n 2 R 2 log 2 ε r nW R log 3 ε W ) . This algorithm draws a uniformly random line ℓ \ell ℓ through the current point x x x and moves to a new point sampled proportional to π \pi π conditioned on ℓ ∩ K \ell\cap K ℓ ∩ K . This approach became influential, inspiring many new variants: a coordinate variant that restricts the random line to coordinate directions was proposed by Laddha and Vempala [ [21 ] , and a version with reflections off the boundary of K K K , called the Billiard Walk [34 ] , was later introduced.
Sampling becomes easier when then convex bodies are polytopes. Kannan and Narayanan [ [13 ] proposed Dikin walk for polytopes that were later generalized for log-concave distributions by Mangoubi and Vishnoi [ [26 ] . More recently, attention has shifted toward guarantees in distances stronger than TV, such as Rényi and R ∞ R_{\infty} R ∞ divergences [19 ] .
Useful Technical Results
We recall a few standard probabilistic tools that will be used throughout our analysis. They are available in any standard probability text book like Ross [ [35 ] . We begin with Markov’s inequality, followed by some basic properties and concentration bounds for Poisson random variables.
Lemma 24 (Markov’s Inequality). Let X X X be a non-negative random variable. Then, for every a > 0 a > 0 a > 0 ,
P ( X ≥ a ) ≤ E [ X ] a . \mathbb{P}(X \geq a) \leq\frac{\mathbb{E}[X]}{a}. P ( X ≥ a ) ≤ a E [ X ] . In particular, for any real-valued random variable Y Y Y with mean μ \mu μ and any ε > 0 \varepsilon> 0 ε > 0 ,
P ( ∣ Y − μ ∣ > ε ) ≤ E [ ∣ Y − μ ∣ ] ε . \mathbb{P}(|Y-\mu| > \varepsilon) \leq\frac{\mathbb{E}[|Y-\mu|]}{\varepsilon}. P ( ∣ Y − μ ∣ > ε ) ≤ ε E [ ∣ Y − μ ∣ ] .
Poissonization. Poisson random variables play a central role in our algorithm. Unlike sampling schemes that require distinct representatives, Poisson sampling naturally accommodates repeated samples. More importantly, the additivity and splitting properties of Poisson distributions allow us to analyze sample counts over disjoint regions of a continuous space. This enables us to work directly with volumes, avoiding the discretization step employed in Shaw et al. [ [38 ] .
We recall the relevant properties below.
Lemma 25 (Additivity of Poisson Random Variables). Let X 1 , … , X L X_1,\ldots,X_L X 1 , … , X L be independent random variables with X i ∼ Pois ( λ i ) X_i \sim\operatorname{Pois}(\lambda_i) X i ∼ Pois ( λ i ) , where λ i > 0 \lambda_i > 0 λ i > 0 . Then
X : = ∑ i = 1 L X i ∼ Pois ( λ ) , where λ : = ∑ i = 1 L λ i . X := \sum_{i=1}^{L} X_i \sim\operatorname{Pois}(\lambda), \qquad\text{where } \lambda:= \sum_{i=1}^{L} \lambda_i. X := i = 1 ∑ L X i ∼ Pois ( λ ) , where λ := i = 1 ∑ L λ i .
The next lemma states the Poisson splitting property: when a Poisson number of independent samples is drawn from a distribution, the numbers falling in disjoint measurable regions are independent Poisson random variables.
Lemma 26 (Poissonization). Let ( S , ν ) (S,\nu) ( S , ν ) be a probability space, and let D D D be a probability distribution on S S S . Consider a partition
S = ⨆ j = 1 L S j S = \bigsqcup_{j=1}^{L} S_j S = j = 1 ⨆ L S j into disjoint measurable subsets. Suppose that N ∼ Pois ( λ ) N \sim\operatorname{Pois}(\lambda) N ∼ Pois ( λ ) and, conditional on N N N , we draw N N N independent samples from D D D .
For each j ∈ [ L ] j \in[L] j ∈ [ L ] , let N j N_j N j denote the number of samples belonging to S j S_j S j . Then N 1 , … , N L N_1,\ldots,N_L N 1 , … , N L are mutually independent, and
N j ∼ Pois ( λ D ( S j ) ) N_j \sim\operatorname{Pois}(\lambda D(S_j)) N j ∼ Pois ( λ D ( S j )) for every j ∈ [ L ] j \in[L] j ∈ [ L ] .
Additionally we state the monotonicity property of Poisson random variable; which essentially states that the tail bound of a Poisson distribution increases when the Poisson parameter is increased.
Lemma 27 (Monotonicity of Poisson Random Variables). For positive reals 0 < μ 1 ≤ μ 2 0 < \mu_1 \le\mu_2 0 < μ 1 ≤ μ 2 and a quantity a > 0 a > 0 a > 0 , Then the following inequality holds:
P ( X > a : X ∼ Pois ( μ 1 ) ) ≤ P ( Y > a : Y ∼ Pois ( μ 2 ) ) . \mathbb{P}(X > a : X \sim\operatorname{Pois}(\mu_1)) \le\mathbb{P}(Y > a : Y \sim\operatorname{Pois}(\mu_2)). P ( X > a : X ∼ Pois ( μ 1 )) ≤ P ( Y > a : Y ∼ Pois ( μ 2 )) .
Proof. We proceed by a coupling argument. Consider independent random variables X ∼ Pois ( μ 1 ) X \sim\operatorname{Pois}(\mu_1) X ∼ Pois ( μ 1 ) , and Z ∼ Pois ( μ 2 − μ 1 ) Z \sim\operatorname{Pois}(\mu_2-\mu_1) Z ∼ Pois ( μ 2 − μ 1 ) . Since μ 2 > μ 1 \mu_2 > \mu_1 μ 2 > μ 1 , this construction is valid. By Lemma 25 , the sum Y ′ : = X + Z ∼ Pois ( μ 2 ) Y' := X + Z \sim\operatorname{Pois}(\mu_2) Y ′ := X + Z ∼ Pois ( μ 2 ) . Thus it remains to prove the claimed inequation, with Y ′ Y' Y ′ in place of Y Y Y (since both follow the same distribution, and all we care about are their tail bounds).
Observe that whenever the event { X > a } \{X > a\} { X > a } occurs, by our construction this naturally forces Y Y Y to be larger than a a a . Hence the event { X > a } \{X > a\} { X > a } is contained within the event { Y > a } \{Y > a\} { Y > a } , and thus the inequality holds.
Finally, we recall a standard concentration inequality for Poisson random variables.
Lemma 28 (Chernoff Bound for Poisson Random Variables). Let X ∼ Pois ( λ ) X \sim\operatorname{Pois}(\lambda) X ∼ Pois ( λ ) . Then, for every ε > 0 \varepsilon> 0 ε > 0 ,
P ( ∣ X − λ ∣ > ε λ ) ≤ 2 exp ( − ε 2 λ 2 ( 1 + ε ) ) . \mathbb{P}(|X-\lambda| > \varepsilon\lambda) \le2\exp\left(-\frac{\varepsilon^2\lambda}{2(1+\varepsilon)}\right). P ( ∣ X − λ ∣ > ε λ ) ≤ 2 exp ( − 2 ( 1 + ε ) ε 2 λ ) .
Definition 4 (Coupling). A coupling of two probability distributions μ \mu μ and ν \nu ν is a pair of random variables ( X , Y ) (X,Y) ( X , Y ) defined on a common probability space such that X ∼ μ X \sim\mu X ∼ μ and Y ∼ ν Y \sim\nu Y ∼ ν . That is, the marginals of the joint distribution of ( X , Y ) (X,Y) ( X , Y ) is exactly μ \mu μ and ν \nu ν respectively.
Lemma 29 (Coupling inequality). (See [10 Theorem 2.4].] ) Let ( X , Y ) (X,Y) ( X , Y ) be any coupling of μ \mu μ and ν \nu ν . Then TV ( μ , ν ) ≤ P ( X ≠ Y ) \operatorname{TV}(\mu,\nu) \le\mathbb{P}(X \ne Y) TV ( μ , ν ) ≤ P ( X = Y ) .
Lemma 30 (Indistinguishability lemma). Let P P P and Q Q Q be two algorithms with total variation distance δ \delta δ . Then if P P P fails with probability at most ρ \rho ρ , then Q Q Q fails with probability at most δ + ρ \delta+\rho δ + ρ .
Property of Almost- Closeness
We compare the proposed guarantee with the two familiar notions of approximate sampling. Throughout, h = d D / d π h = \mathrm{d}D/\mathrm{d}\pi h = d D / d π is as defined above.
ℓ ∞ \ell_\infty ℓ ∞ closeness. We say that D D D is η \eta η -ℓ ∞ \ell_\infty ℓ ∞ close to π \pi π if
∥ h − 1 ∥ L ∞ ( π ) : = e s s s u p x ∈ S ∣ h ( x ) − 1 ∣ ≤ η . \lVert h - 1\rVert_{L^\infty(\pi)} := \mathop{\mathrm{ess\,sup}}_{x \in S} \lvert h(x) - 1\rvert\le\eta. ∥ h − 1 ∥ L ∞ ( π ) := ess sup x ∈ S ∣ h ( x ) − 1 ∣ ≤ η .
Equivalently,
1 − η ≤ h ( x ) ≤ 1 + η for π -almost every x ∈ S . 1 - \eta\le h(x) \le1 + \eta\qquad\text{for $\pi$-almost every $x \in S$.} 1 − η ≤ h ( x ) ≤ 1 + η for π -almost every x ∈ S .
This is a stronger requirement than almost-ℓ ∞ \ell_\infty ℓ ∞ closeness, since it demands multiplicative control of the sampling density over the entire domain, without allowing any exceptional region. Indeed, if D D D is η \eta η -ℓ ∞ \ell_\infty ℓ ∞ close to π \pi π , then
π ( Bad η ( D , π ) ) = D ( Bad η ( D , π ) ) = 0. \pi(\operatorname{Bad}_{\eta}(D,\pi)) = D(\operatorname{Bad}_{\eta}(D,\pi)) = 0. π ( Bad η ( D , π )) = D ( Bad η ( D , π )) = 0.
Consequently, D D D is ( η , β ) (\eta,\beta) ( η , β ) -close to π \pi π for every β > 0 \beta> 0 β > 0 .
ℓ 1 \ell_1 ℓ 1 closeness. Recall that the ℓ 1 \ell_1 ℓ 1 distance between D D D and π \pi π is defined as
∥ D − π ∥ 1 : = ∫ S ∣ h ( x ) − 1 ∣ d π ( x ) = 2 d T V ( D , π ) . \lVert D - \pi\rVert_1 := \int_S \lvert h(x) - 1\rvert\,\mathrm{d}\pi(x) = 2d_{\mathrm{TV}}(D,\pi). ∥ D − π ∥ 1 := ∫ S ∣ h ( x ) − 1 ∣ d π ( x ) = 2 d TV ( D , π ) .
Unlike ℓ ∞ \ell_\infty ℓ ∞ closeness, an ℓ 1 \ell_1 ℓ 1 guarantee controls only the average deviation of the sampling density. Consequently, η \eta η -ℓ 1 \ell_1 ℓ 1 closeness does not necessarily imply ( η , β ) (\eta,\beta) ( η , β ) -almost-ℓ ∞ \ell_\infty ℓ ∞ closeness when β \beta β is small.
For example, let π \pi π be uniform on [ 0 , 1 ] [0,1] [ 0 , 1 ] and consider a distribution D D D with relative density
h ( x ) = { 1 + 2 η , x ∈ [ 0 , 1 / 4 ] , 1 − 2 η 3 , x ∈ ( 1 / 4 , 1 ] , h(x) =
\begin{cases}
1 + 2\eta, & x \in[0,1/4],\\
1 - \dfrac{2\eta}{3}, & x \in(1/4,1],
\end{cases} h ( x ) = ⎩ ⎨ ⎧ 1 + 2 η , 1 − 3 2 η , x ∈ [ 0 , 1/4 ] , x ∈ ( 1/4 , 1 ] ,
where 0 < η < 1 / 2 0 < \eta< 1/2 0 < η < 1/2 . Clearly, h h h is a valid probability density, and
∥ D − π ∥ 1 = 1 4 ( 2 η ) + 3 4 ( 2 η 3 ) = η . \lVert D - \pi\rVert_1 = \frac{1}{4}(2\eta) + \frac{3}{4}\left(\frac{2\eta}{3}\right)
= \eta. ∥ D − π ∥ 1 = 4 1 ( 2 η ) + 4 3 ( 3 2 η ) = η .
However, [ 0 , 1 / 4 ] ⊆ Bad η ( D , π ) [0,1/4] \subseteq\operatorname{Bad}_{\eta}(D,\pi) [ 0 , 1/4 ] ⊆ Bad η ( D , π ) , implying
π ( Bad η ( D , π ) ) ≥ 1 4 . \pi(\operatorname{Bad}_{\eta}(D,\pi)) \ge\frac{1}{4}. π ( Bad η ( D , π )) ≥ 4 1 .
Therefore, D D D is not ( η , β ) (\eta,\beta) ( η , β ) -close to π \pi π for any β < 1 / 4 \beta< 1/4 β < 1/4 . In particular, an ℓ 1 \ell_1 ℓ 1 guarantee of order η \eta η is insufficient for the regime β = Θ ( ε / M ) \beta= \Theta(\varepsilon/M) β = Θ ( ε / M ) required by our application.
Nevertheless, a substantially stronger ℓ 1 \ell_1 ℓ 1 guarantee does imply almost-ℓ ∞ \ell_\infty ℓ ∞ closeness, as established by the following lemma.
Properties 1. Let D ≪ π D \ll\pi D ≪ π and η , β ∈ ( 0 , 1 ) \eta,\beta\in(0,1) η , β ∈ ( 0 , 1 ) .
If D D D is ( η , β ) (\eta,\beta) ( η , β ) -close to π \pi π , ∥ D − π ∥ 1 ≤ η + 3 β \lVert D - \pi\rVert_1 \le\eta+ 3\beta ∥ D − π ∥ 1 ≤ η + 3 β .
If ∥ D − π ∥ 1 ≤ η β \lVert D-\pi\rVert_1 \leq\eta\beta ∥ D − π ∥ 1 ≤ η β , then D D D is ( η , β ) (\eta,\beta) ( η , β ) -close to π \pi π .
The comparison clarifies the strength of our requirement. Global multiplicative ℓ ∞ \ell_\infty ℓ ∞ closeness implies ( η , β ) (\eta,\beta) ( η , β ) -closeness for every β > 0 \beta> 0 β > 0 , whereas an ℓ 1 \ell_1 ℓ 1 error of order η \eta η need not suffice when β \beta β is small. The conversion above instead requires ℓ 1 \ell_1 ℓ 1 error at most η β \eta\beta η β ; for our parameter regime, this is O ( ε 2 / M ) O(\varepsilon^2/M) O ( ε 2 / M ) . This is a sufficient condition, not a necessary one: almost-ℓ ∞ \ell_\infty ℓ ∞ closeness allows larger average error provided that the density distortion is localized and its exceptional mass is controlled.
Exceptional Sampling Guarantees for Hit and Run
In this appendix, we provide a proof of Theorem 21 . We restate it below too after recalling the relevant notions.
Let us first recall the point sampling subroutine described in § 4.2 . For a convex body K ⊂ R n K \subset\mathbb{R}^n K ⊂ R n , we require independent samples from a distribution D D D that is ( η , β ) (\eta,\beta) ( η , β ) -close to the uniform distribution π K \pi_K π K . If ρ = d D / d π K \rho= dD/d\pi_K ρ = d D / d π K and
Bad η = { x ∈ K : ∣ ρ ( x ) − 1 ∣ > η } , \operatorname{Bad}_{\eta} = \{x \in K : \lvert\rho(x)-1\rvert> \eta\}, Bad η = { x ∈ K : ∣ ρ ( x ) − 1 ∣ > η } ,
then the implementation used in the analysis uses the two bounds
π K ( Bad η ) ≤ β , D ( Bad η ) ≤ 2 β . (16) \pi_K(\operatorname{Bad}_{\eta}) \leq\beta,\qquad D(\operatorname{Bad}_{\eta}) \leq2\beta. \tag*{(16)} π K ( Bad η ) ≤ β , D ( Bad η ) ≤ 2 β . (16)
In particular, in line 4 of Algorithm 1, we assign the parameters
η = ε 32 , β = ε 32 M . (17) \eta= \frac{\varepsilon}{32},\qquad\beta= \frac{\varepsilon}{32M}. \tag*{(17)} η = 32 ε , β = 32 M ε . (17)
We recall the geometric setup and Hit and Run terminology here again for convenience. Some other standard notions will be recalled as we move through the section. Let K K K contain a Euclidean ball of radius r r r (called the inball) and be contained in a Euclidean ball of radius R R R (called the outball). We start from an interior point x 0 x_0 x 0 and let d = dist ( x 0 , ∂ K ) > 0 d = \operatorname{dist}(x_0,\partial K) > 0 d = dist ( x 0 , ∂ K ) > 0 . Let D t D_t D t denote the distribution after t t t Hit and Run steps. We use π = π K \pi= \pi_K π = π K for the uniform distribution and ρ t = d D t / d π \rho_t = dD_t/d\pi ρ t = d D t / d π for the relative density. These densities exist for t ≥ 1 t \geq1 t ≥ 1 by the transition-density formula of Lovász and Vempala [Lovász and Vempala, 2006, equation (5)]. The exceptional set at time t t t (so after step t t t ) is precisely the set Bad t , η \operatorname{Bad}_{t,\eta} Bad t , η introduced in § 6.2.2 .
The theorem we want to prove is this.
Theorem 31 (Walk length for the sampling subroutine). With η = ε 32 \eta= \frac{\varepsilon}{32} η = 32 ε and β = ε 32 M \beta= \frac{\varepsilon}{32M} β = 32 M ε , both bounds in Equation (10) can be obtained in
t = 1 + ⌊ n / 2 ⌋ + O ( n 2 ( R r ) 2 [ n log 32 R d + log 32 ε + log M ] ) (18) t = 1 + \lfloor n/2\rfloor+ O\left(n^2\left(\frac{R}{r}\right)^2\left[n\log\frac{32R}{d}+\log\frac{32}{\varepsilon}+\log M\right]\right) \tag*{(18)} t = 1 + ⌊ n /2 ⌋ + O ( n 2 ( r R ) 2 [ n log d 32 R + log ε 32 + log M ] ) (18) Hit and Run steps.
For the proof, we would require to invoke the convex-body diameter bound of [33 Equation 4.3] , whose proof was corrected by [3 ] . We will use the formulation of [31 Theorem 5.10] consistently.
Let us now proceed towards proving Theorem 31 .
General sampling and contraction bounds
We write γ H R \gamma_{\mathrm{HR}} γ HR for the spectral gap of Hit and Run. Also since in dimension one, a single Hit and Run step samples exactly uniformly from the interval K K K , we assume from now on that n ≥ 2 n \ge2 n ≥ 2 .
What we will prove abstractly is the following theorem, which gives a sufficient number of steps required to run Hit and Run for, starting from any interior point, so that we can satisfy the guarantees of Equation (17) .
Theorem 32. Let 0 < η , β < 1 0 < \eta, \beta< 1 0 < η , β < 1 . Then every integer t t t satisfying
t ≥ 1 + ⌊ n / 2 ⌋ + ⌈ n log ( 32 R / d ) + log ( 1 / ( η 2 β ) ) 2 γ H R ⌉ (19) t \ge1 + \lfloor n/2 \rfloor+ \left\lceil\frac{n \log(32R/d) + \log(1/(\eta^2\beta))}{2\gamma_{\mathrm{HR}}} \right\rceil \tag*{(19)} t ≥ 1 + ⌊ n /2 ⌋ + ⌈ 2 γ HR n log ( 32 R / d ) + log ( 1/ ( η 2 β )) ⌉ (19) satisfies the guarantees
π ( B a d t , η ) ≤ β , D t ( B a d t , η ) ≤ 2 β . \pi(Bad_{t,\eta}) \le\beta,\qquad D_t(Bad_{t,\eta}) \le2\beta. π ( B a d t , η ) ≤ β , D t ( B a d t , η ) ≤ 2 β .
Given this theorem, if we have a lower bound on γ H R \gamma_{\mathrm{HR}} γ HR , then we can complete the proof of Theorem 31 . Towards that, let us define the following quantity. We define C P I ( π ) C_{\mathrm{PI}}(\pi) C PI ( π ) as the least constant for which
Var π ( f ) ≤ C P I ( π ) ∫ K ∥ ∇ f ∥ 2 d π \operatorname{Var}_{\pi}(f) \le C_{\mathrm{PI}}(\pi) \int_K \lVert\nabla f \rVert^2 \,\mathrm{d}\pi Var π ( f ) ≤ C PI ( π ) ∫ K ∥ ∇ f ∥ 2 d π
holds for every f ∈ H 1 ( int K ) f \in H^1(\operatorname{int} K) f ∈ H 1 ( int K ) . Here H 1 H^1 H 1 consists of square-integrable functions with square-integrable weak derivatives5 . Then we have the following.
Lemma 33 (Contraction for Hit and Run Corollary and Extension of [20 Theorem 1.1] ). There is a universal constant c > 0 c > 0 c > 0 such that
γ H R ≥ c r 2 n 2 C P I ( π ) . (20) \gamma_{\mathrm{HR}} \ge c\frac{r^2}{n^2 C_{\mathrm{PI}}(\pi)}. \tag*{(20)} γ HR ≥ c n 2 C PI ( π ) r 2 . (20) In particular
γ H R ≥ c r 2 n 2 R 2 . (21) \gamma_{\mathrm{HR}} \ge c\frac{r^2}{n^2R^2}. \tag*{(21)} γ HR ≥ c n 2 R 2 r 2 . (21) Moreover, for every mean-zero f ∈ L 2 ( π ) f \in L^2(\pi) f ∈ L 2 ( π ) and every integer s ≥ 0 s \ge0 s ≥ 0 ,
∥ P s f ∥ L 2 ( π ) ≤ e − γ H R s ∥ f ∥ 2 ≤ exp ( − c r 2 s n 2 C P I ( π ) ) ∥ f ∥ L 2 ( π ) (22) \lVert P^s f\rVert_{L^2(\pi)} \le e^{-\gamma_{\mathrm{HR}}s}\lVert f\rVert_2 \le\exp\left(-c\frac{r^2s}{n^2 C_{\mathrm{PI}}(\pi)}\right)\lVert f\rVert_{L^2(\pi)} \tag*{(22)} ∥ P s f ∥ L 2 ( π ) ≤ e − γ HR s ∥ f ∥ 2 ≤ exp ( − c n 2 C PI ( π ) r 2 s ) ∥ f ∥ L 2 ( π ) (22)
Now we prove Theorem 31 .
Proof of Theorem 31. Substituting the parameter values gives
η 2 β = ε 3 32 3 M \eta^2\beta= \frac{\varepsilon^3}{32^3M} η 2 β = 3 2 3 M ε 3
and thus
log 1 η 2 β = 3 log 32 ε + log M \log\frac{1}{\eta^2\beta} = 3\log\frac{32}{\varepsilon} + \log M log η 2 β 1 = 3 log ε 32 + log M
By Theorem 32 , both sampling guarantees hold whenever
t ≥ 1 + ⌊ n / 2 ⌋ + ⌈ n log ( 32 R / d ) + 3 log ( 32 / ε ) + log M 2 γ H R ⌉ . (23) t \ge1 + \lfloor n/2 \rfloor+ \left\lceil\frac{n\log(32R/d) + 3\log(32/\varepsilon) + \log M}{2\gamma_{\mathrm{HR}}} \right\rceil. \tag*{(23)} t ≥ 1 + ⌊ n /2 ⌋ + ⌈ 2 γ HR n log ( 32 R / d ) + 3 log ( 32/ ε ) + log M ⌉ . (23)
Plugging Equation (21) in this bound gives Equation (18) .
With this settled, we move on to the proofs of Theorem 32 and Lemma 33.
Regularising the point-start density
We now prove Theorem 32 . The idea of the proof is as follows:
First use a few steps of Hit and Run to make the density square-integrable
Then use the remaining steps to reduce its (squared) error by spectral contraction.
Let us first see how a squared-error bound gives both sampling guarantees in Equation (10) . This will justify why we want item (2).
Lemma 34. Let 0 < η , β < 1 0 < \eta, \beta< 1 0 < η , β < 1 , and let D D D have relative density ρ \rho ρ with respect to π \pi π . If
χ 2 ( D ∥ π ) : = ∫ K ∣ ρ − 1 ∣ 2 d π ≤ η 2 β , \chi^2(D\mathbin{\|}\pi) := \int_K \lvert\rho- 1 \rvert^2 \,\mathrm{d}\pi\le\eta^2\beta, χ 2 ( D ∥ π ) := ∫ K ∣ ρ − 1 ∣ 2 d π ≤ η 2 β , then π ( B a d η ) ≤ β \pi(\mathit{Bad}_{\eta}) \le\beta π ( Bad η ) ≤ β and D ( B a d η ) ≤ ( 1 + η ) β ≤ 2 β D(\mathit{Bad}_{\eta}) \le(1+\eta)\beta\le2\beta D ( Bad η ) ≤ ( 1 + η ) β ≤ 2 β .
Proof. For the first guarantee, we can use Markov’s inequality to get
π ( B a d η ) ≤ 1 η 2 ∫ K ∣ ρ − 1 ∣ 2 d π ≤ β . \pi(\mathit{Bad}_{\eta}) \le\frac{1}{\eta^2}\int_K \lvert\rho- 1 \rvert^2 \,\mathrm{d}\pi\le\beta. π ( Bad η ) ≤ η 2 1 ∫ K ∣ ρ − 1 ∣ 2 d π ≤ β .
For the second guarantee, we can use Cauchy-Schwarz on the exceptional set to get
D ( B a d η ) = π ( B a d η ) + ∫ B a d η ( ρ − 1 ) d π ≤ π ( B a d η ) + ( π ( B a d η ) ∫ K ∣ ρ − 1 ∣ 2 d π ) 1 / 2 ≤ β + η β . \begin{aligned}
D(\mathit{Bad}_{\eta}) = \pi(\mathit{Bad}_{\eta}) + \int_{\mathit{Bad}_{\eta}}(\rho- 1)\,\mathrm{d}\pi\\
&\le\pi(\mathit{Bad}_{\eta}) + \left(\pi(\mathit{Bad}_{\eta})\int_K \lvert\rho- 1 \rvert^2 \,\mathrm{d}\pi\right)^{1/2} \\
&\le\beta+ \eta\beta.
\end{aligned} D ( Bad η ) = π ( Bad η ) + ∫ Bad η ( ρ − 1 ) d π ≤ π ( Bad η ) + ( π ( Bad η ) ∫ K ∣ ρ − 1 ∣ 2 d π ) 1/2 ≤ β + η β .
Now we proceed to towards item (1), that is, bound the number of steps required for the first square-integrable step. For that we need a bound on the density after the first few steps. Let us write κ n = Vol ( B 2 n ) \kappa_n = \operatorname{Vol}(B_2^n) κ n = Vol ( B 2 n ) , where B 2 n B_2^n B 2 n is the Euclidean unit ball.
Lemma 35 (The first square-integrable step). Let k = ⌊ n / 2 ⌋ + 1 k = \lfloor n/2 \rfloor+ 1 k = ⌊ n /2 ⌋ + 1 . Then
∫ K ρ k 2 d π ≤ 32 n Vol ( K ) κ n d n ≤ ( 32 R d ) n . (24) \int_K \rho_k^2 \,\mathrm{d}\pi\le32^n\frac{\operatorname{Vol}(K)}{\kappa_n d^n} \le\left(\frac{32R}{d}\right)^n. \tag*{(24)} ∫ K ρ k 2 d π ≤ 3 2 n κ n d n Vol ( K ) ≤ ( d 32 R ) n . (24) and ρ k \rho_k ρ k is the first square-integrable density.
Let us first see how this estimate completes the proof of Theorem 32 .
Proof of Theorem 32 . Let k = 1 + ⌊ n / 2 ⌋ k = 1 + \lfloor n/2 \rfloor k = 1 + ⌊ n /2 ⌋ . Since ρ k \rho_k ρ k is a probability density, ρ k − 1 \rho_k - 1 ρ k − 1 has mean zero and so by Lemma 35 , we have
∥ ρ k − 1 ∥ 2 2 = ∫ K ρ k 2 d π − 1 ≤ ( 32 R d ) n . \lVert\rho_k - 1 \rVert_2^2 = \int_K \rho_k^2 \,\mathrm{d}\pi- 1 \le\left(\frac{32R}{d}\right)^n. ∥ ρ k − 1 ∥ 2 2 = ∫ K ρ k 2 d π − 1 ≤ ( d 32 R ) n .
Applying Equation (22) from Lemma 33 then gives, for t ≥ k t \ge k t ≥ k ,
χ 2 ( D t ∥ π ) = ∥ P t − k ( ρ k − 1 ) ∥ 2 2 ≤ e − 2 γ H R ( t − k ) ∥ ρ k − 1 ∥ 2 2 ≤ e − 2 γ H R ( t − k ) ( 32 R d ) n . \chi^2(D_t\mathbin{\|}\pi) = \lVert P^{t-k}(\rho_k - 1)\rVert_2^2 \le e^{-2\gamma_{\mathrm{HR}}(t-k)}\lVert\rho_k - 1\rVert_2^2 \le e^{-2\gamma_{\mathrm{HR}}(t-k)}\left(\frac{32R}{d}\right)^n. χ 2 ( D t ∥ π ) = ∥ P t − k ( ρ k − 1 ) ∥ 2 2 ≤ e − 2 γ HR ( t − k ) ∥ ρ k − 1 ∥ 2 2 ≤ e − 2 γ HR ( t − k ) ( d 32 R ) n .
Then plugging in the value in Equation (19) bounds the right-hand side by η 2 β \eta^2\beta η 2 β and hence both sampling guarantees now follow from Lemma 34 .
Remark 1. Let us also mention what the proof gives for convergence from a point start in standard Hit and Run terms. With k = 1 + ⌊ n / 2 ⌋ k = 1 + \lfloor n/2 \rfloor k = 1 + ⌊ n /2 ⌋ , for every t ≥ k t \ge k t ≥ k , note that we have
χ 2 ( D t ∥ π ) ≤ ( 32 R d ) n e − 2 γ H R ( t − k ) \chi^2(\mathcal{D}_t\Vert\pi) \le\left(\frac{32R}{d}\right)^n e^{-2\gamma_{\mathrm{HR}}(t-k)} χ 2 ( D t ∥ π ) ≤ ( d 32 R ) n e − 2 γ HR ( t − k )
Consequently, for any 0 < ε < 1 0 < \varepsilon< 1 0 < ε < 1 , we have χ 2 ( D t ∥ π ) ≤ ε \chi^2(\mathcal{D}_t\Vert\pi) \le\varepsilon χ 2 ( D t ∥ π ) ≤ ε whenever
t ≥ k + n log ( 32 R / d ) + log ( 1 / ε ) 2 γ H R t \ge k + \frac{n\log(32R/d)+\log(1/\varepsilon)}{2\gamma_{\mathrm{HR}}} t ≥ k + 2 γ HR n log ( 32 R / d ) + log ( 1/ ε )
We can also get total variation error at most ε \varepsilon ε by replacing ε \varepsilon ε by ε 2 \varepsilon^2 ε 2 since TV ( D t , π ) ≤ 1 2 χ 2 ( D t ∥ π ) \operatorname{TV}(\mathcal{D}_t,\pi) \le\frac{1}{2}\sqrt{\chi^2(\mathcal{D}_t\Vert\pi)} TV ( D t , π ) ≤ 2 1 χ 2 ( D t ∥ π ) . Let us compare this with the bound Lovasz-Vempala got. Their original point-start result gives total variation error at most ε \varepsilon ε in
O ( n 3 ( R r ) 2 [ log R d + log 1 ε ] ) \mathcal{O}\left(n^3\left(\frac{R}{r}\right)^2\left[\log\frac{R}{d}+\log\frac{1}{\varepsilon}\right]\right) O ( n 3 ( r R ) 2 [ log d R + log ε 1 ] )
steps [Lovász and Vempala, 2006, Corollary 1.2]. The same also follows from [20 Theorem 1.1 and Corollary 1.2] , using the usual first-step truncation together with the convex-domain diameter bound [31 Theorem 5.10] for the Poincare. On the other hand, Lovasz-Vempala’s conductance bound [Lovász and Vempala, 2006, Theorem 4.2] with our regularisation estimate gives the same total variation guarantee in
O ( n 3 ( R r ) 2 log 32 R d + n 2 ( R r ) 2 log 1 ε ) \mathcal{O}\left(n^3\left(\frac{R}{r}\right)^2\log\frac{32R}{d}+n^2\left(\frac{R}{r}\right)^2\log\frac{1}{\varepsilon}\right) O ( n 3 ( r R ) 2 log d 32 R + n 2 ( r R ) 2 log ε 1 )
steps. Thus our result improves the coefficient of log ( 1 / ε ) \log(1/\varepsilon) log ( 1/ ε ) by a factor of order n n n .
Let us now prove Lemma 35 . We recall some standard facts about Hit and Run. For distinct x , y ∈ K x,y\in K x , y ∈ K , let ℓ ( x , y ) \ell(x,y) ℓ ( x , y ) be the length of the chord on the line through x x x and y y y . The Lebesgue transition density is [Lovász and Vempala, 2006, equation (5)]
p ( x , y ) = 2 n κ n ℓ ( x , y ) ∣ x − y ∣ n − 1 . (25) p(x,y)=\frac{2}{n\kappa_n\ell(x,y)|x-y|^{n-1}}. \tag*{(25)} p ( x , y ) = n κ n ℓ ( x , y ) ∣ x − y ∣ n − 1 2 . (25)
Note that this formula is symmetric in x , y x,y x , y (so we have a reversible Markov chain). Consequently densities evolve by ρ j + 1 = P ρ j \rho_{j+1}=P\rho_j ρ j + 1 = P ρ j , where
P f ( y ) = ∫ K p ( x , y ) f ( x ) d x . Pf(y)=\int_K p(x,y)f(x)\,\mathrm{d}x. P f ( y ) = ∫ K p ( x , y ) f ( x ) d x .
For nonnegative integrable functions these identities follow by Tonelli’s theorem.
The ball B ( x 0 , d ) B(x_0,d) B ( x 0 , d ) lies inside K K K , so every chord through x 0 x_0 x 0 has length at least 2 d 2d 2 d . It follows that
ρ 1 ( y ) ≤ Vol ( K ) n κ n d ∣ y − x 0 ∣ 1 − n . (26) \rho_1(y)\le\frac{\operatorname{Vol}(K)}{n\kappa_n d}|y-x_0|^{1-n}. \tag*{(26)} ρ 1 ( y ) ≤ n κ n d Vol ( K ) ∣ y − x 0 ∣ 1 − n . (26)
Observe that the factor ∣ y − x 0 ∣ 1 − n |y-x_0|^{1-n} ∣ y − x 0 ∣ 1 − n is due to the singularity near the starting point. The idea for the proof of Lemma 35 is to follow this singularity near x 0 x_0 x 0 through the initial steps and keep track of it inside the fixed ball U = B ( x 0 , a ) U=B(x_0,a) U = B ( x 0 , a ) with a = d / 2 a=d/2 a = d /2 . Since every x ∈ U x\in U x ∈ U has boundary distance at least d / 2 d/2 d /2 , the kernel in Equation (25) satisfies
p ( x , y ) ≤ 2 n κ n d ∣ x − y ∣ 1 − n for all x ∈ U , y ∈ K . (27) p(x,y)\le\frac{2}{n\kappa_n d}|x-y|^{1-n}\qquad\text{for all }x\in U,\ y\in K. \tag*{(27)} p ( x , y ) ≤ n κ n d 2 ∣ x − y ∣ 1 − n for all x ∈ U , y ∈ K . (27)
The next lemma is a small technicality that explains why applying this kernel shaves off a power from the singularity, and we will then use this to prove Lemma 35 .
Lemma 36. For ϕ s ( y ) = ( ∣ y − x 0 ∣ / a ) s − n \phi_s(y) = (\lvert y-x_0\rvert/a)^{s-n} ϕ s ( y ) = (∣ y − x 0 ∣ / a ) s − n and 3 / 4 ≤ s ≤ n / 2 − 1 / 4 3/4 \le s \le n/2 - 1/4 3/4 ≤ s ≤ n /2 − 1/4 ,
P ( ϕ s 1 U ) ( y ) ≤ 16 ϕ s + 1 ( y ) for almost every y ∈ K . P(\phi_s 1_U)(y) \le16\phi_{s+1}(y) \quad\text{for almost every } y \in K. P ( ϕ s 1 U ) ( y ) ≤ 16 ϕ s + 1 ( y ) for almost every y ∈ K .
Let us now use this estimate to prove Lemma 35 and then prove Lemma 36 itself.
Proof of Lemma 35 . We split the density at each step into a singular part supported on U U U and a bounded part. Let us define the sequence6
c 1 = Vol ( K ) n κ n d a 1 − n , c j = 16 j − 1 c 1 , c_1 = \frac{\operatorname{Vol}(K)}{n\kappa_n d}a^{1-n}, \qquad c_j = 16^{j-1}c_1, c 1 = n κ n d Vol ( K ) a 1 − n , c j = 1 6 j − 1 c 1 ,
and initially let ρ 1 = b 1 + u 1 \rho_1 = b_1 + u_1 ρ 1 = b 1 + u 1 , where u 1 = ρ 1 1 U u_1 = \rho_1 1_U u 1 = ρ 1 1 U and b 1 = ρ 1 1 U c b_1 = \rho_1 1_{U^c} b 1 = ρ 1 1 U c . By Equation (26) , we have
b 1 ≤ c 1 , u 1 ≤ c 1 ϕ 3 / 4 1 U . b_1 \le c_1, \qquad u_1 \le c_1\phi_{3/4}1_U. b 1 ≤ c 1 , u 1 ≤ c 1 ϕ 3/4 1 U .
For 1 ≤ j < k 1 \le j < k 1 ≤ j < k , we define7
u j + 1 = 1 U P u j , b j + 1 = P b j + 1 U c P u j . (28) u_{j+1} = 1_U P u_j, \qquad b_{j+1} = P b_j + 1_{U^c}P u_j. \tag*{(28)} u j + 1 = 1 U P u j , b j + 1 = P b j + 1 U c P u j . (28)
Both u j + 1 u_{j+1} u j + 1 and b j + 1 b_{j+1} b j + 1 are nonnegative and sum to ρ j + 1 \rho_{j+1} ρ j + 1 . Thus each component has π \pi π -integral at most one.
We now claim that for every j ≤ k j \le k j ≤ k ,
u j ≤ c j ϕ j − 1 / 4 1 U , ∥ b j ∥ ∞ ≤ ∑ i = 1 j c i ≤ 16 15 c j . u_j \le c_j\phi_{j-1/4}1_U, \qquad\lVert b_j\rVert_\infty\le\sum_{i=1}^{j}c_i \le\frac{16}{15}c_j. u j ≤ c j ϕ j − 1/4 1 U , ∥ b j ∥ ∞ ≤ i = 1 ∑ j c i ≤ 15 16 c j .
The claim holds at j = 1 j=1 j = 1 . If it holds at j < k j<k j < k , then 3 / 4 ≤ j − 1 / 4 ≤ n / 2 − 1 / 4 3/4 \le j-1/4 \le n/2-1/4 3/4 ≤ j − 1/4 ≤ n /2 − 1/4 , so Lemma 36 gives
P u j ≤ 16 c j ϕ j + 3 / 4 = c j + 1 ϕ j + 3 / 4 . P u_j \le16c_j\phi_{j+3/4} = c_{j+1}\phi_{j+3/4}. P u j ≤ 16 c j ϕ j + 3/4 = c j + 1 ϕ j + 3/4 .
This profile is at most one on U c U^c U c because j + 3 / 4 < n j+3/4<n j + 3/4 < n . Consequently the second term in the expression for b j + 1 b_{j+1} b j + 1 is bounded by c j + 1 c_{j+1} c j + 1 . Since P P P is a Markov operator, it contracts L ∞ L^\infty L ∞ and hence we have
∥ b j + 1 ∥ ∞ ≤ ∥ b j ∥ ∞ + c j + 1 ≤ ∑ i = 1 j + 1 c i . \lVert b_{j+1}\rVert_\infty\le\lVert b_j\rVert_\infty+ c_{j+1} \le\sum_{i=1}^{j+1}c_i. ∥ b j + 1 ∥ ∞ ≤ ∥ b j ∥ ∞ + c j + 1 ≤ i = 1 ∑ j + 1 c i .
This proves the claim by induction.
Now at step k k k , the exponent k − 1 / 4 k-1/4 k − 1/4 satisfies 2 ( k − 1 / 4 ) − n ≥ 1 / 2 2(k-1/4)-n \ge1/2 2 ( k − 1/4 ) − n ≥ 1/2 . Moving to polar coordinates therefore gives
∫ U ϕ k − 1 / 4 2 d π = n κ n a n Vol ( K ) ( 2 k − 1 / 2 − n ) ≤ 2 n κ n a n Vol ( K ) . \int_U \phi_{k-1/4}^{2}\,\mathrm{d}\pi
= \frac{n\kappa_n a^n}{\operatorname{Vol}(K)(2k-1/2-n)}
\le\frac{2n\kappa_n a^n}{\operatorname{Vol}(K)}. ∫ U ϕ k − 1/4 2 d π = Vol ( K ) ( 2 k − 1/2 − n ) n κ n a n ≤ Vol ( K ) 2 n κ n a n .
Using this and the mass bound ∫ K b k d π ≤ 1 \int_K b_k\,\mathrm{d}\pi\le1 ∫ K b k d π ≤ 1 , we obtain the estimates (where all norms are with respect to π \pi π )
∥ b k ∥ 2 2 ≤ ∥ b k ∥ ∞ ≤ 16 15 c k \lVert b_k\rVert_2^2 \le\lVert b_k\rVert_\infty\le\frac{16}{15}c_k ∥ b k ∥ 2 2 ≤ ∥ b k ∥ ∞ ≤ 15 16 c k
and
∥ u k ∥ 2 2 ≤ 2 n κ n a n Vol ( K ) c k 2 = 2 n − 1 Vol ( K ) n κ n d n 16 2 k − 2 \lVert u_k\rVert_2^2 \le\frac{2n\kappa_n a^n}{\operatorname{Vol}(K)}c_k^2 = \frac{2^{n-1}\operatorname{Vol}(K)}{n\kappa_n d^n}16^{2k-2} ∥ u k ∥ 2 2 ≤ Vol ( K ) 2 n κ n a n c k 2 = n κ n d n 2 n − 1 Vol ( K ) 1 6 2 k − 2
Now since 1 ≤ k − 1 = ⌊ n / 2 ⌋ ≤ n / 2 1 \le k-1=\lfloor n/2\rfloor\le n/2 1 ≤ k − 1 = ⌊ n /2 ⌋ ≤ n /2 , we have
∥ ρ k ∥ 2 2 ≤ 2 ∥ b k ∥ 2 2 + 2 ∥ u k ∥ 2 2 ≤ 2 n Vol ( K ) n κ n d n [ 16 15 16 k − 1 + 16 2 k − 2 ] ≤ 32 2 n Vol ( K ) κ n d n ≤ ( 32 R d ) n \lVert\rho_k\rVert_2^2 \le2\lVert b_k\rVert_2^2+2\lVert u_k\rVert_2^2 \le\frac{2^n\operatorname{Vol}(K)}{n\kappa_n d^n}\left[\frac{16}{15}16^{k-1}+16^{2k-2}\right]\le32\frac{2^n\operatorname{Vol}(K)}{\kappa_n d^n}\le\left(\frac{32R}{d}\right)^n ∥ ρ k ∥ 2 2 ≤ 2 ∥ b k ∥ 2 2 + 2 ∥ u k ∥ 2 2 ≤ n κ n d n 2 n Vol ( K ) [ 15 16 1 6 k − 1 + 1 6 2 k − 2 ] ≤ 32 κ n d n 2 n Vol ( K ) ≤ ( d 32 R ) n
This proves Equation (24) . All that remains to show is that ρ k \rho_k ρ k is really the density at the first square-integrable step (or equivalently, k k k is the first square-integrable step). For this, observe that every chord has length at most 2 R 2R 2 R . Thus Equation (25) gives
p ( x , y ) ≥ 1 n κ n R ∣ x − y ∣ 1 − n . (29) p(x,y)\ge\frac{1}{n\kappa_nR}\lvert x-y\rvert^{1-n}. \tag*{(29)} p ( x , y ) ≥ n κ n R 1 ∣ x − y ∣ 1 − n . (29)
We claim that for some positive constants a j a_j a j , we have
ρ j ( y ) ≥ a j ∣ y − x 0 ∣ j − n \rho_j(y)\ge a_j\lvert y-x_0\rvert^{j-n} ρ j ( y ) ≥ a j ∣ y − x 0 ∣ j − n
for almost every 0 < ∣ y − x 0 ∣ < d 0<\lvert y-x_0\rvert<d 0 < ∣ y − x 0 ∣ < d , 1 ≤ j ≤ ⌊ n / 2 ⌋ 1\le j\le\lfloor n/2\rfloor 1 ≤ j ≤ ⌊ n /2 ⌋ .
To show the claim, we again use induction on j j j . The lower bound in Equation (29) , together with ρ 1 ( y ) = Vol ( K ) p ( x 0 , y ) \rho_1(y)=\operatorname{Vol}(K)p(x_0,y) ρ 1 ( y ) = Vol ( K ) p ( x 0 , y ) , proves the case of j = 1 j=1 j = 1 . For the inductive step, we let s = ∣ y − x 0 ∣ < d s=\lvert y-x_0\rvert<d s = ∣ y − x 0 ∣ < d and integrate over B ( x 0 , s ) B(x_0,s) B ( x 0 , s ) . On that ball, ∣ x − y ∣ ≤ 2 s \lvert x-y\rvert\le2s ∣ x − y ∣ ≤ 2 s and ∣ x − x 0 ∣ j − n ≥ s j − n \lvert x-x_0\rvert^{j-n}\ge s^{j-n} ∣ x − x 0 ∣ j − n ≥ s j − n , giving ρ j + 1 ( y ) ≥ a j 2 1 − n s j + 1 − n / ( n R ) \rho_{j+1}(y)\ge a_j2^{1-n}s^{j+1-n}/(nR) ρ j + 1 ( y ) ≥ a j 2 1 − n s j + 1 − n / ( n R ) . For 2 j ≤ n 2j\le n 2 j ≤ n , the squared-density integral consequently contains the divergent radial integral
∫ 0 d s 2 j − n − 1 d s = ∞ . \int_0^d s^{2j-n-1}\,ds=\infty. ∫ 0 d s 2 j − n − 1 d s = ∞.
Thus together with Equation (24) , this shows ∫ K ρ j 2 d π = ∞ \int_K\rho_j^2\,\mathrm{d}\pi=\infty ∫ K ρ j 2 d π = ∞ for 1 ≤ j < k 1\le j<k 1 ≤ j < k while ρ k \rho_k ρ k is square-integrable. Hence this proves that k k k is the first square-integrable step.
Remark 2. It is interesting to note that the number of steps required for regularisation is completely independent of the required accuracy and depends only on the dimension. To the best of our knowledge, this exact threshold for square-integrability from an interior point has not been stated previously for Hit and Run.
Remark 3. We also want to remark the following. The introduction of Kook and Vempala [ [20 ] mentions applying convergence after one Hit and Run step and their χ 2 \chi^2 χ 2 convergence estimate uses a square-integrable initial relative density [20 Corollary 1.2 and equation (1.2] . For a point start, note that χ 2 ( D 1 ∥ π ) = ∞ \chi^2(D_1\mathbin\Vert\pi)=\infty χ 2 ( D 1 ∥ π ) = ∞ for n ≥ 2 n\ge2 n ≥ 2 , but still the usual first-step truncation gives a total variation guarantee [Lovász and Vempala, 2006, Corollary 1.2 and Section 5]. In contrast, our Lemma 35 proves that 1 + ⌊ n / 2 ⌋ 1+\lfloor n/2\rfloor 1 + ⌊ n /2 ⌋ steps are necessary and sufficient for the full density to actually acquire finite χ 2 \chi^2 χ 2 .
We finish this subsection by proving Lemma 36 . For that we will use the Riesz convolution formula [40 Chapter V, Section 1] , for 0 < s < n − 1 0<s<n-1 0 < s < n − 1 and y ≠ 0 y\ne0 y = 0 , which states that
∫ R n ∣ x ∣ s − n ∣ x − y ∣ 1 − n d x = C n , s ∣ y ∣ s + 1 − n \int_{\mathbb{R}^n}\lvert x\rvert^{s-n}\lvert x-y\rvert^{1-n}\,\mathrm{d}x=C_{n,s}\lvert y\rvert^{s+1-n} ∫ R n ∣ x ∣ s − n ∣ x − y ∣ 1 − n d x = C n , s ∣ y ∣ s + 1 − n
where
C n , s = π ( n + 1 ) / 2 Γ ( s / 2 ) Γ ( ( n − s − 1 ) / 2 ) Γ ( ( n − s ) / 2 ) Γ ( ( n − 1 ) / 2 ) Γ ( ( s + 1 ) / 2 ) . C_{n,s}=\frac{\pi^{(n+1)/2}\Gamma(s/2)\Gamma((n-s-1)/2)}{\Gamma((n-s)/2)\Gamma((n-1)/2)\Gamma((s+1)/2)}. C n , s = Γ (( n − s ) /2 ) Γ (( n − 1 ) /2 ) Γ (( s + 1 ) /2 ) π ( n + 1 ) /2 Γ ( s /2 ) Γ (( n − s − 1 ) /2 ) .
Proof of Lemma 36. Using Equation (27) , enlarging the integration domain to R n \mathbb{R}^{n} R n , and recalling that 2 a = d 2a=d 2 a = d , we obtain
P ( ϕ s 1 U ) ( y ) ≤ C n , s n κ n ϕ s + 1 ( y ) . P(\phi_{s1_U})(y) \le\frac{C_{n,s}}{n\kappa_n}\phi_{s+1}(y). P ( ϕ s 1 U ) ( y ) ≤ n κ n C n , s ϕ s + 1 ( y ) .
All that is left is to bound C n , s / ( n κ n ) C_{n,s}/(n\kappa_n) C n , s / ( n κ n ) . For that, we can use the fact that Γ \Gamma Γ is log-convex on the positive reals and ( n − s − 1 ) / 2 ≥ n / 16 ≥ 1 / 8 (n-s-1)/2 \ge n/16 \ge1/8 ( n − s − 1 ) /2 ≥ n /16 ≥ 1/8 and s / 2 ≥ 3 / 8 s/2 \ge3/8 s /2 ≥ 3/8 to get
C n , s n κ n = π 2 Γ ( n / 2 ) Γ ( ( n − 1 ) / 2 ) Γ ( ( n − s − 1 ) / 2 ) Γ ( ( n − s ) / 2 ) Γ ( s / 2 ) Γ ( ( s + 1 ) / 2 ) ≤ 2 3 140 π < 16. \frac{C_{n,s}}{n\kappa_n} = \frac{\sqrt{\pi}}{2}\frac{\Gamma(n/2)}{\Gamma((n-1)/2)}\frac{\Gamma((n-s-1)/2)}{\Gamma((n-s)/2)}\frac{\Gamma(s/2)}{\Gamma((s+1)/2)} \le\frac{2}{3}\sqrt{140\pi} < 16. n κ n C n , s = 2 π Γ (( n − 1 ) /2 ) Γ ( n /2 ) Γ (( n − s ) /2 ) Γ (( n − s − 1 ) /2 ) Γ (( s + 1 ) /2 ) Γ ( s /2 ) ≤ 3 2 140 π < 16.
This proves the lemma.
Contraction for Hit and Run
We now give the geometric proof of Lemma 33, following the half-volume comparison described before.
Without loss of generality, let us translate the centre of an inball to the origin, so r B 2 n ⊆ K rB_{2}^{n} \subseteq K r B 2 n ⊆ K . Let h ( K ) h(K) h ( K ) be the functional Cheeger constant [31 Lemma 2.2] , which is the largest constant such that every Lipschitz function f f f satisfies
h ( K ) inf z ∈ R ∫ K ∣ f − z ∣ d π ≤ ∫ K ∥ ∇ f ∥ d π . (30) h(K)\inf_{z\in\mathbb{R}}\int_K |f-z|\,\mathrm{d}\pi\le\int_K \lVert\nabla f\rVert\,\mathrm{d}\pi. \tag*{(30)} h ( K ) z ∈ R inf ∫ K ∣ f − z ∣ d π ≤ ∫ K ∥ ∇ f ∥ d π . (30)
For succinctness, let δ K ( x ) = dist ( x , ∂ K ) \delta_K(x)=\operatorname{dist}(x,\partial K) δ K ( x ) = dist ( x , ∂ K ) and let R K = max x ∈ K ∣ x ∣ R_K=\max_{x\in K}|x| R K = max x ∈ K ∣ x ∣ be the radius measured from the chosen centre.
We will use this slightly technical lemma that bounds the deviation of any Lipschitz f f f over the body K K K using the (norm of the) gradient of f f f and h ( K ) h(K) h ( K ) .
Lemma 37. For every Lipschitz function f f f on K K K ,
inf z ∈ R ∫ K ∣ f − z ∣ d π ≤ 8 n r h ( K ) ∫ K δ K ∥ ∇ f ∥ d π . (31) \inf_{z\in\mathbb{R}}\int_K |f-z|\,\mathrm{d}\pi\le\frac{8n}{r h(K)}\int_K \delta_K\lVert\nabla f\rVert\,\mathrm{d}\pi. \tag*{(31)} z ∈ R inf ∫ K ∣ f − z ∣ d π ≤ r h ( K ) 8 n ∫ K δ K ∥ ∇ f ∥ d π . (31)
Towards proving this, it will help to break down slowly what we really need. One can consider this discussion to be part of the proof itself. Since r B 2 n ⊆ K rB_{2}^{n} \subseteq K r B 2 n ⊆ K , it makes sense to consider the scaled version C = 2 − 1 / n K C=2^{-1/n}K C = 2 − 1/ n K of K K K so that π ( C ) = 1 / 2 \pi(C)=1/2 π ( C ) = 1/2 (technically speaking, any scaling that makes the measure a constant less than 1 works, but 2 − 1 / n 2^{-1/n} 2 − 1/ n is convenient because taking half the volume makes life a lot easier as we will later see). Let p K ( x ) = inf { s > 0 : x ∈ s K } p_K(x)=\inf\{s>0:x\in sK\} p K ( x ) = inf { s > 0 : x ∈ sK } be the gauge8 of K K K . Then using the convexity of K K K and the inball r B 2 n rB_{2}^{n} r B 2 n , we have
x + ( 1 − p K ( x ) ) r B 2 n ⊆ K , δ K ( x ) ≥ r ( 1 − p K ( x ) ) . x+(1-p_K(x))rB_{2}^{n}\subseteq K,\qquad\delta_K(x)\ge r(1-p_K(x)). x + ( 1 − p K ( x )) r B 2 n ⊆ K , δ K ( x ) ≥ r ( 1 − p K ( x )) .
In particular, every point x ∈ C x\in C x ∈ C is at least r ( 1 − 2 − 1 / n ) r(1-2^{-1/n}) r ( 1 − 2 − 1/ n ) from the boundary, that is
δ K ( x ) ≥ r ( 1 − 2 − 1 / n ) . (32) \delta_K(x)\ge r(1-2^{-1/n}). \tag*{(32)} δ K ( x ) ≥ r ( 1 − 2 − 1/ n ) . (32)
The Cheeger inequality in Equation (30) , applied after scaling K K K to C C C , will control the error on C C C once we choose z z z as a median of f f f on C C C there. To pass from C C C to K K K , we want to bound the following difference by something:
∫ K ∣ f − z ∣ d π − 2 ∫ C ∣ f − z ∣ d π = 2 ∫ K ( 1 2 − 1 C ) ∣ f − z ∣ d π . (33) \int_K |f-z|\,\mathrm{d}\pi-2\int_C |f-z|\,\mathrm{d}\pi=2\int_K\left(\frac{1}{2}-1_C\right)|f-z|\,\mathrm{d}\pi. \tag*{(33)} ∫ K ∣ f − z ∣ d π − 2 ∫ C ∣ f − z ∣ d π = 2 ∫ K ( 2 1 − 1 C ) ∣ f − z ∣ d π . (33)
Now we observe that for any Lipschitz vector field F F F , we have the identity
2 ∫ K F ⋅ ∇ ∣ f − z ∣ d π = − 2 ∫ K div ( F ) ∣ f − z ∣ d π + 2 Vol ( K ) ∫ ∂ K ∣ f − z ∣ ( F ⋅ ν ) d s 2\int_K F\cdot\nabla|f-z|\,\mathrm{d}\pi=-2\int_K\operatorname{div}(F)|f-z|\,\mathrm{d}\pi+\frac{2}{\operatorname{Vol}(K)}\int_{\partial K}|f-z|(F\cdot\nu)\,\mathrm{d}s 2 ∫ K F ⋅ ∇∣ f − z ∣ d π = − 2 ∫ K div ( F ) ∣ f − z ∣ d π + Vol ( K ) 2 ∫ ∂ K ∣ f − z ∣ ( F ⋅ ν ) d s
where ν \nu ν is the outward unit normal vector to ∂ K \partial K ∂ K and s s s is the boundary measure.
So it is natural to ask for a vector field F F F such that div F = 1 2 − 1 C \operatorname{div}F=\frac{1}{2}-\mathbf{1}_C div F = 2 1 − 1 C almost everywhere and F ∣ ∂ K = 0 F|_{\partial K}=0 F ∣ ∂ K = 0 so that the right hand side of Equation (33) turns into9
− 2 ∫ K F ⋅ ∇ ∣ f − z ∣ d π -2\int_K F\cdot\nabla|f-z|\,\mathrm{d}\pi − 2 ∫ K F ⋅ ∇∣ f − z ∣ d π
which is much easier to handle. For the actual bound in Lemma 37, we note that
∣ − 2 ∫ K F ⋅ ∇ ∣ f − z ∣ d π ∣ ≤ 2 ∫ K ∣ F ( x ) ∣ ∥ ∇ f ( x ) ∥ d π \left|-2\int_K F\cdot\nabla|f-z|\,\mathrm{d}\pi\right|\leq2\int_K|F(x)|\lVert\nabla f(x)\rVert\,\mathrm{d}\pi − 2 ∫ K F ⋅ ∇∣ f − z ∣ d π ≤ 2 ∫ K ∣ F ( x ) ∣ ∥ ∇ f ( x )∥ d π
and hence we also want ∣ F ( x ) ∣ ≤ ( R K / r ) δ K ( x ) |F(x)|\leq(R_K/r)\delta_K(x) ∣ F ( x ) ∣ ≤ ( R K / r ) δ K ( x ) . This turns out to be a boundary value problem, which has as (one of its) solutions
F ( x ) = ϕ ( p K ( x ) ) x , ϕ ( q ) = { − 1 / ( 2 n ) , 0 ≤ q ≤ 2 − 1 / n , ( 1 − q − n ) / ( 2 n ) , 2 − 1 / n < q ≤ 1. F(x)=\phi(p_K(x))x,\qquad\phi(q)=
\begin{cases}
-1/(2n), & 0\leq q\leq2^{-1/n},\\
(1-q^{-n})/(2n), & 2^{-1/n}<q\leq1.
\end{cases} F ( x ) = ϕ ( p K ( x )) x , ϕ ( q ) = { − 1/ ( 2 n ) , ( 1 − q − n ) / ( 2 n ) , 0 ≤ q ≤ 2 − 1/ n , 2 − 1/ n < q ≤ 1.
So we will work with this. Let us quickly verify that this actually works.
The gauge p K p_K p K is easily seen to be Lipschitz and satisfies x ⋅ ∇ p K ( x ) = p K ( x ) x\cdot\nabla p_K(x)=p_K(x) x ⋅ ∇ p K ( x ) = p K ( x ) almost everywhere, and so directly differentiating the vector field gives10
F ∣ ∂ K = 0 , div F = 1 2 − 1 C . F|_{\partial K}=0,\qquad\operatorname{div}F=\frac{1}{2}-\mathbf{1}_C. F ∣ ∂ K = 0 , div F = 2 1 − 1 C .
Also note that q ∣ ϕ ( q ) ∣ ≤ 1 − q q|\phi(q)|\leq1-q q ∣ ϕ ( q ) ∣ ≤ 1 − q for 0 ≤ q ≤ 1 0\leq q\leq1 0 ≤ q ≤ 1 and ∣ x ∣ ≤ R K p K ( x ) |x|\leq R_Kp_K(x) ∣ x ∣ ≤ R K p K ( x ) , so
∣ F ( x ) ∣ ≤ R K ( 1 − p K ( x ) ) ≤ R K r δ K ( x ) . (34) |F(x)|\leq R_K(1-p_K(x))\leq\frac{R_K}{r}\delta_K(x). \tag*{(34)} ∣ F ( x ) ∣ ≤ R K ( 1 − p K ( x )) ≤ r R K δ K ( x ) . (34)
This is the core of the geometric argument, the rest is going through the motions to get the final bounds. So let us now begin the formal proof of Lemma 37 assuming the above context and notions.
Proof of Lemma 37. Choose a median z z z of f f f on C C C . Integration by parts gives
∫ K ∣ f − z ∣ d π = 2 ∫ C ∣ f − z ∣ d π − 2 ∫ K F ⋅ ∇ ∣ f − z ∣ d π . (35) \int_K|f-z|\,\mathrm{d}\pi=2\int_C|f-z|\,\mathrm{d}\pi-2\int_K F\cdot\nabla|f-z|\,\mathrm{d}\pi. \tag*{(35)} ∫ K ∣ f − z ∣ d π = 2 ∫ C ∣ f − z ∣ d π − 2 ∫ K F ⋅ ∇∣ f − z ∣ d π . (35)
To control the first term, we have
∫ C ∣ f − z ∣ d π ≤ 2 − 1 / n h ( K ) ∫ C ∥ ∇ f ∥ d π ≤ 1 r h ( K ) ( 2 1 / n − 1 ) ∫ K δ K ∥ ∇ f ∥ d π \int_C|f-z|\,\mathrm{d}\pi\leq\frac{2^{-1/n}}{h(K)}\int_C\lVert\nabla f\rVert\,\mathrm{d}\pi\leq\frac{1}{rh(K)(2^{1/n}-1)}\int_K\delta_K\lVert\nabla f\rVert\,\mathrm{d}\pi ∫ C ∣ f − z ∣ d π ≤ h ( K ) 2 − 1/ n ∫ C ∥ ∇ f ∥ d π ≤ r h ( K ) ( 2 1/ n − 1 ) 1 ∫ K δ K ∥ ∇ f ∥ d π
where the first inequality comes from applying the Cheeger inequality in Equation (30) to x ↦ f ( 2 − 1 / n x ) x \mapsto f(2^{-1/n}x) x ↦ f ( 2 − 1/ n x ) and changing variables from K K K to C C C , and the second inequality follows from the distance bound in Equation (32) . Substituting this and Equation (34) into Equation (35) gives
∫ K ∣ f − z ∣ d π ≤ [ 2 r h ( K ) ( 2 1 / n − 1 ) + 2 R K r ] ∫ K δ K ∥ ∇ f ∥ d π ≤ [ 2 n r h ( K ) log 2 + 2 R K r ] ∫ K δ K ∥ ∇ f ∥ d π , (36) \begin{aligned}
\int_K |f-z|\,\mathrm{d}\pi&\leq\left[\frac{2}{r h(K)(2^{1/n}-1)}+\frac{2R_K}{r}\right]\int_K \delta_K\lVert\nabla f\rVert\,\mathrm{d}\pi\\
&\leq\left[\frac{2n}{r h(K)\log2}+\frac{2R_K}{r}\right]\int_K \delta_K\lVert\nabla f\rVert\,\mathrm{d}\pi, \tag*{(36)}
\end{aligned} ∫ K ∣ f − z ∣ d π ≤ [ r h ( K ) ( 2 1/ n − 1 ) 2 + r 2 R K ] ∫ K δ K ∥ ∇ f ∥ d π ≤ [ r h ( K ) log 2 2 n + r 2 R K ] ∫ K δ K ∥ ∇ f ∥ d π , (36)
where we used 2 1 / n − 1 ≥ ( log 2 ) / n 2^{1/n}-1\geq(\log2)/n 2 1/ n − 1 ≥ ( log 2 ) / n .
We now need to bound 2 R K / r 2R_K/r 2 R K / r . For that, we use the elementary estimate R K h ( K ) ≤ 2 n R_Kh(K)\leq2n R K h ( K ) ≤ 2 n . To see this, choose a unit vector e e e with R K e ∈ K R_Ke\in K R K e ∈ K , and let q q q be the density of e ⋅ X e\cdot X e ⋅ X for X ∼ π X\sim\pi X ∼ π , with support [ a , b ] [a,b] [ a , b ] and median m m m . By the Brunn–Minkowski theorem [37 Theorem 7.1.1] , q 1 / ( n − 1 ) q^{1/(n-1)} q 1/ ( n − 1 ) is concave and hence q ( t ) ≥ q ( m ) ( ( b − t ) / ( b − m ) ) n − 1 q(t)\geq q(m)((b-t)/(b-m))^{n-1} q ( t ) ≥ q ( m ) (( b − t ) / ( b − m ) ) n − 1 for m ≤ t ≤ b m\leq t\leq b m ≤ t ≤ b . Integrating this bound gives
1 2 ≥ q ( m ) ( b − m ) n \frac{1}{2}\geq\frac{q(m)(b-m)}{n} 2 1 ≥ n q ( m ) ( b − m )
Analogously
1 2 ≥ q ( m ) ( m − a ) n \frac{1}{2}\geq\frac{q(m)(m-a)}{n} 2 1 ≥ n q ( m ) ( m − a )
Thus in particular, we have q ( m ) ≤ n / ( b − a ) q(m)\leq n/(b-a) q ( m ) ≤ n / ( b − a ) . To turn this into a bound on h ( K ) h(K) h ( K ) , we show h ( K ) ≤ 2 q ( m ) h(K)\leq2q(m) h ( K ) ≤ 2 q ( m ) by testing the Cheeger inequality on functions approaching the indicator of the median halfspace { e ⋅ x > m } \{e\cdot x>m\} { e ⋅ x > m } . For s > 0 s>0 s > 0 , consider the function
ψ s ( x ) = min { 1 , ( e ⋅ x − m ) + s } \psi_s(x)=\min\left\{1,\frac{(e\cdot x-m)_+}{s}\right\} ψ s ( x ) = min { 1 , s ( e ⋅ x − m ) + }
This function has median zero, so Equation (30) gives
h ( K ) ∫ K ψ s d π ≤ ∫ K ∥ ∇ ψ s ∥ d π = 1 s ∫ m m + s q ( t ) d t . h(K)\int_K\psi_s\,\mathrm{d}\pi\leq\int_K\lVert\nabla\psi_s\rVert\,\mathrm{d}\pi=\frac{1}{s}\int_m^{m+s}q(t)\,\mathrm{d}t. h ( K ) ∫ K ψ s d π ≤ ∫ K ∥ ∇ ψ s ∥ d π = s 1 ∫ m m + s q ( t ) d t .
Letting s ↓ 0 s\downarrow0 s ↓ 0 gives h ( K ) / 2 ≤ q ( m ) h(K)/2\leq q(m) h ( K ) /2 ≤ q ( m ) . Since b − a ≥ R K + r b-a\geq R_K+r b − a ≥ R K + r , we obtain
h ( K ) ≤ 2 n R K + r . (37) h(K)\leq\frac{2n}{R_K+r}. \tag*{(37)} h ( K ) ≤ R K + r 2 n . (37)
Using Equation (37) in Equation (36) , we have the bound
2 n r h ( K ) log 2 + 2 R K r ≤ ( 4 + 2 log 2 ) n r h ( K ) < 8 n r h ( K ) . \frac{2n}{rh(K)\log2}+\frac{2R_K}{r}\leq\left(4+\frac{2}{\log2}\right)\frac{n}{rh(K)}<\frac{8n}{rh(K)}. r h ( K ) log 2 2 n + r 2 R K ≤ ( 4 + log 2 2 ) r h ( K ) n < r h ( K ) 8 n .
Taking the infimum over constants proves the lemma. □
We can now finish the proof of Lemma 33. Also, we recall that the Babuška–Aziz constant C B A C_{BA} C B A is the least constant such that every mean-zero f ∈ L 2 ( π ) f\in L^2(\pi) f ∈ L 2 ( π ) admits a vector field G ∈ H 0 1 ( int K ; R n ) G\in H_0^1(\operatorname{int}K;\mathbb{R}^n) G ∈ H 0 1 ( int K ; R n ) with div G = f \operatorname{div}G=f div G = f and
∫ ∥ ∇ G ∥ F 2 d π ≤ C B A ∥ f ∥ 2 2 \int\lVert\nabla G\rVert_F^2\,\mathrm{d}\pi\leq C_{BA}\lVert f\rVert_2^2 ∫ ∥ ∇ G ∥ F 2 d π ≤ C B A ∥ f ∥ 2 2
Proof of Lemma 33. Let us first turn the inequality from Lemma 37 into a variance bound. For a Lipschitz function f f f , choose a median z z z under π \pi π and apply Equation (31) separately to ( f − z ) + 2 (f-z)_{+}^{2} ( f − z ) + 2 and ( z − f ) + 2 (z-f)_{+}^{2} ( z − f ) + 2 , each of which has median zero. Applying Cauchy-Schwarz and adding the bounds gives
Var π ( f ) ≤ 256 n 2 r 2 h ( K ) 2 ∫ K δ K 2 ∥ ∇ f ∥ 2 d π . (38) \operatorname{Var}_{\pi}(f) \le\frac{256n^{2}}{r^{2}h(K)^{2}}\int_{K}\delta_{K}^{2}\lVert\nabla f\rVert^{2}\,\mathrm{d}\pi. \tag*{(38)} Var π ( f ) ≤ r 2 h ( K ) 2 256 n 2 ∫ K δ K 2 ∥ ∇ f ∥ 2 d π . (38)
The inequality in Equation (38) is the improved Poincare inequality [42 Definition 3.1] and thus the improved Poincare constant is 256 n 2 r 2 h ( K ) 2 \frac{256n^{2}}{r^{2}h(K)^{2}} r 2 h ( K ) 2 256 n 2 .
To connect the improved Poincare constant with the Babuška-Aziz constant C B A C_{\mathrm{BA}} C BA , we would need Equation (38) to hold on a larger class than just Lipschitz functions. To that end, let us show that we can extend the inequality to f ∈ L 2 ( π ) ∩ H l o c 1 ( int K ) f \in L^{2}(\pi) \cap H^{1}_{\mathrm{loc}}(\operatorname{int} K) f ∈ L 2 ( π ) ∩ H loc 1 ( int K ) as follows11 . For 0 < s < 1 0 < s < 1 0 < s < 1 , contract f f f and let f s ( x ) = f ( s x ) f_{s}(x) = f(sx) f s ( x ) = f ( s x ) . The function f s f_{s} f s is H 1 H^{1} H 1 on a neighbourhood of K K K , and convexity gives δ K ( s x ) ≥ s δ K ( x ) \delta_{K}(sx) \ge s\delta_{K}(x) δ K ( s x ) ≥ s δ K ( x ) . Thus its weighted energy12 is at most s − n s^{-n} s − n times that of f f f . Convolving f s f_{s} f s with mollifiers gives smooth functions converging to it in H 1 ( int K ) H^{1}(\operatorname{int} K) H 1 ( int K ) [1 Section 2.2] . Since δ K \delta_{K} δ K is bounded, we can pass to the limit in Equation (38) to obtain it for f s f_{s} f s . Finally, f s → f f_{s} \to f f s → f in L 2 ( π ) L^{2}(\pi) L 2 ( π ) as s ↑ 1 s \uparrow1 s ↑ 1 , so Var π ( f s ) → Var π ( f ) \operatorname{Var}_{\pi}(f_{s}) \to\operatorname{Var}_{\pi}(f) Var π ( f s ) → Var π ( f ) . Using the weighted-energy bound above and s − n → 1 s^{-n} \to1 s − n → 1 now gives Equation (38) for f f f .
We now use Equation (38) to bound the Babuška-Aziz constant C B A C_{\mathrm{BA}} C BA , and then apply the comparison with the Hit and Run spectral gap γ H R \gamma_{\mathrm{HR}} γ HR .
Applying the Costabel-Zsuppán comparison [8 Lemma 3.4 and Remark 3.6] (Theorem 2.1][Zsuppán 2020) to Equation (38) gives13
C B A ≤ 1 + 1024 n 2 r 2 h ( K ) 2 . C_{\mathrm{BA}} \le1 + \frac{1024n^{2}}{r^{2}h(K)^{2}}. C BA ≤ 1 + r 2 h ( K ) 2 1024 n 2 .
Next we can use [20 Proposition 2.1] to get
γ H R ≥ n + 2 n ( 2 + C B A ) . \gamma_{\mathrm{HR}} \ge\frac{n+2}{n(2+C_{\mathrm{BA}})}. γ HR ≥ n ( 2 + C BA ) n + 2 .
Using Equation (38) and r h ( K ) / n ≤ 1 rh(K)/n \le1 r h ( K ) / n ≤ 1 from Equation (37) , we have
γ H R ≥ 1 1027 r 2 h ( K ) 2 n 2 . \gamma_{\mathrm{HR}} \ge\frac{1}{1027}\frac{r^{2}h(K)^{2}}{n^{2}}. γ HR ≥ 1027 1 n 2 r 2 h ( K ) 2 .
The Cheeger-Poincare equivalence for convex bodies then gives h ( K ) 2 ≥ c / C P I ( π ) h(K)^{2} \ge c/C_{\mathrm{PI}}(\pi) h ( K ) 2 ≥ c / C PI ( π ) for a universal c > 0 c > 0 c > 0 [31 Theorem 1.5] . This proves Equation (20) .
For the geometric bound of Equation (21) , we use Milman’s convex-domain diameter estimate [31 Theorem 5.10] to get
C P I ( π ) ≤ diam ( K ) 2 π 2 ≤ 4 R 2 π 2 . (39) C_{\mathrm{PI}}(\pi) \le\frac{\operatorname{diam}(K)^{2}}{\pi^{2}} \le\frac{4R^{2}}{\pi^{2}}. \tag*{(39)} C PI ( π ) ≤ π 2 diam ( K ) 2 ≤ π 2 4 R 2 . (39)
Substituting this in Equation (20) proves Equation (21) .
Finally, let us prove the L 2 L^2 L 2 contraction claim. For each fixed direction, averaging along parallel chords is a conditional-expectation operator and hence an orthogonal projection. Averaging these projections over the sphere gives a self-adjoint positive operator P P P that preserves π \pi π [20 Section 2.1] , see also [36 Section 3.1] . Its spectral gap is
γ H R = inf f ∈ L 2 ( π ) , ∫ f d π = 0 f ≠ 0 ⟨ f , ( I − P ) f ⟩ L 2 ( π ) ∥ f ∥ L 2 ( π ) 2 . \gamma_{\mathrm{HR}} = \inf_{\substack{f\in L^2(\pi),\ \int f\,\mathrm{d}\pi=0\\ f\ne0}} \frac{\langle f,(I-P)f\rangle_{L^2(\pi)}}{\lVert f\rVert_{L^2(\pi)}^2}. γ HR = f ∈ L 2 ( π ) , ∫ f d π = 0 f = 0 inf ∥ f ∥ L 2 ( π ) 2 ⟨ f , ( I − P ) f ⟩ L 2 ( π ) .
On the P P P -invariant subspace { f ∈ L 2 ( π ) : ∫ K f d π = 0 } \{f\in L^2(\pi):\int_K f\,\mathrm{d}\pi=0\} { f ∈ L 2 ( π ) : ∫ K f d π = 0 } , the spectrum of P P P lies in [ 0 , 1 − γ H R ] [0,1-\gamma_{\mathrm{HR}}] [ 0 , 1 − γ HR ] and thus the spectral theorem gives
∥ P s f ∥ L 2 ( π ) ≤ ( 1 − γ H R ) s ∥ f ∥ L 2 ( π ) ≤ e − γ H R s ∥ f ∥ L 2 ( π ) ≤ exp ( − r 2 s n 2 C P I ( π ) ) ∥ f ∥ L 2 ( π ) . \lVert P^s f\rVert_{L^2(\pi)}\le(1-\gamma_{\mathrm{HR}})^s\lVert f\rVert_{L^2(\pi)}\le e^{-\gamma_{\mathrm{HR}}s}\lVert f\rVert_{L^2(\pi)}\le\exp\left(-\frac{r^2s}{n^2C_{\mathrm{PI}}(\pi)}\right)\lVert f\rVert_{L^2(\pi)}. ∥ P s f ∥ L 2 ( π ) ≤ ( 1 − γ HR ) s ∥ f ∥ L 2 ( π ) ≤ e − γ HR s ∥ f ∥ L 2 ( π ) ≤ exp ( − n 2 C PI ( π ) r 2 s ) ∥ f ∥ L 2 ( π ) .
where the last inequality follows from Equation (20) .
The one-step truncation bound
Finally, in this subsection, we justify the one-step deduction used in Equation (13) . The idea is to separate the mass in a neighborhood around x 0 x_0 x 0 after the first step and apply the contraction bound in Lemma 33 to the density outside this neighbourhood. For arbitrary 0 < η , β < 1 0<\eta,\beta<1 0 < η , β < 1 , both sampling guarantees hold whenever
t ≥ 1 + 1 2 γ H R [ n log 8 R d + ( n + 1 ) log 1 η + n log 1 β ] . (40) t\ge1+\frac{1}{2\gamma_{\mathrm{HR}}}\left[n\log\frac{8R}{d}+(n+1)\log\frac{1}{\eta}+n\log\frac{1}{\beta}\right]. \tag*{(40)} t ≥ 1 + 2 γ HR 1 [ n log d 8 R + ( n + 1 ) log η 1 + n log β 1 ] . (40)
To see this, let a = η β / 4 a=\eta\beta/4 a = η β /4 for simplicity of notations and consider the neighborhood S = B ( x 0 , a d ) S=B(x_0,ad) S = B ( x 0 , a d ) . Conditional on the line chosen in the first step of Hit and Run, the fraction of the chord that lies inside S S S is at most a a a . Hence the first-step probability of being inside S S S is at most a a a . By Equation (26) , the density on S c S^c S c is bounded by
ρ 1 1 S c ≤ 1 n a n − 1 ( R d ) n . \rho_1\mathbf{1}_{S^c}\le\frac{1}{na^{n-1}}\left(\frac{R}{d}\right)^n. ρ 1 1 S c ≤ n a n − 1 1 ( d R ) n .
We want to understand what happens to the error that we controlled in Lemma 33 for this neighborhood. So define
f = P t − 1 ( ρ 1 1 S c ) − ( 1 − D 1 ( S ) ) f=P^{t-1}(\rho_1\mathbf{1}_{S^c})-(1-\mathcal{D}_1(S)) f = P t − 1 ( ρ 1 1 S c ) − ( 1 − D 1 ( S ))
where the first term captures the part of the first-step density outside S S S after another t − 1 t-1 t − 1 steps, and the second term is the mean. Then f f f has mean zero by definition and
ρ t − 1 = f + P t − 1 ( ρ 1 1 S ) − D 1 ( S ) . \rho_{t-1}=f+P^{t-1}(\rho_1\mathbf{1}_S)-\mathcal{D}_1(S). ρ t − 1 = f + P t − 1 ( ρ 1 1 S ) − D 1 ( S ) .
The contribution from S S S is nonnegative, and its total mass is preserved
∫ K P t − 1 ( ρ 1 1 S ) d π = D 1 ( S ) ≤ a . \int_K P^{t-1}(\rho_1\mathbf{1}_S)\,\mathrm{d}\pi=\mathcal{D}_1(S)\le a. ∫ K P t − 1 ( ρ 1 1 S ) d π = D 1 ( S ) ≤ a .
and thus Lemma 33 gives
∥ f ∥ 2 2 ≤ 1 n a n − 1 ( R d ) n e − 2 γ H R ( t − 1 ) . \lVert f\rVert_2^2\le\frac{1}{na^{n-1}}\left(\frac{R}{d}\right)^n e^{-2\gamma_{\mathrm{HR}}(t-1)}. ∥ f ∥ 2 2 ≤ n a n − 1 1 ( d R ) n e − 2 γ HR ( t − 1 ) .
Now suppose this squared norm is at most η 2 β / 8 \eta^2\beta/8 η 2 β /8 . Each of the sets
{ ∣ f ∣ > η / 2 } and { P t − 1 ( ρ 1 1 S ) > η / 2 } \{ |f| > \eta/2 \} \quad\text{and}\quad\{ P^{t-1}(\rho_1\mathbf{1}_S) > \eta/2 \} { ∣ f ∣ > η /2 } and { P t − 1 ( ρ 1 1 S ) > η /2 }
has π \pi π -measure at most β / 2 \beta/2 β /2 by Markov’s inequality, and hence their union has measure at most β \beta β . Outside this union, the upper deviation of ρ t \rho_t ρ t from one is at most η \eta η , and the lower deviation is at most η / 2 + a ≤ η \eta/2+a\leq\eta η /2 + a ≤ η .
Finally, to bound the probability of sampling from the exceptional set, observe that
D t ( B a d t , η ) ≤ β + β ∥ f ∥ 2 + a ≤ β + η β 8 + η β 4 ≤ 2 β . D_t(\mathrm{Bad}_t,\eta) \leq\beta+\sqrt{\beta}\lVert f\rVert_2+a \leq\beta+\frac{\eta\beta}{\sqrt{8}}+\frac{\eta\beta}{4}\leq2\beta. D t ( Bad t , η ) ≤ β + β ∥ f ∥ 2 + a ≤ β + 8 η β + 4 η β ≤ 2 β .
Taking logarithms shows that Equation (40) gives ∥ f ∥ 2 2 ≤ η 2 β / 8 \lVert f\rVert_2^2\leq\eta^2\beta/8 ∥ f ∥ 2 2 ≤ η 2 β /8 , as required. Substituting Equation (17) in this threshold and using Equations (20) and (39) gives Equation (13) .