Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2021
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2102.05077 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909448073641984 |
|---|---|
| author | Kuszmaul, William Qi, Qi |
| author_facet | Kuszmaul, William Qi, Qi |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2102_05077 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | The Multiplicative Version of Azuma's Inequality, with an Application to Contention Analysis Kuszmaul, William Qi, Qi Data Structures and Algorithms 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. |
| title | The Multiplicative Version of Azuma's Inequality, with an Application to Contention Analysis |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2102.05077 |