Extremal Weighted Path Lengths in Random Binary Search Trees
Lasmar, Rafik Aguech, Hosam Mahmoud, Nabil . 2007
We consider weighted path lengths to the extremal leaves in a random binary search tree. When linearly scaled, the weighted path length to the minimal label has Dickman's infinitely divisible distribution as a limit. By contrast, the weighted path length to the maximal label needs to be centered and scaled to converge to a standard normal variate in distribution. The exercise shows that path lengths associated with different ranks exhibit different behaviors depending on the rank. However, the majority of the ranks have a weighted path length with average behavior similar to that of the weighted path to the maximal node.
In this paper, we consider a two-dimension symmetric random walk with reset. We give, in the first part, some results about the distribution of every component. In the second part, we give some…
In this paper, we give some results about a multi-drawing urn with random
addition matrix. The process that we study is described as: at stage n ≥ 1,
we pick out at random…
I
In this article, we consider several models of random walks in one or several
dimensions, additionally allowing, at any unit of time, a reset (or “catastrophe”) of
the walk…