I'm trying to prove that the best moment tail bound is no worse than the best Chernoff bound. I have all pieces other than this little frustration here:If c ≤ a i b i ∀ i, then c ≤ ∑ i = 1 ∞ a i ∑ i = 1 ∞ b i

Question

I&#039;m trying to prove that the best moment tail bound is no worse than the best Chernoff bound. I have all pieces other than this little frustration here:If   c  ≤            a      i              b      i        ∀  i, then   c  ≤                    ∑                  i          =          1                ∞                    a        i                            ∑                  i          =          1                ∞                    b        i

Sanaa Holder · Accepted Answer

Assuming all numbers are positive and that the series are convergent, you have  c      b    i    ≤      a    i  for all   i. Hence, summing all up, you have  c      ∑    i        b    i    ≤      ∑    i        a    i  which is equivalent to  c  ≤                    ∑        i                    a        i                            ∑        i                    b        i

If c <= (a_i)/(b_i) AA i, then c <= (sum_(i=1)^oo a_i)/(sum_(i=1)^oo b_i)

Answered question

Answer & Explanation

New Questions in Pre-Algebra