Asymptotic normality of recursive algorithms via martingale difference arrays

Abstract

We propose martingale central limit theorems as an tool to prove asymptotic normality of the costs of certain recursive algorithms which are subjected to random input data. The recursive algorithms that we have in mind are such that if input data of size N produce random costs L N, then L N = D L n + L N-n +R N for N ≥ n 0 ≥2, where n follows a certain distribution P N on the integers {0, … ,N} and L k = D L k for k≥0. L n, L N-n and R N are independent, conditional on n, and R N are random variables, which may also depend on n, corresponding to the cost of splitting the input data of size N (into subsets of size n and N-n) and combining the results of the recursive calls to yield the overall result. We construct a martingale difference array with rows converging to Z N:= [L N- EL N ] / [√ Var L N ]. Under certain compatibility assumptions on the sequence (P N) N≥0 we show that a pair of sufficient conditions (of Lyapunov type) for Z N → D N(0,1) can be restated as a pair of conditions regarding asymptotic relations between three sequences. All these sequences satisfy the same type of linear equation, that is also the defining equation for the sequence (EL N) N≥0 and thus very likely a well studied object. In the case that the P N are binomial distributions with the same parameter p, and for deterministic R N, we demonstrate the power of this approach. We derive very general sufficient conditions in terms of the sequence (R N) N≥0 (and for the scale R N =N α a characterization of those α) leading to asymptotic normality of Z N.