A simple master Theorem for discrete divide and conquer recurrences
Garet, Olivier
HAL, hal-02049382 / Harvested from HAL
Text on HAL
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 p_j n \rfloor},$$ where the $p_i$'s belong to $(0,1)$. 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$.
Publié le : 2019-02-26
Classification:  Divide-and-conquer recurrence,  Tauberian theorem,  Dirichlet series,  AMS: 11B37,68W40,60F15.,  [MATH.MATH-CA]Mathematics [math]/Classical Analysis and ODEs [math.CA],  [MATH.MATH-PR]Mathematics [math]/Probability [math.PR] 
@article{hal-02049382,
     author = {Garet, Olivier},
     title = {A simple master Theorem for discrete divide and conquer recurrences},
     journal = {HAL},
     volume = {2019},
     number = {0},
     year = {2019},
     language = {en},
     url = {http://dml.mathdoc.fr/item/hal-02049382}
}

Garet, Olivier. A simple master Theorem for discrete divide and conquer recurrences. HAL, Tome 2019 (2019) no. 0, . http://gdmltest.u-ga.fr/item/hal-02049382/