Control some function by the average of its extreme values on an interval

Question

Let $\lambda \geq 1$ and $\varepsilon \leq \frac{1}{2}\sqrt{\lambda}$.

Why is it the case that $\exists C$ a universal constant (i.e. that does not depend on $\lambda, \varepsilon$) such that $\forall i \in \mathbb{N}, \forall t \in [\lambda - \varepsilon , \lambda + \varepsilon ]$, $$e^{-t} t^i \leq \frac{1}{2} C \left( e^{-(\lambda - \varepsilon)}(\lambda - \varepsilon)^i + e^{-(\lambda + \varepsilon)}(\lambda + \varepsilon)^i \right) $$

The careful reader will have noticed that this is a property about the pmf of the Poisson distribution. For information, this statement appears in "An Automatic Inequality Prover and Instance Optimal Identity testing -- G. Valiant & P. Valiant, Lemma 7" , but it isn't as obvious to me as it is to them.

---

Here is were we are at so far:

Write $f_i(t) = e^{-t}t^i$ for simplicity of notation, we then want to show that there exists $C$ universal such that $f_i(t) \leq \frac{1}{2} C \left( f_i(\lambda - \varepsilon) + f_i(\lambda + \varepsilon) \right) $.

Notice that since $f_i'(t) = f_{(i-1)}(t)(i-t)$, $f_i$ is increasing on $[0, i]$ and decreasing on $[i, \infty]$.

• For $i < \lambda - \varepsilon$ it is the case that $f_i(t) \leq f_i(\lambda - \varepsilon)$ and $C = 2$ is sufficient.
• For $i > \lambda + \varepsilon$ it is the case that $f_i(t) \leq f_i(\lambda + \varepsilon)$ and $C = 2$ is sufficient as well.
• For $i \in [\lambda - \varepsilon, \lambda + \varepsilon]$, $\max_{t \in [\lambda - \varepsilon, \lambda + \varepsilon]} f_i(t) = f_i(i) = e^{-i}i^i = e^{i(\ln(i) - 1)} := M_i$. Now I can bound $e^{-i}i^i \leq e^{-(\lambda - \varepsilon)}(\lambda+\varepsilon)^i$ from the definition of the range of $i$, but $e^{-(\lambda - \varepsilon)}(\lambda+\varepsilon)^i = e^{3\varepsilon}e^{-(\lambda + \varepsilon)}(\lambda+\varepsilon)^i$ so this does not control it by a constant, rather a function of $\varepsilon$.

Could this come from some convexity argument ? Consider the function $h: x \mapsto e^{-x}x^x$, and compute its second derivative $h''(x) = e^{-x} x^{x-1} [x \ln^2(x) + 1]$ which is positive on the range of interest, yielding convexity of $h$.

Answer 1

I'll change the notation up a bit, otherwise I'll get confused.

For $n=1,2,\dots,$ let $f_n(x) = e^{-x}x^n, x\ge 0.$ Verify that $f_n$ is increasing on $[0,n],$ decreasing thereafter, with a global maximum value of $e^{-n}n^n.$

As you indicated, we only need to worry about $n\in[\lambda-\epsilon, \lambda+\epsilon].$ Suppose first $n\in[\lambda-\epsilon, \lambda].$ I'll show

$$\tag 1\frac{e^{-n}n^n}{e^{-(\lambda-\epsilon)}(\lambda-\epsilon)^n}$$

is bounded independent of $n\in [\lambda-\epsilon,\lambda],$ $\lambda\ge 1$ and $\epsilon \le \sqrt \lambda /2.$

Now $n= \lambda-\epsilon +\delta$ for some $\delta \in [0,\epsilon].$ Substitute that into $(1)$ to get

$$\frac{e^{-(\lambda-\epsilon +\delta)}(\lambda-\epsilon +\delta)^{\lambda-\epsilon +\delta}}{ {e^{-(\lambda-\epsilon)}(\lambda-\epsilon)^{\lambda-\epsilon +\delta}}}$$

$$\tag 2= e^{-\delta} \cdot \left (1+\frac{\delta}{\lambda -\epsilon}\right)^{\lambda -\epsilon}\cdot\left (1+\frac{\delta}{\lambda -\epsilon}\right)^{\delta}.$$

We need a few lemmas:

Lemma 1: If $0\le u\le v,$ then

$$ \left(1+\frac{u}{v} \right )^v \le e^u.$$

Lemma 2: If $u\ge 1,$ then

$$\left(1+\frac{u/2}{u^2-u/2}\right)^{u/2} \le e^{1/2}.$$

I'll leave the proofs of these to you for now. Now Lemma 1 implies the second factor in $(2)$ is $\le e^{\delta}.$ As for the third factor, it only gets larger if we take $\delta = \epsilon=\sqrt \lambda/2.$ Lemma 2 then implies, with $u=\sqrt \lambda,$ that the third factor is no more than $e^{1/2}.$

So we have shown the desired boundedness in $(1),$ assuming $n\in[\lambda-\epsilon, \lambda].$ Surely the same result, using similar ideas, holds for $n\in[\lambda,\lambda+\epsilon].$ I haven't checked the latter super carefully, so it might be a good exercise for you. Assuming everything works, we have shown the desired universal $C$ exists. (And probably there is a simple estimate for $C$ that can be found.)

Answer 2

Define $f_i : [\lambda - \varepsilon , \lambda + \varepsilon ] \to \mathbb{R}, f_i(t) = e^{-t}t^i$. This is a continuous function with positive values. It attains a maximum $m_i > 0$. Moreover, $d_i = \frac{1}{2}(f_i(\lambda - \varepsilon) + f_i(\lambda + \varepsilon)) > 0$ and we find $C_i > 0$ such that $f_i(\ell) \le m_i < C_i d_i$ (for example $C_i = \frac{m_i}{d_i} +1 $).

We have $f'_i(t) = -e^{-t}t^i + ie^{-t}t^{i-1} = e^{-t}t^{i-1}(i - t) = f_{i-1}(t)(i - t)$. Hence $f'_i(t) > 0$ for all $t$ and $i > \lambda + \varepsilon$.

Therefore, for $i > \lambda + \varepsilon$, we see that $f_i$ is strictly increasing so that $m_i = f_i(\lambda + \varepsilon)$ and we can take $C_i =2$.

Now take $C = \max \{C_i \}$.

More detailed proof:

Define $f_n : (0,\infty) \to \mathbb{R}, f_n(t) = e^{-t}t^n$. This is a continuous function with positive values. Moreover , define $d_n = \frac{1}{2}(f_n(\lambda - \varepsilon) + f_n(\lambda + \varepsilon)) > 0$.

We have $f'_n(t) = -e^{-t}t^n + ne^{-t}t^{n-1} = e^{-t}t^{n-1}(n - t) = f_{n-1}(t)(n - t)$. Hence $f'_n(t) > 0$ for all $t < n$, $f'_n(n) = 0$ and $f'_n(t) < 0$ for all $t > n$. This means that $f_n$ is strictly increasing on $(0,n]$, attains its (global) maximum $M_n = f_n(n) = e^{-n} n^n = e^{n(\ln(n)-1)}$ at $t = n$ and is strictly decreasing on $[n,\infty)$.

The maximum $m_n$ of $f_n$ on the interval $[\lambda - \varepsilon, \lambda + \varepsilon]$ is therefore $m_n = f_n(\lambda - \varepsilon)$ for $n \le \lambda - \varepsilon$, $m_n = M_n > 2d_n$ for $\lambda - \varepsilon < n < \lambda + \varepsilon$ and $m_n = f_n(\lambda + \varepsilon)$ for $n \ge \lambda + \varepsilon$.

We conclude $f_n(\ell) < f_n(\lambda - \varepsilon) + f_n(\lambda + \varepsilon) = 2d_n$ for $n \notin (\lambda - \varepsilon, \lambda + \varepsilon)$.

For the finitely many $n \in (\lambda - \varepsilon, \lambda + \varepsilon)$ we have $f_n(\ell) \le M_n = \frac{M_n}{d_n} d_n$.

Define $M = \max \{ \frac{M_n}{d_n} \mid n \in (\lambda - \varepsilon, \lambda + \varepsilon) \}$. We have $M > 2$. Choose any $C > M$. Then for all $n \in \mathbb{N}$

$$f_n(\ell) < C d_n .$$

Added:

To show that that there exists a universal constant $C$ such that $f_n(\ell) < C d_n$ for all $n \in \mathbb{N}, \lambda \ge 1, \varepsilon \in [0,\frac{1}{2}\sqrt{\lambda}]$ we proceed as follows.

As we know it suffices to find $C$ such that $ \frac{M_n}{d_n} < C$ for all $n \in (\lambda - \varepsilon, \lambda + \varepsilon)$. We claim that $C = 2 e^2$ will do.

We have $$d_n > \frac{1}{2}f_n(\mu)$$ where $\mu = \lambda - \varepsilon$. Therefore $$\frac{M_n}{d_n} < 2 \frac{f_n(n)}{f_n(\mu)} .$$ Noting $f_n(x) = e^{n \ln(x) - x}$ we get $$\frac{f_n(n)}{f_n(\mu)} = e^{n(\ln(n) - \ln(\mu)) - (n - \mu)} .$$ It remains to verify that $n(\ln(n) - \ln(\mu)) - (n - \mu) < 2$, i.e. $$n \frac{\ln(n) - \ln(\mu)}{n - \mu} < \frac{2}{n - \mu} + 1 .$$ The mean value theorem provides $x \in (\mu,n)$ such that $$n \frac{\ln(n) - \ln(\mu)}{n - \mu} = n \ln'_n(x) = n \frac{1}{x} < \frac{n}{\mu} < \frac{\lambda + \frac{1}{2}\sqrt{\lambda}}{\lambda - \frac{1}{2}\sqrt{\lambda}} .$$ Now $n - \mu < 2\varepsilon \le \sqrt{\lambda}$, hence it suffices to verify $$\frac{\lambda + \frac{1}{2}\sqrt{\lambda}}{\lambda - \frac{1}{2}\sqrt{\lambda} } \le \frac{2}{\sqrt{\lambda}} + 1 .$$ This can be left as an exercise.

Note that $C = 2 e^2$ is the result of a brute force calculation. We can improve this to $C = 2 e^{\frac{1}{2}}$ as in the answer by zhw.

Repeat the above calculations for $n \in (\lambda - \varepsilon,\lambda]$ and $C = 2 e^{\frac{1}{2}}$. Then you have to verify $$\frac{\lambda}{\lambda - \frac{1}{2}\sqrt{\lambda} } \le \frac{1}{\sqrt{\lambda}} + 1 .$$ For $n \in [\lambda, \lambda + \varepsilon)$ replace $\mu$ by $\nu = \lambda + \varepsilon$ and verify by similar arguments $$n(\ln(n) - \ln(\nu)) - (n -\nu) < \frac{1}{2} .$$