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, \ldots ,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 - E L_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 → ^DN(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 (E L_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.
Discrete Mathematics & Theoretical Computer Science
