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.

Consider the sum

$$\sum_{k=0}^{n_0} {n \choose k} \cdot \alpha^k$$

where $\alpha \in \mathbb{R}$ arbritary, $n_0 < n$. So it looks like binomial theorem,

$$\sum_{k=0}^n {n \choose k} \cdot \alpha^k = (1+\alpha)^n$$

I would like to find an estimate $$\sum_{k=0}^{n_0} {n \choose k} \cdot \alpha^k \geq c \cdot (1+\alpha)^n$$ where $c$ is a constant one can calculate explicitely. I tried to use binomial theorem and symmetry, i.e. ${n \choose k} = {n \choose n-k}$ and things like that, but it didn't work. (I would like to apply the estimate in particular for $n_0 := \lfloor \frac{n}{2} \rfloor$.)

share|improve this question

2 Answers 2

up vote 3 down vote accepted

You can apply Chernoff Bound - It states $\sum_{i > \lfloor \frac{n}{2} \rfloor} \binom{n}{i} p^i (1-p)^{n-i} \ge 1 - e^{-\frac{n}{2p}(p-\frac{1}{2})^2}$.

If you write the sum in reverse and use the symmetry of binomial coefficients, you obtain

$$\sum_{i < \lceil \frac{n}{2} \rceil} \binom{n}{i} p^{n-i} (1-p)^{i} \ge 1 - e^{-\frac{n}{2p}(p-\frac{1}{2})^2}$$ or $$\sum_{i < \lceil \frac{n}{2} \rceil} \binom{n}{i} (\frac{1-p}{p})^{i} \ge p^{-n}(1 - e^{-\frac{n}{2p}(p-\frac{1}{2})^2}) $$

Choosing $p \in (0,1)$ such that $\frac{1-p}{p} = \alpha$ (assuming $\alpha > 0$), i.e. $p=\frac{1}{1+\alpha}$, we obtain

$$\sum_{i < \lceil \frac{n}{2} \rceil} \binom{n}{i} \alpha^{i} \ge (1+\alpha)^{n}(1 - e^{-\frac{n}{8}\frac{(1-\alpha)^2}{(1+\alpha)}})$$ So you can take the following $C$ that depends on $n$ and $p$, at least in the case $n_0=\lfloor \frac{n}{2} \rfloor$: $$C=1 - e^{-\frac{n}{8}\frac{(1-\alpha)^2}{(1+\alpha)}}$$

EDIT: By choosing $\alpha = \frac{p}{1-p}$ you can get the following upper bound: $$\sum_{i \le \lfloor \frac{n}{2} \rfloor} \binom{n}{i} \alpha^{i} \le (1+\alpha)^{n} e^{-\frac{n}{8}\frac{(1-\alpha)^2}{\alpha(1+\alpha)}}$$

EDIT 2: In general, if $\alpha>0$ and we divide your inequality by $(1+\alpha)^n$ we obtain: $\sum_{k\le n_0} \binom{n}{k} (\frac{\alpha}{1+\alpha})^{k} (\frac{1}{1+\alpha})^{n-k} \ge c$, so we want to bound the probability that among $n$ coin tosses, we got "Head" no more than $n_0$ times, where the probability for head is $\frac{\alpha}{1+\alpha}$. Under the condition $\alpha < 1$, I can replace that "8" in the denominator by "2", see Hoeffding.

share|improve this answer

I think you're going to have a hard time getting such an inequality. Suppose you were able to prove the existence of a constant $c$ such that $$\sum_{k=0}^{\lfloor n/2\rfloor}\binom{n}{k}\alpha^k \geq c(1+\alpha)^n$$ for all $\alpha>0$. Dividing this inequality by $\alpha^n$ would give $$\sum_{k=0}^{\lfloor n/2\rfloor}\binom{n}{k}\alpha^{k-n}\geq c(1 + \alpha^{-1})^n.$$ When $\alpha\to +\infty$, the right hand side of this expression tends to $c$, whereas the left hand side tends to $0$, a contradiction.

This shows the constant $c$ would have to depend on $\alpha$ (and quite probably $n$ and $n_0$ as well), which seems like it would make such an inequality useless, unless you are really just looking for a very computable expression for $c$.

share|improve this answer

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.