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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2001, 4 (2), pp.363-398
Liste complète des métadonnées

Littérature citée [29 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00958968
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : jeudi 13 mars 2014 - 16:53:54
Dernière modification le : mercredi 29 novembre 2017 - 10:26:22
Document(s) archivé(s) le : vendredi 13 juin 2014 - 12:06:04

Fichier

dm040221.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

81

Téléchargements de fichiers

194