Dynamic tree algorithms

Mathematics – Probability

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Published in at http://dx.doi.org/10.1214/09-AAP617 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Inst

Scientific paper

10.1214/09-AAP617

In this paper, a general tree algorithm processing a random flow of arrivals is analyzed. Capetanakis--Tsybakov--Mikhailov's protocol in the context of communication networks with random access is an example of such an algorithm. In computer science, this corresponds to a trie structure with a dynamic input. Mathematically, it is related to a stopped branching process with exogeneous arrivals (immigration). Under quite general assumptions on the distribution of the number of arrivals and on the branching procedure, it is shown that there exists a positive constant $\lambda_c$ so that if the arrival rate is smaller than $\lambda_c$, then the algorithm is stable under the flow of requests, that is, that the total size of an associated tree is integrable. At the same time, a gap in the earlier proofs of stability in the literature is fixed. When the arrivals are Poisson, an explicit characterization of $\lambda_c$ is given. Under the stability condition, the asymptotic behavior of the average size of a tree starting with a large number of individuals is analyzed. The results are obtained with the help of a probabilistic rewriting of the functional equations describing the dynamics of the system. The proofs use extensively this stochastic background throughout the paper. In this analysis, two basic limit theorems play a key role: the renewal theorem and the convergence to equilibrium of an auto-regressive process with a moving average.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Dynamic tree algorithms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Dynamic tree algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamic tree algorithms will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-506881

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.