Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm working on a proof and to complete it I need to find a way to choose an $n$ such that $(1-a)^n < \epsilon$ for a fixed $a$ such that $\frac12 < a < 1$ and any small $\epsilon$. I'm trying to prove that a discrete probability space cannot contain an event $\mathcal A$ with probability at most $(1-a)^n$ since this clearly must go to 0. I'm just having a hard time finding an appropriate formula for $n$ to prove this goes to 0.

share|cite|improve this question
a = min(p, 1-p) – rmh52 Sep 11 '12 at 3:37
?? If a=min(p,1-p), then a<1/2. – Did Sep 11 '12 at 5:47

Try using the natural logarithmic function..

share|cite|improve this answer
The answer in the book bounds it with exp(-na) but I'm not sure I understand the procedure to arrive at this. Could you please explain? This is an optional assignment I'm just trying to understand the method. – rmh52 Sep 11 '12 at 3:41
If you require $(1-a)^n<\epsilon$, then $\ln (1-a)^n< \ln \epsilon \Rightarrow n \ln(1-a)<\ln \epsilon$, thus (since $\ln (1-a)$ is negative) $n > \frac{\ln \epsilon}{\ln (1-a)}$. – Tarnation Sep 11 '12 at 3:47

Let $1-a=\dfrac{1}{1+b}$. Note that $b$ is positive. You can solve for $b$ and get $b=\dfrac{a}{1-a}$.

By the Binomial Theorem, for any $n \ge 1$, we have $(1+b)^n \ge 1+nb$.
It follows that $$(1-a)^n =\frac{1}{(1+b)^n}\le \frac{1}{1+nb}\lt \frac{1}{nb}.$$ So to make $(1-a)^n \lt \epsilon$, it is enough to pick choose $n$ so that $\dfrac{1}{nb}\lt \epsilon$, that is, to choose $n$ so that $n\ge \dfrac{1}{\epsilon b}$. To be really explicit, if $n \ge \left\lceil\dfrac{1}{\epsilon b}\right\rceil$, then the desired inequality holds.

share|cite|improve this answer

$$\frac{1}{2}<a<1\Longrightarrow 0<1-a<1\Longrightarrow \exists\,1<b\in\Bbb R\,\,\;s.t.\,\, 1-a=\frac{1}{b}\Longrightarrow$$

$$\Longrightarrow (1-a)^n=\frac{1}{b^n}\xrightarrow [n\to\infty] {}0 $$

share|cite|improve this answer

Note that $1-a\leqslant\mathrm e^{-a}$ for every $a$ hence $(1-a)^n\leqslant\mathrm e^{-na}$ for every $a\leqslant1$. Assume that $a\leqslant1$. If $n\geqslant-(\log\varepsilon)/a$, then $\mathrm e^{-na}\leqslant\varepsilon$, which, in turn, ensures that $(1-a)^n\leqslant\varepsilon$.

With the addiditional hypothesis that $a\geqslant1/2$, the condition that $n\geqslant-2\log\varepsilon$ suffices.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.