12
$\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$
2
  • 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, 2019 at 5:24
  • 1
    $\begingroup$ Yes, that's the proof I came up with, Calvin. $\endgroup$
    – Vince Vatter
    Oct 16, 2019 at 15:26

1 Answer 1

Reset to default
21
$\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.$$

$\endgroup$

You must log in to answer this question.

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