How do I minimise this sum?

125 Views Asked by At

Edit: The context is a probabilistic problem where we are trying to guess some correct answer. We know the probability of the guess being $x(i)$-close to the correct answer is no more than $1/x(i)^2$. Using union bounds you can convince yourself the two examples sums bound the expected distance from the correct answer, and from here generalise to the allowed sequences. I'm trying to select the sequence that gives the lowest bound.


Suppose we have positive numbers $x(1)<x(2)<\ldots < x(n)$. We can select any $r \le n$ and sequence $1=a(1) \le b(1) < a(2) \le b(2) < \ldots < a(r) \le b(r)=n $ and compute the sum $$ \sum_{i=1}^r \frac{x(b(i))}{x(a(i))^2}$$

For example if $r=n$ and all $a(i)=b(i)=i$ the sum becomes $$ \sum_{i=1}^r \frac{1}{x(i)}$$

and if $r=1$ and $a(1)=1$ and $b(1)=n$ the sum becomes $$\frac{x(n)}{x(1)^2}.$$

We want to select the sequence that minimises the sum. For example if all $x(i)$ coincide the sum is proportional to $r$ and the second example $r=1$ and $a(1)=1$ and $b(1)=n$ is optimal.

In case $n=2$ we can derive the conditions for when $r=1$ is a better choice than $r=2$. Writing $x(1)=x$ and $x(2)=y$ we get

$$\frac{y}{x^2} \le \frac{1}{x} + \frac{1}{y} \iff y^2\le xy+x^2 \iff y^2-xy\le x^2 \iff \left ( y - \frac{x}{2} \right )^2 - \frac{x^2}{4} \le \Delta_1^2\\ \iff y \le \left ( \frac{\sqrt 3+1}{2} \right ) x \sim 1.366 x.$$

In general, what is the closest we can hope to get to a closed form for either the sequence that minimises the sum, or the corresponding value of the sum?

1

There are 1 best solutions below

2
On

Changing the answer after the typo in the question was fixed. :)

Consider $r, b(1), ..., b(r)=n$ to be fixed for now, and lets try to minimize across only the choices of $a(i)$ for $i\ge 2$. (Recall $a(1) = 1$ is constrained.) Each $a(i)$ appears in only one term ${x(b(i)) \over x(a(i))^2}$ in the summation, and the choice of one $a(i)$ does not constrain the choice of any other $a(j)$ (because the $b(k)$'s act as fixed boundaries). So you want to individually maximize each $x(a(i))$, which means you maximize each $a(i)$ since the $x$'s are increasing. This means the optimizing choice is $\color{red}{a(i) = b(i) \ \forall i \ge 2}$.

In other words, for any fixed $r \ge 2, b(i)_{1\le i\le r}$, the minimum sum occurs at $a(i) = b(i)$ (except $a(1) = 1$) and the value of the sum is

$$\sum_{i=1}^r {x(b(i)) \over x(a(i))^2} = {x(b(1)) \over x(1)^2} + \sum_{i=2}^r {1 \over x(b(i))} = {x(b(1)) \over x(1)^2} + \sum_{i=2}^{r-1} {1 \over x(b(i))} + {1 \over x(n)}$$

where in the last equality we have used the constraint $b(r) = n$.

Next consider the first term $x(b(1))/x(1)$. The minimizing choice is $\color{red}{b(1) = 1}$, and this does not further constrain any other choices. [More formally: consider any $r, (b(1), b(2), ..., b(r)=n)$ and note that a slightly modified $r'=r, (b'(1)=1, b'(2)=b(2), ..., b'(r)=b(r)=n)$ is still a valid choice and makes the sum equal or smaller.] So the minimal sum happens at $b(1)=1$ and the value becomes:

$${1 \over x(1)} + \sum_{i=2}^{r-1} {1 \over x(b(i))} + {1 \over x(n)}$$

From this, since every term in the summation is positive, the sum is minimized when there are no terms in the summation, i.e. $\color{red}{r=2}$.

To summarize, among all choices of $r, a, b$ with $r\ge 2$, the choice minimizing the sum is $r=2, a(1)=b(1)=1, a(2)=b(2)=n$ and the sum is:

$${1 \over x(1)} + {1 \over x(n)}$$

So now you only have to compare it with the special $r=1$ case where the sum is ${x(n) \over x(1)^2}$, a comparison you have already done for the $r=2$ case.