Central limit theorems for fringe trees in patricia tries
- We give theorems about asymptotic normality of general additive functionals on patricia tries, derived from results on tries. These theorems are applied to show asymptotic normality of the distribution of random fringe trees in patricia tries. Formulas for asymptotic mean and variance are given. The proportion of fringe trees with ๐ keys is asymptotically, ignoring oscillations, given by (1โ๐(๐))/(๐ป +๐ฝ)๐(๐โ1) with the source entropy ๐ป, an entropy-like constant ๐ฝ, that is ๐ป in the binary case, and an exponentially decreasing function ๐(๐). Another application gives asymptotic normality of the independence number and the number of ๐-protected nodes.
Download full text files
Additional Services
| Author: | Ferdinand Jasper Ischebeck |
|---|---|
| URN: | urn:nbn:de:hebis:30:3-737310 |
| Place of publication: | Frankfurt am Main |
| Document Type: | Master's Thesis |
| Language: | English |
| Date of Publication (online): | 2023/05/09 |
| Year of first Publication: | 2022 |
| Publishing Institution: | Universitรคtsbibliothek Johann Christian Senckenberg |
| Granting Institution: | Johann Wolfgang Goethe-Universitรคt |
| Release Date: | 2023/05/09 |
| Tag: | central limit theorem; fringe tree; independence number; patricia trie; random tree |
| Page Number: | 38 |
| HeBIS-PPN: | 507635329 |
| Institutes: | Informatik und Mathematik |
| Dewey Decimal Classification: | 5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik |
| Sammlungen: | Universitรคtspublikationen |
| Licence (German): |  Creative Commons - CC BY - Namensnennung 4.0 International |
