Ludger Rüschendorf: Asymptotics of First Moments, the Clue for the Asymptotics of the Distribution of Recursive Sequences

This is a joint work with Ralph Neininger.

For a general class of recursive sequences of the divide and conquer type the asymptotics of the distribution can be obtained directly as a consequence of the asymptotics of first moment(s). The reason for this transfer is the stabilization of the normalized recursive sequence. Also the conditions on the moments allow to establish convergence of the algorithm via a contraction argument with respect to the Zolotarev metric. As consequence of this result we also obtain several related convergence properties as local convergence results. Applications are given to the asymptotics of several parameters in search trees and in digital structures.

Back to the Index


Please send comments and corrections to Thomas Klausner.