Distribution Testing Meets Sum Estimation

Pinki Pradhan, Sampriti Roy · 2025

Read Distribution Testing Meets Sum Estimation by Pinki Pradhan, Sampriti Roy (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-15153.txt.

Introduction

Pinki Pradhan and Sampriti Roy estimate the total weight of a sorted list while sampling only a sliver of it, in a 2025 paper. The universe holds n items with non-increasing weights; the goal is the sum, within a small factor, using few conditional samples. Sum estimation under this sampling model was unexplored.

Their algorithm hits the target with a number of weighted and uniform samples that grows only mildly with list size and accuracy demands. It matches a known logarithmic lower bound, so the cost is near optimal. The approach extends to unimodal weight profiles with a few extra queries to find the lightest point. A companion algorithm estimates how many items carry any weight at all, under a threshold assumption. The work imports ideas from distribution testing into a classic estimation problem, with tight guarantees on both sides.

Catalog record

CREATORPinki Pradhan, Sampriti Roy
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE48 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-15153

Browse the full library · About the Tower of Babel

Full text

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

Distribution Testing Meets Sum Estimation Pinki Pradhan, Sampriti Roy Abstract We study the problem of estimating the sum of n n elements, each associated with a weight w ⁡ ( i ) w(i) , within a structured universe. Specifically, our goal is to estimate the sum W = ∑ i = 1 n w ⁡ ( i ) W=\sum_{i=1}^{n}w(i) within a factor of ( 1 ± ϵ ) (1\pm\epsilon) using a sublinear number of samples, under the assumption that the weights are non-increasing, i.e., w ⁡ ( 1 ) ≥ w ⁡ ( 2 ) ≥ ⋯ ≥ w ⁡ ( n ) w(1)\geq w(2)\geq\dots\geq w(n) . The sum estimation problem is well-studied under different access models to the universe U U . However, to the best of our knowledge, nothing is known about the sum estimation problem using non-adaptive conditional sampling. To address this gap, we explore the sum estimation problem using non-adaptive conditional weighted and non-adaptive conditional uniform samples, assuming that the underlying distribution ( D ⁡ ( i ) = w ⁡ ( i ) / W D(i)=w(i)/W ) is monotone. Furthermore, we extend our approach to the case where the underlying distribution of U U is unimodal. Additionally, we investigate the problem of approximating the support size of U U when w ⁡ ( i ) = 0 w(i)=0 or w ⁡ ( i ) ≥ W / n w(i)\geq W/n using hybrid sampling, where both weighted and uniform sampling are available for accessing U U . We provide an algorithm for estimating the sum of n n elements where the weights of the elements are non-increasing. Our algorithm requires O ⁡ ( 1 ϵ 3 ​ log ⁡ n + 1 ϵ 6 ) O(\frac{1}{\epsilon^{3}}\log{n}+\frac{1}{\epsilon^{6}}) non-adaptive weighted conditional samples and O ⁡ ( 1 ϵ 3 ​ log ⁡ n ) O(\frac{1}{\epsilon^{3}}\log{n}) non-adaptive uniform conditional samples. Our algorithm also follows the Ω ⁡ ( log ⁡ n ) \Omega(\log{n}) lower bound proposed by [ 2 ] . We also extend our algorithm when the underlying distribution D D is unimodal. The sample complexity of the algorithm is the same as that of monotone with an additional O ⁡ ( log ⁡ n ) O(\log{n}) adaptive evaluation queries to find the minimum weighted point in the domain [ n ] [n] . Additionally, we investigate the problem of estimating the support size of U U , which consists of n n elements such that the weight corresponding to them is either 0 0 or at least W / n W/n . The algorithm uses O ⁡ ( log 3 ⁡ ( n / ϵ ) ϵ 8 ⋅ log 4 ⁡ log ⁡ ( n / ϵ ) ϵ ) O\big(\frac{\log^{3}{(n/\epsilon)}}{\epsilon^{8}}\cdot\log^{4}{\frac{\log{(n/\epsilon)}}{\epsilon}}\big) uniform samples and O ⁡ ( log ⁡ ( n / ϵ ) ϵ 2 ⋅ log ⁡ log ⁡ ( n / ϵ ) ϵ ) O\big(\frac{\log{(n/\epsilon)}}{\epsilon^{2}}\cdot\log{\frac{\log{(n/\epsilon)}}{\epsilon}}\big) weighted samples from the universe and approximate the support size k k such that k − 2 ​ ϵ ​ n ≤ k ^ ≤ k + ϵ ​ n k-2\epsilon n\leq\hat{k}\leq k+\epsilon n . National Institute of Science Education and Research, An OCC of Homi Bhabha National Institute, Bhubaneswar, Odisha, [email protected] Department of Computer Science and Engineering, IIT Madras, [email protected] ccs \textcolor redAlgorithms, Distribution testing, Sub-linear Algorithms keywords Sum estimation, Conditional sampling, Hybrid sampling, Monotone, Unimodal † † runningauthor: P. Pradhan, S. Roy † † copyright: Jane Open Access and Joan R. Public † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction In recent years, distribution testing and sum estimation have attracted considerable attention due to their applications in statistics and data science. Distribution testing is a subfield of property testing that aims to determine whether an unknown distribution satisfies a certain property \mathcal{P} or if it is \epsilon -far from \mathcal{P} . In this context, the distribution is accessed through samples, and the key measure of interest is the number of samples needed to test the property effectively (see [ 25 ] , [ 27 ] , [ 28 ] , [ 8 ] for comprehensive overviews). On the other hand, sum estimation involves efficiently approximating the total sum of a set, where each element is assigned a weight. Let U be a universe of n elements, with each element i\in[n] associated with a weight w(i):U\to[0,\infty) . We do not have access to the entire universe U , and the goal is to compute the sum W=\sum_{i=1}^{n}w(i) by sampling elements from U . Each time we get a sample, we observe one element along with its weight to estimate W using a sublinear number of samples. Since exact computation of W requires \Omega(n) many samples, we aim to provide an estimated value \hat{W} such that for any \epsilon\in(0,1) , (1-\epsilon)W\leq\hat{W}\leq(1+\epsilon)W with probability at least \frac{2}{3} . The universe of elements U can be viewed as an unknown distribution D . Sampling an element from U is equivalent to drawing an index i independently and identically distributed according to D in the standard access model. For example, the underlying distribution of the universe can be thought of as D(i)=\frac{w(i)}{W} and sampling an element from U according to its weight is equivalent to sampling an element i according to the standard access oracle of D . Each sample we get is a pair containing the index and the weight of the element corresponding to this index, i.e., (i,w(i)) . The sum estimation problem was first introduced by Motwani et al. [ 30 ] , where the authors developed a weighted sampling method to estimate W=\sum_{i\in[n]}w(i) . This was later improved by Beretta and Tětek [ 7 ] . However, an open question remains whether it is possible to further optimize the sample complexity under certain assumptions about the universe. In addition to fundamental problems such as testing uniformity, identity, and closeness, distribution testing has been extended to cases where the distribution is assumed to have a specific structure. As we consider an underlying distribution D corresponding to the universe’s weights, it is worth checking whether the sample complexity of the classical sum estimation problem can be improved under some assumptions about the structure of D . Another interesting connection between distribution testing and sum estimation is exploring whether approximation problems in distribution testing can be applied to the universe of a set of elements when the weights are unknown. For example, consider the problem of estimating the support size of a distribution. Let D be a distribution over [n] , and the support size of D is defined as the number of non-zero elements in the domain [n] . A similar question arises when considering a universe of n elements, where we aim to estimate the support size without knowing the weights. 1.1 Sampling Oracles The primary goal of a distribution testing algorithm is to test the properties of an unknown distribution without accessing the entire distribution. Similarly, in

Read the complete text