2

I'm currently going through a research paper and was trying to redo a proof on my side. The paper states : $$ \begin{align} \text{P}[failure] &\le \text{P}[s + 1 \text{ runs of A fail}] \\ &\le \sum_{i \ge s + 1} \binom{2s + 1}{i} \left(\frac{1}{4}\right)^i \left(\frac{3}{4}\right)^{2s + 1 - i} \\ &\le \left(\frac{1}{4}\right)^{s + 1} \left(\frac{3}{4}\right)^s \sum_{i \ge s + 1} \binom{2s + 1}{i} \end{align} $$

I just can't seem to understand why one can move from the second to the last line. I understand that we use the frontier $i = s + 1$ and replace, but I don't get why this means we can extract the fractions from the sum, and why the expression is larger than the line before.

What is the obvious thing I'm missing ?

olirwin
  • 135

2 Answers2

2
  1. You probably have a typo in the exponent of $ \frac{3}{4} $, it should be $ s $.
  2. What you are asking is equivalent to why is
    $$ \left( \frac{1}{4} \right)^a \ge \left( \frac{1}{4} \right)^b, $$
    given that $ 0 < a \le b $.
  3. Try to understand the inequality with everything inside the sums, that is
    \begin{equation} \sum_{i \ge s + 1} \binom{2s + 1}{i} \left(\frac{1}{4}\right)^i \left(\frac{3}{4}\right)^{2s + 1 - i} \le \sum_{i \ge s + 1} \binom{2s + 1}{i}\left(\frac{1}{4}\right)^{s + 1} \left(\frac{3}{4}\right)^s \end{equation} Since the last two terms do not depend on $ i $, we can simply factor them out of the sum - same way we can write
    $ a x + b x + c x = x(a+b+c)$
shortmanikos
  • 1,425
  • I fixed the exponent, it is indeed $s$. I understand why if $a \le b$, then $\left( \frac{1}{4} \right)^a \ge \left( \frac{1}{4} \right)^b$, but I can't wrap my head around the fact that this is sufficient proof to bound the sum. I might be missing an elementary theorem or property though – olirwin Nov 18 '21 at 19:48
  • @olirwin I 've added a third part in my answer to make things clearer, hope it helps – shortmanikos Nov 18 '21 at 22:14
  • Aaah yes I think I've got it now, thank you very much :) – olirwin Nov 19 '21 at 14:08
1

There is a typo in the paper. It makes no sense to bring out from the summation operator $\Sigma$ a quantity $\left(\frac{3}{4}\right)^i$ that depends on the summation index $i$. The reason why they can bound the sum using $\left(\frac{1}{4}\right)^{s+1}$ is that $\left(\frac{1}{4}\right)^{i} \le \left(\frac{1}{4}\right)^{s+1}$ for all $i\geq s +1$. Where he writes $\left(\frac{3}{4}\right)^i$ he meant $\left(\frac{3}{4}\right)^{s}$. The reason is that $\left(\frac{3}{4}\right)^s \geq \left(\frac{3}{4}\right)^{2s+1-i}$ for all $i \geq s+1$ since $s\geq 2s+1-i \iff i \geq s+1$.

Martin Geller
  • 1,059