uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A weakly 1-stable distribution for the number of random records and cuttings in split trees
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Applied Mathematics. (Mathematics)
2011 (English)In: Advances in Applied Probability, ISSN 0001-8678, E-ISSN 1475-6064, Vol. 43, no 1, 151-177 p.Article in journal (Refereed) Published
Abstract [en]

In this paper we study the number of random records in an arbitrary split tree (or, equivalently, the number of random cuttings required to eliminate the tree). We show that a classical limit theorem for the convergence of sums of triangular arrays to infinitely divisible distributions can be used to determine the distribution of this number. After normalization the distributions are shown to be asymptotically weakly 1-stable. This work is a generalization of our earlier results for the random binary search tree in Holmgren (2010), which is one specific case of split trees. Other important examples of split trees include m-ary search trees, quad trees, medians of (2k + 1)-trees, simplex trees, tries, and digital search trees.

Place, publisher, year, edition, pages
2011. Vol. 43, no 1, 151-177 p.
Keyword [en]
Random tree, split tree, cut, record, stable distribution, infinitely divisible distribution
National Category
Mathematics
Research subject
Mathematics
Identifiers
URN: urn:nbn:se:uu:diva-112235DOI: 10.1239/aap/1300198517ISI: 000289223300008OAI: oai:DiVA.org:uu-112235DiVA: diva2:285450
Available from: 2010-01-12 Created: 2010-01-12 Last updated: 2017-12-12Bibliographically approved
In thesis
1. Split Trees, Cuttings and Explosions
Open this publication in new window or tab >>Split Trees, Cuttings and Explosions
2010 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

This thesis is based on four papers investigating properties of split trees and also introducing new methods for studying such trees. Split trees comprise a large class of random trees of logarithmic height and include e.g., binary search trees, m-ary search trees, quadtrees, median of (2k+1)-trees, simplex trees, tries and digital search trees. Split trees are constructed recursively, using “split vectors”, to distribute n “balls” to the vertices/nodes. The vertices of a split tree may contain different numbers of balls; in computer science applications these balls often represent “key numbers”.

In the first paper, it was tested whether a recently described method for determining the asymptotic distribution of the number of records (or cuts) in a deterministic complete binary tree could be extended to binary search trees. This method used a classical triangular array theorem to study the convergence of sums of triangular arrays to infinitely divisible distributions. It was shown that with modifications, the same approach could be used to determine the asymptotic distribution of the number of records (or cuts) in binary search trees, i.e., in a well-characterized type of random split trees.

In the second paper, renewal theory was introduced as a novel approach for studying split trees. It was shown that this theory is highly useful for investigating these types of trees. It was shown that the expected number of vertices (a random number) divided by the number of balls, n, converges to a constant as n tends to infinity. Furthermore, it was demonstrated that the number of vertices is concentrated around its mean value. New results were also presented regarding depths of balls and vertices in split trees.

In the third paper, it was tested whether the methods of proof to determine the asymptotic distribution of the number of records (or cuts) used in the binary search tree, could be extended to split trees in general. Using renewal theory it was demonstrated for the overall class of random split trees that the normalized number of records (or cuts) has asymptotically a weakly 1-stable distribution.

In the fourth paper, branching Markov chains were introduced to investigate split trees with immigration, i.e., CTM protocols and their generalizations. It was shown that there is a natural relationship between the Markov chain and a multi-type (Galton-Watson) process that is well adapted to study stability in the corresponding tree. A stability condition was presented to de­scribe a phase transition deciding when the process is stable or unstable (i.e., the tree explodes). Further, the use of renewal theory also proved to be useful for studying split trees with immi­gration. Using this method it was demonstrated that when the tree is stable (i.e., finite), there is the same type of expression for the number of vertices as for normal split trees.

Place, publisher, year, edition, pages
Uppsala: Department of Mathematics, 2010. 52 p.
Series
Uppsala Dissertations in Mathematics, ISSN 1401-2049 ; 67
Keyword
Random Graphs, Random Trees, Split Trees, Renewal Theory, Binary Search Trees, Cuttings, Records, Tree Algorithms, Markov Chains, Galton-Watson Processes
National Category
Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:uu:diva-112239 (URN)978-91-506-2124-2 (ISBN)
Public defence
2010-02-19, Polhemssalen, Ångströmslaboratoriet, Lägerhyddsv. 1, Uppsala, 13:15 (English)
Opponent
Supervisors
Available from: 2010-01-29 Created: 2010-01-12 Last updated: 2010-01-29Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Authority records BETA

Holmgren, Cecilia

Search in DiVA

By author/editor
Holmgren, Cecilia
By organisation
Analysis and Applied Mathematics
In the same journal
Advances in Applied Probability
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 490 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf