In this paper we prove a functional limit theorem for the weighted profile of a b-ary tree. For the proof we use classical martingales connected to branching Markov processes and a generalized version of the profile-polynomial martingale. By embedding, choosing weights and a branch factor in a right way, we finally rediscover the profiles of some well-known discrete time trees.
Publié le : 2010-06-15
Classification:
Functional limit theorem,
b-ary trees,
profile of trees,
random trees,
analysis of algorithms,
martingales,
60F17,
68Q25,
68P10
@article{1276867302,
author = {Schopp, Eva-Maria},
title = {A functional limit theorem for the profile of b-ary trees},
journal = {Ann. Appl. Probab.},
volume = {20},
number = {1},
year = {2010},
pages = { 907-950},
language = {en},
url = {http://dml.mathdoc.fr/item/1276867302}
}
Schopp, Eva-Maria. A functional limit theorem for the profile of b-ary trees. Ann. Appl. Probab., Tome 20 (2010) no. 1, pp. 907-950. http://gdmltest.u-ga.fr/item/1276867302/