Choosing a $\lambda$ s.t. $ \left(\frac{1}{1-\lambda}\right)^n \exp(-\lambda\varepsilon) \leq \left(\frac\varepsilon n\right)^n \exp(n-\varepsilon). $

Question

Context: The motivation for the following inequality comes from bounding tail probabilities of sums of i.i.d. random variables where one applies Markov's Inequality.

For a fixed $\varepsilon>0$ and $n \in \mathbb{N}$, I want to prove that I can choose a $\lambda \in (0,1)$ such that $$ \left(\frac{1}{1-\lambda}\right)^n \exp(-\lambda\varepsilon) \leq \left(\frac\varepsilon n\right)^n \exp(n-\varepsilon). $$

---

Some initial observations / things to keep in mind:

• Note $\lambda$ can (and certainly must) depend on both $n$ and $\varepsilon$.

• We know nothing about the relation of $n$ and $\epsilon$.

• The left hand side is a product of an increasing function and a decresing function in $\lambda \in(0,1)$. Hence, optimization could cause some trouble.

• It is not necessary to compute the exact value of $\lambda$. It would suffice to show there exists such a $\lambda$ as specified

---

Solution Attempt 1

Here I try to find the value of $\lambda$. I do not know how to systematically tackle this, so I have tried different values of $\lambda$ to see if anything would work. For instance choosing

$$ \lambda = 1-\frac{\text{min}(\varepsilon,n)}{\varepsilon} \in (0,1) $$

yields

$$ \left(\frac{1}{1-\lambda}\right)^n \exp(-\lambda\varepsilon) = \left(\frac{\varepsilon}{\text{min}(\varepsilon,n)}\right)^n \exp\left(\frac{\text{min}(\varepsilon,n)}{n}-\varepsilon\right) \leq \left(\frac{\varepsilon}{\text{min}(\varepsilon,n)}\right)^n \exp(n-\varepsilon). $$ The problem is know as mentioned above that it is not so easy to get the the upper bound from here as the other factor becomes smaller if the minimum is replaced by one of the elements. I have tried to extend this idea further by considering "nested" max/min on the form $\text{max}(\text{min}(...,...),\text{min}(...,...))$ but I have become convinced that this is a dead end and not something that can ever work.

Solution Attempt 2

Here I will simply try to show the existence of $\lambda$. The left hand side is continuous in $\lambda$ (and based on plots also seem convex, but I have not shown this (yet)). For $\lambda \to 0$ the right-hand side goes to 1 and for $\lambda \to 1$ the right hand side goes to $\infty$. One idea would then be to use the intermediate value theorem to get the existence of $\lambda$. Note we could further upper-bound the right-hand side if need be before using the IVT. But I have not managed to achieve anything here either as the left hand side easily can become less than 1.

Can anyone help me show this inequality?

Answer 1

I can provide a partial answer.

If $\varepsilon>n$ then:

$$\begin{align}(1-\lambda)^{-n}\exp(-\lambda\varepsilon)&\le(n/\varepsilon)^{-n}\exp(n)\exp(-\varepsilon)\\\iff(1-\lambda)^{-n}\exp((1-\lambda)\varepsilon)&\le(n/\varepsilon)^{-n}\exp(n)\\\iff t^{-n}\exp(t\varepsilon)&\le(n/\varepsilon)^{-n}\exp(n)\end{align}$$Where $t:=1-\lambda\in(0,1)$.

So clearly if $n/\varepsilon\in(0,1)$, that is, $\varepsilon>n$, we have equality when $t=n/\varepsilon$, or $\lambda=1-\frac{n}{\varepsilon}$.

As Martin comments, if $n=\varepsilon$ then no solutions for $\lambda\in(0,1)$ can be found.

I do not know about the case $n>\varepsilon$.

Answer 2

If $\varepsilon = n$, as @Martin R pointed out, there is no $\lambda \in (0, 1)$ such that the inequality holds.

If $\varepsilon < n$, there is no $\lambda \in (0, 1)$ such that the inequality holds.

If $\varepsilon > n$, there exists exactly one $\lambda \in (0, 1)$ such that the inequality holds.

Proof.

Let $a = \varepsilon /n$. The desired inequality is written as $$\left(\frac{1}{1 - \lambda}\mathrm{e}^{-a\lambda }\right)^n \le \left(a \mathrm{e}^{1 - a}\right)^n. \tag{1}$$

Let $$f(\lambda) := \frac{1}{1 - \lambda}\mathrm{e}^{-a\lambda }.$$ We have $$f'(\lambda) = \frac{a\lambda - a + 1}{(1 - \lambda)^2}\mathrm{e}^{-a\lambda}.$$

If $0 < a < 1$, we have $f'(\lambda) > 0$ on $(0, 1)$, and thus $f(\lambda) \ge f(0) = 1$. However, we have $$ \left(a \mathrm{e}^{1 - a}\right)^n = (\mathrm{e}^{\ln a - (a - 1)})^n < 1$$ where we use $\ln a < a - 1$ (easy to prove). Thus, the inequality (1) does not hold for all $\lambda \in (0, 1)$.

If $a > 1$, we have $f'(\lambda) < 0$ on $(0, (a-1)/a)$, and $f'(\lambda) > 0$ on $((a-1)/a, 1)$. Thus, the minimum of $f(\lambda)$ on $(0, \lambda)$ is $$f_{\min} = f((a-1)/a) = a\mathrm{e}^{1-a}$$ achieved at $\lambda = (a-1)/a$ (uniquely). Thus, the inequality (1) holds only at $\lambda = (a-1)/a$.

We are done.

---

Remark: Actually, the reversed inequality holds, that is, for all $\varepsilon, n > 0$ and all $\lambda \in [0, 1)$, $$\bigg(\frac{1}{1-\lambda}\bigg)^n \exp(-\lambda\varepsilon) \ge \bigg(\frac\varepsilon n\bigg)^n \exp(n-\varepsilon).$$