A simple master Theorem for discrete divide and conquer recurrences
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2019
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913804647923712 |
|---|---|
| author | Garet, Olivier |
| author_facet | Garet, Olivier |
| contents | The aim of this note is to provide a Master Theorem for some discrete divide and conquer recurrences: $$X_{n}=a_n+\sum_{j=1}^m b_j X_{\lfloor{\frac{n}{m_j}}\rfloor},$$ where the $m_i$'s are integers with $m_i\ge 2$. The main novelty of this work is there is no assumption of regularity or monotonicity for $(a_n)$. Then, this result can be applied to various sequences of random variables $(a_n)_{n\ge 0}$, for example such that $\sup_{n\ge 1}\mathbb{E}(|a_n|)<+\infty$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1902_10600 |
| institution | arXiv |
| publishDate | 2019 |
| record_format | arxiv |
| spellingShingle | A simple master Theorem for discrete divide and conquer recurrences Garet, Olivier Classical Analysis and ODEs Probability The aim of this note is to provide a Master Theorem for some discrete divide and conquer recurrences: $$X_{n}=a_n+\sum_{j=1}^m b_j X_{\lfloor{\frac{n}{m_j}}\rfloor},$$ where the $m_i$'s are integers with $m_i\ge 2$. The main novelty of this work is there is no assumption of regularity or monotonicity for $(a_n)$. Then, this result can be applied to various sequences of random variables $(a_n)_{n\ge 0}$, for example such that $\sup_{n\ge 1}\mathbb{E}(|a_n|)<+\infty$. |
| title | A simple master Theorem for discrete divide and conquer recurrences |
| topic | Classical Analysis and ODEs Probability |
| url | https://arxiv.org/abs/1902.10600 |