Extending Wormald's Differential Equation Method to One-sided Bounds
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909451814961152 |
|---|---|
| author | Bennett, Patrick MacRury, Calum |
| author_facet | Bennett, Patrick MacRury, Calum |
| contents | In this note, we formulate a "one-sided" version of Wormald's differential equation method. In the standard "two-sided" method, one is given a family of random variables which evolve over time and which satisfy some conditions including a tight estimate of the expected change in each variable over one time step. These estimates for the expected one-step changes suggest that the variables ought to be close to the solution of a certain system of differential equations, and the standard method concludes that this is indeed the case. We give a result for the case where instead of a tight estimate for each variable's expected one-step change, we have only an upper bound. Our proof is very simple, and is flexible enough that if we instead assume tight estimates on the variables, then we recover the conclusion of the standard differential equation method. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_12358 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Extending Wormald's Differential Equation Method to One-sided Bounds Bennett, Patrick MacRury, Calum Probability Discrete Mathematics Combinatorics G.3; G.2.1 In this note, we formulate a "one-sided" version of Wormald's differential equation method. In the standard "two-sided" method, one is given a family of random variables which evolve over time and which satisfy some conditions including a tight estimate of the expected change in each variable over one time step. These estimates for the expected one-step changes suggest that the variables ought to be close to the solution of a certain system of differential equations, and the standard method concludes that this is indeed the case. We give a result for the case where instead of a tight estimate for each variable's expected one-step change, we have only an upper bound. Our proof is very simple, and is flexible enough that if we instead assume tight estimates on the variables, then we recover the conclusion of the standard differential equation method. |
| title | Extending Wormald's Differential Equation Method to One-sided Bounds |
| topic | Probability Discrete Mathematics Combinatorics G.3; G.2.1 |
| url | https://arxiv.org/abs/2302.12358 |