# Approximating the area below average of a concave function

Given a non-decreasing concave function $f:[0,1]\rightarrow \mathbb{R}^+$. Define

\begin{align*} F(n)=\displaystyle\sum_{i=1}^n \min\left\{\frac{1}{n},\frac{f\left(\frac{i}{n+1}\right)}{n+1}\right\} \end{align*}

We want to find a tight lower bound for $F(n)$ in terms of $n$, knowing that $\int_0^{1} f(x) dx =1$.

For instance, I am able to prove that $F(1)\geq \frac{1}{2}$, $F(2)\geq \frac{2}{3}$, $F(3)\geq \frac{1}{3}+\frac{3}{8}$ and see that they are tight for the function $f(x)=2x$. Also, I can prove that $\displaystyle\lim_{n\rightarrow \infty} F(n) \geq 3/4$, and again observe that it is tight for the function $f(x)=2x$. Thanks for your time and attention!

-
This is a Riemann sum, for $f(x) = 2 x$ the limit is just $\int_0^1 2 x d x = 1$. – vonbrand Jan 21 '13 at 20:48
@vonbrand It's not a Riemann sum for $f$, due to the presence of $\min$. (And the cut-off value in min changes with $n$, so this is not really the Riemann sum for any fixed function). The limit is $\int_0^1 \min(f,1)\,dx$, which for $f(x)=2x$ is indeed $3/4$. It's easy to see that the limit cannot be smaller. However, proving that $f(x)=2x$ is also optimal for every finite $n$ does not appear to be easy. – user53153 Jan 21 '13 at 23:03

$f(x)$ is non-decreasing. For given $n$, split the range of the sum at $n^*$, where $$\frac{f(n^* / (n + 1))}{n + 1} = \frac{1}{n}$$ Then the sum is: $$F(n) = \frac{1}{n + 1} \sum_{1 \le i \le n^*} f(i / (n + 1)) + (n - n^*) / n$$ We want to minimize this, and this means keeping as much in the first range (which collects the small values) as we can. By the relation defining $n^*$ we see that it is enough to make sure that $f(x) < \frac{n + 1}{n}$ to have $n^* = n$ for all $n$. By the condition that $\int_0^1 f(x) dx = 1$, this means $f(x) = 1$, and the sum is just $F(n) = \frac{n}{n + 1}$.
This is incorrect. It is to our benefit to have values of $f$ that are greater than the threshold, so that the $\min$ truncates them. This is how we get $3/4$ (rather than $n/(n+1)\approx 1$) asymptotically). – user53153 Jan 22 '13 at 14:20
Next try: Consider the function that is 0 on $[1, 1 - \epsilon]$ and a straight line from $(1 - \epsilon, 0)$ to $(1, 2 / \epsilon)$. The value to sum will be 0 up to $1 - \epsilon$, and will be $1 / n$ on the piece from $1 - \epsilon$ to 1. Take $\epsilon$ small enough, and the sum is as small as you please. – vonbrand Jan 22 '13 at 19:01