The Multiplicative Version of Azuma's Inequality, with an Application to Contention Analysis

William Kuszmaul, Qi Qi

Azuma's inequality is a tool for proving concentration bounds on random variables. The inequality can be thought of as a natural generalization of additive Chernoff bounds. On the other hand, the analogous generalization of multiplicative Chernoff bounds has, to our knowledge, never been explicitly formulated. We formulate a multiplicative-error version of Azuma's inequality. We then show how to apply this new inequality in order to greatly simplify (and correct) the analysis of contention delays in multithreaded systems managed by randomized work stealing.

Knowledge Graph

arrow_drop_up

Comments

Sign up or login to leave a comment