\documentclass[12pt]{article}
\usepackage{e-jc}

\usepackage{amsmath,amssymb,amsthm,latexsym,color,times,mathrsfs}

\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}
\usepackage{tikz}
\usetikzlibrary{shapes}

\def\dd#1{{\,\mathrm{d}}#1}
\def\ve{\varepsilon}
\def\pf{\noindent {\em Proof.}\ }
\def\qed{{\quad\rule{1mm}{3mm}\,}}
\def\tr#1{{\left\lfloor{#1}\right\rfloor}}
\def\JS{\mathscr{J\!\!S}}
\newcommand{\E}{{\mathbb{E}}}
\newcommand{\V}{{\mathbb{V}}}
\newcommand{\Prob}{{\mathbb{P}}}
\newtheorem{thm}{Theorem}
\newtheorem{lmm}{Lemma}
\newtheorem{cor}{Corollary}
\newtheorem{pro}{Proposition}
\newtheorem{Def}[thm]{Definition}
\theoremstyle{remark}\newtheorem{Rem}{Remark}

\title{\bf A General Central Limit Theorem for Shape Parameters of $m$-ary Tries and PATRICIA Tries}
\author{Michael Fuchs and Chung-Kuei Lee\thanks{Both authors acknowledge partial support by the NSF project under grant NSC-102-2115-M-009-002.} \\
\small Department of Applied Mathematics\\[-0.8ex]
\small National Chiao Tung University\\[-0.8ex]
\small Hsinchu, 300, Taiwan}

\date{\dateline{}{}\\
\small Mathematics Subject Classifications: 05C05, 60F05, 68R05, 68W40}

\begin{document}
\maketitle
\begin{abstract}
Tries and PATRICIA tries are fundamental data structures in computer science with numerous applications. In a recent paper, a general framework for obtaining the mean and variance of additive shape parameters of tries and PATRICIA tries under the Bernoulli model was proposed. In this note, we show that a slight modification of this framework yields a central limit theorem for shape parameters, too. This central limit theorem contains many of the previous central limit theorems from the literature and it can be used to prove recent conjectures and derive new results. As an example, we will consider a refinement of the size of tries and PATRICIA tries, namely, the number of nodes of fixed outdegree and obtain (univariate and bivariate) central limit theorems. Moreover, trivariate central limit theorems for size, internal path length and internal Wiener index of tries and PATRICIA tries are derived as well.

\bigskip\noindent \textbf{Keywords:} Tries, nodes of fixed out-degree, total path length, Wiener index, moments, multivariate central limit theorems
\end{abstract}

\section{Introduction and Results}\label{intro}
{\it Tries} (from the word data re{\it tri}val) have, since their introduction by de la Briandais \cite{Br} in 1959, found many applications, e.g., in searching, sorting, dynamic hashing, coding, polynomial factorization, regular languages, contention tree algorithms, automatically correcting words in texts, retrieving IP addresses and satellite data, internet routing, and molecular biology; see Park et al. \cite{PaHwNiSz} for details and many references. Also, many variants of tries have been proposed, where one of the simplest and most popular variant are {\it PATRICIA tries} which were invented by D. R. Morrison\footnote{According to Wikipedia, PATRICIA tries were independently invented by G. Gwehenberger \cite{Gw}.} \cite{Mo} in 1968. (PATRICIA is an acronym which stands for {\it P}ractical {\it A}lgorithm {\it T}o {\it R}etrieve {\it I}nformation {\it C}oded {\it I}n {\it A}lphanumeric.)

Due to their importance, tries and PATRICIA tries have been extensively studied. The purpose of this paper is to contribute to their analysis. We start by giving a precise definition. Both structures are built from a set of $n$ infinite strings over a finite alphabet $S$ of cardinality $m\geq 2$. For the sake of simplicity, we let $S=\{1,\ldots, m\}$. From the $n$ strings, we will build an $m$-ary tree consisting of internal and external ($=$leaf) nodes, where the strings are stored in the external nodes. For the trie this is done recursively as follows: if $n=1$, then the only string is stored in the root; otherwise an internal node is created and the $n$ strings are divided into $m$ sets according to their first letter. Then, the first letters of every string are removed and the $m$ subtrees of the root are built recursively from the $m$ sets. PATRICIA tries are built according to the same rules with the only difference that the creation of internal nodes with outdegree one is avoided. Thus, PATRICIA tries can be seen as a space-optimized version of tries.

Next, we will explain the random model which will be used throughout this paper: letters will be assumed to be generated independently with the probability of a letter being $i$ equal to $p_i$ with $0<p_i<1$ and $\sum_{i}p_i=1$. This is the most simple, but also most unrealistic random model for practical applications. More realistic random models have been proposed by Vall\'{e}e \cite{Va} and analyzed by Bourdon \cite{Bo} and Vall\'{e}e et al. \cite{ClFlVa}. However, deriving stochastic properties beyond the mean of these models still remains challenging. Therefore, we restrict ourself to the above simple model in the current paper.

Under the above random model, shape parameters of tries and PATRICIA tries become random variables; see \cite{PaHwNiSz} for many examples of shape parameters. Stochastic properties of such shape parameters have been extensively studied, where a lot of attention was paid to additive shape parameters. For a random trie of size $n$, an additive shape parameter $X_n$ is defined as follows: $X_n$ is a sequence of random variables satisfying the distributional recurrence
\begin{equation}\label{asp-dis-rec}
X_n\stackrel{d}{=}\sum_{i=1}^{m}X_{I_n^{(i)}}^{(i)}+T_n,\qquad (n\geq n_0),
\end{equation}
where $n_0>0$ is an integers, $X_n,X_n^{(1)},\ldots,X_n^{(m)},(I_n^{(1)},\ldots,I_n^{(m)}),T_n$ are independent, $X_n^{(i)}$ has the same distribution as $X_n$ and
\[
\pi_{j_1,\ldots,j_m}=P(I_n^{(1)}=j_1,\ldots,I_n^{(m)}=j_m)=\binom{n}{j_1,\cdots,j_m}p_1^{j_1}\cdots p_m^{j_m}
\]
with $j_1,\ldots,j_m\geq 0$ and $j_1+\cdots+j_m=n$. This recurrence can be explained as follows: the shape parameter $X_n$ is computed as the sum of shape parameters for all subtrees of the root plus some additional cost which is given by $T_n$. ($T_n$ is called {\it toll-function} and might be random.)

The analysis of moments of (\ref{asp-dis-rec}) is by now relatively standard and a lot of sophisticated tools have been introduced, most of them belonging to the field of Analytic Combinatorics; see Flajolet and Sedgewick \cite{FlSe}. We recall here the three most important analytic tools which have been proposed.
\begin{itemize}
\item Mellin Transform: suggested by N. G. de Bruijn to D. Knuth; see Knuth \cite{Kn} and the excellent survey article by Flajolet et al. \cite{FlGoDu}.
\item Rice Method: suggested by S. O. Rice to D. Knuth; see \cite{Kn} and Flajolet and Sedgewick \cite{FlSe2}.
\item Analytic Depoissonization: proposed by Jacquet and R\'{e}gnier \cite{JaRe} and systematically developed by
Jacquet and Szpankowski \cite{JaSz}.
\end{itemize}
In Fuchs et al. \cite{FuHwZa}, the authors used Mellin transform together with the theory of JS-admissibility which was introduced in Hwang et al. \cite{HwFuZa} (and which is largely based on analytic Depoissonization) and the idea of ``corrected poissonized variance" which is also from \cite{HwFuZa} to propose a general framework for deriving asymptotic expansions of mean and variance of additive shape parameters in random tries and random PATRICIA tries. In this article, which is intended to be a supplement to \cite{FuHwZa}, we will show that the same framework with only minor modifications gives a general central limit theorem for a large class of additive shape parameters, which in particular covers most of the previous central limit theorems for shape parameters in random tries and random Patricia tries. We will only state in details the result for $m$-ary random tries, a similar result for $m$-ary PATRICIA tries is straightforward.

Now, in order to state our result, we first recall the following definition; see \cite{FuHwZa,HwFuZa,JaSz}.
\begin{Def}
Let $\tilde{f}(z)$ be an entire function and $\alpha,\gamma\in{\mathbb R}$. Then, we say that $\tilde{f}(z)$ is JS-admissible and write $\tilde{f}(z)\in\JS$ (or more precisely, $\tilde{f}(z)\in\JS_{\alpha,\gamma})$ if for $0<\phi<\pi/2$ and all $\vert z\vert\geq 1$ the following two conditions hold.
\begin{itemize}
\item[{\bf (I)}] Uniformly for $\vert\arg(z)\vert\leq\phi$,
\[
\tilde{f}(z)={\mathcal O}\left(\vert z\vert^{\alpha}(\log_{+}\vert
z\vert)^{\gamma}\right),
\]
where $\log_{+}x:=\log(1+x)$.
\item[{\bf (O)}] Uniformly for $\phi\leq\vert\arg(z)\vert\leq\pi$,
\[
f(z):=e^{z}\tilde{f}(z)={\mathcal O}\left(e^{(1-\epsilon)\vert
z\vert}\right),
\]
where $\epsilon>0$.
\end{itemize}
\end{Def}
Moreover, we need the following notations
\[
\tilde{g}_1(z)=e^{-z}\sum_{n\geq 2}{\mathbb E}(T_n)\frac{z^n}{n!},\quad
\tilde{g}_2(z)=e^{-z}\sum_{n\geq 2}{\mathbb E}(T_n^2)\frac{z^n}{n!}
\]
and
\[
\tilde{V}_T(z)=\tilde{g}_2(z)-\tilde{g}_1(z)-z\tilde{g}'_1(z)^2.
\]
(The latter is the corrected Poissonized variance of $T_n$; see \cite{FuHwZa}.) Then, the main result of the paper is the following general central limit theorem.
\begin{thm}\label{limit-law} Assume that $\tilde{g}_1(z)\in\JS_{\alpha_1,\gamma_1}$ with $0\leq\alpha_1<1/2$, $\tilde{g}_2(z)\in\JS$ and $\tilde{V}_T(z)\in\JS_{\alpha_2,\gamma_2}$ with $\alpha_2<1$. Moreover, assume that $\|T_n\|_{s}=o(\sqrt{n}), 2<s\leq 3$ and ${\rm Var}(X_n)\geq cn$ for all $n$ large enough with $c>0$. Then, as $n\rightarrow\infty$,
\[
\frac{X_n-{\mathbb E}(X_n)}{\sqrt{{\rm Var}(X_n)}}\stackrel{d}{\longrightarrow}N(0,1).
\]
\end{thm}
\begin{Rem}
In Section \ref{sec-ll}, we will discuss how to check the above assumption of at least linear growth for the variance.
\end{Rem}

As an application, we will consider the number of internal nodes of outdegree $k$ in a random trie of size $n$ which will be denoted by $N_n^{(k)}$. (This is a refinement of the size of tries and PATRICIA tries; see Corollary \ref{cor-size} below.) We will give a multivariate study of these parameters by considering
\[
Z_n=\sum_{k=1}^{m}a_kN_n^{(k)},
\]
where $a_1,\ldots, a_m$ are arbitrary real number with $a_i\ne (i-1)a_2$ for some $i$ (this is to make sure that $Z_n$ is not deterministic; see Lemma \ref{pos-var} and the remark succeeding it). Note that a similar multivariate framework was considered in Hubalek et al. \cite{HuHwLeMaPr} for shape parameters in digital search trees. However, our analysis will take into account many tools developed after \cite{HuHwLeMaPr}. (In fact, one could give a similar framework as in our paper also for digital search trees.) We have the following result.

\begin{thm}\label{main-result-1} We have, as $n\rightarrow\infty$,
\[
{\mathbb E}(Z_n)\sim nP(\log_{1/a}n),\qquad {\rm Var}(Z_n)\sim nQ(\log_{1/a}n),
\]
where $a>0$ is a suitable constant and $P(z), Q(z)$ are infinitely differentiable, $1$-periodic functions (possibly constant). Moreover, ${\rm Var}(Z_n)>0$ for all $n$ large enough and
\[
\frac{Z_n-{\mathbb E}(Z_n)}{\sqrt{{\rm Var}(Z_n)}}\stackrel{d}{\longrightarrow} N(0,1).
\]
\end{thm}
As a consequence, we consider the size of tries and PATRICIA tries
\[
N_n^{(T)}=\sum_{k=1}^{m}N_n^{(k)},\qquad N_n^{(P)}=\sum_{k=2}^{m}N_n^{(k)}.
\]
Note that $N_n^{(P)}$ equals $n-1$ if $m=2$ and this case was excluded from our definition of $Z_n$. We have the following consequence of Theorem \ref{main-result-1}.
\begin{cor}\label{cor-size}
For $m\geq 2$, as $n\rightarrow\infty$,
\[
\frac{N_n^{(T)}-{\mathbb E}(N_n^{(T)})}{\sqrt{{\rm Var}(N_n^{(T)})}}\stackrel{d}{\longrightarrow} N(0,1)
\]
and for $m\geq 3$, as $n\rightarrow\infty$,
\[
\frac{N_n^{(P)}-{\mathbb E}(N_n^{(P)})}{\sqrt{{\rm Var}(N_n^{(P)})}}\stackrel{d}{\longrightarrow} N(0,1).
\]
\end{cor}
The result for the size of tries with $m=2$ is classical; see \cite{JaRe} for an analytic proof and Neininger and R\"{u}schendorf \cite{NeRu} for a proof using the contraction method.

As another consequence of Theorem \ref{main-result-1}, we obtain
\begin{equation}\label{cov-asymp}
{\rm Cov}(N_n^{(k_1)},N_n^{(k_2)})\sim nQ^{(k_1,k_2)}(\log_{1/a}n)
\end{equation}
for all $1\leq k_1,k_2\leq m$, where $Q^{(k_1,k_2)}(z)$ is an infinitely differentiable, $1$-periodic function (possibly constant). Set
\[
{\rm Var}(N_n^{(k_1)})\sim nQ^{(k_1)}(\log_{1/a}n),\quad {\rm Var}(N_n^{(k_2)})\sim nQ^{(k_2)}(\log_{1/a}n)
\]
and
\[
\Sigma_n=\left(\begin{array}{cc} nQ^{(k_1)}(\log_{1/a}n) & nQ^{(k_1,k_2)}(\log_{1/a}n)\\
nQ^{(k_1,k_2)}(\log_{1/a}n) & nQ^{(k_2)}(\log_{1/a}n)\end{array}\right).
\]
Then, we have the following bivariate limit law.
\begin{thm}\label{main-result-2}
Assume that $(k_1,k_2,m)\not\in\{(1,2,2),(2,3,3)\}$. Then, $\Sigma_n$ is positive definite for $n$ large enough and, as $n\rightarrow\infty$,
\[
\Sigma_n^{-1/2}\left(\begin{array}{c} N_n^{(k_1)}-{\mathbb E}(N_n^{(k_1)}) \\ N_n^{(k_2)}-{\mathbb E}(N_n^{(k_2)})
\end{array}\right)\stackrel{d}{\longrightarrow} N(0,I_2),
\]
where $I_2$ denotes the $2\times 2$ identity matrix.
\end{thm}

\begin{Rem}
If $(k_1,k_2,m)\in\{(1,2,2),(2,3,3)\}$, then the covariance matrix is singular and thus Theorem \ref{main-result-2} does not hold; see Remark \ref{sing-cov} below.
\end{Rem}

A similar result could be also given for $(N_n^{(k_1)},N_n^{(k_2)},N_n^{(k_3)})$, however, proving that the corresponding covariance matrix is positive definite would be technically complicated (and the problem becomes even more intractable when considering stochastic vectors of higher dimension).

Finally, we will consider the internal path length (sum of all distances of internal nodes to the root) and the internal Wiener index (sum of all distances between unordered pairs of internal nodes) which will be denoted by $T_n^{(\star)}$ and $W_n^{(\star)}$, respectively, where $\star\in\{T,P\}$ depending on whether we consider tries or PATRICIA tries. We have to following trivariate limit law.
\begin{thm}\label{main-result-3}
For $\star=T$ and $m\geq 2$ or $\star=P$ and $m\geq 3$, we have, as $n\rightarrow\infty$,
\begin{align*}
{\mathbb E}(N_n^{(\star)})\sim\ &nP(\log_{1/a}n),\quad {\mathbb E}(T_n^{(\star)})\sim h^{-1}n\log n P(\log_{1/a}n),\\
&{\mathbb E}(W_n^{(\star)})\sim h^{-1}n^2\log n P(\log_{1/a}n)^2
\end{align*}
and
\begin{align*}
{\rm Var}(N_n^{(\star)})\sim n&Q(\log_{1/a}n),\quad {\rm Var}(T_n^{(\star)})\sim h^{-2}n\log^2n Q(\log_{1/a}n),\\
{\rm Var}(W_n^{(\star)})&\sim 4h^{-2}n^3\log^2 nP(\log_{1/a}n)^2Q(\log_{1/a}n),
\end{align*}
where $h=-\sum_{i}p_i\log p_i$ and $P(z),Q(z)$ are infinitely differentiable, $1$-periodic functions (possibly constant). Moreover, we have
\[
\left(\frac{N_n^{(\star)}-{\mathbb E}(N_n^{(\star)})}{\sqrt{{\rm Var}(N_n^{(\star)})}},\frac{T_n^{(\star)}-{\mathbb E}(T_n^{(\star)})}{\sqrt{{\rm Var}(T_n^{(\star)})}},\frac{W_n^{(\star)}-{\mathbb E}(W_n^{(\star)})}{\sqrt{{\rm Var}(W_n^{(\star)})}}\right)\stackrel{d}{\longrightarrow} (X,X,X),
\]
where $X$ is standard normal distributed.
\end{thm}
The result for tries when $m=2$ was already stated in \cite{FuLe}, where we studied many types of Wiener indices for digital trees. However, the result for PATRICIA tries was not included in \cite{FuLe} since the proof will make use of Corollary \ref{cor-size}. This is, in fact, another motivation for the current study.

We conclude the introduction by giving a short sketch of the paper. In the next section, we will recall the framework for deriving asymptotic expansions of mean and variance of additive shape parameters for tries from \cite{FuHwZa}. Moreover, we will explain that with a slight modification of the framework, our main result can be obtained. Then, in Section 3, we will apply our framework to derive Theorem \ref{main-result-1} (in Subsection 3.1) and Theorem \ref{main-result-2} (in Subsection 3.2). In Section 4, we will discuss the internal path length and Wiener index and prove Theorem \ref{main-result-3}. Finally, we will conclude the paper with some remarks in Section 5.

\section{Moments and Central Limit Theorems}\label{mom-and-ll}

Throughout this section, in addition to the assumptions on $X_n$ from the introduction, we will also assume that $n_0=2$ and $X_0=X_1=0$. (Modifications to other values of $n_0, X_0, X_1$ are straightforward.)

\subsection{Preliminaries}\label{pre}

In this subsection, we are going to recall some definitions and results from \cite{FuHwZa} and \cite{HwFuZa} and some properties from Flajolet et al. \cite{FlRoVa}.

First, note that from (\ref{asp-dis-rec}), we immediately obtain that all moments of $X_n$ satisfy a recurrence of the form
\begin{equation}\label{asp-mom-rec}
f_n=\sum_{i=1}^{m}\sum_{j=0}^{n}\binom{n}{j}p_i^j(1-p_i)^{n-j}f_j+g_n,\qquad (n\geq 2),
\end{equation}
where $g_n$ is a suitable given sequence and $f_0=f_1=0$. Due to the appearance of the binomial distribution, it is advantageous to consider {\it Poisson generating functions}
\[
\tilde{f}(z)=e^{-z}\sum_{n\geq 0}f_n\frac{z^n}{n!},\qquad\tilde{g}(z)=e^{-z}\sum_{n\geq 2}g_n\frac{z^n}{n!}.
\]
Then, (\ref{asp-mom-rec}) becomes
\begin{equation}\label{asp-mom-dep}
\tilde{f}(z)=\sum_{i=1}^{m}\tilde{f}(p_iz)+\tilde{g}(z).
\end{equation}
Note that (\ref{asp-mom-rec}) and (\ref{asp-mom-dep}) correspond to two different models: in the first, the number $n$ of strings is fixed, whereas in the second (the so-called {\it Poisson model}), $n$ is replaced by a Poisson random variable with parameter $z$.

Due to the concentration property of the Poisson distribution, we expect a close relationship between the two models above. More precisely, we expect that $f_n\sim\tilde{f}(n)$ (the so-called {\it Poisson heuristic}) and hence an asymptotic study of (\ref{asp-mom-dep}) is sufficient in order to obtain an asymptotic expansion of $f_n$ (which is our main goal). The Poisson heuristic was made precise in \cite{JaSz} and we combined the latter with Hayman's theory of admissible functions \cite{Ha} leading to the notion of JS-admissibility from \cite{FuHwZa} and \cite{HwFuZa}; see the introduction for the precise definition of JS-admissible functions.

JS-admissible functions satisfy closure properties; see Lemma 2.3 in \cite{HwFuZa}. Moreover, the Hadamard product is also closed under JS-admissibility; see \cite{FuHwZa}. From this and asymptotic transfer theorems from \cite{FuHwZa}, one shows, e.g., that the Poisson generating function of the first and second moment of $X_n$ are both JS-admissible provided that the Poisson generating function of the first and second moment of $T_n$ are JS-admissible; see \cite{FuHwZa}. Hence, for asymptotic purpose, we can entirely concentrate on (\ref{asp-mom-dep}).

Finding an asymptotic expansion as $z\rightarrow\infty$ of $\tilde{f}(z)$ satisfying (\ref{asp-mom-dep}) is standard. The main tool for this purpose is the Mellin transform; see \cite{FlGoDu}. Denote the Mellin transform of $\tilde{f}(z)$ and $\tilde{g}(z)$ by
\[
F(\omega)=\mathscr{M}[\tilde{f}(z);\omega];\qquad G(\omega)=\mathscr{M}[\tilde{g}(z);\omega].
\]
Then,
\[
F(\omega)=\frac{G(\omega)}{1-\sum_{i}p_i^{-\omega}}.
\]
An asymptotic expansion of $\tilde{f}(z)$ is obtained from this by the inverse Mellin transform
\begin{equation}\label{inv-mel}
\tilde{f}(z)=\frac{1}{2\pi i}\int_{(-3/2)}F(\omega)z^{-\omega}{\rm d}\omega
\end{equation}
and shifting the line of integration to the right and collecting residues. To carry out this program, we need suitable decay properties of $F(\omega)$ as well as a good understanding of its residues.

Assume now that $\tilde{g}(z)\in\JS_{\alpha,\gamma}$ with $\alpha<1$. Then, $G(\omega)$ is analytic in the {\it fundamental strip} $-2<\Re(\omega)<-\alpha$ (subsequently, we will denote this set by $\langle -2,-\alpha\rangle$). Moreover, by Proposition 5 in \cite{FlGoDu} (which we nicknamed {\it exponential smallness lemma} in \cite{FuHwZa}), we have exponential decay of $G(\omega)$ along vertical lines in its fundamental strip. Consequently, all residues of $F(\omega)$ come from zeros of $P(\omega)=1-\sum_{i}p_i^{-\omega}$ which are easily seen to satisfy $\Re(\omega)\geq -1$. We use the notations
\[
{\mathcal Z}_{=-1}=\{\Re(\omega)=-1\ :\ P(\omega)=0\},\qquad {\mathcal Z}_{<\delta}=\{-1\leq \Re(\omega)<\delta\ :\ P(\omega)=0\},
\]
where $\delta>-1$. A great deal about theses zeros is known; see the deep study \cite{FlRoVa} and references therein. First, as for ${\mathcal Z}_{=-1}$, there are two cases.
\begin{itemize}
\item Periodic case: $\log p_i/\log p_j$ is rational for all $i,j$, or equivalently, there exists an $0<a<1$ and $\alpha_i\in{\mathbb N}$ such that $p_i=a^{\alpha_i}$ for all $i$. In this case, all the zeros with $\Re(\omega)=-1$ are given by ${\mathcal Z}_{=-1}=\{-1+2\ell\pi i/\log(1/a)\ :\ \ell\in{\mathbb Z}\}$.
\item Aperiodic case: at least one of the ratios $\log p_i/\log p_j$ is irrational. In this case, there is only one zero with $\Re(\omega)=-1$, namely, the (trivial) zero $-1$.
\end{itemize}
Beyond the line $\Re(\omega)=-1$, the behavior of the zeros of $P(\omega)$ is more chaotic. Nevertheless, the zero distribution still shows some regularity, for instance, the zeros are uniformly separated, $1/P(\omega)$ is uniformly bounded provided that $\omega$ is uniformly far away from the zeros, etc; see \cite{FlRoVa}. These properties combined with the above properties of $G(\omega)$ allow one to shift the line of integration in (\ref{inv-mel}) to the right and use the residue theorem. This yields, as $z\rightarrow\infty$,
\[
\tilde{f}(z)\sim-\sum_{\omega_{\ell}\in{{\mathcal Z}_{<-\alpha+\epsilon}}}\frac{G(\omega_{\ell})}{P'(\omega_{\ell})}z^{-\omega_{\ell}}+{\mathcal O}\left(z^{-\alpha+\epsilon}\right)
\]
for $\epsilon>0$. The same asymptotics then also holds for $f_n$ due to theory of JS-admissibility.

\subsection{Mean and Variance}

We recall here the results concerning asymptotics of mean and variance of $X_n$ satisfying (\ref{asp-dis-rec}) from \cite{FuHwZa}, where we only concentrate on the case where the Poisson generating function of first and second moment of $T_n$ is small. We need the following notations
\begin{align*}
\tilde{f}_1(z)&=e^{-z}\sum_{n\geq 0}{\mathbb E}(X_n)\frac{z^n}{n!},\quad
\tilde{f}_2(z)=e^{-z}\sum_{n\geq 0}{\mathbb E}(X_n^2)\frac{z^n}{n!}.
\end{align*}
Moreover, recall the definitions of $\tilde{g}_1(z),\tilde{g}_2(z)$ and $\tilde{V}_T(z)$ from the introduction.

\begin{thm}[Mean of $X_n$; see \cite{FuHwZa}]\label{mean-xn}
Assume that $\tilde{g}_1(z)\in\JS_{\alpha,\gamma}$ with $0\leq\alpha<1$. Then, as $n\rightarrow\infty$,
\[
{\mathbb E}(X_n)=\sum_{\omega_{\ell}\in{{\mathcal Z}_{<-\alpha+\epsilon}}}G_1(\omega_{\ell})n^{-\omega_{\ell}}+{\mathcal O}\left(n^{-\alpha+\epsilon}\right),
\]
where $\epsilon>0$ and $G_1(\omega)$ is an analytic function of exponential decay on $\Re(\omega)=\gamma\in\langle -2,-\alpha+\epsilon\rangle$.
\end{thm}

\begin{thm}[Variance of $X_n$; see \cite{FuHwZa}]\label{var-xn}
Assume that $\tilde{g}_2(z)\in\JS$ and $\tilde{g}_1(z),\tilde{V}_T(z)\in\JS_{\alpha,\gamma}$ with $\alpha<1$. Then, as $n\rightarrow\infty$,
\[
{\rm Var}(X_n)\sim\sum_{\omega_{\ell}\in{{\mathcal Z}_{=-1}}}G_2(\omega_{\ell})n^{-\omega_{\ell}},
\]
where $G_2(\omega)$ is an analytic function of exponential decay on $\Re(\omega)=-1$.
\end{thm}
Note that from the discussion in Section \ref{pre}, in the periodic case, the last result can be rewritten to
\[
{\rm Var}(X_n)\sim nQ(\log_{1/a}n),
\]
where $Q(z)$ is an infinitely differentiable, $1$-periodic function. (Infinite differentiability is readily obtained from the exponential decay on $\Re(\omega)=-1$.) In the aperiodic case, we obtain that
\[
{\rm Var}(X_n)\sim cn,
\]
where $c$ is a suitable constant. (Both cases can be merged by, e.g., setting $a=1$ in the aperiodic case.)

\subsection{Central Limit Theorems}\label{sec-ll}

In this section, we are going to prove our main result, namely, Theorem \ref{limit-law}. Before doing so, we will however need to discuss how to show that the variance is positive for all $n$ large enough which is needed for normalization purposes. (Note that since the variance is by definition nonnegative, so, proving that it is positive amounts to showing that it is nonzero.) This is a non-trivial problem, even though an explicit expression can be given for the main term in the asymptotic expansion of the variance; see \cite{FuHwZa}. This explicit expression is, however, too involved and also depends on the parameters $p_1,\ldots,p_m$ (and on $k$ in the example discussed in Section \ref{intro}).

In order to solve this problem, we will consider the recurrence satisfied by the variance which is of the form (\ref{asp-mom-rec}) and apply the following result which is based on a result of Schachinger \cite{Sc}. (Since we need similar arguments in the proof of Proposition \ref{qua-cov} below, we will give the proof which is also largely based on \cite{Sc}.)

\begin{pro}\label{scha-pro}
Let $f_n$ be a sequence satisfying (\ref{asp-mom-rec}) with $f_0=f_1=0$. Assume that $g_n$ is non-negative and $g_{n_0}>0$ for some $n_0\geq 2$. Then, $f_n=\Omega(n)$.
\end{pro}
\pf We first bring (\ref{asp-mom-rec}) into the following form
\[
f_n=\sum_{i=1}^{m}\sum_{j=0}^{n-1}\binom{n}{j}\frac{p_i^{j}(1-p_i)^{n-j}}{1-\sum_{i}p_i^n}f_j
+\frac{g_n}{1-\sum_{i}p_i^n}.
\]

Next, note that from Chernoff's bound, we have
\[
\sum_{\vert j-p_in\vert>p_in^{2/3}}\binom{n}{j}\frac{p_i^{j}(1-p_i)^{n-j}}{1-\sum_{i}p_i^n}={\mathcal O}\left(n^{-3}\right)
\]
for all $1\leq i\leq m$. Moreover, note that due to the assumptions, $f_n>0$ for all $n\geq n_0$.

We will use the following notations
\[
F_n=f_n/n,\quad\underline{F}_n=\min_{n_0\leq k\leq n}F_k,\quad n_{+}=n+n^{2/3},\quad n_{-}=n-n^{2/3}.
\]
Our goal is to prove that $\underline{F}_n$ has a positive lower bound.

First, observe for $n$ sufficiently large
\begin{align}
F_n&\geq\sum_{i=1}^{m}\sum_{\vert j-p_in\vert\leq p_in^{2/3}}\binom{n}{j}\frac{p_i^{j}(1-p_i)^{n-j}}{1-\sum_{i}p_i^n}\cdot\frac{j}{n}F_j\nonumber\\
&\geq\sum_{i=1}^{m}\underline{F}_{\lceil p_in_{+}\rceil}\frac{p_in_{-}}{n}\sum_{\vert j-p_in\vert\leq p_in^{2/3}}\binom{n}{j}\frac{p_i^{j}(1-p_i)^{n-j}}{1-\sum_{i}p_i^n}\geq\left(1-Cn^{-1/3}\right)
\sum_{i=1}^{m}\underline{F}_{\lceil p_in_{+}\rceil}p_i,\label{posvar-1}
\end{align}
where $C>0$ is a suitable constant. W.l.o.g. assume that $p_1=\max_{1\leq i\leq m}p_i$. Set $p'=(1+p_1)/2$. Then, for $n$ sufficiently large, we have $\lceil p_in_{+}\rceil\leq\lfloor p'n\rfloor$ for all $i$. Thus, (\ref{posvar-1}) becomes for $n$ large enough
\begin{equation}\label{posvar-2}
F_n\geq \underline{F}_{\lfloor p'n\rfloor}\left(1-Cn^{-1/3}\right).
\end{equation}

Next, we only consider $n$ with $\underline{F}_{n-1}>F_n$, i.e., $n$ for which $\underline{F}_{n}$ jumps. If the number of such $n$ is finite, then our goal is obviously established. Otherwise, pick such an $n$ which is large enough and denote it by $N_0$. Moreover, define recursively
\[
N_{k+1}=\max\{n\in{\mathbb N}\ :\ \underline{F}_{n-1}>F_n\ \text{and}\ \underline{F}_{\lfloor p'n\rfloor}\geq F_{N_k}\}.
\]
Note that $N_k$ is increasing and $N_{k+2}>N_{k}/p'$, i.e., $N_k$ grows exponentially fast. The latter implies that
\[
\prod_{k=0}^{\infty}\left(1-CN_{k}^{-1/3}\right)
\]
is convergent and hence there exists a $k_0$ large enough such that
\[
\prod_{j=k_0+1}^{\infty}\left(1-CN_{j}^{-1/3}\right)\geq 1/2.
\]

Finally, observe that from (\ref{posvar-2})
\[
\underline{F}_{N_{k}}=F_{N_k}\geq\underline{F}_{\lfloor p'N_k\rfloor}\left(1-CN_k^{-1/3}\right)\geq
\underline{F}_{N_{k-1}}\left(1-CN_k^{-1/3}\right)
\]
and iterating this gives for all $k\geq k_0$
\[
\underline{F}_{N_{k}}\geq\underline{F}_{N_{k_0}}\prod_{j=k_0+1}^{k}\left(1-CN_j^{-1/3}\right)\geq
\underline{F}_{N_{k_0}}/2.
\]
This proves our goal.\qed

Now, we turn to the proof of Theorem \ref{limit-law}. (For specific shape parameters, a proof was already given in \cite{NeRu}. Our proof is a generalization with some simplifications.)

\vspace*{0.3cm}\noindent{\it Proof of Theorem \ref{limit-law}.} First, from Theorem \ref{mean-xn} and Theorem \ref{var-xn}, as $n\rightarrow\infty$,
\[
{\mathbb E}(X_n)=\sum_{\omega_{\ell}\in{\mathcal Z}_{<-\alpha_1+\epsilon}}G_1(\omega_{\ell})n^{-\omega_{\ell}}+{\mathcal O}\left(n^{-\alpha_1+\epsilon}\right),\quad {\rm Var}(X_n)\sim\sum_{\omega_{\ell}\in{\mathcal Z}_{=-1}}G_2(\omega_{\ell})n^{-\omega_{\ell}},
\]
where $\epsilon>0$ is chosen such that $\alpha_1+\epsilon<1/2$. Set
\[
\Phi_1(x)=\sum_{\omega_{\ell}\in{\mathcal Z}_{<-\alpha_1+\epsilon}}G_1(\omega_{\ell})x^{-\omega_{\ell}},\qquad
\Phi_2(x)=\sum_{\omega_{\ell}\in{\mathcal Z}_{=-1}}G_2(\omega_{\ell})x^{-\omega_{\ell}-1}.
\]
We collect some obvious properties of these functions.
\begin{itemize}
\item We have,
\begin{equation}\label{fact1}
\sum_{i=1}^m\Phi_1(p_ix)=\sum_{\omega_{\ell}\in{\mathcal Z}_{<-\alpha_1+\epsilon}}G_1(\omega_{\ell})x^{-\omega_{\ell}}\sum_{i=1}^{m}p_i^{-\omega_{\ell}}=\Phi_1(x).
\end{equation}
\item For all $1\leq i,j\leq m$,
\begin{equation}\label{fact2}
\Phi_1'(p_ix)-\Phi_1'(p_jx)=\sum_{\omega_{\ell}\in{\mathcal Z}_{<-\alpha_1+\epsilon}}G_1(\omega_{\ell})(-\omega_{\ell})x^{-\omega_{\ell}-1}\left(p_i^{-\omega_{\ell}-1}-p_j^{-\omega_{\ell}-1}\right)=o(x),
\end{equation}
where the last equality follows from the fact that $p_i^{-\omega_{\ell}-1}=p_j^{-\omega_{\ell}-1}$ for all $\omega_{\ell}\in{\mathcal Z}_{=-1}$.
\item We have,
\begin{equation}\label{fact3}
\Phi_1''(x)=\sum_{\omega_{\ell}\in{\mathcal Z}_{<-\alpha_1+\epsilon}}G_1(\omega_{\ell})(-\omega_{\ell})(-\omega_{\ell}-1)x^{-\omega_{\ell}-2}={\mathcal O}(1/x).
\end{equation}
\item $\Phi_2(p_ix)=\Phi_2(x)$ for all $1\leq i\leq m$ and $\Phi'_2(x)={\mathcal O}(1/x)$.
\end{itemize}

For the proof we will use the contraction method; see Corollary 5.2 in \cite{NeRu}. We have to verify the following assumptions:
\begin{align}
&\Phi_2(n)^{-1/2}\left(T_n-\Phi_1(n)+\sum_{i=1}^{m}\Phi_1(I_n^{(i)})\right)\stackrel{L_s}{\longrightarrow} 0,\label{cond-1}\\
\left(\frac{I_n^{(i)}\Phi_2(I_n^{(i)})}{n\Phi_2(n)}\right)^{1/2}&\stackrel{L_s}{\longrightarrow} A_i,\quad \sum_{i=1}^{m}A_i^2=1,
\quad P(\exists i\ :\ A_i=1)<1.\label{cond-2}
\end{align}

We start with the verification of (\ref{cond-2}). First, observe that the strong law of large numbers for $I_n^{(i)}$ implies that
\begin{equation}\label{step-1}
\frac{I_n^{(i)}}{n}\stackrel{\text{a.s.}}{\longrightarrow}p_i.
\end{equation}
Next, by Taylor series expansion and the properties of $\Phi_2(x)$ from above, we obtain
\[
\Phi_2(I_n^{(i)})=\Phi_2(n)+{\mathcal O}\Big(\Big\vert\frac{I_n^{(i)}}{n}-p_i\Big\vert\Big).
\]
Thus,
\begin{equation}\label{step-2}
\frac{\Phi_2(I_n^{(i)})}{\Phi_2(n)}-1=\Phi_2(n)^{-1}{\mathcal O}\Big(\Big\vert \frac{I_n^{(i)}}{n}-p_i\Big\vert\Big)\stackrel{\text{a.s.}}{\longrightarrow}0,
\end{equation}
where we used the assumption on ${\rm Var}(X_n)$ and (\ref{step-1}). Now, combining (\ref{step-1}) and (\ref{step-2}) yields the first claim of (\ref{cond-2}) with a.s convergence and $A_i=\sqrt{p_i}$. The dominated convergence theorem implies that a.s. convergence can be replaced by $L_s$ convergence. The other claims of (\ref{cond-2}) are easily verified.

Now, we turn to (\ref{cond-1}). First, note that the assumption on $\|X_n\|_{s}$ and ${\rm Var}(X_n)$ imply that $T_n$ in (\ref{cond-1}) can be dropped. Next, set
\[
A_n=\bigcap_{i=1}^{m}\{\vert I_{n}^{(i)}-p_in\vert\leq p_in^{2/3}\}
\]
and denote by $\chi_{A_n}$ the indicator function of $\chi_{A_n}$. Chernoff's bound yields
\[
P(A_{n}^{c})={\mathcal O}\left(e^{-p_mn^{1/3}/3}\right),
\]
where w.l.o.g. $p_m=\min_{1\leq i\leq m}p_i$. Consequently,
\[
\left\|\Phi_2(n)^{-1/2}\left(-\Phi_1(n)+\sum_{i=1}^{m}\Phi_1(I_n^{(i)})\right)\chi_{A_n^c}\right\|_s={\mathcal O}\left(\sqrt{n}e^{-p_mn^{1/3}/(3s)}\right)=o(1).
\]
Next, on $A$, we use Taylor series expansion and (\ref{fact3}) which gives
\[
\Phi_1(I_n^{(i)})=\Phi_1(p_in)+\Phi_1'(p_in)\left(I_n^{(i)}-p_in\right)+{\mathcal O}\left(\left(I_n^{(i)}-p_in\right)^2/n\right)
\]
for $1\leq i\leq m$. Thus,
\begin{align*}
\Bigg\|\Phi_2&(n)^{-1/2}\left(-\Phi_1(n)+\sum_{i=1}^{m}\Phi_1(I_n^{(i)})\right)\chi_{A_n}\Bigg\|_s\\
&\leq\left\|\Phi_2(n)^{-1/2}\sum_{i=1}^{m}\Phi_1'(p_in)\left(I_n^{(i)}-p_in\right)\right\|_s+\left\|\Phi_2(n)^{-1/2}\sum_{i=1}^{m}
{\mathcal O}\left(\left(I_n^{(i)}-p_in\right)^2/n\right)\right\|_s,
\end{align*}
where we used (\ref{fact1}). Using (\ref{fact2}) and the assumption on ${\rm Var}(X_n)$, the first term is estimated as
\begin{align*}
\Bigg\|\Phi_2(n)^{-1/2}\sum_{i=1}^{m}\Phi_1'(p_in)&\left(I_n^{(i)}-p_in\right)\Bigg\|_s\\
&=\left\|\Phi_2(n)^{-1/2}\sum_{i=1}^{m-1}\left(\Phi_1'(p_in)-\Phi_1'(p_mn)\right)\left(I_n^{(i)}-p_in\right)\right\|_s\\
&\leq o(1)\sum_{i=1}^{m}\left\|\left(I_n^{(i)}-p_in\right)/\sqrt{n}\right\|_s=o\left(\|N(0,1)\|_s\right)=o(1).
\end{align*}
Similarly, for the second term, we obtain
\[
\left\|\Phi_2(n)^{-1/2}\sum_{i=1}^{m}
{\mathcal O}\left(\left(I_n^{(i)}-p_in\right)^2/n\right)\right\|_s={\mathcal O}\left(\|N(0,1)^2\|_s/\sqrt{n}\right)=o(1).
\]
Combining everything yields (\ref{cond-1}). This concludes the proof of the theorem.\qed

\section{Nodes of Fixed Out-degree}
\subsection{Proof of Theorem \ref{main-result-1}}
After the preparations from the previous section, the proof of Theorem \ref{main-result-1} is relatively straightforward.

First, observe that $Z_n$ is indeed an additive shape parameter satisfying a recurrence of type (\ref{asp-dis-rec}). In order to see this, note that
\[
N_n^{(k)}\stackrel{d}{=}\sum_{i=1}^{m}(N_{I_n^{(i)}}^{(k)})^{(i)}+T_{n}^{(k)},\qquad (n\geq 2),
\]
where notation is as in Section \ref{intro}, $N_0^{(k)}=N_1^{(k)}=0$ and
\[
T_n^{(k)}=\begin{cases} 1,&\text{if $\#\{1\leq i\leq m\ :\ I_n^{(i)}\ne 0\}=k$};\\ 0,&\text{otherwise}.\end{cases}
\]
Consequently,
\begin{equation}\label{rec-zn}
Z_n\stackrel{d}{=}\sum_{i=1}^{m}Z_{I_n^{(i)}}^{(i)}+T_n,\qquad (n\geq 2),
\end{equation}
where $Z_0=Z_1=0$ and
\begin{equation}\label{toll-zn}
T_n=\sum_{k=1}^ma_kT_n^{(k)}.
\end{equation}

Next, observe that $T_n$ is not independent of $(I_n^{(1)},\ldots,I_n^{(m)})$ and hence, strictly speaking, our results from the previous sections do not apply. However, it is easily checked that the proofs of the results from the previous section still work for the current situation under the same assumptions; see Section 5.4 in \cite{FuHwZa} for a similar example.

Now, in order to apply the results, we have to check that the assumptions hold. This is not complicated since $\tilde{g}_1(z)$ and $\tilde{g}_2(z)$ are easily computed. For instance, to compute $\tilde{g}_1(z)$, note that
\[
{\mathbb E}\left(T_{n}^{(k)}\right)=\sum_{\{i_1,\ldots,i_k\}\subseteq S}\sum_{\substack{j_{i_1}+\cdots+j_{i_k}=n\\ j_{i_1},\ldots,j_{i_k}\geq 1}}\binom{n}{j_{i_1},\ldots,j_{i_k}}p_{i_1}^{j_{i_1}}\cdots p_{i_k}^{j_{i_k}}.
\]
Consequently, for $k\geq 2$,
\[
e^{-z}\sum_{n\geq 2}{\mathbb E}\left(T_n^{(k)}\right)\frac{z^n}{n!}=\sum_{\{i_1,\ldots,i_k\}\subseteq S}e^{-z}\left(e^{p_{j_{i_1}}z}-1\right)\cdots\left(e^{p_{j_{i_k}}z}-1\right)
\]
and similar for $k=1$. From this, we obtain $\tilde{g}_1(z)$ by (\ref{toll-zn}) and linearity of the mean.

In particular, we see that $\tilde{g}_1(z)$ is a linear combination of functions of the form $e^{-az}$ with $a\geq 0$. Hence, from the closure properties of \cite{FuHwZa}, we have that $\tilde{g}_1(z)\in\JS_{0,0}$. The same result is also easily verified to hold for $\tilde{g}_2(z)$. Thus, the claims about mean and variance in Theorem \ref{main-result-1} follow from Theorem \ref{mean-xn} and Theorem \ref{var-xn}.

Next, we turn to the limit law. We are going to apply Theorem \ref{limit-law}. The only assumption of this theorem which needs further explanation is the assumption on the positiveness of the variance (or more precisely, the assumption of the at least linear growth of the variance). This assumption will be verified via the next two results.
\begin{lmm}\label{pos-var}
$Z_n$ is not deterministic for $n$ large enough.
\end{lmm}
\begin{figure}[h]
\begin{center}
\begin{tikzpicture}
\draw (0cm,0cm) node[inner sep=1.5pt,circle,fill=black,draw] (1) {};
\draw (-0.3cm,-0.8cm) node[inner sep=1.5pt,circle,fill=black,draw] (2) {};
\draw (0.3cm,-0.8cm) node[inner sep=1.5pt,circle,draw] (3) {};
\draw (-0.48cm,-1.28cm) node[inner sep=0.5pt] (04) {};
\draw (-0.51cm,-1.36cm) node[inner sep=0.5pt] (004) {};
\draw (-0.69cm,-1.84cm) node[inner sep=0.5pt] (114) {};
\draw (-0.72cm,-1.92cm) node[inner sep=0.5pt] (14) {};
\draw (0cm,-1.6cm) node[inner sep=1.5pt,circle,draw] (5) {};
\draw (-0.9cm,-2.4cm) node[inner sep=1.5pt,circle,fill=black,draw] (6) {};
\draw (-1.2cm,-3.2cm) node[inner sep=1.5pt,circle,fill=black,draw] (7) {};
\draw (-0.6cm,-3.2cm) node[inner sep=1.5pt,circle,draw] (8) {};
\draw (-1.6cm,-4cm) node[inner sep=1.5pt,circle,draw] (9) {};
\draw (-1.4cm,-4cm) node[inner sep=1.5pt,circle,draw] (10) {};
\draw (-1.1cm,-4cm) node (11) {${\scriptstyle \cdots}$};
\draw (-0.8cm,-4cm) node[inner sep=1.5pt,circle,draw] (12) {};

\draw (1) -- (2);
\draw (1) -- (3);
\draw (2) -- (04);
\draw (2) -- (5);
\draw [thick,dotted] (004) -- (114);
\draw (14) -- (6);
\draw (6) -- (7);
\draw (6) -- (8);
\draw (7) -- (9);
\draw (7) -- (10);
\draw (7) -- (12);

\draw (4cm,0cm) node[inner sep=1.5pt,circle,fill=black,draw] (81) {};
\draw (3.7cm,-0.8cm) node[inner sep=1.5pt,circle,fill=black,draw] (82) {};
\draw (4.3cm,-0.8cm) node[inner sep=1.5pt,circle,draw] (83) {};
\draw (3.52cm,-1.28cm) node[inner sep=0.5pt] (804) {};
\draw (3.49cm,-1.36cm) node[inner sep=0.5pt] (8004) {};
\draw (3.31cm,-1.84cm) node[inner sep=0.5pt] (8114) {};
\draw (3.28cm,-1.92cm) node[inner sep=0.5pt] (814) {};
\draw (4cm,-1.6cm) node[inner sep=1.5pt,circle,draw] (85) {};
\draw (3.1cm,-2.4cm) node[inner sep=1.5pt,circle,fill=black,draw] (86) {};
\draw (2.7cm,-3.2cm) node[inner sep=1.5pt,circle,fill=black,draw] (87) {};
\draw (2.9cm,-3.2cm) node[inner sep=1.5pt,circle,draw] (887) {};
\draw (3.15cm,-3.2cm) node (8887) {${\scriptstyle \cdots}$};
\draw (3.4cm,-3.2cm) node[inner sep=1.5pt,circle,draw] (88) {};
\draw (2.3cm,-4cm) node[inner sep=1.5pt,circle,draw] (89) {};
\draw (2.5cm,-4cm) node[inner sep=1.5pt,circle,draw] (810) {};
\draw (2.8cm,-4cm) node (811) {${\scriptstyle \cdots}$};
\draw (3.1cm,-4cm) node[inner sep=1.5pt,circle,draw] (812) {};

\draw (81) -- (82);
\draw (81) -- (83);
\draw (82) -- (804);
\draw (82) -- (85);
\draw [thick,dotted] (8004) -- (8114);
\draw (814) -- (86);
\draw (86) -- (87);
\draw (86) -- (887);
\draw (86) -- (88);
\draw (87) -- (89);
\draw (87) -- (810);
\draw (87) -- (812);
\end{tikzpicture}
\end{center}
\caption{Two tries with internal nodes black and external nodes white. The trie on the left has all internal nodes of outdegree $2$ except the last which is of outdegree $i$; the trie on the right has all internal nodes of outdegree $2$ expect the last two which are of outdegree $i$.}
\end{figure}
\pf First, observe that the claim is trivial if $a_1\ne 0$. Thus, we may assume that $m\geq 3$ and $a_i\ne (i-1)a_2$ for $i\geq 3$. For this case, consider the two tries from Figure 1. For the first trie, we have $Z_n=(n-i)a_2+a_i$; for the second, we have $Z_n=(n-2i+1)a_2+2a_i$. From our assumption, these two values are different. This concludes the proof.\qed

\begin{Rem}\label{det}
If $a_i=(i-1)a_2$ for all $i$, then it is easy to see that $Z_n=a_2(n-1)$ for all $n$.
\end{Rem}

\begin{pro}\label{lin-var}
We have, ${\rm Var}(Z_n)\geq cn$ with $c>0$ for all $n$ large enough.
\end{pro}
\pf We first derive the recurrence for ${\rm Var}(Z_n)$. Set $\mu_n={\mathbb E}(Z_n)$ and
\[
M_n(y)={\mathbb E}\left(e^{(Z_n-\mu_n)y}\right).
\]
Then, from (\ref{rec-zn}),
\begin{align*}
M_n(y)=\sum_{j_1+\cdots+j_m=n}\pi_{j_1,\ldots,j_m}M_{j_1}(y)\cdots M_{j_m}(y){\mathbb E}\Big(e^{(T_n-\mu_n+\sum_{i}\mu_{j_i})y}\vert
I_n^{(1)}=j_1,\ldots,I_n^{(m)}=j_m\Big)
\end{align*}
with $n\geq 2$ and $M_0(y)=M_1(y)=1$. Observe that
\[
\sigma_n^2={\rm Var}(Z_n)=M_n(y)''\Big\vert_{y=0}.
\]
Differentiating yields
\[
\sigma_n^2=\sum_{i=1}^{m}\sum_{j=0}^{n}\binom{n}{j}p_i^j(1-p_i)^{n-j}\sigma_j^2+\eta_n,\qquad (n\geq 2),
\]
where $\sigma_0^2=\sigma_1^2=0$ and
\[
\eta_n=\sum_{j_1+\cdots+j_m=n}\pi_{j_1,\ldots,j_m}{\mathbb E}\Big(\big(T_n-\mu_n+\sum_{i}\mu_{j_i}\big)^2\vert
I_n^{(1)}=j_1,\ldots,I_n^{(m)}=j_m\Big).
\]

From the last expression, we see that $\xi_n\geq 0$. Consequently, by Proposition \ref{scha-pro}, either ${\rm Var}(X_n)$ grows at least linearly or equals zero for all $n$. The latter, however, is impossible by Lemma \ref{pos-var}.\qed

Now, we can apply Theorem \ref{limit-law}. This concludes the proof of Theorem \ref{main-result-1}.

\subsection{Proof of Theorem \ref{main-result-2}}

In this subsection, we will prove Theorem \ref{main-result-2}.

First note that the covariance of $N_n^{(k_1)}$ and $N_n^{(k_2)}$ can be obtained from Theorem \ref{main-result-1} via the relation
\[
2{\rm Cov}\left(N_n^{(k_1)},N_n^{(k_2)}\right)={\rm Var}\left(N_n^{(k_1)}+N_n^{(k_2)}\right)-{\rm Var}\left(N_n^{(k_1)}\right)-{\rm Var}\left(N_n^{(k_2)}\right).
\]
This relation and Theorem \ref{main-result-1} gives (\ref{cov-asymp}).

Next, as in the previous subsection, we have to show for normalization purposes that $\Sigma_n$ is positive definite. We will do this again in two steps. Recall from Theorem \ref{main-result-1} the requirement that $(k_1,k_2,m)\not\in\{(1,2,2),(2,3,3)\}$.
\begin{lmm}\label{lemma-cc}
The correlation coefficient $\rho(N_n^{(k_1)},N_n^{(k_2)})$ is not $-1$ or $1$ for all $n$ large enough.
\end{lmm}
\pf We use proof by contradiction. Thus, assume that $\rho(N_n^{(k_1)},N_n^{(k_2)})\in\{-1,1\}$ which implies that for some $a_n,b_n\in{\mathbb R}$ with $a_n\ne0$, we have that
\[
N_n^{(k_1)}=a_nN_n^{(k_2)}+b_n.
\]
Obviously this cannot hold if $k_1=1$. Thus, we may assume that $k_1\geq 2$. First, consider $k_1=2$ and set $i\ne k_2$ (this is possible due to the assumption on $(k_1,k_2,m)$). Then, we get a contradiction from the two tries in Figure 1 (since $N_n^{(2)}$ decreases, whereas $N_n^{(k_2)}$ remains constant). Next, consider $k_1>2$ and set $i=k_2$. Then, again a contradiction is obtained from Figure 1 (now, $N_n^{(k_1)}$ remains constant, whereas $N_n^{(i)}$ increases).\qed
\begin{Rem}\label{sing-cov}
$(k_1,k_2,m)=(1,2,2)$ is the only case where the correlation coefficient is not defined ($N_n^{(2)}$ is deterministic in this case; see Remark \ref{det}). If $(k_1,k_2,m)=(2,3,3)$, then $N_n^{(2)}=n-1-2N_n^{(3)}$ (again by Remark \ref{det}). Hence, in this case $\rho(N_n^{(2)},N_n^{(3)})=-1$.
\end{Rem}

\begin{pro}\label{qua-cov}
$\Sigma_n$ is positive definite for all $n$ large enough.
\end{pro}
\pf It is sufficient to show that $\det(\Sigma_n)>0$ for all $n$ large enough. For the proof of this,
we will need some notation. First,
\[
\mu_n^{(k_1)}={\mathbb E}(N_n^{(k_1)}),\qquad\mu_n^{(k_2)}={\mathbb E}(N_n^{(k_2)}).
\]
Moreover,
\[
\xi_{n}={\rm Var}(N_n^{(k_1)}),\qquad \nu_{n}={\rm Cov}(N_n^{(k_1)},N_n^{(k_2)}),\qquad \kappa_n={\rm Var}(N_n^{(k_2)}).
\]
Then, by setting
\[
F_n(u,v)={\mathbb E}\left(e^{(N_n^{(k_1)}-\mu_n^{(k_1)})u+(N_n^{(k_2)}-\mu_n^{(k_2)})v}\right)
\]
and arguing as in Proposition \ref{lin-var}, we obtain (after a lengthy computation)
\begin{align}
\xi_{n_1}\kappa_{n_2}&+\xi_{n_2}\kappa_{n_1}-2\nu_{n_1}\nu_{n_2}\nonumber\\
&=\sum_{j_1+\cdots+j_m=n_1}\sum_{l_1+\cdots+l_m=n_2}\pi_{j_1,\ldots,j_m}\pi_{l_1,\ldots,l_m}\sum_{i=1}^{m}\sum_{u=1}^{m}
\left(\xi_{j_i}\kappa_{l_u}+\xi_{l_u}\kappa_{j_i}-2\nu_{j_i}\nu_{l_u}\right)+\tau_{n_1,n_2}\label{rec-biv}
\end{align}
for $n_1,n_2\geq 2$ and all initial conditions equal to $0$. In order to describe $\tau_{n_1,n_2}$ set
\begin{align*}
\alpha_{j_1,\ldots,j_m}&={\mathbb E}\Big(\big(T_n^{(k_1)}-\mu_n^{(k_1)}+\sum_{i}\mu_{j_i}^{(k_1)}\big)^2\vert
I_n^{(1)}=j_1,\ldots,I_n^{(m)}=j_m\Big),\\
\beta_{j_1,\ldots,j_m}&={\mathbb E}\Big(\big(T_n^{(k_2)}-\mu_n^{(k_2)}+\sum_{i}\mu_{j_i}^{(k_2)}\big)^2\vert
I_n^{(1)}=j_1,\ldots,I_n^{(m)}=j_m\Big).
\end{align*}
Then,
\[
\tau_{n_1,n_2}=\sum_{j_1+\cdots+j_m=n_1}\sum_{l_1+\cdots+l_m=n_2}\pi_{j_1,\ldots,j_m}\pi_{l_1,\ldots,l_m}\left(
\Theta_{j_1,\ldots,j_m,l_1,\ldots,l_m}+\Xi_{j_1,\ldots,j_m,l_1,\ldots,l_m}\right),
\]
where
\[
\Theta_{j_1,\ldots,j_m,l_1,\ldots,l_m}=(\alpha_{j_1,\ldots,j_m}\beta_{l_1,\ldots,l_m}-\alpha_{l_1,\ldots,l_m}
\beta_{j_1,\ldots,j_m})^2
\]
and
\begin{align*}
\Xi_{j_1,\ldots,j_m,l_1,\ldots,l_m}=&\sum_{i=1}^{m}{\mathbb E}\left(\alpha_{l_1,\ldots,l_m}(N_{j_i}^{(k_1)}-\mu_{j_i}^{(k_1)})-\beta_{l_1,\ldots,l_m}(N_{j_i}^{(k_1)}-\mu_{j_i}^{(k_2)}
)\right)^2\\
&+\sum_{u=1}^{m}{\mathbb E}\left(\alpha_{j_1,\ldots,j_m}(N_{l_u}^{(k_2)}-\mu_{j_u}^{(k_2)})-\beta_{j_1,\ldots,j_m}(N_{l_u}^{(k_1)}-\mu_{l_u}^{(k_1)}
)\right)^2.
\end{align*}

Now, note that $\tau_{n_1,n_2}\geq 0$ for all $n_1,n_2$. By applying a similar line of arguments as in Proposition \ref{scha-pro} to (\ref{rec-biv}) one obtains that
\[
\xi_{n_1}\kappa_{n_2}+\xi_{n_2}\kappa_{n_1}-2\nu_{n_1}\nu_{n_2}
\]
is either identical zero for all $n_1,n_2$ or $\geq cn_1n_2$ with $c>0$. The former is however impossible due to Lemma \ref{lemma-cc}. Finally, by setting $n_1=n_2$, we obtain that $\det(\Sigma_n)\geq cn^2$ with $c>0$.\qed

As a consequence of this proposition, $\Sigma_n^{1/2}$ exists for $n$ large enough. For the proof of the bivariate limit law in Theorem \ref{main-result-2}, we need some notation
\[
\left(\begin{array}{c} b_n^{(1)}\\b_n^{(2)}\end{array}\right)=\Sigma_n^{-1/2}\left(\left(\begin{array}{c} T_n^{(k_1)}\\T_n^{(k_2)}\end{array}\right)
-\left(\begin{array}{c}\mu_n^{(k_1)}\\\mu_n^{(k_2)}\end{array}\right)+\sum_{i=1}^{k}\left(\begin{array}{c}\mu_{I_n^{(i)}}^{(k_1)}\\\mu_{I_n^{(i)}}^{(k_2)}
\end{array}\right)\right),
\]
where $\mu_{n}^{(k_1)}$ and $\mu_n^{(k_2)}$ are as in the proof of the above proposition and
\[
A_n^{(i)}=\Sigma_n^{-1/2}\Sigma_{I_n^{(i)}}^{1/2},\qquad 1\leq i\leq m.
\]
Explicit expressions for these vectors and matrices can be derived by Maple and are given in Appendix A.

\vspace*{0.2cm}\noindent{\it Proof of the bivariate limit law in Theorem \ref{main-result-2}.} We use the multivariate version of the contraction method; see Neininger and R\"{u}schendorf \cite{NeRu}. We have to verify the following assumptions for $2<s\leq 3$:
\begin{align}
&\left(\begin{array}{c} b_n^{(1)}\\b_n^{(2)}\end{array}\right)\stackrel{L_s}{\longrightarrow}\left(\begin{array}{c} 0\\ 0\end{array}\right),\qquad A_n^{(i)}\stackrel{L_s}{\longrightarrow}A_i,\label{mcc}\\
&{\mathbb E}\sum_{i=1}^{m}\|A_i\|_{\text{op}}^s<1,\qquad{\mathbb E}\left(
\|A_i\|_{\text{op}}^s\chi_{\{I_n^{(i)}\leq j\}\cup\{I_n^{(i)}=n\}}\right)\rightarrow 0\label{trivial-cond}
\end{align}
for all $1\leq i\leq m$ and $j\in{\mathbb N}$, where $\|\cdot\|_{\text{op}}$ denotes the operator norm of a matrix.

First, recall that from Subsection 3.1, we have
\[
\frac{T_n^{(\star)}-\mu_n^{(\star)}+\sum_{i=1}^{m}\mu_{i}^{(\star)}}{\sqrt{n}}\stackrel{L_s}{\longrightarrow}0
\]
for $\star\in\{k_1,k_2\}$. This together with the boundedness of $\Omega_1(n),\Omega_2(n),\Omega_3(n)$ (from Proposition \ref{lin-var}) and $D(n)$ (from the proof of Proposition \ref{qua-cov}) shows the claimed result for $b_n^{(1)}$ and $b_n^{(2)}$ in (\ref{mcc}).

Next, to show the second claim in (\ref{mcc}), we argue as in the proof of (\ref{cond-2}) in Theorem \ref{limit-law}. For instance, for the expressions in $A_n^{(i)}(1,1)$, we obtain
\[
\frac{\Omega_1(I_n^{(i)})+\Omega_2(I_n^{(i)})+2\sqrt{D(I_n^{(i)})}}{\Omega_1(n)+\Omega_2(n)+2\sqrt{D(n)}}\stackrel{
\text{a.s.}}{\longrightarrow} 1
\]
and
\[
\frac{\left(\Omega_1(I_n^{(i)})+\sqrt{D(I_n^{(i)})}\right)\left(\Omega_2(n)+\sqrt{D(n)}\right)-\Omega_3(n)\Omega_3(I_n^{(i)})}
{2D(n)+(\Omega_1(n)+\Omega_2(n))\sqrt{D(n)}}\stackrel{\text{a.s.}}{\longrightarrow} 1
\]
which are proved similar as (\ref{step-2}). Plugging this into the expression for $A_n^{(i)}(1,1)$ and using (\ref{step-1}) then gives
\[
A_n^{(i)}(1,1)\stackrel{\text{a.s.}}{\longrightarrow}\sqrt{p_i}.
\]
By dominated convergence, the same holds in $L_s$. Similarly, the other entries of $A_n^{(i)}$ are treated. Overall, we obtain
\begin{equation}\label{conv-mat}
A_n^{(i)}\stackrel{L_s}{\longrightarrow}\sqrt{p_i}I_2
\end{equation}
which shows the second claim in (\ref{mcc}).

From (\ref{conv-mat}) it follows immediately that $\|A_i\|_{\text{op}}=\sqrt{p_i}$. Using this, the two conditions in (\ref{trivial-cond}) are easily checked.

Finally, by applying the multivariate contraction method, we obtain convergence in distribution of the random vector from Theorem \ref{main-result-2} to a random variable whose distribution is the unique solution of a distributional fixed point equation (see \cite{NeRu2}). It is easily verified that the only solution of this fixed point equation is the (2-dimensional) standard normal distribution. This completes the proof of Theorem \ref{main-result-2}.\qed

\section{Size, Total Path Length and Wiener Index}

This section will be concerned with the proof of Theorem \ref{main-result-3}.  We start by recalling the definition of $T_n^{(\star)}$ and $W_n^{(\star)}$ from the introduction: $T_n^{(\star)}$ is the internal path length and $W_n^{(\star)}$ is the internal Wiener index. Here, $\star\in\{T,P\}$ depending on whether tries or PATRICIA tries are considered (in the latter case, we have in addition that $m\geq 3$). We will only give the proof for PATRICIA tries, the proof for tries being similar. For the sake of simplicity, we are going to drop all superindices.

First, observe that the internal path length and internal Wiener index satisfy the following distribution recurrences for $n\geq 2$
\begin{equation}\label{rec-tn}
T_n\stackrel{d}{=}\begin{cases}\sum_{i=1}^{m}\left(T_{I_n^{(i)}}^{(i)}+N_{I_n^{(i)}}^{(i)}\right),&\text{if $I_n^{(i)}\ne n$ for all $i$};\\
T_n,&\text{otherwise}\end{cases}
\end{equation}
and
\begin{equation}\label{rec-wn}
W_n\stackrel{d}{=}\begin{cases}\sum_{i=1}^{m}\left(W_{I_n^{(i)}}^{(i)}+T_{I_n^{(i)}}^{(i)}+N_{I_n^{(i)}}^{(i)}\right)+\sum_{(i,j)\in S_2}N_{I_n^{(i)}}^{(i)}
\Big(T_{I_n^{(j)}}^{(j)}+N_{I_n^{(j)}}^{(j)}\Big),&\text{if $I_n^{(i)}\ne n$ for all $i$};\\
W_n,&\text{otherwise},\end{cases}
\end{equation}
where notation is as in Section \ref{intro}, $S_2=\{(i,j)\ :\ 1\leq i,\leq m, i\ne j\}$ and $T_0=T_1=W_0=W_1=0$.

\paragraph{Mean Values.} We consider Poisson generating functions
\[
\tilde{f}_{N}(z)=e^{-z}\sum_{n\geq 0}{\mathbb E}(N_n)\frac{z^n}{n!},\quad \tilde{f}_{T}(z)=e^{-z}\sum_{n\geq 0}{\mathbb E}(T_n)\frac{z^n}{n!},\quad
\tilde{f}_{W}(z)=e^{-z}\sum_{n\geq 0}{\mathbb E}(W_n)\frac{z^n}{n!}.
\]

Then, from (\ref{rec-tn}) and (\ref{rec-wn}),
\begin{equation}\label{pois-tn}
\tilde{f}_T(z)=\sum_{i=1}^{m}\tilde{f}_T(p_iz)+\sum_{i=1}^{m}\tilde{f}_N(p_iz)-\sum_{i=1}^{m}e^{(p_i-1)z}\tilde{f}_N(p_iz)
\end{equation}
and
\begin{align}
\tilde{f}_W(z)=&\sum_{i=1}^{m}\tilde{f}_W(p_iz)+\sum_{(i,j)\in S_2}\tilde{f}_{N}(p_iz)\tilde{f}_T(p_jz)+\sum_{(i,j)\in S_2}\tilde{f}_{N}(p_iz)\tilde{f}_N(p_jz)\nonumber\\
&\qquad+\sum_{i=1}^{m}\left(\tilde{f}_{T}(p_iz)+\tilde{f}_{N}(p_iz)\right)-\sum_{i=1}^{m}e^{(p_i-1)z}\left(\tilde{f}_T(p_iz)+\tilde{f}_N(p_iz)\right).
\label{pois-wn}
\end{align}

Recall that from Theorem \ref{main-result-1}, we have, as $n\rightarrow\infty$,
\[
{\mathbb E}(N_n)\sim nP(\log_{1/a}n),
\]
where $P(z)$ is an infinitely differentiable, $1$-periodic function (possibly constant). We show now the following result.
\begin{pro}\label{mean-values}
We have, as $n\rightarrow\infty$,
\[
{\mathbb E}(T_n)\sim h^{-1}n\log nP(\log_{1/a}n),\qquad {\mathbb E}(W_n)\sim h^{-1}n^2\log nP(\log_{1/a}n)^2.
\]
\end{pro}
\pf We show these asymptotic expansions (with $n$ replaced by $z$) for $\tilde{f}_T(z)$ and $\tilde{f}_W(z)$. The above results follow then by the theory of JS-admissibility; see the explanation in Section \ref{pre} and \cite{FuHwZa}.

First, we need the following expansion which follows from the analysis of $N_n$
\begin{equation}\label{exp-fnz}
\tilde{f}_{N}(z)=\sum_{\omega_{l}\in{\mathbb Z}_{<\epsilon}}G_1(\omega_{\ell})z^{-\omega_l}+{\mathcal O}(z^{\epsilon})
\end{equation}
uniformly in $z$ with $\vert\arg(z)\vert\leq\phi$ and $0<\phi<\pi/2$; see the discussion in Section \ref{pre} and \cite{FuHwZa}. Note that the same asymptotic expansion also holds for
\[
\sum_{i=1}^{m}\tilde{f}_{N}(p_iz)=\sum_{\omega_{l}\in{\mathbb Z}_{<\epsilon}}G_1(\omega_{\ell})z^{-\omega_l}+{\mathcal O}(z^{\epsilon}).
\]

By the direct mapping theorem in \cite{FlGoDu} this implies that the Mellin transform
\[
G_{T}^{(1)}(\omega)={\mathscr M}\left[\sum_{i=1}^{m}\tilde{f}_{N}(p_iz);\omega\right],\qquad \omega\in\langle -2,-1\rangle,
\]
can be extended to a meromorphic function in $\langle -2,-\epsilon\rangle$ with simply poles at $\omega=\omega_l, \omega_l\in{\mathcal Z}_{<\epsilon}$ and residue $-G_1(\omega_{\ell})$. Also, again by (\ref{exp-fnz}),
\[
G_{T}^{(2)}(\omega)={\mathscr M}\left[-\sum_{i=1}^{m}e^{(p_i-1)z}\tilde{f}_N(p_iz);\omega\right]
\]
is analytic in $\langle -2,-\epsilon\rangle$. Finally, observe that by results from Section 8 in \cite{FlGoDu} both $G_{T}^{(1)}(z)$ and $G_{T}^{(2)}(z)$ decay exponentially along vertical lines in $\langle -2,-\epsilon\rangle$.

Now, set
\[
F_{T}(\omega)={\mathscr M}[\tilde{f}_{N}(z);\omega].
\]
Then, from (\ref{pois-tn}), we obtain
\begin{equation}\label{mel-ftz}
F_{T}(\omega)=\frac{G_{T}^{(1)}(\omega)+G_{T}^{(2)}(\omega)}{1-\sum_{i}p_i^{-\omega}}.
\end{equation}
Using inverse Mellin transform gives the claimed expansion for the mean of $T_n$.

As for the mean of $W_n$, similar arguments can be used. We only give a sketch. Set
\[
F_{W}(\omega)={\mathscr M}[\tilde{f}_{N}(z)-cz^2;\omega],
\]
where $cz^2$ is the first term in the Maclaurin series of $\tilde{f}_N(z)$ (subtracting this term is necessary for existence of the Mellin transform). Then, from (\ref{pois-wn}), we obtain
\begin{equation}\label{mel-fwz}
F_{W}(\omega)=\frac{G_{W}(\omega)}{1-\sum_{i}p_i^{-\omega}},
\end{equation}
where now the main contribution to $G_{W}(\omega)$ comes from
\[
{\mathscr M}\left[\sum_{(i,j)\in S_2}\tilde{f}_{N}(p_iz)\tilde{f}_T(p_jz);\omega\right]
\]
which has double poles at $\omega=-\omega_{l_1}-\omega_{l_2},\omega_{l_1},\omega_{l_2}\in{\mathcal Z}_{<\epsilon}$. Carefully analyzing the main term of the Laurent series expansion at the singularities (which is again done with the direct mapping theorem together with (\ref{exp-fnz}) and the corresponding expansion for $\tilde{f}_T(z)$ which one obtains from (\ref{mel-ftz}) by inverse Mellin transform) and applying inverse Mellin transform to (\ref{mel-fwz}) then gives the claimed result for the mean of $W_n$.

As an example, assume that we are in the irrational case. Then, the only singularity of $G_{W}(\omega)$ with $\Re(\omega)=-2$ is $-2$. The Laurent series of $G_W(\omega)$ at $\omega=-2$ starts as follows
\[
\left(\sum_{(i,j)\in S_2}p_ip_j\right)\frac{G_1(-1)^2}{h(w+2)^2}+\cdots
\]
Consequently, by inverse Mellin transform applied to (\ref{mel-fwz}), we obtain for the main term of $\tilde{f}_W(z)$
\[
\frac{\sum_{(i,j)\in \tilde{S}}p_ip_j}{1-\sum_{i}p_i^{2}}\cdot\frac{G_1(-1)^2}{h}z^2\log z=\frac{G_1(-1)^2}{h}z^2\log z
\]
which then gives the claimed result.\qed

\paragraph{Variance and Covariances.} Here, we consider the variances and covariances of $N_n,T_n$ and $W_n$. Again, we can restrict ourself to the Poisson model. Let $\tilde{f}_{N^2}(z)$, $\tilde{f}_{N,T}(z)$, $\tilde{f}_{T^2}(z)$, $\tilde{f}_{N,W}(z)$, $\tilde{f}_{T,W}(z)$ and $\tilde{f}_{W^2}(z)$ denote the Poisson generating functions of ${\mathbb E}(N_n^2)$, ${\rm Cov}(N_n,T_n)$, ${\mathbb E}(T_n^2)$, ${\rm Cov}(N_n,W_n)$, ${\rm Cov}(T_n,W_n)$ and ${\mathbb E}(W_n^2)$, respectively. Moreover, consider corrected poissonized variances and covariances:
\begin{align*}
\tilde{V}_N(z)&=\tilde{f}_{N^2}(z)-\tilde{f}_{N}(z)^2-z\tilde{f}'_{N}(z)^2,\\
\tilde{C}_{N,T}(z)&=\tilde{f}_{N,T}(z)-\tilde{f}_{N}(z)\tilde{f}_{T}(z)-z\tilde{f}'_{N}(z)\tilde{f}'_{T}(z),\\
\tilde{V}_T(z)&=\tilde{f}_{T^2}(z)-\tilde{f}_{T}(z)^2-z\tilde{f}'_{T}(z)^2,\\
\tilde{C}_{N,W}(z)&=\tilde{f}_{N,W}(z)-\tilde{f}_{N}(z)\tilde{f}_{W}(z)-z\tilde{f}'_{N}(z)\tilde{f}'_{W}(z),\\
\tilde{C}_{T,W}(z)&=\tilde{f}_{T,W}(z)-\tilde{f}_{T}(z)\tilde{f}_{W}(z)-z\tilde{f}'_{T}(z)\tilde{f}'_{W}(z),\\
\tilde{V}_W(z)&=\tilde{f}_{W^2}(z)-\tilde{f}_{W}(z)^2-z\tilde{f}'_{W}(z)^2.
\end{align*}
These functions correspond to the variances and covariances in the Poisson model; see \cite{FuHwZa} and \cite{HwFuZa}. Functional equations which are obtained from (\ref{rec-tn}), (\ref{rec-wn}) and (\ref{pois-tn}) and (\ref{pois-wn}) are collected in Appendix B.

Recall now, that from Theorem \ref{main-result-1}, we have, as $n\rightarrow\infty$,
\[
{\rm Var}(N_n)\sim nQ(\log_{1/a}n),
\]
where $Q(z)$ is an infinite differentiable, $1$-periodic function (possibly zero). As for the other variances and covariances, we have the following result.
\begin{pro}\label{variances}
We have, as $n\rightarrow\infty$,
\begin{align*}
{\rm Cov}(N_n,T_n)&\sim h^{-1}n\log nQ(\log_{1/a}n),\\
{\rm Var}(T_n)&\sim h^{-2}n\log^2nQ(\log_{1/a}n),\\
{\rm Cov}(N_n,W_n)&\sim 2h^{-1}n^2\log nP(\log_{1/a}n)Q(\log_{1/a}n),\\
{\rm Cov}(T_n,W_n)&\sim 2h^{-2}n^2\log^2nP(\log_{1/a}n)Q(\log_{1/a}n),\\
{\rm Var}(W_n)&\sim 4h^{-2}n^3\log^2nP(\log_{1/a}n)^2Q(\log_{1/a}n).
\end{align*}
In particular,
\[
\rho(N_n,T_n)\longrightarrow 0,\quad \rho(N_n,W_n)\longrightarrow 0,\quad \rho(T_n,W_n)\longrightarrow 0,
\]
where $\rho(\cdot,\cdot)$ denotes the correlation coefficient.
\end{pro}
\pf Similar to Proposition \ref{mean-values}.\qed

\paragraph{Limit Law.} What is left is the proof of the trivariate limit law in Theorem \ref{main-result-3}. For the proof, we argue as in \cite{FuLe}. For the readers convenience we repeat the (easy) argument. Let $X$ be a random variable with a standard normal distribution. Then, from Corollary \ref{cor-size},
\begin{equation}\label{ll-step1}
\left(\frac{N_n-{\mathbb E}(N_n)}{\sqrt{{\rm Var}(N_n)}},\frac{N_n-{\mathbb E}(N_n)}{\sqrt{{\rm Var}(N_n)}},\frac{N_n-{\mathbb E}(N_n)}{\sqrt{{\rm Var}(N_n)}}\right)\stackrel{d}{\longrightarrow}(X,X,X).
\end{equation}
Now, set
\begin{align*}
U_n&=\frac{T_n-{\mathbb E}(T_n)}{\sqrt{{\rm Var}(T_n)}}-\frac{N_n-{\mathbb E}(N_n)}{\sqrt{{\rm Var}(N_n)}},\\
V_n&=\frac{W_n-{\mathbb E}(W_n)}{\sqrt{{\rm Var}(W_n)}}-\frac{N_n-{\mathbb E}(N_n)}{\sqrt{{\rm Var}(N_n)}}.
\end{align*}
Note that
\[
{\mathbb E}(U_n^2)=2-2\rho(N_n,T_n),\qquad{\mathbb E}(V_n^2)=2-2\rho(N_n,W_n).
\]
From this and Proposition \ref{variances}, we obtain that $U_n,V_n\stackrel{P}{\longrightarrow}0$, where $\stackrel{P}{\longrightarrow}$ denotes convergence in probability. Thus,
\[
\left(0,U_n,V_n\right)\stackrel{P}{\longrightarrow}(0,0,0).
\]
By Slutsky's theorem, the latter can be added to (\ref{ll-step1}) which yields the result.

\section{Conclusion}
In this paper, we showed that the recent framework from \cite{FuHwZa} for deriving asymptotic expansions of mean and variance of additive shape parameters in tries and PATRICIA tries can be modified to obtain central limit theorems, too. We used this modified framework to give a multivariate study of the number of nodes of fixed out-degree in tries (which generalizes the size of tries and PATRICIA tries). Moreover, we proved multivariate central limit theorem for size, internal path length and internal Wiener index in tries and PATRICIA tries. The latter Wiener index is one more type of Wiener index; see \cite{FuLe} for many other types.

Our framework can be applied to other parameters as well. One example is the number of $2$-protected nodes (internal nodes with a distance at least two to a leaf) which was recently studied by Gaither et al. \cite{GaHoSeWa} and Gaither and Ward \cite{GaWa}. Indeed, it is easily seen that this parameter is also an additive shape parameter. So, our results can be used to re-derive the results of \cite{GaHoSeWa} and \cite{GaWa} and add a central limit theorem (which was conjectured in \cite{GaWa}). Details might appear elsewhere.

\section*{Acknowledgments}

The authors are indebted to the anonymous reviewer for pointing out that more emphasis should be put on Theorem \ref{limit-law}, in particular, for her/his suggestion to move this result from Section \ref{mom-and-ll} to the introduction.

\begin{thebibliography}{99}
\bibitem{Bo} J. Bourdon (2001). Size and path length of Patricia tries: dynamical sources context, Random Structures Algorithms, {\bf 19}, 289--315.
\bibitem{Br} R. De la Briandais (1959). File searching using variable length keys, In Papers presented at the {\it Western Joint Computer Conference} (March 3-5, 1959), {\it ACM}, 295--298.
\bibitem{ClFlVa} J. Cl\'{e}ment, P. Flajolet, and B. Vall\'{e}e (2001). Dynamical sources in information theory: A general analysis of trie structures, {\it Algorithmica}, {\bf 29:1}, 307--369.
\bibitem{FlGoDu} P. Flajolet, X. Gourdon, and P. Dumas (1995). Mellin transforms and asymptotics: Harmonic sums, {\it Theor. Comput. Sci.}, {\bf 144}, 3--58.
\bibitem{FlRoVa} P. Flajolet, M. Roux, and B. Vall\'{e}e (2010). Digital trees and memoryless sources: from arithmetics to analysis. In {\it 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)}, {\it Discrete Math. Theor. Comput. Sci. Proc.}, 233--260.
\bibitem{FlSe2} P. Flajolet and R. Sedgewick (1995). Mellin transforms and asymptotics: Finite diferences and Rice's integrals, {\it Theoret. Comp. Sci.}, {\bf 144}, 101--124.
\bibitem{FlSe} P. Flajolet and R. Sedgewick. {\it Analytic Combinatorics}, Cambridge University Press, Cambridge, 2009.
\bibitem{FuHwZa} M. Fuchs, H.-K. Hwang, and V. Zacharovas. An analytic approach to the asymptotic variance of trie statistics and related structures, submitted.
\bibitem{FuLe} M. Fuchs and C.-K. Lee. The Wiener index of random digital trees, submitted.
\bibitem{GaHoSeWa} J. Gaither, Y. Homma, M. Sellke, and M. D. Ward (2012). On the number of 2-protected nodes in tries and suffix trees, In {\it 23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'12)}, {\it Discrete Math. Theor. Comput. Sci. Proc.}, 381--398.
\bibitem{GaWa} J. Gaither and M. D. Ward (2013). The variance of the number of $2$-protected nodes in tries, In {\it Proceedings of the Eighth Workshop on Analytic Algorithmics and Combinatorics (ANALCO)}, 43--51.
\bibitem{Gw} G. Gwehenberger (1968). Anwendung einer bin\"{a}ren Verweiskettenmethode beim Aufbau von Listen, {\it Elektronische Rechenanlagen}, {\bf 10}, 223--226.
\bibitem{Ha} W. K. Hayman (1956). A generalisation of Stirling's formula, {\it J. Reine Angew. Math.}, {\bf 196}, 67--95.
\bibitem{HuHwLeMaPr} F. Hubalek, H.-K. Hwang, W. Lew, H. Mahmoud, and H. Prodinger (2002). A multivariate view of random bucket digital search trees, {\it J. Algorithms}, {\bf 44:1}, 121--158.
\bibitem{HwFuZa} H.-K. Hwang, M. Fuchs, and V. Zacharovas (2010). Asymptotic variance of random
    symmetric digital search trees, {\it Discrete Math. Theor. Comput. Sci.}, {\bf 12:2}, 103--165.
\bibitem{JaRe} P. Jacquet and M. R\'{e}gnier (1988). Normal limiting distribution of the size of tries, In {\it Performance'87} (Brussels, 1987), North-Holland, Amsterdam, 209--223.
\bibitem{JaSz} P. Jacquet and W. Szpankowski (1998). Analytical de-Poissonization and its applications, {\it Theoret. Comput. Sci.}, {\bf 201:1-2}, 1--62.
\bibitem{Kn} D. E. Knuth. {\it The Art of Computer Programming, volume 3: Sorting and Searching}, Addison-Wesley,
1973, Second edition, 1998.
\bibitem{Le} C.-K. Lee. Ph.D.-thesis, National Chiao Tung University, in preparation.
\bibitem{Mo} D. R. Morrison (1968). PATRICIA - Practical Algorithm To Retrieve Information Coded In Alphanumeric, {\it J. ACM}, {\bf 15}, 514--534.
\bibitem{NeRu} R. Neininger and L. R\"{u}schendorf (2004). A general limit theorem for recursive algorithms and combinatorial structures, {\it Ann. Appl. Probab.}, {\bf 14:1}, 378--418.
\bibitem{NeRu2} R. Neininger and L. R\"{u}schendorf (2006). A survey of multivariate aspects of the contraction method, {\it Discrete Math. Theor. Comput. Sci.}, {\bf 8}, 31--56.
\bibitem{PaHwNiSz} G. Park, H.-K. Hwang, P. Nicod\`{e}me, and W. Szpankowski (2009). Profiles of tries, {\it SIAM J. Comput.}, {\bf 38:5}, 1821--1880.
\bibitem{Sc} W. Schachinger (1995). On the variance of a class of inductive valuations of data structures for digital search, {\it Theoret. Comput. Sci.}, {\bf 144}, 251--275.
\bibitem{Va} B. Vall\'{e}e (2001), Dynamical sources in information theory: Fundamental intervals and word prefixes, {\it Algorithmica}, 29:1-2, (2001), 262--306.
\end{thebibliography}

\section*{Appendix A}

We will use the following notations
\[
\Omega_1(n)=Q^{(k_1)}(\log_{1/a}n),\qquad\Omega_2(n)=Q^{(k_2)}(\log_{1/a}n),\qquad\Omega_3(n)=Q^{(k_1,k_2)}(\log_{1/a}n)
\]
and
\[
D(n)=\Omega_1(n)\Omega_2(n)-\Omega_3(n)^2.
\]
Then,
\begin{align*}
b_n^{(1)}&=\frac{T_n^{(k_1)}-\mu_n^{(k_1)}+\sum_{i=1}^m\mu_{I_i}^{(k_1)}}{\sqrt{n}}\cdot\frac{\left(\Omega_1(n)+
\sqrt{D(n)}\right)\left(\sqrt{\Omega_1(n)+\Omega_2(n)+2\sqrt{D(n)}}\right)}{2D(n)+(\Omega_1(n)+\Omega_2(n))\sqrt{D(n)}}\\
&\qquad\quad-\frac{T_n^{(k_2)}-\mu_n^{(k_2)}+\sum_{i=1}^m\mu_{I_i}^{(k_2)}}{\sqrt{n}}\cdot\frac{\Omega_3(n)
\sqrt{\Omega_1(n)+\Omega_2(n)+2\sqrt{D(n)}}}{2D(n)+(\Omega_1(n)+\Omega_2(n))\sqrt{D(n)}},\\
b_n^{(2)}&=\frac{T_n^{(k_2)}-\mu_n^{(k_2)}+\sum_{i=1}^m\mu_{I_i}^{(k_2)}}{\sqrt{n}}\cdot\frac{\left(\Omega_2(n)+
\sqrt{D(n)}\right)\left(\sqrt{\Omega_1(n)+\Omega_2(n)+2\sqrt{D(n)}}\right)}{2D(n)+(\Omega_1(n)+\Omega_2(n))\sqrt{D(n)}}\\
&\qquad\quad-\frac{T_n^{(k_1)}-\mu_n^{(k_1)}+\sum_{i=1}^m\mu_{I_i}^{(k_1)}}{\sqrt{n}}\cdot\frac{\Omega_3(n)
\sqrt{\Omega_1(n)+\Omega_2(n)+2\sqrt{D(n)}}}{2D(n)+(\Omega_1(n)+\Omega_2(n))\sqrt{D(n)}}
\end{align*}
and
\begin{align*}
A_n^{(i)}(1,1)&=B_n^{(i)}\cdot\frac{\left(\Omega_1(I_n^{(i)})+\sqrt{D(I_n^{(i)})}\right)\left(\Omega_2(n)+
\sqrt{D(n)}\right)-\Omega_3(n)\Omega_3(I_r^{(n)})}{2D(n)+(\Omega_1(n)+\Omega_2(n))\sqrt{D(n)}},
\end{align*}
\begin{align*}
A_n^{(i)}(1,2)&=B_n^{(i)}\cdot\frac{\Omega_3(I_n^{(i)})\left(\Omega_2(n)+\sqrt{D(n)}\right)-\Omega_3(n)\left(\Omega_2(I_n^{(i)})+
\sqrt{D(I_n^{(i)})}\right)}{2D(n)+(\Omega_1(n)+\Omega_2(n))\sqrt{D(n)}},\\
A_n^{(i)}(2,1)&=B_n^{(i)}\cdot\frac{\Omega_3(I_n^{(i)})\left(\Omega_1(n)+\sqrt{D(n)}\right)-\Omega_3(n)\left(\Omega_1(I_n^{(i)})+
\sqrt{D(I_n^{(i)})}\right)}{2D(n)+(\Omega_1(n)+\Omega_2(n))\sqrt{D(n)}},\\
A_n^{(i)}(2,2)&=B_n^{(i)}\cdot\frac{\left(\Omega_1(n)+\sqrt{D(n)}\right)\left(\Omega_2(I_n^{(i)})+
\sqrt{D(I_n^{(i)})}\right)-\Omega_3(n)\Omega_3(I_r^{(n)})}{2D(n)+(\Omega_1(n)+\Omega_2(n))\sqrt{D(n)}},
\end{align*}
where
\[
B_n^{(i)}=\sqrt{\frac{I_n^{(i)}}{n}}\cdot\sqrt{\frac{\Omega_1(n)+\Omega_2(n)+2\sqrt{D(n)}}{\Omega_1(I_n^{(i)})+
\Omega_2(I_n^{(i)})+2\sqrt{D(I_n^{(i)})}}}.
\]

\section*{Appendix B}

We give all functional equations in the form
\[
\tilde{f}(z)=\sum_{i=1}^{m}\tilde{f}(p_iz)+\tilde{g}(z),
\]
where for $\tilde{g}(z)$ we only give the main term and size of the error term (this is sufficient for obtaining the main terms in Proposition \ref{variances}; see the proof of Proposition \ref{mean-values}). For precise expressions of $\tilde{g}(z)$ see Lee \cite{Le}.

We have,
\begin{align*}
\tilde{C}_{N,T}(z)&=\sum_{i=1}^{m}\tilde{C}_{N,T}(p_iz)+\sum_{i=1}^{m}\tilde{V}_N(p_iz)+\tilde{g}_{N,T}(z),\\
\tilde{V}_T(z)&=\sum_{i=1}^{m}\tilde{V}_T(p_iz)+2\sum_{i=1}^{m}\tilde{C}_{N,T}(p_iz)+\tilde{g}_T(z),\\
\tilde{C}_{N,W}(z)&=\sum_{i=1}^{m}\tilde{C}_{N,W}(p_iz)+\sum_{(i,j)\in S_2}\left(\tilde{V}_N(p_iz)\tilde{f}_T(p_jz)
+\tilde{C}_{N,T}(p_iz)\tilde{f}_N(p_jz)\right)+\tilde{g}_{N,W}(z),\\
\tilde{C}_{T,W}(z)&=\sum_{i=1}^{m}\tilde{C}_{T,W}(p_iz)+\sum_{(i,j)\in S_2}\left(\tilde{C}_{N,T}(p_iz)\tilde{f}_T(p_jz)+\tilde{V}_T(p_iz)\tilde{f}_N(p_jz)\right)+\tilde{g}_{T,W}(z),\\
\tilde{V}_W(z)&=\sum_{i=1}^{m}\tilde{V}_W(p_iz)+\sum_{(i,j)\in S_2}\Big(\tilde{V}_N(p_iz)\tilde{f}_T(p_jz)^2
+2\tilde{C}_{N,T}(p_iz)\tilde{f}_N(p_jz)\tilde{f}_T(p_jz)\\
&\quad+\tilde{V}_T(z)\tilde{f}_N(p_jz)^2
+2\tilde{C}_{N,W}\tilde{f}_T(p_jz)+2\tilde{C}_{T,W}(p_iz)\tilde{f}_N(p_jz)\Big)
\end{align*}
\begin{align*}
&\quad+\sum_{(i,j,k)\in S_3}\Big(\tilde{V}_N(p_iz)\tilde{f}_T(p_jz)\tilde{f}_T(p_kz)
+2\tilde{C}_{N,T}(p_iz)\tilde{f}_N(p_jz)\tilde{f}_T(p_kz)\\
&\quad+\tilde{V}_T(p_iz)\tilde{f}_N(p_jz)\tilde{f}_N(p_kz)\Big),
\end{align*}
where $S_3=\{(i,j,k)\ : 1\leq i,j,k\leq m, i\ne j, j\ne k, i\ne k\}$ and
\begin{align*}
\tilde{g}_{N,T}(z)&=o(z),\\
\tilde{g}_{T}(z)&={\mathcal O}(z),\\
\tilde{g}_{N,W}(z)&={\mathcal O}(z^2),\\
\tilde{g}_{T,W}(z)&={\mathcal O}(z^2\log z),\\
\tilde{g}_{W}(z)&={\mathcal O}(z^3\log z)
\end{align*}
uniformly in $z$ with $\vert\arg(z)\vert\leq\phi$ and $0<\phi<\pi/2$.
\end{document}
