TY  - THES
A1  - Ischebeck, Ferdinand Jasper
T1  - Central limit theorems for fringe trees in patricia tries
N2  - 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.
KW  - patricia trie
KW  - fringe tree
KW  - central limit theorem
KW  - independence number
KW  - random tree
Y1  - 2023
UR  - http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/73731
UR  - https://nbn-resolving.org/urn:nbn:de:hebis:30:3-737310
CY  - Frankfurt am Main
ER  -