4
$\begingroup$

Basically, I can understand the proofs' details for both inequalities, but still I have no idea why the bound of Hoeffding is sharper than that of Markov? Is there any underlying intuitive that can be explained in "natural language" other than mathematical formulas?

$\endgroup$
1
$\begingroup$

Hoeffding's inequality is proven by applying Markov's inequality (not to be confused with Chebeycheff's inequality!).

Hence it is NOT sharper but less sharp than what the Markov inequality can possibly give.

It is just simpler and more convenient to use which explains it's popularity. You can check that by reading the proof in the Wikipedia article of Hoeffding's inequality.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.