1
$\begingroup$

Let $x_1,x_2,x_3,\dots,x_n$ be n points on the unit segment $[0,1]$.Mathematically it can be shown that there always exists a point $\in[0,1]$ such that $$ \frac1n \sum_1^n|x-x_i|=\frac12$$. Given $x_1,x_2,x_3,\dots,x_n$, how do we find(numerically) $x$ satisfying the above relation to given level of accuracy?In other words ,given $x_1,x_2,x_3,\dots,x_n$ and $\epsilon>0$ ,the task is to find $x$ such that $$ \Bigg|{\frac1n \sum_1^n|x-x_i|-\frac12}\Bigg| < \epsilon$$.Thank you for any hints/suggestions in advance.

$\endgroup$

1 Answer 1

2
$\begingroup$

The function $f(x)= \sum_{i=1}^n |x -x_i|$ is a piecewise linear continuous function with angles at the points $x_i$. Assuming the points are ordered, one can compute successively $f(0), f(x_1),\cdots ,f(x_n), f(1)$. It remains to see on which interval the function crosses the value $\frac{n}{2}$ and find the intersection point by interpolation on this interval.

The values of the function can be computed efficiently because one has \begin{equation} |x_{k+1} - x_i| - |x_k - x_i| = (x_{k+1}- x_k)([i\le k]-[i > k]) \end{equation} where $[]$ is Iverson's bracket. Hence \begin{equation} f(x_{k+1}) - f({x_k}) = (x_{k+1}-x_k)(k - (n-k)) = (x_{k+1}-x_k)(2k-n) \end{equation}

The above arguments also shows that $f(x_k)$ decreases and reaches its minimum when $k = \lfloor\frac{n+1}{2}\rfloor$ then increases. The maximum of $f$ is reached at $x=0$ or $x=1$. In fact one has $f(0)+f(1) = n$, so the algorithm could start from $x=0$ or from $x=1$, depending of which value of $f$ is larger than $n/2$.

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