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
Branching Markov chains: Stability and Applications
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics. (Mathematics)
INRIA, Paris.
(English)Manuscript (preprint) (Other (popular science, discussion, etc.))
Abstract [en]

We address the stability of certain tree algorithms used to solve the problem of communication between multiple users through a unique shared channel. We propose a general model based on branching Markov chains which allows us to write an intuitive stability condition. When the algorithm is stable, we show that there exist an asymptotic throughput, which is related to the asymptotic size of the underlying tree.

National Category
Discrete Mathematics
Research subject
Mathematics
Identifiers
URN: urn:nbn:se:uu:diva-112238OAI: oai:DiVA.org:uu-112238DiVA: diva2:285452
Available from: 2010-01-12 Created: 2010-01-12 Last updated: 2010-12-16
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

Authority records BETA

Holmgren, Cecilia

Search in DiVA

By author/editor
Holmgren, Cecilia
By organisation
Department of Mathematics
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 509 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