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 have a sequence

$$a_n = (1-p)^n \sum_{\frac{n}{2}\le k \le n} \binom{n}{k} \left( \frac{p}{1-p} \right)^k.$$

I want to show that $a_n\to 0$ when $n\to\infty$ if $0\le p < \frac{1}{2}$. Here's a plot of the sequence for $p=\frac{1}{3}$:

plot of a_n


Failed attempt:

$$\begin{align} (1-p)^n \sum_{\frac{n}{2}\le k \le n} \binom{n}{k} \left( \frac{p}{1-p} \right)^k <& (1-p)^n \sum_{0 \le k \le n} \binom{n}{k}\left(\frac{p}{1-p}\right)^k \text{ for } n\ge 1\\ =& (1-p)^n \left(1+\frac{p}{1-p}\right)^n = 1. \end{align}$$

My hope here was to end up with something like $0.99^n$ in that last step so I could argue that since $a_n<0.99^n$ and $0.99^n\to 0$ as $n\to\infty$, $a_n\to\infty$. Unfortunately it came out to 1, not $0.99^n$.

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

This is a probability question in disguise. Let $X$ be a binomial$(n,p)$ random variable, so $X$ has mean $\mu=np$ and variance $\sigma^2=np(1-p)$. We can write your sum as $a_n=P(X\geq n/2)$, and by Chebyshev's inequality we get $$a_n\leq P\left(|X-\mu|\geq n(1/2-p)\right)\leq {\sigma^2\over n^2(1/2-p)^2}={p(1-p)\over n(1/2-p)^2}.$$ This clearly goes to zero as $n\to\infty$.

You could reverse engineer this proof to eliminate the probability, if necessary.

share|improve this answer
    
Thanks! Looking back at my class notes, it seems my professor invoked a form of Chebyshev's inequality a few times without referring to it by name. It's nice to know what it's called. –  Snowball Feb 13 '12 at 3:56
    
@Snowball Glad to be of help. –  Byron Schmuland Feb 13 '12 at 4:04
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.