0
$\begingroup$

Assume we are given two vectors $A,B$ that each contains $c$ numbers: $A=[a_i>0]_{1 \times c}$. We want to see the weighted summation of which one is larger. In other words, given two vectors $A$ and $B$:

$$ws(A) = \sum_{1 \leq i \leq c}{i.a_i}, ~~~~ws(B) = \sum_{1 \leq i \leq c}{i.b_i}$$

we want to know $ws(A)>ws(B)?$

For making the problem simpler, I add another condition to the problem:

$$\sum_{1 \leq i \leq c}{a_i} = \sum_{1 \leq i \leq c}{b_i}$$

Now, is there any way to approximately claim which one of these vectors is larger without running the summation (We may consider the summation of a small number of elements and decide based on that)?

$\endgroup$
  • 2
    $\begingroup$ What do you mean by "approximately"? And there are only a finite number of elements to start with so you can't consider anything other than a finite number of them! $\endgroup$ – David Richerby Dec 8 '14 at 9:00
  • $\begingroup$ It is obvious that we can calculate this summation exactly by summing over all the elements. But if we consider the elements $1..(c-1)$, there will be some error with our calculation. I need to know whether there exist some mathematical work on this. Even though with any assumption on the distribution of these numbers, it would be appreciated. $\endgroup$ – orezvani Dec 8 '14 at 10:29
  • 1
    $\begingroup$ If you get to consider $1..(c-1)$ then you can still solve the problem exactly because of the equal sum condition. The value of $b_c-a_c$ follows from the first $c-1$ values. If you get to inspect less values, you must make some assuption about the distribution of the input to say anything about the accuracy of the algorithm. This then becomes an exercise in probability theory. This paper may be relevant: math.uni.wroc.pl/~pms/files/16.2/Article/16.2.11.pdf $\endgroup$ – Tom van der Zanden Dec 8 '14 at 11:04
  • $\begingroup$ Why do you want to compute the weighted sum, and not just the sum? I mean, there is a natural 1-1 correspondence between $i\cdot a_i$ and an element $f_i$ and a 1-1 correspondence between $i\cdot b_i$ and an element $g_i$, where $f_i$ and $g_i$ are the i-th values in some vectors $F$ and $G$. Then essentially you are asking if the sum of the numbers in one vector ($F$) is different from the sum of the numbers in the other vector ($G$). Am I missing something in your question? $\endgroup$ – MightyMouse Dec 8 '14 at 22:54
  • $\begingroup$ @TomvanderZanden Thank you for pointing out the problem with my example, that's right, for $c-1$ it is still obvious and we are looking for smaller values. However, your explanation seems to be useful for me, as I can have assumption on the distribution of such numbers. I will read that paper and hope to be able to incorporate it ;) $\endgroup$ – orezvani Dec 9 '14 at 5:24
2
$\begingroup$

Let's consider the problem of comparing the sums of two vectors $A$ and $B$ that have all their $N$ real values in the range $[0, c]$.

First, let's start with two facts.

Union Bound. Let $Y_1, \ldots, Y_K$ be K events in a probability space. Then \begin{equation} Pr\left(\bigcup_{j=1}^KY_j\right) \leq \sum_{j=1}^K Pr\left(Y_j\right). \end{equation} (The inequality is equality for disjoint events $Y_j$.)

Hoeffding Bound (1, 2). Let $X_1, \ldots, X_R$ be $R$ independent random variables, each taking values in the range $\mathcal{J} = [\alpha, \beta]$. Let $\mu$ denote the mean of their expectations. Then \begin{equation} Pr\left(\left|\frac{1}{R}\sum_{i=1}^RX_i - \mu\right|\geq \epsilon\right) \leq e^{-2R\epsilon^2/(\beta-\alpha)^2} \end{equation}

Idea

The first idea is that we are going to approximate the values of the sums for the two vectors $A$ and $B$ within some precision $\varepsilon$ with high probability (high confidence if you prefer). Then the argument that the two expectations that we have for the actual sums of the vectors $A$ and $B$ are well separated will be a simple application of the Union bound assuming that we have very high confidence for both expectations.

Definitions

Let $S(A), S(B)$ be the actual sum for the vectors $A$ and $B$ respectively and $S^*(A)$ and $S^*(B)$ be the approximations of the two values that we are going to come up with. In particular, $$\begin{array}{rcl} S(A) &=& \mu_A\cdot N \\ S(B) &=& \mu_B\cdot N \end{array}$$ where $\mu_A$ and $\mu_B$ are the true mean values of the entries of the vectors respectively.

We now reduce the problem of approximating the sums to that of approximating the mean values $\mu_A$ and $\mu_B$; let's call the approximations $\mu_A^*$ and $\mu_B^*$.

Well Separated Approximations of Sums. We will say that the two approximated sums are well separated if the following holds: \begin{eqnarray} \left|S^*(A) - S^*(B)\right| &=& \left|\mu_A^*\cdot N - \mu_B^*\cdot N\right| \\ &=& \left|\mu_A^* - \mu_B^*\right|\cdot N \\ &\geq& 2\cdot\epsilon\cdot N \end{eqnarray} where $\epsilon$ is the accuracy within which we have approximated the means $\mu_A^*$ and $\mu_B^*$.

(The intuition is that the sums are well separated if their respective mean values are well separated.)

Continuation

By the Hoeffding bound, if we require that our estimate is incorrect bounded by some small probability $\delta/2$ (it will be apparent soon why I divide $\delta$ by two), then we need $$R \geq \left\lceil\frac{(\beta-\alpha)^2}{2\epsilon^2}\cdot\ln\frac{2}{\delta}\right\rceil = \left\lceil\frac{c^2}{2\epsilon^2}\cdot\ln\frac{2}{\delta}\right\rceil$$ samples (runs) so that we can come up with the real values $\mu_A^*$ and $\mu_B^*$ that approximate the true real values $\mu_A$ and $\mu_B$ respectively within $\epsilon$ with probability at least $1-\frac{\delta}{2}$. In other words, it is only with probability at most $\frac{\delta}{2}$ that we will not have good estimates for each of the $\mu_A^*$ and $\mu_B^*$.

Now, by the Union bound, either of our estimates is incorrect with probability at most $\delta/2 + \delta/2 = \delta$. Or, the other way around, with probability at least $1-\delta$ both of our estimates $\mu_A^*$ and $\mu_B^*$ are within $\epsilon$ of their true values.

Theorem

Drawing $R$ samples from each vector where $$R \geq \left\lceil\frac{c^2}{2\epsilon^2}\cdot\ln\frac{2}{\delta}\right\rceil$$ it is guaranteed that with probability $1-\delta$ both of our estimates for $\mu_A^*$ and $\mu_B^*$ are within $\epsilon$ of their true values, and thus the approximations $S^*(A)$ and $S^*(B)$ that we have for the sums $S(A)$ and $S(B)$ are within $\epsilon\cdot N$ of their true values. Thus, it suffices to check if the inequality $$\left|S^*(A) - S^*(B)\right| \geq 2\cdot\epsilon\cdot N$$ holds. If the inequality holds, then with probability $1-\delta$ (that's our confidence) the two sums are different and in fact we can say which one is bigger with the same confidence.

Concluding Remark

Just to note that with the approach above we need $\epsilon^{-1} = o\left(\sqrt{N}\right)$ so that the number of samples/runs $R$ is sublinear (btw, sublinear algorithms is an active field of research) and thus it makes sense to take samples from the huge vectors $A$ and $B$ rather than computing the sums directly. This also means that with this approach the separation bound between the two approximated sums should be $\Omega\left(\sqrt{N}\right)$.

References

[1] Wassily Hoeffding. Probability Inequalities for Sums of Bounded Random Variables. Journal of the American Statistical Association, 58(301):13–30, March 1963

[2] L. Devroye, L. Györfi, and G. Lugosi. A Probabilistic Theory of Pattern Recognition. Springer, 1996.

Code

Below is some code that I wrote yesterday for playing around with the problem. The difference is I think that I did not divide by 2 the $\delta$, and moreover, for the approximations I am expressing $\delta$ as a negative power of $e$ ($\approx 2.71828\ldots$) so that I can simplify the calculations and not take logarithms. Other than that, I generate two big arrays with slightly skewed entries; the first one with values between 0 and 9 and the other one with values between 1 and 10. In principle this needs a GMP implementation, but I guess the following will do for now. I really enjoyed the problem! Thanks! I am of course very interested in seeing different approaches to the problem.

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <ctgmath>

#define SIZE 1000000
#define EPSILON 0.1
#define DELTA_EXPONENT 4

#define MIN_VALUE  0
#define MAX_VALUE 10

/************************************************************************************/

void assignRandomValues (unsigned int * array, const unsigned long int size, const int low, const int high);
unsigned int trueSum (unsigned int * array, const unsigned long int size);
bool areTheApproximationsSufficientlyDifferent (const unsigned long int size, const long double epsilon, const unsigned int difference);
unsigned int approximateSum (unsigned int * array, const unsigned long int size, const int maxValue, const long double epsilon, const int deltaExponent);
long double approximateMean (unsigned int * array, const unsigned long int size, const int maxValue, const long double epsilon, const int deltaExponent);

/************************************************************************************/

int main () {
    unsigned int * a1, * a2, s1, s2, s1Approx, s2Approx, difference;
    bool flag;
    time_t timer;

    // Randomize
    timer = time(NULL);

    // Print the basic properties
    std::cout << "Timer seed: " << timer << std::endl;
    std::cout << "Size      : " << SIZE << std::endl;
    std::cout << "Epsilon   : " << EPSILON << std::endl;
    std::cout << "Delta exp : " << DELTA_EXPONENT << std::endl << std::endl;

    // Reserve memory
    a1 = new unsigned int [SIZE];
    a2 = new unsigned int [SIZE];

    // Generate the arrays
    assignRandomValues (a1, SIZE, MIN_VALUE, MIN_VALUE + (MAX_VALUE - MIN_VALUE)/2 + 4);
    assignRandomValues (a2, SIZE, MIN_VALUE + (MAX_VALUE - MIN_VALUE)/2 - 4, MAX_VALUE);

    // Find and print the true values
    s1 = trueSum (a1, SIZE);
    s2 = trueSum (a2, SIZE);
    std::cout << "The true sum value for a1 is: " << s1 << std::endl;
    std::cout << "The true sum value for a2 is: " << s2 << std::endl;

    // Find and print the approximate values
    s1Approx = approximateSum (a1, SIZE, MAX_VALUE, EPSILON, DELTA_EXPONENT);
    s2Approx = approximateSum (a2, SIZE, MAX_VALUE, EPSILON, DELTA_EXPONENT);
    std::cout << "The approximate sum value for a1 is: " << s1Approx << std::endl;
    std::cout << "The approximate sum value for a2 is: " << s2Approx << std::endl;

    // Print the approximate difference and indicate if they are sufficiently separated
    difference = static_cast<unsigned int>(fabs(static_cast<long double>(s1Approx) - static_cast<long double>(s2Approx)));
    std::cout << "The approximated difference is: " << difference << std::endl;
    flag = areTheApproximationsSufficientlyDifferent(SIZE, EPSILON, difference);
    std::cout << "The approximated difference is sufficiently big (w.h.p.): ";
    std::cout << (flag ? "YES" : "NO") << std::endl;

    // Deallocate memory
    delete [] a1;
    delete [] a2;

    return 0;
}

/************************************************************************************/

void assignRandomValues (unsigned int * array, const unsigned long int size, const int low, const int high) {
    unsigned long int i;

    for (i = 0; i < size; i++) {
        array [i] = low + (rand() % (high - low + 1));
    }
}

/************************************************************************************/

unsigned int trueSum (unsigned int * array, const unsigned long int size) {
    unsigned long int i, sum = 0;
    for (i = 0; i < size; i++)
        sum += array[i];
    return sum;
}

/************************************************************************************/

bool areTheApproximationsSufficientlyDifferent (const unsigned long int size, const long double epsilon, const unsigned int difference) {
    unsigned int bound = static_cast<unsigned int>(ceil(2.0*size*epsilon));
    if (difference > bound)
        return true;
    return false;
}

/************************************************************************************/

unsigned int approximateSum (unsigned int * array, const unsigned long int size, const int maxValue, const long double epsilon, const int deltaExponent) {
    long double mean = approximateMean (array, size, maxValue, epsilon, deltaExponent);
    return static_cast<unsigned int>(round(mean * size));
}

long double approximateMean (unsigned int * array, const unsigned long int size, const int maxValue, const long double epsilon, const int deltaExponent) {
    unsigned long int samples, i, sum, pos, integerPart;
    long double floatingPart, mean;

    samples = static_cast<unsigned long int>(ceil(maxValue * maxValue * deltaExponent / (static_cast<long double>(2.0) * epsilon * epsilon)));

    std::cout << "Requiring " << samples << " samples for the approximation." << std::endl;

    sum = 0;
    for (i = 0; i < samples; i++) {
        pos = rand () % size;
        sum += array[pos];
    }

    integerPart  = sum / samples;
    floatingPart = static_cast<long double>((sum - integerPart * samples)) / static_cast<long double>(samples);
    mean = static_cast<long double>(integerPart) + floatingPart;
    return mean;
}

/************************************************************************************/

Wrapping Up for the Original Question

In the original question we want to approximate values of the form $i\cdot a_i$ or $i\cdot b_i$ and this means that these new values are now in the range $[0, c\cdot N]$ assuming that $a_i, b_i \in [0, c]$ for $i\in{0, 1,\ldots, N}$.

Above, I assumed that $c \ll N$. However, since the number of samples that is required has quadratic dependence on the maximum value that can be found in these new vectors, we really need to draw $R \geq \Omega\left(\frac{c^2\cdot N^2}{\epsilon^2}\ln\left(\frac{1}{\delta}\right)\right)$ samples. On the other hand, a direct summation will perform $O(N)$ additions of $O(N)$ multiplications. Thus, sampling would make sense in terms of savings if we could say that $R=o\left(N\right)$. In other words, ignoring the logarithmic dependence on $\delta$, we want $$\frac{c^2\cdot N^2}{\epsilon^2} = o(N)\;.$$ This would be true if $$\epsilon = \omega(c\cdot N^{1/2})$$ thus yielding $R=o\left(N\right)$.

The question is if this $\epsilon$ is meaningful for comparisons. The answer is yes when the two vectors are significantly different (contrary to the helper that original vectors have values that add up to the same number). Let's see what I mean by an example.

Example

Let $c=N$. Moreover, let $$ \begin{array}{rcl} A &=& \left\langle 1, 1, \ldots, 1, \ldots, 1\right\rangle \\ B &=& \left\langle 1, 2, \ldots, i, \ldots, N\right\rangle \end{array} $$ be two vectors with $N$ elements. Then, the requested summation of the products $i\cdot a_i$ and $i\cdot b_i$ can be seen as the summation on the vectors $$ \begin{array}{rcl} F &=& \left\langle 1, 2, \ldots, i, \ldots, N\right\rangle \\ G &=& \left\langle 1^2, 2^2, \ldots, i^2, \ldots, N^2\right\rangle \end{array} $$ Note that $S(F) = \sum_{i=1}^N f_i = \Theta\left(N^2\right)$ and $S(G) = \sum_{i=1}^N g_i = \Theta\left(N^3\right)$. Similarly, their mean values are significantly different, since $\mu_{F} = \Theta\left(N\right)$ while $\mu_G = \Theta\left(N^2\right)$

The accuracy $\epsilon$ that we are talking about involves the estimate of these last true mean values $\mu_F$ and $\mu_G$. Thus, if we set $$\epsilon = \Theta\left(c\cdot N^{1/2+\xi}\right) = \Theta\left(N^{3/2+\xi}\right)$$ for some $\xi\in(0,1/2)$ there will be cases (like in this example) where the mean values will be significantly far away on the real line and thus we will be able to tell which one is bigger than the other with few samples (and as a consequence we will be able to separate the two sums on the real line with that many samples).

Concluding the Wrap-Up

Now if we revisit our definition for well-separated sums, we are going to require the following inequality for our definition: $$\left|S^*(F)-S^*(G)\right| \geq 2\cdot N^{5/2+\xi}$$ for some $\xi\in\left(0, 1/2\right)$. Actually any $\xi\in\left(0,1/2\right)$ will do. The larger the $\xi$ the fewer samples that we draw. However, the catch is that the larger the $\xi$, the more restrictive our inequality is for separating the two sums. In other words, the closer $\xi$ is to $1/2$ the more unlikely it is to encounter vectors that can be separated using our method, since we require the gap between their true values to be even larger.

I believe the above clears up everything, but in case it does not, just drop me a line and I will try to explain more the details.

$\endgroup$

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.