We study the problem of estimating the sum of n elements of a universe U, \(|U|=n\) , each associated with a weight \( w(i)> 0\) , within a structured universe. Specifically, our goal is to estimate the sum \(W = \sum _{i=1}^n w(i)\) within a factor of \((1 \pm \epsilon )\) using a sublinear number of samples, under the assumption that the weights are non-increasing, i.e., \( w(1) \ge w(2) \ge \ldots \ge w(n) \) . The sum estimation problem is well-studied under different access models to the universe 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\) ) is monotone. Furthermore, we extend our approach to the case where the underlying distribution of U is unimodal. We also address the problem of approximating the support size of U when \(w(i) = 0\) or \(w(i) \ge W/n\) using hybrid sampling, where both weighted and uniform sampling are available to access U. We provide an algorithm for estimating the sum of n elements where the weights of the elements are non-increasing. Our algorithm requires \(O(\frac{1}{\epsilon ^3}\log {n}+\frac{1}{\epsilon ^6})\) non-adaptive weighted conditional samples and \(O(\frac{1}{\epsilon ^3}\log {n})\) non-adaptive uniform conditional samples. Our algorithm also follows the \(\varOmega (\log {n})\) lower bound proposed by [2]. We also extend our algorithm when the underlying distribution D is unimodal. The sample complexity of the algorithm is the same as that of monotone with an additional \(O(\log {n})\) adaptive evaluation queries to find the minimum weighted point in the domain [n]. Additionally, we investigate the problem of estimating the support size of U, which consists of n elements such that the weight corresponding to them is either 0 or at least W/n. Our algorithm uses \(O\big ( \frac{\log ^3{(n/\epsilon )}}{\epsilon ^8}\cdot \log ^4{\frac{\log {(n/\epsilon )}}{\epsilon }}\big )\) uniform samples and \(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 such that \(k-2\epsilon n\le \hat{k}\le k+\epsilon n\) .

Distribution Testing Meets Sum Estimation

会议论文
发表日期：

2026年

查看全文

Sampriti Roy

摘要

We study the problem of estimating the sum of n elements of a universe U, \(|U|=n\) , each associated with a weight \( w(i)> 0\) , within a structured universe. Specifically, our goal is to estimate the sum \(W = \sum _{i=1}^n w(i)\) within a factor of \((1 \pm \epsilon )\) using a sublinear number of samples, under the assumption that the weights are non-increasing, i.e., \( w(1) \ge w(2) \ge \ldots \ge w(n) \) . The sum estimation problem is well-studied under different access models to the universe 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\) ) is monotone. Furthermore, we extend our approach to the case where the underlying distribution of U is unimodal. We also address the problem of approximating the support size of U when \(w(i) = 0\) or \(w(i) \ge W/n\) using hybrid sampling, where both weighted and uniform sampling are available to access U. We provide an algorithm for estimating the sum of n elements where the weights of the elements are non-increasing. Our algorithm requires \(O(\frac{1}{\epsilon ^3}\log {n}+\frac{1}{\epsilon ^6})\) non-adaptive weighted conditional samples and \(O(\frac{1}{\epsilon ^3}\log {n})\) non-adaptive uniform conditional samples. Our algorithm also follows the \(\varOmega (\log {n})\) lower bound proposed by [2]. We also extend our algorithm when the underlying distribution D is unimodal. The sample complexity of the algorithm is the same as that of monotone with an additional \(O(\log {n})\) adaptive evaluation queries to find the minimum weighted point in the domain [n]. Additionally, we investigate the problem of estimating the support size of U, which consists of n elements such that the weight corresponding to them is either 0 or at least W/n. Our algorithm uses \(O\big ( \frac{\log ^3{(n/\epsilon )}}{\epsilon ^8}\cdot \log ^4{\frac{\log {(n/\epsilon )}}{\epsilon }}\big )\) uniform samples and \(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 such that \(k-2\epsilon n\le \hat{k}\le k+\epsilon n\) .