3

Trying to prove a proposition in my paper, which can potentially use a conjecture about convex (concave) functions. I think the following is intuitive but have no idea how to rigorously prove it.

Conjecture

For a convex (concave) function $f(x):[0,1]↦[0,1]$.$f(0)=0,f(1)=1$.$f$ is continuous and increasing on $[0,1]$. Then $$ (1/(N+1))∑_{n=1}^{N}f(n/N) $$ should be decreasing (increasing) in $N$.

I thought I could prove it by seeing the expression as an approximation of Reimann integral of a convex (concave) function on [0,1], but it seems hard for me...

I appreciate any thoughts on this.

Chang
  • 87
  • 6

2 Answers2

0

Assume that $f$ is convex and nondecreasing. Then there exists some nonnegative function $g$ such that $f(x)=\int\limits_0^xg(y)\mathrm dy$ for every $x$ in $[0,1]$ hence the function $f$ is the pointwise limit of some linear combinations with positive coefficients of the functions $f_z:x\mapsto(zx-1)^+$. Let $$ R_N(f)=\frac1{N+1}\sum_{n=1}^Nf\left(\frac{n}N\right). $$ Each $R_N(f)$ is a linear functional of the function $f$ involved hence it is sufficient to solve the case of the functions $f_z$.

The case $f_2$ is allright (this requires to compute $R_{2N}(f_2)=R_{2N+1}(f_2)=\frac{N+1}{2(2N+1)}$).

Maybe check $f_3$...

Did
  • 279,727
  • Thanks for your answer! It seems a bit tedious to work with $f_k$ case... by the way, it seems the claim that $f$ is the pointwise limite of some linear combinations with positive coefficients of functions $f_z$ is a well-known theorem. Hard to me to see this... Is there a reference? – Chang Sep 14 '13 at 04:59
0

I think I find a proof. Actually the conjecture can be strengthened: no need to assume $f(0) = 0, f(1) = 1$, only concavity/convexity of $f(0)$ is needed.The proof uses the definition of concave(convex) function. Suppose $f(x)$ is a concave function, note that

\begin{equation*} \frac{k-1}{N}<\frac{k}{N+1}<\frac{k}{N} \end{equation*} and \begin{equation*} \frac{k}{N+1}=\frac{k}{N+1}\cdot \frac{k-1}{N}+\left( 1-\frac{k}{N+1}\right) \cdot \frac{k}{N} \end{equation*} Suppose $f\left( x\right) $ is concave, then \begin{eqnarray*} f\left( \frac{k}{N+1}\right) &\geq &\frac{k}{N+1}f\left( \frac{k-1}{N}% \right) +\left( 1-\frac{k}{N+1}\right) f\left( \frac{k}{N}\right) \\ S_{N+1} &=&\frac{1}{N+2}\sum_{k=0}^{N+1}f\left( \frac{k}{N+1}\right) \\ &\geq &\frac{1}{N+2}\left\{ f\left( 1\right) +f(0)+\sum_{k=1}^{N}\left[ \frac{k}{N+1}f\left( \frac{k-1}{N}\right) +\left( 1-\frac{k}{N+1}\right) f\left( \frac{k}{N}\right) \right] \right\} \\ &=&\frac{1}{N+1}\sum_{k=0}^{N}f\left( \frac{k}{N}\right) =S_{N} \end{eqnarray*} If $f\left( x\right) $ is convex, then vice versa.

If anyone spots a mistake, please tell me. Thanks in advance.

I have a different conjecture about concave function. If you are interested, please see my generalized conjecture here. I appreciate any thoughts on this.

Community
  • 1
Chang
  • 87
  • 6