Godland, Philipp: Markov renewal theory in the analysis of random strings and iterated function systems. 2020
Inhalt
- Renewal theory in the analysis of random digital trees
- Introduction
- Preliminaries
- Tries and trie-like structures
- Input models
- Parameters
- Type of main results
- Markov renewal theory and notation
- Central Markov-modulated sequence
- Distributional identity
- Lattice
- Null-homology
- Asymptotic analysis of depth and imbalance factor
- Average-case analysis of further characteristic parameters
- Appendix
- Convergence rates of iterated function systems of Markov-modulated Lipschitz maps by regenerative methods
- Introduction
- Preliminaries
- Measurability and remarks
- Dual chain and distributional identity
- Elton's theorem
- Markov renewal theory and conditions
- Convergence rates in Elton's theorem
- Main results
- Proof of Theorem 7.1 by cyclic decomposition
- Convergence rate under polynomial-type moment conditions
- Convergence rate under geometric-type moment conditions
- Appendix
- References
- Acronyms
- List of symbols