A simple master Theorem for discrete divide and conquer recurrences
Olivier Garet







Université de Lorraine, Institut Élie Cartan de Lorraine, UMR 7502, Vandoeuvre-lès-Nancy, F-54506, France



CNRS, Institut Élie Cartan de Lorraine, UMR 7502, Vandoeuvre-lès-Nancy, F-54506, France


Olivier.Garet@univ-lorraine.fr


Divide-and-conquer recurrence, Dirichlet series, Tauberian theorem.

[2010]11B37,68W40,60F15.




  The aim of this note is to provide a Master Theorem for some
  discrete divide and conquer recurrences:
  
    X_n=a_n+∑_j=1^m b_j X_n/m_j,

  where the m_i's are integers with m_i≥ 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≥ 0, for example
  such that sup_n≥ 1(|a_n|)<+∞.
  


A simple Master Theorem for Discrete Divide and Conquer Recurrences
    Olivier Garet
    December 30, 2023
===================================================================





§ 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 <cit.> or Goodrich and Tamassia <cit.>.


In the sequel, we consider  sequences (X_n)_n≥ 0 that are defined by
X_0=a_0, then

    X_n   =a_n+∑_j=1^m b_j X_n/m_j,

where the m_i's are integer with m_i≥ 2 and x denotes the only n∈ℤ such that x-n∈ [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 <cit.>. 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 <cit.>, 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 <cit.>. Recent results by Drmota and Szpankowski <cit.>) 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 ∑_j=1^m b_j>1, that the m_i are integers with m_i≥ 2 and such that there exists j,ℓ with log m_j/log m_ℓ∉. 
The rational case, which is not considered here, is also of great interest in Computer Science – see e.g. Roura <cit.> or  Drmota and Szpankowski <cit.>.

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

    ∑_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 

    ∑_n=1^+∞|a_n|/n^s_0<+∞,

we prove that the sequence 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.



§ THE DETERMINISTIC THEOREM


  Let m≥ 1, (b_1,…,b_m) be a family of non-negative numbers and   (m_1,…,m_m) be a family of integers with m_i≥ 2 and such that
  
  
  * there exists j,ℓ with log m_j/log m_ℓ∉;
  
  * ∑_j=1^m b_j>1.
  
  We denote by s_0 the positive root s_0 for the equation

    ∑_j=1^m b_j m_j^-s=1.

  Then, there exists a sequence (ℓ_j)_j≥ 0 of positive numbers such that for every sequence (a_n)_n≥ 0 with
  
    ∑_n=1^+∞|a_n|/n^s_0<+∞,

  then the sequence (X_n)_n≥ 0 defined by X_0=a_0 and the recursion (<ref>) satisfies
  
    lim_n→ +∞X_n/n^s_0=∑_j=0^+∞ℓ_j a_j.



Note that if the sequence (a_j)_j≥ 0 is non-negative and not identically zero, the limit ∑_j=0^+∞ℓ_j a_j is positive, so we have found the correct speed for the growth of (X_n)_n≥ 0. 



We denote by L_n(a) the value of X_n corresponding to  the recursion (<ref>) 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)=∑_j=1^m b_j X(n/m_j).

We can choose C such that |X_k|≤ Ck^s_0 for 0<k≤ n_1=max(n_0,m_1,…,m_m).
Then, it follows by natural induction that  | X_k|≤ C k^s_0 for each k∈^*.
In the sequel, we put X(t)=X(t) to simplify some notation.
Now define

    ϕ(s)   =s∫_n_0+1^+∞X(t)/t^s+1 dt


for s∈ with (s)>s_0. The recursion Equation leads to


    ϕ(s)   =s∫_n_0+1^+∞∑_j=1^m b_j X(t/m_j)/t^s+1 dt=s∑_j=1^m b_jm_j^-s∫_n_0+1/m_j^+∞X(t)/t^s+1 dt
       =(∑_j=1^m b_jm_j^-s)ϕ(s)+s∑_j=1^m b_jm_j^-s∫_n_0+1/m_j^n_0+1X(t)/t^s+1 dt.


Since

    |∑_j=1^m b_jm_j^-s|≤∑_j=1^m |b_jm_j^-s|= ∑_j=1^m b_jm_j^-(s)
      <∑_j=1^m b_jm_j^-s_0=1,

we can write, for (s)>s_0:

    ϕ(s)   =P(s)/1-∑_j=1^m b_jm_j^-s, with P(s)=s∑_j=1^m b_jm_j^-s∫_n_0+1/m_j^n_0+1X(t)/t^s+1 dt




 §.§ Tauberian magic

Now, fix a non-negative integer n_0 and suppose that the sequence a=(a_n)_n≥ 0 is a=I^n_0 with 
    I^n_0_i=_i≤ n_0=1     if i≤ n_0
     0    else.

By natural induction, it is easy to see that (X_n)_n≥ 0 is non-decreasing.

It is also not difficult to see that
1-∑_j=1^m b_jm_j^-s does not vanish for s∈ with (s)≥ s_0 and s s_0.
Proceeding as in Choimet and Queffelec (see <cit.>, section 4), we can note that, for (s)=s_0

    (  ∑_j=1^m b_jm_j^-s)= ∑_j=1^m b_jm_j^-s_0cos(log m_j (s))≤∑_j=1^m b_jm_j^-s_0=1

In fact, the inequality in strict when (s) 0. Overwise, we would have
log m_j (s)∈ 2π for each j, whence  log m_j/log m_k∈ for each j,k, which has been excluded.

It follows that for 
    c=Res_s_0ϕ=P(s_0)/∑_j=1^m b_jm_j^-s_0log(m_j),
 the map s↦ϕ(s)-c/s-s_0 is holomorphic on {s∈;(s)≥ s_0}.

Now note
b(x)=∑_n_0<n≤ x (X_n-X_n-1).
The Abel transformation gives

    ∑_n=n_0+1^+∞X_n-X_n-1/n^s=s∫_n_0+1^+∞b(t)/t^s+1 dt

Since b(t)=X(t)-X_n_0, we have

    ∑_n=n_0+1^+∞X_n-X_n-1/n^s   =s∫_n_0+1^+∞X(t)/t^s+1 dt-X_n_0/(n_0+1)^s
      =ϕ(s)-X_n_0/(n_0+1)^s.


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

 Let (a_n)_n≥ 1 be a sequence
of non-negative real numbers, and a, c be positive real numbers. Suppose that
the Dirichlet series Φ(s)=∑_n=1^+∞a_n n^-s
is defined on the open half-plane (s) > a and that, more precisely, with
A(x) =∑_n≤ x a_n for x≥ 0,
the following properties are verified:


  * A(x)x^-a is bounded on ^+ ;

  * Φ(s)-c/s-a has a holomorphic extension G on the closed half-plane (s)≥ a.

Then we have A(x) ∼c/a  x^a as x→ +∞.




Since (X_n)_n≥ 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→ +∞, we get b(x)∼c/s_0x^s_0,so


    lim_n→ +∞L_n(I^n_0)/n^s_0=∑_j=1^m b_jm_j^-s_0∫_n_0+1/m_j^n_0+1L_t(I^n_0)/t^s_0+1 dt/∑_j=1^m b_jm_j^-s_0log(m_j).


For n_0=0, we have


    ℓ_0=lim_n→ +∞L_n(δ^0)/n^s_0   =lim_n→ +∞L_n(I^0)/n^s_0=1/∑_j=1^m b_jm_j^-s_0log (m_j)∑_j=1^m b_jm_j^-s_0∫_1/m_j^11/t^s_0+1 dt
       =1/∑_j=1^m b_jm_j^-s_0log (m_j)∑_j=1^m b_jm_j^-s_0m_j^s_0-1/s_0


Note that this equality and the related convergence form the result by  Erdős et al <cit.>.



















Let n_0≥ 1. The sequence (δ^n_0_n)_n≥ 0 is defined by

    δ^n_0_n=1   if n=n_0
     0   else.

  Since δ^n_0=I^n_0-I^n_0-1, it follows that
  
    L_n(δ^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 ℓ_n_0.
 
 
 

  

To compute it, take a=δ^n_0 and consider again the associated ϕ.
  From (<ref>), we get ℓ_n_0=lim_s→ s_0^+1/s_0 (s-s_0)ϕ(s).
  On the other side, Equation (<ref>) is still valid, with 
  
    P(s)   =s∑_j=1^m b_jm_j^-s∫_n_0+1/m_j^n_0+1X(t)/t^s+1 dt
       =s∑_j=1^m b_jm_j^-s∫_max(n_0,n_0+1/m_j)^n_0+11/t^s+1 dt,

  also 
    1/s_0(s-s_0)ϕ(s)=-s/s_0s_0-s/1-∑_j=1^m b_j m_j^-s∑_j=1^m b_jm_j^-s∫_max(n_0,n_0+1/m_j)^n_0+11/t^s+1 dt

  and, considering that m_j≥ 2, we get


  
    ℓ_n_0=1/∑_j=1^m b_jm_j^-s_0log (m_j)∑_j=1^m b_jm_j^-s_0∫_n_0^n_0+11/t^s_0+1 dt.


  Thanks to this expression and the previous one, it is clear that
  ℓ_j>0 holds for each j≥ 0.
  

 §.§ The general case


For n,j≥ 0, we note K^j_n=L_n(δ^j).
It is obvious that K^j_n=0 for n<j and K^j_j=1.
It easily follows by natural induction on n that 0≤ K^j_n≤K^0_n/K^0_j.
Now, the affine nature of the recursion gives


    X_n   =∑_j=0^n K^j_n a_j


For each j≥ 0, we have lim_n→ +∞K_n^j/n^s_0=ℓ_j. Also, the K^0_j's are positive, with lim_j→ +∞K_j^0/j^s_0=ℓ_0>0, so there exists M such that 0<1/K_j^0≤M/j^s_0 for each j≥ 1
Then, for each j,n≥ 1, we have

    |K^j_n a_j/n^s_0|   ≤K_n^0/n^s_0|a_j|/K^0_j≤|a_j|/K^0_j≤ M|a_j|/j^s_0


  and by the Weierstrass criterion,
  
    lim_n→ +∞X_n/n^s_0=∑_j=0^+∞ℓ_j a_j.


  

§ APPLICATION TO SEQUENCES OF RANDOM VARIABLES


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



 §.§ Convergence


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≥ 0 defined by X_0=a_0 and the recursion (<ref>) is such that
  X_n/n^s_0 almost surely converges to some random variable,
  given as the sum of the random series:
  
    L=∑_j=0^+∞ℓ_j a_j.

  
    
  (A) ∑_j=1^m b_j/m_j>1 and the (a_n) are integrable random variables with C=sup_n≥ 1|a_n|<+∞.

  (B) ∑_j=1^m b_j/m_j^2>1 and the a_n are random variables following the Cauchy 𝒞(0,1) Law.
  


 
    
  (A) the condition ∑_j=1^m b_j/m_j>1 implies that s_0>1. We have
  (∑_n=1^+∞|a_n|/n^s_0)≤ Cζ(s_0)<+∞, so
  ∑_n=1^+∞|a_n|/n^s_0<+∞ almost surely, which gives the almost sure behavior of X_n/n^s_0.

  (B)  the condition ∑_j=1^m b_j/m_j^2>1 implies that s_0>2. We fix η>1 with s_0-η>1.
  Then (|a_n|>n^η)=O(n^-η) and ∑_n=1^+∞(|a_n|>n^η)<+∞, so by the Borel-Cantelli Lemma,
  for almost every ω, there exists n_0(ω) with  |a_n(ω)|≤ n^η for n≥ n_0(ω), which
  gives the convergence of ∑_n≥ 1|a_n|/n^s_0 and our Master Theorem still applies.
  




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



  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≥ 0 such that a_j is non-atomic.
  Then, the limit L=∑_j=0^+∞ℓ_j a_j is non-atomic, and particularly
  (L=0)=0.


  By independence, the characteristic function of L satisfies
  
    ∀ t∈   |ϕ_L(t)|=∏_j=0^+∞|ϕ_ℓ_j a_j(t)|≤ |ϕ_ℓ_j_0 a_j_0(t)|.


  Therefore

  
    lim_T→ +∞1/2T∫_-T^T |ϕ_L(t)|^2 dt≤lim_T→ +∞ 1/2T∫_-T^T |ϕ_ℓ_0a_j_0(t)|^2 dt=0,

  which implies that L is non-atomic (see e.g. Durrett <cit.>, section 3.3).
  


 §.§ Exponential moments



  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≥ 0 is defined by X_0=a_0 and the recursion (<ref>).
  
  
  * If there exists a distribution μ with exponential moments such that |a_n| is stochastically dominated by μ^*n for each n≥ 0, then |X_n| has exponential moments for each n.
  
  * If s_0>1 (or equivalently ∑_j=1^m b_j/m_j>1) and there exists a distribution μ with exponential moments such that |a_n| is stochastically dominated by μ for each n≥ 0, then  X_n/n^s_0→ L a.s. where |L| has exponential moments.
   
  * If s_0>2 (or equivalently ∑_j=1^m b_j/m_j^2>1) and there exists a distribution μ with exponential moments such that |a_n| is stochastically dominated by μ^*n for each n≥ 0, then X_n/n^s_0→ L a.s. where |L| has exponential moments.
  



 We begin with an easy lemma: 

Let X be a random variable with  (e^α X)<+∞ and Y a random variable
following the exponential law  ℰ(α) 
Then, for  a=1/αlog (e^α X_1), we have the stochastic domination
X≺ Y+a.


We just have to prove that for t∈, (X≥ t)≤(Y+a≥ t),
or equivalently (X≥ t)≤(Y≥ t-a).
For t≤ a, we have (X≥ t)≤ 1=(Y≥ t-a).
For t≥ a, the Markov inequality gives

    (X≥ t)≤ e^α X/e^α t=e^α a/e^α t=exp(-α (t-a))=P(Y≥ t-a).

This completes the proof.

Now, we have a and α such that for each n≥ 1


    |a_n|≺μ^* n≺ (δ^a*ℰ(α))^*n=δ^na*Γ(n,θ).


Let (Z_n)_n≥ 0 be a sequence of independent  variables with Z_n∼Γ(n,θ), where Γ(a,γ) is the Law with the density

    x↦γ^a/Γ(a)x^a-1e^-γ x _]0,+∞[(x).


|X_n|/n^s_0 is stochastically dominated by


    M∑_j=0^n ja+Z_j/(j+1)^s_0,

so for t<1/α, we have



    (e^t|X_n|/n^s_0)   ≤exp(Ma ∑_j=1^n+1 j^-s_0)∏_j=0^nexp(tZ_j/(j+1)^s_0)
       ≤exp(Ma ∑_j=1^n+1 j^-s_0)∏_j=0^n (1-α t/(j+1)^s_0)^-j

When j is large enough, (1-α t/(j+1)^s_0)^-j≤exp(α t/j^s_0-1), which gives the existence of an exponential moment  for s_0>2.

The proof in the case |a_n|≺μ and s_0>1 is similar.

  
 
As an example of domination by μ^*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 μ=𝒢(p).
  
References
plain


