A simple Master Theorem for Discrete Divide and Conquer Recurrences

Abstract

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 \).