11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I guess you mean $\sum_{k=1}^n a_k \leq 1-\varepsilon$. $\endgroup$ – R B Dec 15 '14 at 17:37
  • $\begingroup$ Indeed -- fixed it. $\endgroup$ – Clement C. Dec 15 '14 at 17:37
  • $\begingroup$ 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... $\endgroup$ – Clement C. Dec 17 '14 at 19:02
  • $\begingroup$ I assume query model allows you to choose the $k$ for which you query $a_k$, is this right? $\endgroup$ – kodlu Dec 17 '14 at 22:27
  • $\begingroup$ Yes (you get to choose whichever point you want to "disclose"). $\endgroup$ – Clement C. Dec 18 '14 at 9:23
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Clement C. Jan 2 '15 at 5:16
  • $\begingroup$ 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 $\endgroup$ – Sariel Har-Peled Jan 2 '15 at 5:28
4
+50
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Clement C. Dec 23 '14 at 9:25
  • $\begingroup$ (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.) $\endgroup$ – Clement C. Dec 25 '14 at 16:44
  • 2
    $\begingroup$ @ClementC., I added a lower bound, per your request. $\endgroup$ – D.W. Dec 27 '14 at 1:36
  • $\begingroup$ 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). $\endgroup$ – Clement C. Dec 29 '14 at 17:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.