# given vector a, how to find vector b such that inifinitive norm of $a -b$ is smallest

I'd appreciate any hint for the following problem: Given a vector $a=(a_1, a_2,\ldots,a_n)$, how can I find a vector $b=(b_1, b_2,\ldots,b_n)$ such that $b_1 \leq b_2 \leq \cdots \leq b_n$ and the infinitive norm of the vector $a-b$ is smallest. Thank you.

-
It would be helpful if you told us what you meant by infinitive norm. I don't think it's a standard term, although I would guess you mean what some people call the infinity norm and I call the supremum norm, namely $\sup_{i}|x_i|$ – Ben Millwood Jun 4 '12 at 20:40
Also, what does this have to do with probability? – Ben Millwood Jun 4 '12 at 21:17
'Supremum' is exactly what I meant, 'infinitive' is what my teacher introduced it to me. :) – cody Jun 5 '12 at 1:54

As @benmachine has pointed out, it is not entirely clear what the infinitive norm is; I'll assume you have been talking about the supremum norm.

A constructive proof

You can find such a function with induction. When $n=1$, take $b_1=a_1$. Suppose, as the induction hypothesis, that for all $k\leq n$ we can find such a sequence $(b_1,\ldots,b_k)$ for any vector $(a_1,\ldots,a_k)$ and let $(a_1,\ldots,a_{n+1})\in\mathbb{R}^{n+1}$. We construct $(b_1,\ldots,b_{n+1})$ in several steps (take pen and paper with you, because it will be easier to follow when you draw what's going on):

1. First find $n_0$ such that $a_{n_0}$ is maximal among the $a_1,\ldots,a_{n+1}$.
• If $n_0=n+1$, define $b_{n+1}:=a_{n_0}$ and construct $(b_1,\ldots, b_n)$ with the induction hypothesis.
• If $n_0<n+1$, find $n_0< n_1\leq n+1$ such that $a_{n_1}$ is minimal among $a_{n_0+1},\ldots,a_{n+1}$. Also, find $$n_2:=\min\{1\leq i\leq n_0:\forall j\geq i,\ a_{n_1}\leq a_j\},$$ Then define $b_{n_2},\ldots,b_{n+1}:=\frac{1}{2}(a_{n_0}+a_{n_1})$. This is clearly the best one can go for.

For the remaining part $1,\ldots,n_2-1$ apply the induction hypothesis to find $b_1,\ldots,b_{n_2-1}$. By the way of construction, it will follow easily that $b_{n_2-1}\leq b_{n_2}$.

You can test your understanding of the above construction by proving that this sequence indeed matches your requirements (that's a good homework too, I guess).

A non-constructive existence proof

To show only existence is easier. For $a\in\mathbb{R}^n$, define the set $$D:=\{\|a-b\|_{\infty}:\min\{a_i\}\leq b_1\leq\cdots\leq b_n\leq\max\{a_i\}\}.$$ This is the image of a continuous function of a compact set, hence it is compact. In particular, it has a minimum. It is not so hard to verify that this minimum is also the infimum of the set $$\{\|a-b\|_{\infty}: b_1\leq\cdots\leq b_n\}.$$

Note that the result can be extended: for every continuous function $a:[0,1]\to\mathbb{R}$ there exists an increasing continuous function $b:[0,1]\to\mathbb{R}$ with the property that $\|a-b\|_\infty$ is minimal.

-
I'm curious: how could you think about induction in the first place? I learned about induction but never used it or thought it would come in handy like in this case. What was the indicator here that made you recognized it? And how did you come up with the claim to prove? Thank you. – cody Jun 5 '12 at 2:13
I work a lot with induction and I just saw it would go this way :) The thing you have to see is how to reduce the problem to a smaller $n$, which was in step 2. Do enough induction proofs in your life and you'll begin to see these things. Which claim do you refer to? – Egbert Jun 5 '12 at 9:06
That's the claim in your conductive proof. You didn't include it but I guess it is: $P(n)$: "There exists vector b of size n such that $b_1 \leq b_2 ... \leq b_n$". – cody Jun 5 '12 at 14:42
I'm confused here... the claim I `came up with' is the claim you asked us to help you with, isn't it? – Egbert Jun 5 '12 at 14:57