2
$\begingroup$

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.

  • 0
    ?? If a=min(p,1-p), then a<1/2.2012-09-11

4 Answers 4

1

Try using the natural logarithmic function..

  • 0
    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)}$.2012-09-11
1

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.

0

$\frac{1}{2}

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

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.