An analytic approach to the asymptotic variance of trie statistics and related structures

Michael Fuchs, Hsien-Kuei Hwang, Vytas Zacharovas

We develop analytic tools for the asymptotics of general trie statistics, which are particularly advantageous for clarifying the asymptotic variance. Many concrete examples are dis…