Paths in m -ary interval trees

We introduce the m -ary interval tree, a random structure that underlies interval division and simultaneous parking problems. Certain significant paths in the m -ary interval trees are considered. When appropriately normed, the length of these paths are shown to converge in distribution to a normal...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2004-10, Vol.287 (1), p.45-53
Main Authors: Javanian, Mehri, Mahmoud, Hosam, Vahidi-Asl, Mohammad
Format: Article
Language:English
Subjects:
Combinatorics
Combinatorics. Ordered structures
Exact sciences and technology
Graph theory
Limit distribution
Mathematical analysis
Mathematics
Ordinary differential equations
Probability and statistics
Probability theory and stochastic processes
Random tree
Sciences and techniques of general use
Stochastic analysis
Stochastic recurrence
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We introduce the m -ary interval tree, a random structure that underlies interval division and simultaneous parking problems. Certain significant paths in the m -ary interval trees are considered. When appropriately normed, the length of these paths are shown to converge in distribution to a normal random variable. The work extends the study of incomplete binary interval trees in Itoh and Mahmoud (J. Appl. Probab. 40 (2003) 645). However, the extension is nontrivial, in the sense that the characterization in the m -ary case involves high-order differential equations, which is to be contrasted with the first-order differential equation that underlies the binary case, and in the sense that the path lengths exhibit oscillatory behavior for m ⩾ 4 , that does not exist in binary and ternary cases.
ISSN:0012-365X
1872-681X
DOI:10.1016/j.disc.2004.06.005