Distributing points with respect to a concave function

Question

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.

Answer 1

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.

Answer 2

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).