# A simple master Theorem for discrete divide and conquer recurrences

Olivier Garet

<figure><img src="image_1.png" /></figure>

## To cite this version:

Olivier Garet. A simple master Theorem for discrete divide and conquer recurrences. 2021. hal-02049382v2

HAL Id: hal-02049382

https://hal.science/hal-02049382v2

Preprint submitted on 15 Feb 2021

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.
# A SIMPLE MASTER THEOREM FOR DISCRETE DIVIDE AND CONQUER RECURRENCES

OLIVIER GARET

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$.

## 1. INTRODUCTION

Divide-and-conquer methods are widely used in Computer Science. The analysis of the cost of the algorithm naturally leads to divide-and-conquer recurrences. The methods to study these recurrences are popularized as “Master theorems” in the literature of Computer Science. See e.g. the reference books by Cormen et al [3] or Goodrich and Tamassia [7].

In the sequel, we consider sequences $(X_n)_{n \ge 0}$ that are defined by $X_0 = a_0$, then

$$(1) \qquad X_n = a_n + \sum_{j=1}^{m} b_j X_{\lfloor \frac{n}{m_j} \rfloor},$$

where the $m_i$'s are integer with $m_i \ge 2$ and $\lfloor x \rfloor$ denotes the only $n \in \mathbb{Z}$ such that $x - n \in [0, 1)$.

Of course, in Computer Science, $a_n$ and $X_n$ represent computation times and are therefore positive. However, the case of negative $a_n$ and $X_n$ can be of theoretical interest.

In the literature of Computer Science, $(a_n)$ is supposed to be deterministic. Nevertheless, in the context of randomized algorithm, eventually involving Monte-Carlo simulation, it is natural to consider the case of a random $(a_n)$ and observe the fluctuations of the computation time.

One of the most general results in the field of Computer Science is due to Akra and Bazzi [1]. They do not seek for an exact asymptotic limit, focusing of the order of the fluctuations. Their methods rely on classical real analysis.

The mathematical literature is more focused on exact methods, that rely on generating functions. The first paper in this spirit is Erdős et al [6], which solved the case $a_n = 0$ with the help of renewal equations. Tauberian theorems lead to simpler proofs of their result, see e.g. Choimet and Queffelec [2]. Recent results

<footnote n="2010">2010 Mathematics Subject Classification. 11B37,68W40,60F15.</footnote>

<footnote>Key words and phrases. Divide-and-conquer recurrence, Dirichlet series, Tauberian theorem.</footnote>
by Drmota and Szpankowski [4]) also rely on Tauberian theorems and some other tools in complex analysis. They request some assumptions of monotonicity.

If one wants to cover the case of a random $(a_n)$, the sequence $(a_n)$ obviously can not be supposed to be monotonic. Quite surprisingly, we did not find in the literature any theorem of this kind, computing an exact limit without making some assumption of monotonicity.

Let us clarify the assumptions: we assume that the $b_i$'s are positive numbers with $\sum_{j=1}^m b_j > 1$, that the $m_i$ are integers with $m_i \ge 2$ and such that there exists $j, \ell$ with $\frac{\log m_j}{\log m_\ell} \notin \mathbb{Q}$. The rational case, which is not considered here, is also of great interest in Computer Science – see e.g. Roura [8] or Drmota and Szpankowski [4].

It is known that the general growth of $(X_n)$ is governed by the value of the positive root $s_0$ for the equation

$$ \sum_{j=1}^{m} b_j m_j^{-s} = 1. $$

As said before, the originality of the present paper lies in the assumption on the $(a_n)$: under the assumption that

$$ \sum_{n=1}^{+\infty} \frac{|a_n|}{n^{s_0}} < +\infty, $$

we prove that the sequence $\frac{X_n}{n^{s_0}}$ admits a limit $L$ when $n$ tends to infinity and give a fairly simple closed expression for it.

As we will see, this allow to apply our Theorem to a large class of random variables. Then, the limit $L$ is a random variable, which appears as the sum of a random series.

If we specialize to the case where the $(a_n)$ are independent, then one can easily control the random fluctuations of $L$.

## 2. THE DETERMINISTIC THEOREM

**Theorem 1.** Let $m \ge 1$, $(b_1, \dots, b_m)$ be a family of non-negative numbers and $(m_1, \dots, m_m)$ be a family of integers with $m_i \ge 2$ and such that

* there exists $j, \ell$ with $\frac{\log m_j}{\log m_\ell} \notin \mathbb{Q}$;

* $\sum_{j=1}^m b_j > 1$.

We denote by $s_0$ the positive root $s_0$ for the equation

$$ \sum_{j=1}^{m} b_j m_j^{-s} = 1. $$

Then, there exists a sequence $(\ell_j)_{j \ge 0}$ of positive numbers such that for every sequence $(a_n)_{n \ge 0}$ with

$$ \sum_{n=1}^{+\infty} \frac{|a_n|}{n^{s_0}} < +\infty, $$

then the sequence $(X_n)_{n \ge 0}$ defined by $X_0 = a_0$ and the recursion (1) satisfies

$$ \lim_{n \to +\infty} \frac{X_n}{n^{s_0}} = \sum_{j=0}^{+\infty} \ell_j a_j. $$
Note that if the sequence $(a_j)_{j \ge 0}$ is non-negative and not identically zero, the limit $\sum_{j=0}^{+\infty} \ell_j a_j$ is positive, so we have found the correct speed for the growth of $(X_n)_{n \ge 0}$.

*Proof.* We denote by $L_n(a)$ the value of $X_n$ corresponding to the recursion (1) for some sequence $a$.

**The recursion equation.** Let $n_0$ be a non-negative integer and suppose first that $a_n = 0$ for $n > n_0$.

For $n > n_0$, we have $X(n) = \sum_{j=1}^{m} b_j X(\lfloor \frac{n}{m_j} \rfloor)$.

We can choose $C$ such that $|X_k| \le Ck^{s_0}$ for $0 < k \le n_1 = \max(n_0, m_1, \dots, m_m)$. Then, it follows by natural induction that $|X_k| \le Ck^{s_0}$ for each $k \in \mathbb{N}^*$. In the sequel, we put $X(t) = X(\lfloor t \rfloor)$ to simplify some notation. Now define

$$ (2) \qquad \phi(s) = s \int_{n_0+1}^{+\infty} \frac{X(t)}{t^{s+1}} dt $$

for $s \in \mathbb{C}$ with $\mathrm{Re}(s) > s_0$. The recursion Equation leads to

$$ \begin{aligned} \phi(s) &= s \int_{n_0+1}^{+\infty} \sum_{j=1}^{m} b_j \frac{X\left(\frac{t}{m_j}\right)}{t^{s+1}} dt = s \sum_{j=1}^{m} b_j m_j^{-s} \int_{\frac{n_0+1}{m_j}}^{+\infty} \frac{X(t)}{t^{s+1}} dt \\ &= \left( \sum_{j=1}^{m} b_j m_j^{-s} \right) \phi(s) + s \sum_{j=1}^{m} b_j m_j^{-s} \int_{\frac{n_0+1}{m_j}}^{n_0+1} \frac{X(t)}{t^{s+1}} dt. \end{aligned} $$

Since

$$ \left| \sum_{j=1}^{m} b_j m_j^{-s} \right| \le \sum_{j=1}^{m} |b_j m_j^{-s}| = \sum_{j=1}^{m} b_j m_j^{-\mathrm{Re}(s)} < \sum_{j=1}^{m} b_j m_j^{-s_0} = 1, $$

we can write, for $\mathrm{Re}(s) > s_0$:

$$ (3) \qquad \phi(s) = \frac{P(s)}{1 - \sum_{j=1}^{m} b_j m_j^{-s}}, \quad \text{with } P(s) = s \sum_{j=1}^{m} b_j m_j^{-s} \int_{\frac{n_0+1}{m_j}}^{n_0+1} \frac{X(t)}{t^{s+1}} dt $$

**Tauberian magic.** Now, fix a non-negative integer $n_0$ and suppose that the sequence $a = (a_n)_{n \ge 0}$ is $a = I^{n_0}$ with

$$ I_i^{n_0} = \mathbb{1}_{i \le n_0} = \begin{cases} 1 & \text{if } i \le n_0 \\ 0 & \text{else} \end{cases}. $$

By natural induction, it is easy to see that $(X_n)_{n \ge 0}$ is non-decreasing.

It is also not difficult to see that $1 - \sum_{j=1}^{m} b_j m_j^{-s}$ does not vanish for $s \in \mathbb{C}$ with $\mathrm{Re}(s) \ge s_0$ and $s \ne s_0$. Proceeding as in Choimet and Queffelec (see [2], section 4), we can note that, for $\mathrm{Re}(s) = s_0$

$$ \mathrm{Re} \left( \sum_{j=1}^{m} b_j m_j^{-s} \right) = \sum_{j=1}^{m} b_j m_j^{-s_0} \cos(\log m_j \mathrm{Im}(s)) \le \sum_{j=1}^{m} b_j m_j^{-s_0} = 1 $$

In fact, the inequality in strict when $\mathrm{Im}(s) \ne 0$. Overwise, we would have $\log m_j \mathrm{Im}(s) \in 2\pi\mathbb{Z}$ for each $j$, whence $\frac{\log m_j}{\log m_k} \in \mathbb{Q}$ for each $j, k$, which has been excluded.
It follows that for

$$c = \operatorname{Res}_{s_0} \phi = \frac{P(s_0)}{\sum_{j=1}^{m} b_j m_j^{-s_0} \log(m_j)},$$

the map $s \mapsto \phi(s) - \frac{c}{s_0}$ is holomorphic on $\{s \in \mathbb{C}; \operatorname{Re}(s) \geq s_0\}$.

Now note $b(x) = \sum_{n_0 < n \leq x} (X_n - X_{n-1})$. The Abel transformation gives

$$\sum_{n=n_0+1}^{+\infty} \frac{X_n - X_{n-1}}{n^s} = s \int_{n_0+1}^{+\infty} \frac{b(t)}{t^{s+1}} dt$$

Since $b(t) = X(t) - X_{n_0}$, we have

$$\sum_{n=n_0+1}^{+\infty} \frac{X_n - X_{n-1}}{n^s} = s \int_{n_0+1}^{+\infty} \frac{X(t)}{t^{s+1}} dt - \frac{X_{n_0}}{(n_0+1)^s} = \phi(s) - \frac{X_{n_0}}{(n_0+1)^s}.$$

Now, we will apply the Ikehara–Newman Theorem for series:

**Proposition 1.** Let $(a_n)_{n \geq 1}$ be a sequence of non-negative real numbers, and $a$, $c$ be positive real numbers. Suppose that the Dirichlet series $\Phi(s) = \sum_{n=1}^{+\infty} a_n n^{-s}$ is defined on the open half-plane $\operatorname{Re}(s) > a$ and that, more precisely, with $A(x) = \sum_{n \leq x} a_n$ for $x \geq 0$, the following properties are verified:

* $A(x)x^{-a}$ is bounded on $\mathbb{R}^+$;

* $\Phi(s) - \frac{c}{s-a}$ has a holomorphic extension $G$ on the closed half-plane $\operatorname{Re}(s) \geq a$.

Then we have $A(x) \sim \frac{c}{a}x^a$ as $x \to +\infty$.

Since $(X_n)_{n \geq 0}$ is non-decreasing, the sequence $(X_n - X_{n-1})_{n > n_0}$ is non-negative, so the Wiener-Ikehara Theorem for series applies: since $b(t) = O(t^{s_0})$ when $t \to +\infty$, we get $b(x) \sim \frac{c}{s_0}x^{s_0}$, so

$$\lim_{n \to +\infty} \frac{L_n(I^{n_0})}{n^{s_0}} = \frac{\sum_{j=1}^{m} b_j m_j^{-s_0} \int_{\frac{n_0+1}{m_j}}^{n_0+1} \frac{L_t(I^{n_0})}{t^{s_0+1}} dt}{\sum_{j=1}^{m} b_j m_j^{-s_0} \log(m_j)}.$$

For $n_0 = 0$, we have

$$\begin{aligned} \ell_0 &= \lim_{n \to +\infty} \frac{L_n(\delta^0)}{n^{s_0}} = \lim_{n \to +\infty} \frac{L_n(I^0)}{n^{s_0}} = \frac{1}{\sum_{j=1}^{m} b_j m_j^{-s_0} \log(m_j)} \sum_{j=1}^{m} b_j m_j^{-s_0} \int_{\frac{1}{m_j}}^{1} \frac{1}{t^{s_0+1}} dt \\ &= \frac{1}{\sum_{j=1}^{m} b_j m_j^{-s_0} \log(m_j)} \sum_{j=1}^{m} b_j m_j^{-s_0} \frac{m_j^{s_0} - 1}{s_0} \end{aligned}$$

Note that this equality and the related convergence form the result by Erdős et al [6].

Let $n_0 \geq 1$. The sequence $(\delta_n^{n_0})_{n \geq 0}$ is defined by

$$\delta_n^{n_0} = \begin{cases} 1 & \text{if } n = n_0 \\ 0 & \text{else} \end{cases}.$$

Since $\delta^{n_0} = I^{n_0} - I^{n_0-1}$, it follows that

$$L_n(\delta^{n_0}) n^{-s_0} = L_n(I^{n_0}) n^{-s_0} - L_n(I^{n_0-1}) n^{-s_0}$$
has a limit when $n$ tends to infinity. Let us denote it by $\ell_{n_0}$.

To compute it, take $a = \delta^{n_0}$ and consider again the associated $\phi$. From (2), we get $\ell_{n_0} = \lim_{s \to s_0^+} \frac{1}{s_0}(s - s_0)\phi(s)$. On the other side, Equation (3) is still valid, with

$$ 
\begin{aligned}
P(s) &= s \sum_{j=1}^{m} b_j m_j^{-s} \int_{\frac{n_0+1}{m_j}}^{n_0+1} \frac{X(t)}{t^{s+1}} dt \\
&= s \sum_{j=1}^{m} b_j m_j^{-s} \int_{\max(n_0, \frac{n_0+1}{m_j})}^{n_0+1} \frac{1}{t^{s+1}} dt,
\end{aligned}
$$

also

$$ \frac{1}{s_0}(s - s_0)\phi(s) = -\frac{s}{s_0} \frac{s_0 - s}{1 - \sum_{j=1}^{m} b_j m_j^{-s}} \sum_{j=1}^{m} b_j m_j^{-s} \int_{\max(n_0, \frac{n_0+1}{m_j})}^{n_0+1} \frac{1}{t^{s+1}} dt $$

and, considering that $m_j \ge 2$, we get

$$ \ell_{n_0} = \frac{1}{\sum_{j=1}^{m} b_j m_j^{-s_0} \log(m_j)} \sum_{j=1}^{m} b_j m_j^{-s_0} \int_{n_0}^{n_0+1} \frac{1}{t^{s_0+1}} dt. $$

Thanks to this expression and the previous one, it is clear that $\ell_j > 0$ holds for each $j \ge 0$.

**The general case.** For $n, j \ge 0$, we note $K_n^j = L_n(\delta^j)$. It is obvious that $K_n^j = 0$ for $n < j$ and $K_j^j = 1$. It easily follows by natural induction on $n$ that $0 \le K_n^j \le \frac{K_n^0}{K_j^0}$. Now, the affine nature of the recursion gives

$$ X_n = \sum_{j=0}^{n} K_n^j a_j $$

For each $j \ge 0$, we have $\lim_{n \to +\infty} \frac{K_n^j}{n^{s_0}} = \ell_j$. Also, the $K_j^0$'s are positive, with $\lim_{j \to +\infty} \frac{K_j^0}{j^{s_0}} = \ell_0 > 0$, so there exists $M$ such that $0 < \frac{1}{K_j^0} \le \frac{M}{j^{s_0}}$ for each $j \ge 1$. Then, for each $j, n \ge 1$, we have

$$ \left| \frac{K_n^j a_j}{n^{s_0}} \right| \le \frac{K_n^0 |a_j|}{n^{s_0} K_j^0} \le \frac{|a_j|}{K_j^0} \le M \frac{|a_j|}{j^{s_0}} $$

and by the Weierstrass criterion,

$$ \lim_{n \to +\infty} \frac{X_n}{n^{s_0}} = \sum_{j=0}^{+\infty} \ell_j a_j. $$

□

### 3. APPLICATION TO SEQUENCES OF RANDOM VARIABLES

We give below some applications of Theorem 1 to sequences of random variables.
### 3.1. Convergence.

**Theorem 2.** Assume that the $m_i$'s, the $b_i$'s and $s_0$ fulfill the assumptions of Theorem 1 and $(a_n)$ is a sequence of random variables. Under each of the following sets of supplementary assumptions, the sequence $(X_n)_{n \ge 0}$ defined by $X_0 = a_0$ and the recursion (1) is such that $\frac{X_0}{n^{s_0}}$ almost surely converges to some random variable, given as the sum of the random series:

$$L = \sum_{j=0}^{+\infty} \ell_j a_j.$$

(A) $\sum_{j=1}^{m} \frac{b_j}{m_j} > 1$ and the $(a_n)$ are integrable random variables with $C = \sup_{n \ge 1} \mathbb{E}|a_n| < +\infty$.

(B) $\sum_{j=1}^{m} \frac{b_j}{m_j^2} > 1$ and the $a_n$ are random variables following the Cauchy $C(0, 1)$ Law.

*Proof.* (A) the condition $\sum_{j=1}^{m} \frac{b_j}{m_j} > 1$ implies that $s_0 > 1$. We have $\mathbb{E}(\sum_{n=1}^{+\infty} \frac{|a_n|}{n^{s_0}}) \le C\zeta(s_0) < +\infty$, so $\sum_{n=1}^{+\infty} \frac{|a_n|}{n^{s_0}} < +\infty$ almost surely, which gives the almost sure behavior of $\frac{X_0}{n^{s_0}}$.

(B) the condition $\sum_{j=1}^{m} \frac{b_j}{m_j^2} > 1$ implies that $s_0 > 2$. We fix $\eta > 1$ with $s_0 - \eta > 1$. Then $\mathbb{P}(|a_n| > n^\eta) = O(n^{-\eta})$ and $\sum_{n=1}^{+\infty} \mathbb{P}(|a_n| > n^\eta) < +\infty$, so by the Borel-Cantelli Lemma, for almost every $\omega$, there exists $n_0(\omega)$ with $|a_n(\omega)| \le n^\eta$ for $n \ge n_0(\omega)$, which gives the convergence of $\sum_{n \ge 1} \frac{|a_n|}{n^{s_0}}$ and our Master Theorem still applies. $\square$

<figure><img src="image_2.png" /></figure>

### 3.2. Non-vanishing limit.
We have already noticed that the limit does not vanish when the $a_j$ are non-negative. In the case of random independent $a_n$, it is very unlikely that the limit is null, even for signed variables.

**Theorem 3.** Assume that the $a_i$'s, $m_i$'s, the $b_i$'s and $s_0$ fulfill the assumptions of Theorem 2 and also that $(a_n)$ is a sequence of independent random variables, with at least one $j_0 \ge 0$ such that $a_j$ is non-atomic. Then, the limit $L = \sum_{j=0}^{+\infty} \ell_j a_j$ is non-atomic, and particularly $\mathbb{P}(L = 0) = 0$.

*Proof.* By independence, the characteristic function of $L$ satisfies

$$\forall t \in \mathbb{R} \quad |\phi_L(t)| = \prod_{j=0}^{+\infty} |\phi_{\ell_j a_j}(t)| \le |\phi_{\ell_{j_0} a_{j_0}}(t)|.$$

Therefore

$$\lim_{T \to +\infty} \frac{1}{2T} \int_{-T}^{T} |\phi_L(t)|^2 dt \le \lim_{T \to +\infty} \frac{1}{2T} \int_{-T}^{T} |\phi_{\ell_0 a_{j_0}}(t)|^2 dt = 0,$$

which implies that $L$ is non-atomic (see e.g. Durrett [5], section 3.3). $\square$

<figure><img src="image_3.png" /></figure>

### 3.3. Exponential moments.

**Theorem 4.** Assume that the $m_i$'s, the $b_i$'s and $s_0$ fulfill the assumptions of Theorem 1 and $(a_n)$ is a sequence of independent random variables. The sequence $(X_n)_{n \ge 0}$ is defined by $X_0 = a_0$ and the recursion (1).
* If there exists a distribution $\mu$ with exponential moments such that $|a_n|$ is stochastically dominated by $\mu^{*n}$ for each $n \ge 0$, then $|X_n|$ has exponential moments for each $n$.

* If $s_0 > 1$ (or equivalently $\sum_{j=1}^m \frac{b_j}{m_j} > 1$) and there exists a distribution $\mu$ with exponential moments such that $|a_n|$ is stochastically dominated by $\mu$ for each $n \ge 0$, then $\frac{X_n}{n^{s_0}} \to L$ a.s. where $|L|$ has exponential moments.

* If $s_0 > 2$ (or equivalently $\sum_{j=1}^m \frac{b_j}{m_j^2} > 1$) and there exists a distribution $\mu$ with exponential moments such that $|a_n|$ is stochastically dominated by $\mu^{*n}$ for each $n \ge 0$, then $\frac{X_n}{n^{s_0}} \to L$ a.s. where $|L|$ has exponential moments.

Proof. We begin with an easy lemma:

**Lemma 1.** Let $X$ be a random variable with $\mathbb{E}(e^{\alpha X}) < +\infty$ and $Y$ a random variable following the exponential law $\mathcal{E}(\alpha)$ Then, for $a = \frac{1}{\alpha} \log \mathbb{E}(e^{\alpha X_1})$, we have the stochastic domination $X \prec Y + a$.

Proof. We just have to prove that for $t \in \mathbb{R}$, $\mathbb{P}(X \ge t) \le \mathbb{P}(Y + a \ge t)$, or equivalently $\mathbb{P}(X \ge t) \le \mathbb{P}(Y \ge t - a)$. For $t \le a$, we have $\mathbb{P}(X \ge t) \le 1 = \mathbb{P}(Y \ge t - a)$. For $t \ge a$, the Markov inequality gives

$$ \mathbb{P}(X \ge t) \le \frac{\mathbb{E}e^{\alpha X}}{e^{\alpha t}} = \frac{e^{\alpha a}}{e^{\alpha t}} = \exp(-\alpha(t-a)) = P(Y \ge t - a). $$

This completes the proof. $\square$

<figure><img src="image_4.png" /></figure>

Now, we have $a$ and $\alpha$ such that for each $n \ge 1$

$$ |a_n| \prec \mu^{*n} \prec (\delta^a * \mathcal{E}(\alpha))^{*n} = \delta^{na} * \Gamma(n, \theta). $$

Let $(Z_n)_{n \ge 0}$ be a sequence of independent variables with $Z_n \sim \Gamma(n, \theta)$, where $\Gamma(a, \gamma)$ is the Law with the density

$$ x \mapsto \frac{\gamma^a}{\Gamma(a)} x^{a-1} e^{-\gamma x} \mathbb{1}_{[0, +\infty[}(x). $$

$\frac{|X_n|}{n^{s_0}}$ is stochastically dominated by

$$ M \sum_{j=0}^{n} \frac{ja + Z_j}{(j + 1)^{s_0}}, $$

so for $t < 1/\alpha$, we have

$$ \begin{aligned} \mathbb{E}(e^{t \frac{|X_n|}{n^{s_0}}}) & \le \exp(Ma \sum_{j=1}^{n+1} j^{-s_0}) \prod_{j=0}^{n} \mathbb{E} \exp(\frac{tZ_j}{(j+1)^{s_0}}) \\ & \le \exp(Ma \sum_{j=1}^{n+1} j^{-s_0}) \prod_{j=0}^{n} (1 - \frac{\alpha t}{(j+1)^{s_0}})^{-j} \end{aligned} $$

When $j$ is large enough, $(1 - \frac{\alpha t}{(j+1)^{s_0}})^{-j} \le \exp(\frac{\alpha t}{j^{s_0-1}})$, which gives the existence of an exponential moment for $s_0 > 2$.

The proof in the case $|a_n| \prec \mu$ and $s_0 > 1$ is similar. $\square$

<figure><img src="image_5.png" /></figure>
As an example of domination by $\mu^{*n}$, we can think about the case where a recursive function called with parameter $n$ requires $n$ simulations with an acceptance-rejection method. Then, $a_n$ appears as the sum of $n$ independent variables following a geometric distribution $\mu = \mathcal{G}(p)$.

## REFERENCES

[1] Mohamad Akra and Louay Bazzi. On the solution of linear recurrence equations. *Comput. Optim. Appl.*, 10(2):195-210, 1998.

[2] D. Choimet and H. Queffélec. *Twelve landmarks of twentieth-century analysis*. Cambridge University Press, New York, 2015. Illustrated by Michaël Monerau, Translated from the 2009 French original by Danièle Gibbons and Greg Gibbons, With a foreword by Gilles Godefroy.

[3] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Stein. *Introduction to Algorithms*. PHI Learning, 2010.

[4] Michael Drmota and Wojciech Szpankowski. A master theorem for discrete divide and conquer recurrences. *J. ACM*, 60(3):Art. 16, 49, 2013.

[5] Rick Durrett. *Probability—theory and examples*, volume 49 of *Cambridge Series in Statistical and Probabilistic Mathematics*. Cambridge University Press, Cambridge, 2019. Fifth edition of [MR1068527].

[6] P. Erdős, A. Hildebrand, A. Odlyzko, P. Pudaite, and B. Reznick. The asymptotic behavior of a family of sequences. *Pacific J. Math.*, 126(2):227-241, 1987.

[7] Michael T. Goodrich and Roberto Tamassia. *Algorithm Design: Foundations, Analysis, and Internet Examples*. Wiley, 2002.

[8] Salvador Roura. Improved master theorems for divide-and-conquer recurrences. *J. ACM*, 48(2):170-205, 2001.

UNIVERSITÉ DE LORRAINE, INSTITUT ÉLIE CARTAN DE LORRAINE, UMR 7502, VANDOEUVRE-LÈS-NANCY, F-54506, FRANCE, AND, CNRS, INSTITUT ÉLIE CARTAN DE LORRAINE, UMR 7502, VANDOEUVRE-LÈS-NANCY, F-54506, FRANCE,

Email address: Olivier.Garet@univ-lorraine.fr