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

arXiv: https://arxiv.org/abs/2102.05077 · HTML: https://mlsanity.com/paper/2102.05077/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Feb 2021.

## Built on by (most cited first, 5 of 5)

- [Nash Regret Guarantees for Linear Bandits](https://mlsanity.com/paper/2310.02023/) (2023)
- [Is Transductive Learning Equivalent to PAC Learning?](https://mlsanity.com/paper/2405.05190/) (2024)
- [On the price of exact truthfulness in incentive-compatible online learning with bandit feedback: A regret lower bound for WSU-UX](https://mlsanity.com/paper/2404.05155/) (2024)
- [Validity and efficiency of the conformal CUSUM procedure](https://mlsanity.com/paper/2412.03464/) (2024)
- [No-regret incentive-compatible online learning under exact truthfulness with non-myopic experts](https://mlsanity.com/paper/2502.11483/) (2025)

## Abstract (arXiv)

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.