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

2021/02/09 by William Kuszmaul, Qi Qi, Kuszmaul, William +1 · 2 citations
Mathematics · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Mathematical Inequalities and Applications #Point processes and geometric inequalities #Random Matrices and Applications

paper · pdf · doi:10.48550/arxiv.2102.05077

openalex publication_date 2021/02/09 · openalex created_date 2021/02/15 · openalex updated_date 2026/07/28

Abstract

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 does not appear to be widely known. 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.

Citations

• Scheduling multithreaded computations by work stealing
• A \widetildeO(n) Non-Adaptive Tester for Unateness

Cited by

• An Asymptotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale
• Faster Dynamic (Δ+1)-Coloring Against Adaptive Adversaries

Related

• On Refined Versions of the Azuma-Hoeffding Inequality with Applications in Information Theory
• Chernoff-Hoeffding Inequality and Applications
• A Variant of Azuma's Inequality for Martingales with Subgaussian Tails
• Concentration inequality using unconfirmed knowledge
• Concentration-Bound Analysis for Probabilistic Programs and Probabilistic Recurrence Relations