6
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ For $n = \epsilon = 1$ your inequality becomes $e^{-\lambda} \le 1- \lambda$, and that does not hold for any non-zero $\lambda$. $\endgroup$
    – Martin R
    Oct 12, 2022 at 14:28
  • 2
    $\begingroup$ @Exodd How do you know? The OP's question is their own, unless you've managed to guess at their workings $\endgroup$
    – FShrike
    Oct 12, 2022 at 14:33

2 Answers 2

1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thanks for the partial answer! Yes I see, that $n$ and $\varepsilon$ need to be different... $\endgroup$
    – Jacobiman
    Oct 12, 2022 at 14:45
1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ What is $t\phantom{}$? Also it seems to me that this proves the inequality in the reverse direction. $\endgroup$
    – Gary
    Oct 12, 2022 at 23:59
  • $\begingroup$ @Gary It is a typo. I see, you are right. $\endgroup$
    – River Li
    Oct 13, 2022 at 0:09
  • 1
    $\begingroup$ @Gary I have posted a new solution. Thanks for pointing out my mistake. $\endgroup$
    – River Li
    Oct 13, 2022 at 0:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .