Asymptotic normality of recursive algorithms via martingale difference arrays
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+...
Main Author: | Werner Schachinger |
---|---|
Format: | Article |
Language: | English |
Published: |
Discrete Mathematics & Theoretical Computer Science
2001-01-01
|
Series: | Discrete Mathematics & Theoretical Computer Science |
Subjects: | |
Online Access: | https://dmtcs.episciences.org/281/pdf |
Similar Items
-
Recursions and divisibility properties for combinatorial Macdonald polynomials
by: Nicholas A. Loehr, et al.
Published: (2011-02-01) -
Exponential bounds and tails for additive random recursive sequences
by: Ludger Rüschendorf, et al.
Published: (2007-01-01) -
Asymptotic results for silent elimination
by: Guy Louchard, et al.
Published: (2010-01-01) -
Asymptotic enumeration on self-similar graphs with two boundary vertices
by: Elmar Teufl, et al.
Published: (2009-01-01) -
Random graphs with bounded maximum degree: asymptotic structure and a logical limit law
by: Vera Koponen
Published: (2012-11-01)