20
$\begingroup$

You're given a list of $22$ points in $[0,1]$ (not necessarily distinct), and you're asked to select, at every iteration, $2$ points to be substituted by their midpoint. After $20$ iteration, you should end up with $2$ points. Is there a selection strategy that leads to $2$ points that are at most $10^{-3}$ apart independently of the distribution of the initial list? For $n$ starting points, what would be the optimal distance between the final $2$ points that one could achieve?

$\endgroup$
  • $\begingroup$ One strategy that comes to mind is, given $x_1\le x_2\le ... \le x_{22}$, selecting $x_1$ and $x_{22}$ as the substitution points, and iterating this. I have yet to completely analyze its behavior though. $\endgroup$ – forallepsilon Aug 27 '14 at 16:02
  • 3
    $\begingroup$ This is a cool question, what's your motivation? $\endgroup$ – Rustyn Aug 27 '14 at 16:41
  • 2
    $\begingroup$ @forallepsilon, your strategy fails on the instance where $x_i=0$ for $1\leq i\leq 10$ and $x_i=1$ for $11\leq i\leq22$. On that instance the final distance is $\frac{1}{8}$. $\endgroup$ – Katy Aug 27 '14 at 18:06
  • 1
    $\begingroup$ You can if you first choose $x_{21}$ and $x_{22}$, then choose $x_{21}$ and $x_{20}$, and then follow your strategy. $\endgroup$ – user133281 Aug 27 '14 at 18:29
  • 1
    $\begingroup$ @Rustyn More than that, we can leave 2 zeros and 2 ones after 18 iterations, which leads to a final configuration of two coinciding points $\endgroup$ – user2097 Aug 29 '14 at 18:47
7
$\begingroup$

Consider the $n$-tuples ${\bf a}_n:=(0,0,\ldots,0,1)\in[0,1]^n$. I claim that for these ${\bf a}_n$ the optimal final distance $d_n$ is given by $$d_n={1\over 2^{n-2}}\ .$$ Proof. This is certainly true for $n=2$. Assume that it is true for an $n\geq2$, and consider ${\bf a}_{n+1}$. At the first step of the process we can either average a $0$ with $1$, or average two zeros. Using the first option we arrive at ${\bf a}_n'=(0,0,\ldots,0,{1\over2})\in[0,1]^n$, and using the second option we arrive at ${\bf a}_n$. It follows that $$d_{n+1}=\min\{{1\over2}d_n,d_n\bigr\}={1\over2}d_n\ .$$ Therefore the best "universal" constant $\delta_n$ is $\geq{1\over 2^{n-2}}$. It is easily checked that $\delta_3={1\over2}$ (here the optimal strategy is to first average the extreme $x_k$). The following figure shows the optimal end result for the quadruple $(0,x,y,1)$. We can learn two things from this figure: When $n=4$ then we can always obtain a final difference $d\leq0.25={1\over 2^2}$, which implies $\delta_4={1\over4}$, and, more important: Things get very complicated with increasing $n$.

enter image description here

For $n=5$ one cannot draw such a figure. Instead one can do the following: Denote by $g(x,y,z)$ the optimal end result for the quintuple $(0,x,y,z,1)$. The following figure shows the $121$ graphs of the functions $$g\left({j\over10},{k\over10},z\right)\qquad(0\leq z\leq 1)$$ for $0\leq j\leq 10$, $\>0\leq k\leq 10$. The figure supports the conjecture $\delta_5={1\over 8}$. Exact computation gives $$g(0,0,0)={1\over8},\qquad g\left(0,0,{3\over4}\right)={1\over8}\ .$$ enter image description here

$\endgroup$
  • $\begingroup$ "It follows that the best 'universal' constant is $\frac{1}{2^{n-2}}$": I'm having trouble making sense of this. Do you mean that the best "universal" constant must be $\ge \frac{1}{2^{n-2}}$? $\endgroup$ – TonyK Sep 2 '14 at 19:07
  • $\begingroup$ @TonyK: You are of course right. $\endgroup$ – Christian Blatter Sep 2 '14 at 19:32
  • $\begingroup$ It seems to me that (0, ..., 0, a, 1) is harder for general a than a = 0, so 2^(-n+2) should not be sharp. $\endgroup$ – Erik Sep 3 '14 at 10:36
  • $\begingroup$ @Erik: See my update. $\endgroup$ – Christian Blatter Sep 3 '14 at 10:51
  • $\begingroup$ @ChristianBlatter: Nice graph! It'd be interesting to see it for larger n. If one wants one of the final points to be 0, then one cannot do better than (1+a)/2^(n-2). Otherwise, the final points are 1/2^k and a/2^l for some (k,l) such that k+l <= n-2. I don't think that distance can be made smaller than 1/2^(n-2) in general (in particular, not for a = 3/4 and n = 7). $\endgroup$ – Erik Sep 3 '14 at 11:20
2
$\begingroup$

This is not a complete answer but just an example in which the distance between two final points is always greater than $\delta_n=\frac{1}{2^{n-2}}$.

In fact, let $n$ be an even number. Consider an n-tuple $(0,\ldots,0,1-\varepsilon,1)$ with $\varepsilon=\frac{1}{2^{n/2-2}}$. Note that the sum of all numbers after $i$th iteration is at least $(2-\varepsilon)/2^i$; therefore, two final points cannot be closer than $(2-\varepsilon)/2^{n-2}=(2+o(1))\delta_n$ if in some iteration we take the midpoint of two nonzero points.

Therefore, what we have to do on every move is either to cancel one of the zeros or to divide one of nonzero numbers by two. Then, we end up with two points $\frac{1}{2^p}$ and $\frac{1-\varepsilon}{2^q}$ with $p+q\leqslant n-2$. For sufficiently large $n$, the minimum of $\left|\frac{1}{2^p}-\frac{1-\varepsilon}{2^q}\right|$ is attained when $p=q=n/2-1$, and this minimum equals $\frac{\varepsilon}{2^{n/2-1}}=\frac{1}{2^{n-3}}=2\delta_n$.

I hope this technique can lead to a much better lower bound being generalized to deal with the case of many nonzero points.

UPD1. Now I noted that this answer exploits the same idea as Erik's comment on Christian Blatter's answer.

UPD2. As TonyK pointed out in the comment, the tuple $(0,0,0,0,5/7,1)$ has a lower bound of $1/14$ for distance between final points.

$\endgroup$
  • $\begingroup$ Looks good to me. The best $\varepsilon$ for this layout is $2/(\alpha+1)$, where $\alpha = 2^{n/2-1}$; this gives $\delta'_n = \varepsilon/\alpha$, e.g. $\delta'_6 = 1/10, \delta'_8=1/36, \delta'_{10} = 1/136$. $\endgroup$ – TonyK Sep 6 '14 at 8:48
  • $\begingroup$ The $n$-tuples for the above values of $\delta'_n$ are $(0,0,0,0,\dfrac{3}{5},1), (0,0,0,0,0,0,\dfrac{7}{9},1)$, and $(0,0,0,0,0,0,0,0,\dfrac{15}{17},1)$. $\endgroup$ – TonyK Sep 6 '14 at 9:01
  • $\begingroup$ @TonyK I agree with the 2nd and 3rd of your examples, but the first of them seems wrong to me. In fact, the condition that 'minimum of $\left|\frac{1}{2^p}-\frac{1-\varepsilon}{2^q}\right|$ is attained when $p=q=n/2-1$' is true only if $\varepsilon\leqslant 1/4$, as far as I see. For instance, $(0,0,0,0,3/5,1)$ can be transformed to $(1/4,3/10)$ with resulting distance $1/20<1/2^4$. $\endgroup$ – user2097 Sep 6 '14 at 14:56
  • 1
    $\begingroup$ Yes, you are quite right. I think it should be $(0,0,0,0,\dfrac{5}{7},1)$ for $\delta'_6 = 1/14$. $\endgroup$ – TonyK Sep 6 '14 at 16:02
  • $\begingroup$ @TonyK Thank you! I think the example is correct, I added it to the answer. $\endgroup$ – user2097 Sep 6 '14 at 18:11

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.