The Multiplicative Version of Azuma's Inequality, with an Application to Contention Analysis
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2021
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _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 |