Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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
add comment

1 Answer

$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}$.

share|improve this answer
    
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
    
I agree with 5PM. For some intuition, you may want to evaluate your expression (without the min) for say f(x)=2x and n=5, and also evaluate the other expression which does have a min. –  afshi7n Jan 22 '13 at 18:38
    
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
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.