Oscillations in the Height of the Yule Tree and Application to the Binary Search Tree

摘要

For a particular case of a branching random walk with lattice support, namely the Yule branching random walk, we prove that the distribution of the centred maximum oscillates around a distribution corresponding to a critical travelling wave in the following sense: there exist continuous functions t bar right arrow a(t) at and x bar right arrow phi(x) such that: