Lower bound on estimating $\sum_{k=1}^n a_k$ for non-increasing $(a_k)_k$

Question

I'd like to know (related to this other question) if lower bounds were known for the following testing problem: one is given query access to a sequence of non-negative numbers $a_n \geq \dots\geq a_1$ and $\varepsilon \in (0,1)$, with the promise that either $\sum_{k=1}^n a_k = 1$ or $\sum_{k=1}^n a_k \leq 1-\varepsilon$.

How many queries (lookups) are sufficient and necessary for an (adaptive) randomized algorithm to distinguish between the two cases, with probability at least $2/3$?

I have found a previous post that gives a logarithmic (in $n$) upper bound for the related problem of approximating the sum, and a roughly matching lower bound on that problem for deterministic algorithms; but couldn't find a result for the specific problem I am considering (in particular, randomized algorithms).

---

Edit: Following the answer below, I guess I should have been clearer: in the above (and particularly in the asymptotics for the lower bound), $n$ is the "main" quantity seen as going to infinity, while $\varepsilon$ is an (arbitrarily small) constant.

Answer 1

Here are the lower bounds I can show. I conjecture that for a fixed $\epsilon$, the right lower bound is $\Omega( \log n)$, but naturally I might be wrong.

I am going to use a decreasing sequence (just for convenience). The basic mechanism is breaking the sequence into $L$ blocks. In the $i$th block there are going to be $n_i$ elements (i.e., $\sum_i n_i = n$).

In the following, we want the algorithm to succeeds with probability $\geq 1-\delta$, for some parameter $\delta >0$.

First lower bound: $\displaystyle \Omega\left( \frac{1}{\epsilon} \log \frac{1}{\delta} \right)$.

The $i$th block has $n_i = 2^{i-1}$ elements, so $L = \lg n$. We set the value of all the elements in the $i$th block to be $(1+X_i)/(2n_iL)$, where $X_i$ is a variable that is either $0$ or $1$. Clearly, the total sum of this sequence is $$ \alpha = \sum_{i=1}^L \frac{1+X_i}{2n_i L} = \frac{1}{2} + \frac{1}{2L}\left(\sum_{i=1}^L X_i \right). $$ Imagine picking each $X_i$ with probability $\beta$ to be $1$ and $0$ otherwise. To estimate $\alpha$, we need a reliable estimate of $\beta$. In particulate, we want to be able to distinguish the base $\beta = 1-4\epsilon$ and, say, $\beta=1$.

Now, imagine sampling $m$ of these random variables, and let $Z_1, \ldots, Z_m$ be the sampled variables. Settings $Y = \sum_{i=1}^m (1-X_i)$ (note, that we are taking the sum of the complement variables), we have $\mu = E[Y] = (1-\beta) m$, and Chernoff inequality tells us that if $\beta =1-4\epsilon$, then $\mu = 4\epsilon m$, and the probability of failure is $$ P\left[ Y \leq 2\epsilon m \right] = P\left[ Y \leq (1-1/2) \mu \right] \leq \exp \left( -\mu (1/2)^2 / 2 \right) = \exp \left( -\epsilon m / 2 \right). $$ To make this quantity smaller than $\delta$, we need $\displaystyle m \geq \frac{2}{\epsilon} \ln \frac{1}{\delta}$.

The key observation is that the Chernoff inequality is tight (one has to be careful, because it is not correct for all parameters, but it is correct in this case), so you can not do better than that (up to constants).

Second lower bound: $\Omega( \log n / \log \log n)$.

Set the $i$th block size to be $n_i = L^i$, where $L = \Theta( \log n / \log \log n)$ is the number of blocks. An element in the $i$th block has value $\alpha_i = \Bigl(1/L\Bigr)/n_i$. So the total sum of the values in the sequence is $1$.

Now, we might decide to pick an arbitrary block, say the $j$th one, and set all values in its block to be $\alpha_{j-1} = L \alpha_j$ (instead of $\alpha_j$). This increases the contribution of the $j$th block from $1/L$ to $1$, and increase the total mass of the sequence to (almost) $2$.

Now, informally, any randomized algorithm must check the value in each one of the blocks. As such, it must read at least $L$ values of the sequence.

To make the above argument more formal, with probability $p=1/2$, give the original sequence of mass $1$ as the input (we refer to this as original input). Otherwise, randomly select the block that has the increased values (modified input). Clearly, if the randomized algorithm reads less than, say, $L/8$ entries, it has probability (roughly) $1/8$ to detect a modified input. As such, the probability this algorithm fails, if it reads less than $L/8$ entries is at least $$ (1-p)(7/8) > 7/16 > 1/3. $$

---

P.S. I think by being more careful about the parameters, the first lower bound can be improved to $\Omega(1/\epsilon^2)$.

Answer 2

Lower bound

At least $\Omega(1/\sqrt{\epsilon})$ queries are necessary to distinguish the two cases.

Consider the sequence $a_1,\dots,a_n$ given by $\epsilon,2\epsilon,3\epsilon,4\epsilon,\dots$, with $n$ chosen so that $a_1+\dots+a_n = 1$. In particular, we can take $n \approx 1/\sqrt{2\epsilon}$.

Now construct a new sequence $a'_1,\dots,a'_n$ by modifying a single element of the above sequence by subtracting $\epsilon$. In other words, $a'_1=a_1$, $a'_2=a_2$, etc., except that $a'_i = a_i - \epsilon$. Notice that $a'_1 + \dots + a'_n = 1-\epsilon$.

How many probes does it take to distinguish $a_1,\dots,a_n$ from $a'_1,\dots,a'_n$? Well, they differ in only a single element (the $i$th element), so it takes $\Omega(n)$ probes to achieve a constant probability of distinguishing. Now recalling that $n \approx 1/\sqrt{2\epsilon}$; we find that $\Omega(1/\sqrt{\epsilon})$ probes are needed.

Upper bound

I think you can distinguish the two cases using $O(\lg(n/\epsilon) [\lg n + 1 / \epsilon^2])$ queries. I don't know if this is optimal.

Here's how. Let's partition the range $[0,1]$ as follows:

$$[0,1] = [0,0.25\epsilon/n] \cup (0.25\epsilon/n,0.5\epsilon/n] \cup (0.5\epsilon/n,\epsilon/n] \cup (\epsilon/n,2\epsilon/n] \cup (2\epsilon/n,4\epsilon/n] \cup \dots \cup (\ldots,1].$$

This is a partition, so each $a_i$ value must fall into exactly one of the ranges above. We'll partition the $a_i$ values according to which range they are in. Each $a_i$ value falls into exactly one of these ranges, and the ones that fall into a particular range all appear consecutively in your sorted order. Therefore, for any given range $[\ell,u]$, we can find the indices $i,j$ such that $a_i,\dots,a_j \in [\ell,u]$ using binary search. This requires $O(\lg(n/\epsilon))$ binary searches. Assume we've done that.

Now, we'll estimate the sum of values in each range. The first range will be handled separately from all the rest:

• For the first range $[0,0.25\epsilon/n)$, we can bound the sum of values in that range to somewhere between $0$ and $m \times 0.25\epsilon/n$, where $m$ is the number of values that fall within that range. Since $m \le n$, the absolute error in this bound will be at most $0.25 \epsilon$.

• For each other range, we can bound the sum of values in that range to within relative error $\delta$ using $O(1/\delta^2)$ random probes. (The key here is that all of the values in that range have a known lower-bound, and are at most $2 \times$ the lower bound.) We'll choose $\delta = 0.25 \epsilon$.

The error in the sum of the estimates for all but the first range will be at most $0.25 \epsilon$. The error in the estimate for the first range will be at most $0.25 \epsilon$. Therefore, the total error in the sum of all these estimates will be $\le 0.5 \epsilon$, which is enough to distinguish between a total of $1$ vs a total of $1-\epsilon$.