10
$\begingroup$

I've seen the following inequality arise in applying the probabilistic method (in combinatorics); potentially it arises elsewhere. For all $n\in\mathbb{N}$ and $0\le x\le 1$, $$1-(1-x)^n\le nx.$$

This inequality is routine to establish with calculus, but that doesn't yield much insight. I realize this question is a bit vague, but is there a perspective in which this inequality is "natural"?

$\endgroup$
  • 1
    $\begingroup$ Is the routine proof the following $(n\ge 1)$? $$ 1 - (1-x)^n = \int_{1-x}^1 n t^{n-1} dt \le \int_{1-x}^1 n 1^{n-1}dt = n(1 - (1-x)) = nx$$ $\endgroup$ – Calvin Khor Oct 16 '19 at 5:24
  • 1
    $\begingroup$ Yes, that's the proof I came up with, Calvin. $\endgroup$ – Vince Vatter Oct 16 '19 at 15:26
16
$\begingroup$

Depends what you mean by 'natural', but here is an explanation you may find useful, if you're happy with the union bound.

Suppose $x$ is the probability that a coin comes up heads. What is the probability that in $n$ independent flips we get at least one head? One way to think about this is that this is the probability that either the first flip is heads, or the second flip, or the third, and so on.

The union bound states that $\mathbb{P}(A_1\cup\cdots \cup A_n)$ is at most $\mathbb{P}(A_1)+\cdots+\mathbb{P}(A_n)$. If we let $A_i$ be the event that the $i$th flip comes up heads, then $\mathbb{P}(A_i)=x$, and so

$$\mathbb{P}(\textrm{at least one coin is heads}) \leq nx.$$

On the other hand, the left-hand side is

$$1-\mathbb{P}(\textrm{all coins are tails})=1-(1-x)^n,$$

and so

$$ 1-(1-x)^n \leq nx.$$

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