8
$\begingroup$

Let $f$ be a positive monotonically increasing real function in $[0,1]$. Let $F$ be the area under the curve of $f$ ($F=\int_0^1{f(x)dx}$)

For every $x\in[0,1]$, let $G(x)=f(x)\cdot (1-x)$ = the area of a rectangle bounded below the curve of $f$ and the $x$ axis:

enter image description here

Let $L=\left\lceil\log_2{\frac{f(1)}{f(0)}}\right\rceil$. Prove that there exists an $x$ such that:

$$G(x)\geq F/(2L)$$

Here is a possible proof:

Partition the interval $[0,1]$ to bins such that, in each bins $[a,b]$, $f(b)\leq 2f(a)$ (i.e. the value of $f$ grows by at most a factor of 2). The number of such bins is at most $L$. Hence, by the pigeonhole principle, there is a bin $[a,b]$ in which the area under the curve ($= \int_a^b{f(x)dx}$) is at least $F/L$. Now, this area is bounded below the rectangle $(b-a)f(b)$. By definition of a bin, $f(a)\geq f(b)/2$. Hence:\begin{align}G(a) &= (1-a)f(a) \\&\geq (b-a)f(a) \\&\geq (b-a)f(b)/2 \\&\geq F/2L\end{align}

MY QUESTIONS ARE:

  1. Is there a simpler proof?

  2. Is there a better bound for the area of the maximal rectangle?

$\endgroup$
  • $\begingroup$ The result you want to prove (and hence also the proof) is false. The key observation is that $L = 0$ if $f(1) = f(0)$, hence, you are "dividing by $0$" in your bound $F/2L$ (which I read as $F/(2L)$. If you actually mean $FL/2$, things are of course different). More precisely, if we let $f(x) = 1+\epsilon x$, then your estimate yields $2 \geq 1+\epsilon \geq (1-x_\epsilon) \cdot (1 + \epsilon x_\epsilon) \geq \frac{1 + \epsilon/2}{2 \cdot \log_2 (1+\epsilon)} \xrightarrow[\epsilon \downarrow 0]{} \infty$, a contradiction. $\endgroup$ – PhoemueX Dec 31 '14 at 13:52
  • $\begingroup$ You are right. I should put the log in $\lceil ... \rceil$ and note that $f(1)>f(0)$ since $f$ is monotonically increasing. $\endgroup$ – Erel Segal-Halevi Dec 31 '14 at 14:23
0
$\begingroup$

Let

  • $f_0 = f(0)$ and $f_1 = f(1)$.
  • $x_*$ be the point which maximizes $G(x) = f(x)(1-x)$ over $[0,1]$.
  • $z_* = G(x_*) = f(x_*)(1-x_*)$.

It is clear $f_0 \le z_* \le f_1$ and by definition of $x_*$, we have

$$f_0 \le f(x) \le \min\left(\frac{z_*}{1-x}, f_1\right)\quad\text{ for } x \in [0,1]$$ This leads to $$ F = \int_0^1 f(x) dx \le \int_0^{1-\frac{z_*}{f_1}} \frac{z_*}{1-x} dx + \int_{1-\frac{z_*}{f_1}}^1 f_1 dx = z_*\left(\log\frac{f_1}{z_*} + 1\right) \le z_*\left(\log\frac{f_1}{f_0} + 1\right) $$ As a result,

$$\max_{x\in [0,1]} G(x) = G(x_*) = z_* \ge \lambda_* F \quad\text{ where }\quad \lambda_* = \frac{1}{\log\frac{f_1}{f_0} + 1}\tag{*1}$$

This ratio $\lambda_*$ is the best we can have.

Let us first consider the case where "monotonic increasing" means "non-decreasing" instead of "strictly increasing". Fixing $f_0$ and $f_1$, the function $\tilde{f} : [0,1] \to [ f_0, f_1 ]$ defined by

$$\tilde{f}(x) = \min\left( \frac{f_0}{1-x}, f_1 \right)\tag{*2}$$

is non-decreasing, satisfying $\tilde{f}(0) = f_0, \tilde{f}(1) = f_1$. At the same time, we have

$$\max_{x\in[0,1]}\left\{ \tilde{f}(x)(1-x)\right\} = f_0 = \frac{1}{\log\frac{f_1}{f_0} + 1}\int_0^1 \tilde{f}(x) dx$$

which make the inequality in $(*1)$ becomes an equality.

If "monotonic increasing" means "strictly increasing", we can replace the $\tilde{f}$ in $(*2)$ by something like

$$\tilde{f}_\epsilon(x) = \min\left(\frac{f_0}{1-x}, f_1 - \epsilon(1-x)\right)$$

where $\epsilon$ is any sufficiently small positive number. Repeat the algebra, it is not hard to show

$$\max_{x\in[0,1]}\left\{ \tilde{f}_\epsilon(x)(1-x)\right\} = f_0 \quad\text{ and }\quad \frac{f_0}{\int_0^1 \tilde{f}_\epsilon(x) dx} \searrow \frac{1}{\log\frac{f_1}{f_0} + 1}\quad\text{ as }\quad\epsilon \searrow 0^{+}$$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.