3
$\begingroup$

The problem statement is as follows:

Can we determine precisely the number of elements less than the mean in a list $A$ of $n$ numbers in only one pass through the array (starting at $A_1$ and ending at $A_n$) with only constant memory?

By "constant memory" I mean a constant number of $O(m \log_2 n)$ bit words where $m$ is the number of bits to represent the largest value in $A$. Some other things to consider:

  1. Assume $m$ is non-constant and $m \geq \log_2 n$. If $m$ were constant, we could not even count $n$ as Yuval mentioned.
  2. Assume values in $A$ are integers, but does it affect the problem if they are rational, or real valued?
  3. Assume values in $A$ are uniform random. It helps if they are uniform random because we can get a tight confidence bound with a constant number of elements. How high of a confidence bound can we get?
  4. Time complexity does not matter. You can spend as much time as you want on a particular $A_i$ if that helps, but once you move to $A_{i+1}$ you cannot go back unless you have stored $A_i$ in one of your constant memory words.
  5. What if the values in $A$ are non-uniform random with distribution is unknown? What if the distribution is known?
  6. What if we are not constrained to going from $A_1$ to $A_n$, perhaps we could randomly sample and get a tight confidence bound even if the distribution is non-uniform?
  7. What if instead of mean, we wanted values less than median? Does this help at all?

It's clear with 2 passes through the array we can get this value precisely with no probability involved. With one pass through the array this seems not be possible, but I am not sure. You could create an adversary that waits until the last element to give it an extreme value and throw off all previous calculations. However, with a uniform distribution this is limited. Any thoughts on these variations or an answer under the assumptions provided would be appreciated.

$\endgroup$
  • $\begingroup$ (1) If you only have constant memory, then you can't even count up to $n$. You can't represent the output within your memory. (2) If $m$ is constant, your model is just a DFA. $\endgroup$ – Yuval Filmus Apr 11 at 20:12
  • $\begingroup$ @YuvalFilmus that's a good point, I missed an assumption that $m \geq \log_2 n$, and by that notion $m$ would no longer be constant. $\endgroup$ – ryan Apr 11 at 20:23
  • $\begingroup$ @YuvalFilmus Would $m \geq \log_2 n$ be too few bits, still? Maybe we couldn't even compute the mean explicitly with this few bits. My goal for requiring constant memory is to prevent someone from "saving" the array elsewhere to go back over. I would like to provide enough memory do necessary operations, without "cheating" in a sense. $\endgroup$ – ryan Apr 11 at 20:30
  • $\begingroup$ You can compute the sum using $O(m\log n)$ bits, so the two-pass algorithm does work. $\endgroup$ – Yuval Filmus Apr 11 at 21:35
  • $\begingroup$ @YuvalFilmus I think thats a fair assumption to make. So a constant number of $O(m \log n)$ bit words are allowed, but only 1 pass through. $\endgroup$ – ryan Apr 11 at 21:39
4
$\begingroup$

Consider an algorithm for arrays of length $n$ consisting of entries from $0$ to $n$, and using space $S$ bits.

Suppose that the first half of the array consists of pairs $a,n-a$ (where $a \leq n/2$). By choosing the second half appropriately, we can make the average of the entire array anything from $n/4$ to $3n/4$ (discretized to multiples of $1/n$). In particular, the state of the memory after reading the first half should store the number of pairs with $n/4 \leq a \leq n/2$. For every non-empty subset of $\{n/4,\ldots,n/2\}$, we can construct a first half of the array which contains exactly these values of $a$. This shows that the number of first halves that are pairwise distinguishable is at least $2^{n/4}$, hence $S = \Omega(n)$.

A very similar construction establishes an $\Omega(n)$ lower bound even when replacing the mean with the median.

$\endgroup$
  • $\begingroup$ That's a good explanation of the information theoretic lower bound. So we must break the "constant" memory constraint to derive a precise count. As a variant mentioned above, how high of a confidence bound could we get on our solution if we allow a constant amount of $O(m \log n)$? $\endgroup$ – ryan Apr 12 at 0:02
  • $\begingroup$ Definitely an interesting question. $\endgroup$ – Yuval Filmus Apr 12 at 11:34

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.