How does the inequality $1 - (1 - x_i)^{\ln{\vert E \vert} + \ln{4}} \leq (\ln{\vert E \vert} +\ln {4})x_i$ stand?

Question

The inequality is $$ 1 - (1 - x_i)^{\ln{\vert E \vert} + \ln{4}} \leq (\ln{\vert E \vert} +\ln {4})x_i $$

With the following constraints:

• $\vert E \vert \in \mathbb{N}^+$
• $x_i \in [0, 1]$.

This appeared during my approximation algorithm class and my professor just gave no explaination on it. Any help is appreciated!

Answer 1

You can rewrite this inequality this way: $$ (1-x_i)^{\ln|E| + \ln4} \geq 1-(\ln|E|+\ln4)x_i$$ with $-x_i > -1$ and $\ln|E| + \ln4 >1$. This is true by Bernoulli's inequality

Answer 2

Let us take $a = \ln |E| + \ln 4$. Then the problem is equivalent to

$1 - (1-x)^a \le ax$ or to rearrange it, $(1-x)^a \ge 1- ax$. Please check out Bernoulli's inequality for the rest. There are some conditions for it to hold which are satisfied in this case.