A probabilistic analysis of some tree algorithms

Random increasing k-trees represent an interesting, useful class of strongly dependent graphs for which analytic-combinatorial tools can be successfully applied. We study in this paper a notion called connectivity-profile and derive asymptotic estimates for it; some interesting consequences will also be given.

This paper deals with the size of the spanning tree of p randomly chosen nodes in a binary search tree. It is shown via generating functions methods, that for fixed p, the (normalized) spanning tree size converges in law to the Normal distribution. The special case p=2 reproves the recent result (obtained by the contraction method by Mahmoud and Neininger [Ann. Appl. Probab. 13 (2003) 253-276]), that the distribution of distances in random binary search trees has a Gaussian l...

In this paper, we investigate a parking process on a uniform random rooted plane tree with $n$ vertices. Every vertex of the tree has a parking space for a single car. Cars arrive at independent uniformly random vertices of the tree. If the parking space at a vertex is unoccupied when a car arrives there, it parks. If not, the car drives towards the root and parks in the first empty space it encounters (if there is one). We are interested in asymptotics of the probability of ...

We study the situations when the solution to a weighted stochastic recursion has a power law tail. To this end, we develop two complementary approaches, the first one extends Goldie's (1991) implicit renewal theorem to cover recursions on trees; and the second one is based on a direct sample path large deviations analysis of weighted recursive random sums. We believe that these methods may be of independent interest in the analysis of more general weighted branching processes...

There are several good reasons you might want to read about uniform spanning trees, one being that spanning trees are useful combinatorial objects. Not only are they fundamental in algebraic graph theory and combinatorial geometry, but they predate both of these subjects, having been used by Kirchoff in the study of resistor networks. This article addresses the question about spanning trees most natural to anyone in probability theory, namely what does a typical spanning tree...

Bounded infinite graphs are defined on the basis of natural physical requirements. When specialized to trees this definition leads to a natural conjecture that the average connectivity dimension of bounded trees cannot exceed two. We verify that this bound is saturated by a class of random trees, in which case we derive also explicit expressions for the growth probabilities.

We extend the results of B. Bollobas, O. Riordan, J. Spencer, G. Tusnady, and Mori. We consider a model of random tree growth, where at each time unit a new node is added and attached to an already existing node chosen at random. The probability with which a node with degree $k$ is chosen is proportional to $w(k)$, where $w$ is a fixed weight function. We prove that if $w$ fulfills some asymptotic requirements then the degree sequence converges in probability, we give the lim...

The present paper gives a statistical adventure towards exploring the average case complexity behavior of computer algorithms. Rather than following the traditional count based analytical (pen and paper) approach, we instead talk in terms of the weight based analysis that permits mixing of distinct operations into a conceptual bound called the statistical bound and its empirical estimate, the so called "empirical O". Based on careful analysis of the results obtained, we have ...

We consider a multivariate distributional recursion of sum-type as arising in the probabilistic analysis of algorithms and random trees. We prove an upper tail bound for the solution using Chernoff's bounding technique by estimating the Laplace transform. The problem is traced back to the corresponding problem for binary search trees by stochastic domination. The result obtained is applied to the internal path length and Wiener index of random b-ary recursive trees with weigh...

In this thesis the properties of two kinds of non-uniform random recursive trees are studied. In the first model weights are assigned to each node, thus altering the attachment probabilities. We will call these trees weighted recursive trees. In the second model a different distribution rather than the uniform one is chosen on the symmetric group, namely a riffle shuffle distribution. These trees will be called biased recursive trees. For both of these models the number of br...