# Proof: Tricky limit going to 0

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.

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

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

-

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

-

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.

-