1
$\begingroup$

Given a sequence of numbers $A = a_1, a_2, \cdots, a_n$.

One way to calculate the mean absolute deviation of $A$ is by $G(A)= \sum_{i=0}^n |a_i - median(A)|$.

yet, there can be an alternative, by first aggregating a histogram with $k$ bins. $A \to (w_1, w_2, \cdots, w_k)$ with edges $e_0, e_1, \cdots, e_k$.

And then get an approximation from bin edges and bin weights.

I'm wondering how can i bound the error given some $k$ bins and assuming $A \sim U(0, m)$. uniformly random.

If $k > n$, the resulting is clearly the same, but if $k<<n$, not sure how can i be sure about the result.

Improve this question
$\endgroup$
5
  • $\begingroup$ Presumably you want to index the sum in $G(A)$ by $i=1$ to $i=n$ and you wish to divide it by $n.$ Since finding the median of $n$ numbers and aggregating them into bins are both $O(n)$ operations (when done optimally), is there any point to estimating the median of $A$ from its binned representation? In fact, what is the point to this procedure, given that all the component operations are very quick $O(n)$ calculations? Would it be that you do not have access to the original $a_i$? $\endgroup$
    – whuber ♦
    Mar 24, 2021 at 18:36
  • $\begingroup$ since i need to calculate $G$ for all subsequences of $A$, using a histogram-based solution would allow me to carry the "state" in an additive manner. please assume this approximation is meaningful and important. how can i approach the error bound part under this assumption $\endgroup$
    – yupbank
    Mar 24, 2021 at 18:39
  • $\begingroup$ If your concern truly is with the all-subsequences version, that's worth separate consideration, because there are some obvious improvements that could be made. For instance, given one subsequence it should be easy to generate many other subsequences with the same median, enabling rapid updating of their MADs. Indeed, how could you even exploit the histogram-based approach, given that the histogram doesn't contain any information about the original order of the numbers in $A$? $\endgroup$
    – whuber ♦
    Mar 24, 2021 at 18:41
  • $\begingroup$ right, well but I'm still interested in this problem, and most importantly, how to approach it. $\endgroup$
    – yupbank
    Mar 24, 2021 at 18:58
  • $\begingroup$ > exploit the histogram-based approach , i can encode $a_i$ into a histogram with bin edges from global, and adding histograms would carry the distribution on subsequences $\endgroup$
    – yupbank
    Mar 24, 2021 at 19:14

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.