Displaying similar documents to “Digital search trees and chaos game representation*”

Large deviations for transient random walks in random environment on a Galton–Watson tree

Elie Aidékon (2010)

Annales de l'I.H.P. Probabilités et statistiques

Similarity:

Consider a random walk in random environment on a supercritical Galton–Watson tree, and let be the hitting time of generation . The paper presents a large deviation principle for /, both in quenched and annealed cases. Then we investigate the subexponential situation, revealing a polynomial regime similar to the one encountered in one dimension. The paper heavily relies on estimates on the tail distribution of the first regeneration time.

Branching random walks on binary search trees: convergence of the occupation measure

Eric Fekete (2010)

ESAIM: Probability and Statistics

Similarity:

We consider branching random walks with binary search trees as underlying trees. We show that the occupation measure of the branching random walk, up to some scaling factors, converges weakly to a deterministic measure. The limit depends on the stable law whose domain of attraction contains the law of the increments. The existence of such stable law is our fundamental hypothesis. As a consequence, using a one-to-one correspondence between binary trees and plane trees, we give a description...