## Distributing points with respect to a concave function

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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.

-
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 2011 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 2011 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 2011 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 2011 at 20:33

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

-

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 98, "mathjax_display_tex": 3, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9432228207588196, "perplexity_flag": "head"}