Lower bound on estimating $\sum_{k=1}^n a_k$ for non-increasing $(a_k)_k$ 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.
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 &gt;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) &gt; 7/16 &gt; 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)$.