Skip to Main content Skip to Navigation
Journal articles

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, \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.
Document type :
Journal articles
Complete list of metadata

Cited literature [29 references]  Display  Hide  Download

https://hal.inria.fr/hal-00958968
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Thursday, March 13, 2014 - 4:53:54 PM
Last modification on : Wednesday, November 29, 2017 - 10:26:22 AM
Long-term archiving on: : Friday, June 13, 2014 - 12:06:04 PM

File

dm040221.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00958968, version 1

Collections

Citation

Werner Schachinger. Asymptotic normality of recursive algorithms via martingale difference arrays. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2001, 4 (2), pp.363-398. ⟨hal-00958968⟩

Share

Metrics

Record views

181

Files downloads

855