Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose I have a concave function defined on the unit interval such that $f(0) = f(1) = 0$ and $\int_0^1 f(t) dt = \alpha$, where $\alpha$ is "small" (say $0.01$ or thereabouts). Say I distribute $n$ points $x_1,\dots,x_n$ on the unit interval and consider the function $F(x_1,\dots,x_n) = \int_0^1 f(t) \cdot \min_i\{|x_i - t|\} dt$. Is there a lower bound on $F$ as a function of $\alpha$ and $n$? If $n=1$, I can show that a lower bound is $\alpha/6$, so I'm curious if something like $\alpha/(6n)$ holds in general.

share|improve this question
    
Did you try to minimize $F$, e.g. by calculating its (sub-)derivatives with respect to all coordinates $x_i$ all solving the resulting equations? –  Dirk Jun 10 '11 at 9:11
1  
Note that for a fixed $f$, the function $F$ is $C^1$ in the variables $(x_1,\dots,x_n)$, even if $f$ is only integrable. There is a minimizer on the closed symplex {$0\le x_1 \le \dots\le x_n\le 1$} by compactness, and it verifies $0 < x_1 < \dots < x_n < 1$ provided $f$ is a.e. positive. –  Pietro Majer Jun 10 '11 at 17:26
    
The size of $\alpha = \int_0^1 f(t) \phantom. dt$ is irrelevant: multiplying $f$ by a scalar $c$ preserves concavity and multiplies $F(x_1,\ldots,x_n)$ by the same $c$, so if a bound like $\alpha/(6n)$ holds for "small" $\alpha$ then it also holds without any such hypothesis. –  Noam D. Elkies Sep 3 '11 at 20:31
    
Is it easy to outline the proof of $F(x_1) \geq \alpha/6$? That might give a start towards the more general problem you ask. –  Noam D. Elkies Sep 3 '11 at 20:33
add comment

2 Answers

You can define the function $f(t)\cdot min_i|x_i-t|$ piecewise so that $f(t)\cdot min_i|x_i-t|=f(t)\cdot|x_i-t|$ when $t$ is on the interval $\left[\frac{x_{i-1}+x_i}{2},\frac{x_i+x_{i+1}}{2}\right]$. Here we have to define $x_0=-x_1$ (so $\frac{x_{0}+x_1}{2}=0$) and $x_{n+1}=2-x_n$ (so $\frac{x_n+x_{n+1}}{2}=1$). This makes the integral \begin{equation} F(x_1,...,x_n)=\sum_{i=1}^n\int_\frac{x_{i-1}+x_i}{2}^\frac{x_i+x_{i+1}}{2}f(t)\cdot|x_i-t|dt \end{equation} Now, $f$ isn't $0$ at the endpoints of these intervals and the intervals don't have length $1$, but they are concave and their average value is $\alpha/n$. You can consider f on each interval as the limit of a sequence of concave functions defined on that interval which are each $0$ at the endpoints, so you should be able to put a lower bound on each integral in the same way that you did it for $\int_0^1f(t)\cdot|x_1-t|dt$. I can't say what that lower bound might be, because I don't know how (or if) you used the length of the interval $[0,1]$ when you found the lower bound for $\int_0^1f(t)\cdot|x_1-t|dt$. If you didn't use the length of the interval at all, the integrals will have to be on average greater than or equal to $\alpha/6n$, implying that $F(x_1,...,x_n)$ is bounded below by $\alpha/6$, which would be kind of interesting. One more thing to note is that unlike your example when $n=1$, for the integrals in the sum above you have the additional condition that $f(x_i)$ is bounded away from $0$ by the value of $f$ at at least one of the endpoints of the intervals. Maybe this will make it possible to put stricter lower bounds on each of these integrals. I hope all that was clear (and correct).

share|improve this answer
add comment

It seems that for large $n$ there will be an upper bound $c_n \alpha$ with $c_n$ asymptotic to $\frac{2}{9n}$ (and thus a bit better than the $\frac{1}{6n}$ suggested by the value of $c_1$). The asymptotic equality condition should be: $f$ is a triangular function $\tau_z$ for some $z \in (0,1)$, defined by $$ \tau_z(x) = \cases{ x/z,& {\rm if}\phantom0x \leq z,\cr (1-x)/(1-t), & {\rm if}\phantom0 x \geq z } $$ (i.e. $\tau_z$ is piecewise linear with a corner only at $x=z$ where $\tau_z$ attains its maximal value of $1$), and $x_1,\ldots,x_n$ are distributed on $(0,1)$ with density proportional to $\sqrt{f\phantom.}$ (which is probably not what most of us would have guessed at first).

The condition that $\alpha = \int_0^1 f(x) \phantom. dx$ be "small" is a red herring because the problem is linear in $f$, so that what works for small $\alpha$ works equally for all $\alpha$. It is also enough to work with $f = \tau_z$ because the convex hull of functions $c \tau_z$ is precisely the concave functions $f$ on $[0,1]$ vanishing at the endpoints; e.g. if such $f$ has a continuous second derivative then $f(x) = \int_{z=0}^1 (z-z^2) \phantom. (-f''(z)) \phantom. \tau_z(x) \phantom. dz$, and $-f''(z) \geq 0$ for $f$ concave.

Now the idea is that if $x_1,\ldots,x_n$ are regularly distributed with density $\delta(\cdot)$ on $[0,1]$ then $\min_i |x_i - t|$ behaves like $1/(4\delta(t))$, because it oscillates between $0$ and $1/(2\delta(t))$ like a nonnegative triangle wave. The only restriction on $\delta$ is that it be a positive function with $\int_0^1 \delta(t) \phantom. dt = n$. By Cauchy-Schwarz, $$ \int_0^1 \frac{\tau_z(t)}{\delta(t)}dt \cdot \int_0^1 \delta(t) \phantom.dt \geq \left( \int_0^1 \sqrt{\tau_z(t)} \phantom. dt \right)^2, $$ with equality iff $\delta^2$ is proportional to $\tau_z$. Now we know $\int_0^1 \delta(t) \phantom. dt = n$, and compute $\int_0^1 \sqrt{\tau_z(t)} \phantom. dt = 2/3$ for all $z$. Hence $\int_0^1 (\tau_z(t) / \delta(t)) \phantom. dt \geq \frac4{9n}$. Since $\int_0^1 \tau_z(t) \phantom. dt = 1/2$, we deduce that $$ \int_0^1 \frac{\tau_z(t)}{4\delta(t)}dt \geq \frac2{9n} \int_0^1 \tau_z(t) \phantom. dt, $$ from which the claimed asymptotic should follow after some epsilon-chasing.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.