<p>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.</p>

<p>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$).</p>

<p>In the following, we want the algorithm to succeeds with probability $\geq 1-\delta$, for some parameter $\delta &gt;0$.</p>

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

<p>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$.</p>

<p>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 <em>complement</em> 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}$.</p>

<p>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).</p>

<p><strong>Second lower bound: $\Omega( \log n / \log \log n)$.</strong></p>

<p>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$.</p>

<p>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$.</p>

<p>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.</p>

<p>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>

<hr>

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

CC BY-SA 3.0
2015-01-02T05:16:54.220Z
Thank you for this! I have a small question regarding the first,$\Omega(1/\epsilon)$ lb (more particularly the possible quadratic improvement). Since we have here the one-sided promise problem, which implies that as soon as the algorithm "sees" any value that gives any evidence that $\beta < 1$, it can conclude without having to get a more accurate estimate of $\beta$: doesn't that mean that the $1/\epsilon$ is optimal for this construction, as basically one would expect either all $X_i$'s to be 1, or at least an $\epsilon$ fraction not to be?
Clement C.
CC BY-SA 3.0
2015-01-02T05:28:05.443Z
Yeah.  If you rally want to distinguish only between 1 and 1-epsilon then of course you can not improve the lower bound... I was thinking about trying to distinguish other ranges... s
Sariel Har-Peled
CC BY-SA 3.0
2015-01-01T21:17:54.640Z
2015-01-01T21:31:56.237Z
2015-01-01T21:31:56.237Z
Sariel Har-Peled
<h2>Lower bound</h2>

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

<p>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}$.</p>

<p>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$.</p>

<p>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.</p>

<h2>Upper bound</h2>

<p>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.</p>

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

<p>$$[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].$$</p>

<p>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.</p>

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

<ul>
<li><p>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$.</p></li>
<li><p>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$.</p></li>
</ul>

<p>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$.</p>

CC BY-SA 3.0
2014-12-23T09:25:48.097Z
Thanks -- this looks interesting (as far as I can tell, it's not the same approach as the one used in the paper/discussion linked above), and I'll have a deeper look at what you wrote. However, I'm looking for a lower bound rather than an upper bound -- i.e., how many queries are *necessary*.
Clement C.
CC BY-SA 3.0
2014-12-25T16:44:33.587Z
(As the time is up, I'm awarding the "bounty" to the answer nonetheless -- although I'm still looking for a reference for a lower bound, if there's one somewhere up there.)
Clement C.
CC BY-SA 3.0
2014-12-27T01:36:12.167Z
@ClementC., I added a lower bound, per your request.
D.W.
CC BY-SA 3.0
2014-12-29T17:27:29.417Z
Thank you (although, as per the usual focus in property testing, I implicitly considered $n$ as the primary quantity going to infinity, while $\varepsilon$ is some arbitrarily small constant: I edited the question to make this explicit).
Clement C.
CC BY-SA 3.0
2014-12-22T23:49:26.340Z
2014-12-27T01:35:57.920Z
2014-12-27T01:35:57.920Z
D.W.
<p>I'd like to know (related to <a href="https://cstheory.stackexchange.com/questions/27492/testing-sortedness-of-a-normalized-list-of-n-numbers">this other question</a>) 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$. </p>

<p>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$?</p>

<p>I have found <a href="https://cstheory.stackexchange.com/questions/9791/approximate-sum-of-a-sorted-list/9813#9813">a previous post</a> 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).</p>

<hr>

<p><strong>Edit:</strong> 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.</p>

CC BY-SA 3.0
2014-12-15T17:37:05.163Z
I guess you mean $\sum_{k=1}^n a_k \leq 1-\varepsilon$.
R B
CC BY-SA 3.0
2014-12-15T17:37:33.310Z
Indeed -- fixed it.
Clement C.
CC BY-SA 3.0
2014-12-17T19:02:36.627Z
Well, without the order a dependence on $n$ would be necessary, I reckon (with or without sampling). A "bad" instance (pair of sequences) would be for instance a sequence with all $a_k$'s being equal to $\frac{1-\varepsilon}{n-1}$, except for one (arbitrary, random) $j$ such that $a_j$ is either equal to $\varepsilon$ (in the first sequence) and $0$ (in the second). Without $\Omega(n)$ queries, the two sequences cannot be told apart...
Clement C.
CC BY-SA 3.0
2014-12-17T22:27:37.257Z
I assume query model allows you to choose the $k$ for which you query $a_k$, is this right?
kodlu
CC BY-SA 3.0
2014-12-18T09:23:12.370Z
Yes (you get to choose whichever point you want to "disclose").
Clement C.
CC BY-SA 3.0
2015-01-01T05:07:42.173Z
I can show lower bounds of $\Omega( \log n / \log \log n)$, and $\Omega(1/\epsilon)$. I assume you want a lower bound of $\Omega( \log n)$?
Sariel Har-Peled
CC BY-SA 3.0
2015-01-01T16:28:50.607Z
@SarielHar-Peled: the latter would be great, but even $\tilde{\Omega}(\log n)$ seems good! Is the proof somewhere "out there in the literature", or is it new?
Clement C.
CC BY-SA 3.0
2015-01-01T21:23:22.463Z
Ok. I posted my lower bound as an answer. It was not immediate at all...
Sariel Har-Peled
<reference-request><randomized-algorithms><property-testing>
Lower bound on estimating $\sum_{k=1}^n a_k$ for non-increasing $(a_k)_k$
Clement C.
# Lower bound on estimating $\sum_{k=1}^n a_k$ for non-increasing $(a_k)_k$

(Asked by: username_0 on 2014-12-15)

I'd like to know (related to [this other question](https://cstheory.stackexchange.com/questions/27492/testing-sortedness-of-a-normalized-list-of-n-numbers)) 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](https://cstheory.stackexchange.com/questions/9791/approximate-sum-of-a-sorted-list/9813#9813) 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.

**Tags:** reference-request, randomized-algorithms, property-testing
> **Comments:**
> **username_1**: I guess you mean $\sum_{k=1}^n a_k \leq 1-\varepsilon$.  
> **username_0**: Indeed -- fixed it.  
> **username_0**: Well, without the order a dependence on $n$ would be necessary, I reckon (with or without sampling). A "bad" instance (pair of sequences) would be for instance a sequence with all $a_k$'s being equal to $\frac{1-\varepsilon}{n-1}$, except for one (arbitrary, random) $j$ such that $a_j$ is either equal to $\varepsilon$ (in the first sequence) and $0$ (in the second). Without $\Omega(n)$ queries, the two sequences cannot be told apart...  
> **username_2**: I assume query model allows you to choose the $k$ for which you query $a_k$, is this right?  
> **username_0**: Yes (you get to choose whichever point you want to "disclose").  
> **username_3**: I can show lower bounds of $\Omega( \log n / \log \log n)$, and $\Omega(1/\epsilon)$. I assume you want a lower bound of $\Omega( \log n)$?  
> **username_0**: @SarielHar-Peled: the latter would be great, but even $\tilde{\Omega}(\log n)$ seems good! Is the proof somewhere "out there in the literature", or is it new?  
> **username_3**: Ok. I posted my lower bound as an answer. It was not immediate at all...  

---

## 2 answers

### Answer by username_3 on 2015-01-01. Score: 5 | Accepted answer

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)$.

> **Comments:**
> **username_0**: Thank you for this! I have a small question regarding the first,$\Omega(1/\epsilon)$ lb (more particularly the possible quadratic improvement). Since we have here the one-sided promise problem, which implies that as soon as the algorithm "sees" any value that gives any evidence that $\beta < 1$, it can conclude without having to get a more accurate estimate of $\beta$: doesn't that mean that the $1/\epsilon$ is optimal for this construction, as basically one would expect either all $X_i$'s to be 1, or at least an $\epsilon$ fraction not to be?  
> **username_3**: Yeah.  If you rally want to distinguish only between 1 and 1-epsilon then of course you can not improve the lower bound... I was thinking about trying to distinguish other ranges... s  

---

### Answer by username_4 on 2014-12-22. Score: 4

## 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$.

> **Comments:**
> **username_0**: Thanks -- this looks interesting (as far as I can tell, it's not the same approach as the one used in the paper/discussion linked above), and I'll have a deeper look at what you wrote. However, I'm looking for a lower bound rather than an upper bound -- i.e., how many queries are *necessary*.  
> **username_0**: (As the time is up, I'm awarding the "bounty" to the answer nonetheless -- although I'm still looking for a reference for a lower bound, if there's one somewhere up there.)  
> **username_4**: @ClementC., I added a lower bound, per your request.  
> **username_0**: Thank you (although, as per the usual focus in property testing, I implicitly considered $n$ as the primary quantity going to infinity, while $\varepsilon$ is some arbitrarily small constant: I edited the question to make this explicit).  

---

