Take the 2-minute tour ×
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.

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|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
add comment

4 Answers

Try using the natural logarithmic function..

share|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
add comment

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|improve this answer
add comment

$$\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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.