Iterative Reed–Muller Decoding

Marvin Geiselhart^*, Ahmed Elkelesh^*, Moustafa Ebada^*, Sebastian Cammerer^† and Stephan ten Brink^*  An extended version of this paper is available [1].

^*Institute of Telecommunications, Pfaffenwaldring 47, University of  Stuttgart, 70569 Stuttgart, Germany

^†NVIDIA, Fasanenstraße 81, 10623 Berlin, Germany

ECCerror-correcting code
HDDhard decision decoding
SDDsoft decision decoding
MLmaximum likelihood
GPUgraphical processing unit
BPbelief propagation
BPLbelief propagation list
LDPClow-density parity-check
HDPChigh density parity check
BERbit error rate
BPSKbinary phase shift keying
AWGNadditive white Gaussian noise
MSEmean squared error
LLRLog-likelihood ratio
LUTlook-up table
MAPmaximum a posteriori
NEnormalized error
BLERblock error rate
PEprocessing elements
SCLsuccessive cancellation list
SCsuccessive cancellation
SCANsoft cancellation
BI-DMCBinary Input Discrete Memoryless Channel
CRCcyclic redundancy check
CA-SCLCRC-aided successive cancellation list
BECBinary Erasure Channel
BSCBinary Symmetric Channel
PSCLpartitioned successive cancellation list
3GPP3rd Generation Partnership Project
eMBBenhanced Mobile Broadband
PCCparity-check concatenated
CA-polar codesCRC-aided polar codes
CNcheck node
VNvariable node
GenAlgGenetic Algorithm
AIArtificial Intelligence
MCMonte Carlo
CSIChannel State Information
PSCLpartitioned successive cancellation list
OSDordered statistic decoding
MWPC-BPminimum-weight parity-check BP
FFGForney-style factor graph
MBBPmultiple-bases belief propagation
NBPneural belief propagation
URLLCultra-reliable low-latency communications
DMCdiscrete memoryless channel
MSBmost significant bit
LSBleast significant bit
RPArecursive projection-aggregation
SGDstochastic gradient descent

Reed–Muller (RM) codes are known for their good ML performance in the short block-length regime. Despite being one of the oldest classes of channel codes, finding a low complexity soft-input decoding scheme is still an open problem. In this work, we present a belief propagation (BP) decoding architecture for RM codes based on their rich automorphism group. The decoding algorithm can be seen as a generalization of multiple-bases belief propagation (MBBP) using polar BP as constituent decoders. We provide extensive error-rate performance simulations and compare our results to existing decoding schemes. We report a near-ML performance for the RM(3,7)-code (e.g., $0.05$ dB away from the ML bound at BLER of $10^{-4}$) at a competitive computational cost.
To the best of our knowledge, our proposed decoder achieves the best performance of all iterative RM decoders presented thus far.

§ INTRODUCTION

The current trend of URLLC applications has urged the need for efficient short length coding schemes in combination with the availability of efficient decoders.
Besides many other coding schemes, this has lead to the revival of one of the oldest error-correcting codes, namely RM codes [2, 3]
– potentially also due to some existent similarities between RM codes and the newly developed family of polar codes [4, 5].
On the one hand, RM codes, as an example of algebraic codes, are known to be capacity-achieving over the BEC for a given rate [6, 7]. Moreover, and practically even more relevant, they enjoy an impressive error-rate performance under ML decoding, which also holds in the short length regime.
To this extent, several decoding algorithms have been developed in the course of RM decoding. On the other hand, to the best of our knowledge, there is still a lack of practical decoders that are characterized by near-ML performance and feasible decoding complexity/latency.

Block diagram of automorphism ensemble decoding. We focus on the case where $ M $ constituent BP decoders are used.
The usage of SC and SCL as constituent decoders is presented in the extended version of this paper [1].

RM decoders can be grouped into two main categories, iterative and non-iterative decoders which we will shortly revisit in the following.
In the literature, the best known decoder for RM codes over an AWGN channel is Dumer’s recursive list decoding algorithm [8], which is now known under the name SCL decoding [9], and a variant using permutations.
Recently, a RPA decoding algorithm for RM codes was proposed in [10], which can be viewed as a weighted BP decoder over a redundant factor graph [11], making use of the symmetry of the RM codes (i.e., its large automorphism group).
RM codes under RPA decoding were shown to outperform the error-rate performance of CRC-aided polar codes under SCL decoding.
A more general usage of the rich automorphism group of RM codes to aid the decoding process is reported in [5], along with the decoding of RM codes using a redundant parity-check matrix proposed earlier in [12].
In this work, for the sake of comparison, we consider the following iterative decoders: multiple-bases belief propagationMBBP (MBBP) decoding [13], minimum weight parity-check belief propagationMWPC-BP (MWPC-BP) decoding [14], neural belief propagationNBP (NBP) decoding [15], pruned neural belief propagation (pruned-NBP) decoding [16].
The inherent parallel nature of iterative decoders allows high throughput implementations.
Besides, their SISO nature makes them suitable for iterative detection and decoding.

In this paper, we propose a new iterative decoding scheme, extending and generalizing some of the previously mentioned decoding algorithms.
To the best of our knowledge, our proposed decoding algorithm achieves the best practical iterative decoding performance of the RM(3,7)-code presented thus far ($0.05$ dB away from the ML bound at BLER of $10^{-4}$).
Fig. <ref> shows an abstract view of our proposed decoding algorithm.

§ PRELIMINARIES

§.§ Reed–Muller Codes

We interpret each message of an RM($ r $,$ m $) code as a multi-linear polynomial $ u(\zv) $ in $ m $ binary variables $ z_j $ (with $j\in\{0,\cdots,m-1\}$) and maximum degree $ r $, over the finite field $ \FF_2 $. To obtain the codeword $ \xv $, the message polynomial is evaluated at all points in the space $ \FF_2^m $, resulting in $ N = 2^m $ codeword bits [2, 3].

§.§ Automorphism Group

The automorphism group (or permutation group) $ \operatorname{Aut}(\mathcal{C}) $ of a code $ \mathcal{C} $ is the set of permutations $ \pi $ of the codeword bit indices that map $ \mathcal{C} $ onto itself, i.e.

\begin{equation}
\pi(\xv) \in \mathcal{C} \quad \forall \xv \in \mathcal{C} \quad \forall \pi \in \operatorname{Aut}(\mathcal{C}),
\end{equation}

where $ \pi(\xv) $ results in the vector $ \xv' $ with $ x_i' = x_{\pi(i)} $. In other words, every codeword is mapped to another (not necessarily different) codeword of the same code.
The automorphism group of RM codes is well known as the general affine group GA($ m $) over the field $ \FF_2 $[17].[In this paper, we only consider the field $ \FF_2 $ and hence, we omit the size of the field in the notation, i.e., we write GA($ m $) instead of GA($ m,2 $).] GA($ m $) is the group of all affine bijections over $ \FF_2^m $, i.e., pairs $ (\Am, \bv) $ defining the mapping $ \zv' = \Am \zv + \bv $, with a non-singular matrix $ \Am \in \FF_2^{m\times m}$ and an arbitrary vector $ \bv \in \FF_2^{m\times 1} $. The vectors $ \zv$, $\zv' \in \FF_2^{m\times 1} $ are the binary representations of the code bit positions $ i $ and $ \pi(i) $, respectively, i.e., $ i = \sum_{j=0}^{m-1}{z_j \cdot 2^j} $. An important subgroup of GA($ m $) is the set of stage-shuffle permutations $ \Pi(m) $, corresponding to the special case where $ \Am $ is a permutation matrix and $ \bv=\zerov $.

§.§ Iterative RM Decoding

In this section, we briefly revise the different iterative decoding techniques which can be used for RM codes.

§.§.§ Naïve Belief Propagation Decoding

BP decoding can be performed over the Tanner graph of a code's parity-check matrix. However, for high-density parity-check codes like RM codes, the performance of this decoder is usually poor due to the numerous short cycles in the graph.

§.§.§ Belief Propagation Decoding over Forney-style Factor Graph

Rather than on a Tanner graph, BP decoding can also be performed over a FFG, constructed from check and variable nodes of degree three [18]. Fig. <ref> shows the FFG of the RM(1,3)-code.

As the frozen nodes always contribute the same LLR (i.e., a priori LLR of $ +\infty $) to the equations, the FFG can be reduced as shown on the right in Fig. <ref>, by removing edges of constant value. This potentially reduces the number of performed arithmetic operations per iteration while preserving the same performance [18]. In this work, whenever the BP decoding is used over the FFG, we use the reduced version.

Forney-style factor graph (FFG) of the RM(1,3)-code (left) and the reduced FFG (right). Note that the dashed lines indicate variables to be computed only in the right-to-left message update.

§.§.§ Minimum Weight Parity-Check Belief Propagation Decoding

Minimum weight parity-check belief propagationMWPC-BP (MWPC-BP) decoding introduced in [14] is based on the concept of iterative decoding over an overcomplete parity-check matrix. An online algorithm tailored to the noisy received sequence $ \yv $ is used to construct the overcomplete parity-check matrix only based on minimum weight parity-checks.

§.§.§ Neural Belief Propagation Decoding

Neural belief propagationNBP (NBP) decoding as introduced in [15] treats the unrolled Tanner graph of the code as a neural network (NN), while assigning trainable weights to all of its edges leading to a soft Tanner graph. These trainable weights are optimized via SGD methods.

§.§.§ Pruned Neural Belief Propagation Decoding

Pruned neural belief propagation (pruned-NBP) decoding [16] combines the idea of MWPC-BP together with NBP. To get started, a redundant parity-check matrix containing (all or some of) the minimum weight parity-checks is constructed. During the offline training phase, all edges connected to a check node are assigned a single trainable weight and the least contributing check nodes are pruned (i.e., removed) from the graph. The authors of [16] refer to this decoder as $ D_1 $. An enhanced version,  decoder $ D_3 $, is the result of assigning trainable weights per edge at the expense of larger memory requirements to save all weights per edges. Furthermore, a pruned NBP decoder without any weights is introduced as $ D_2 $, however with the expense of a significant degradation in error-rate performance.

§ AUTOMORPHISM ENSEMBLE DECODING

Ensemble decoding uses multiple constituent decoders (i.e., a decoder ensemble of size $ M $) to generate a set of codeword estimates and selects one of these codewords, using a predefined metric, as the decoder output. Typically, a least-squares metric is used, as this corresponds to the ML decision for the AWGN channel. Hence, this method is also called ML-in-the-list. This can be formulated as

\begin{equation} \label{eq:mlinthelist}
\hat{\xv} = \argmin_{\hat{\xv}_j, j \in \LP 1, \dots, M\RP} \left\Vert \hat{\xv}_j - \yv \right\Vert^2 = \argmax_{\hat{\xv}_j, j \in \LP 1, \dots, M\RP} \sum_{i=0}^{N-1} \hat{x}_{j,i} \cdot y_i,
\end{equation}

where $ \hat{x}_{j,i} \in \LP \pm 1 \RP$, $\hat{\xv}_j$ is the estimated codeword from decoder $j$ for the received vector $ \yv $ and $\hat{\xv}$ is the final codeword estimate of the ensemble.

MBBP is a well-known example for ensemble decoding that uses $ M $ BP decoders, each based on a different random parity-check matrix [13]. Another instance of ensemble decoding is BPL decoding of polar codes, where the stages of the FFG are randomly permuted for each constituent decoder [19].

In this work, we propose automorphism ensemble BP decoding (Aut-$M$-BP) for RM codes. The main idea is to make use of the already existent polar BP decoder. Furthermore, we use the RM code symmetry in the decoding algorithm itself, as permuting a valid RM codeword with a permutation from the code's automorphism group results in another valid RM codeword.

An abstract view of our proposed Aut-$M$-BP decoding algorithm is shown in Fig. <ref>.
The input to the decoder is the received noisy codeword $\yv$.
We randomly sample $M$ different permutations from the RM automorphism group, where each permutation is denoted by $\pi_j$, with $j$ being the decoder index and $j \in \{1,2,\cdots,M\}$.
The $\yv$-vector is interleaved (i.e., permuted) with the $M$ different permutations $\pi_j$ leading to $M$ permuted noisy codewords $\yv'_j$, where $j \in \{1,2,\cdots,M\}$.
Now we decode every $\yv'_j$-vector independently using BP, whose output is the interleaved estimated codeword $\hat{\xv}'_j$.
A de-interleaving phase is applied to all $M$ interleaved estimated codewords $\hat{\xv}'_j$ and, thus, we have $M$ codeword estimates $\hat{\xv}_j$. Let $ \operatorname{BP}(\cdot) $ denote the BP decoding function that maps $ \yv'_j $ to $ \hat{\xv}_j' $. Then we can write the interleaved decoding as

\begin{equation}\label{eq:aut_dec}
\hat{\xv}_j = \pi^{-1}_j\left(\operatorname{BP}\left(\pi_j(\yv)\right)\right).
\end{equation}

Similar to MBBP and BPL decoding, our proposed decoding algorithm uses the ML-in-the-list picking rule according to Eq. (<ref>) to choose the most likely codeword from the list to get the final decoder output $\hat{\xv}$.

As the decoders are linear, their decoding behavior is only dependent on the noise induced by the channel, and not the choice of the transmitted codeword. Therefore, decoding using automorphisms according to Eq. (<ref>) corresponds to permuting the noise. It is reasonable to conclude that suboptimal (i.e., not ML) decoders may react differently to noise realizations in different permutations, which is exactly the property that automorphism ensemble decoding seeks to exploit.

Our proposed algorithm can be therefore seen as a natural generalization of the BPL decoder [19]: We still use $M$ parallel independent BP decoders. However, we use a more general set of permutations. It was shown in [20] that the stage-shuffling of the FFG is equivalent to a bit-interleaving operation while keeping the factor graph unchanged; these permutations correspond to the automorphism subgroup $ \Pi(m) $. In contrast, we use permutations from the whole RM code automorphism group $ \operatorname{GA}(m) $ (rather than only $\Pi(m)$, which is used in BPL decoding as proposed in [19]).

It is worth mentioning that the usage of a BP decoder as a constituent decoder has some similarities when compared to automorphism group decoding of BCH and Golay codes for the BEC [21] and for the AWGN channel [22].
Automorphism group decoding is based on permuting the received sequence exploiting automorphisms of the code while applying an iterative message passing algorithm.

BLER comparison between non SGD-optimized iterative decoders, recursive list decoding and our proposed Aut-BP decoding scheme for the RM(3,7)-code over the BI-AWGN channel.

§ RESULTS

Regarding practical applications, both error-rate performance and the computational complexity of the decoding scheme have to be considered. We compare the described decoding schemes for the RM(3,7)-code with $ N=128 $ and $ k=64 $. In the following, we specify the parameters of some of the compared decoders for reproducibility:

* MWPC-BP utilizes 5% of the minimum-weight parity-checks, as reported in [14].

* MBBP operates over $ M=60 $ randomly generated parity-check matrices with 6 iterations each.

* Neural-BP uses all 94488 minimum-weight parity-checks over 6 iterations.

* The pruned neural-BP employs on average 3% of the minimum-weight parity-checks over a total of 6 iterations. We consider the three variants of this decoder as introduced in [16], with tied weights ($ D_1 $), no weights ($ D_2 $) and free weights ($ D_3 $).

* For our proposed Aut-BP, we show results for both $ M=8 $ and $ M=32 $ randomly chosen permutations from the full automorphism group. Here, up to $ N_\mathrm{it,max} = 200 $ iterations are performed with, however, an early stopping condition (i.e., when $ \hat{\xv}=\hat{\uv}\Gm $) employed to reduce the average total number of iterations. Furthermore, the FFG have been reduced from 1792 to 1334 box-plus and addition operations per full iteration by removing operations with constant results, as presented in Section <ref>.

§.§ Error-Rate Performance

BLER comparison between SGD-optimized (NN-based) iterative decoders and Aut-BP for the RM(3,7)-code over the BI-AWGN channel. All neural-BP decoders use $ N_\mathrm{it} = 6 $ iterations.

In Fig. <ref> and Fig. <ref>,  we showcase the error-rate performance of the described decoding schemes for the RM(3,7)-code over the AWGN channel using BPSK mapping. Furthermore, we show the ML performance of the code as provided by [23]. As no data beyond an SNR of 3.5 dB is available, the ML performance is estimated using order-4 OSD.

Fig. <ref> compares the non-SGD-optimized iterative decoders with Aut-BP and ML. One can observe that the naïve BP decoding suffers from a very poor performance for RM codes, compared to BP decoding over FFG. Moreover, using multiple $ \Hm $-matrices in MBBP leads to a significant enhancement in performance. All of the previous methods are outperformed by both Aut-8-BP and MWPC-BP, with similar performance. However, in the high SNR regime, Aut-8-BP beats MWPC-BP by 0.2 dB. Aut-32-BP even closes the gap to ML to less than 0.05 dB at a BLER of $ 10^{-4} $.
We further observe the gains of sampling from $ \operatorname{GA}(m) $ in Aut-BP compared to $ \Pi(m) $, as used in BPL decoding. We can see that for all ensemble sizes $ M $, sampling from $ \operatorname{GA}(m) $ consistently outperforms $ \Pi(m) $ by up to 0.3 dB. This confirms the sub-optimality of restricting the automorphisms to a small subgroup. Moreover, Aut-32-BP can even outperform SCL [9] with list size $L=32$ (i.e., SCL-32) and its permutation variant DS-32 [8] in the high SNR regime.

Fig. <ref> compares the SGD-optimized (NN-based) decoders with Aut-BP and ML. Here, the neural-BP decoder is much closer to the ML bound, and the pruned variant with free weights $ D_3 $ outperforms NBP, which uses all overcomplete parity-checks. The pruned NBP $ D_2 $ decoder without weights suffers from a significant performance degradation. Over the whole SNR range, $ D_1 $ and $ D_3 $ are outperformed by Aut-32-BP. Furthermore, it can be seen that using only $ M=8 $ parallel BP decoders (i.e., Aut-8-BP) results in a small performance degradation of less than 0.2 dB over the whole SNR range, offering an attractive trade-off for lower complexity. Simulation results for the RM(4,8)-code are presented in [1].

§.§ Iterative Decoding Complexity

Complexity comparison of different iterative decoders using basic operations weighted according to Table <ref> (e.g., weight for multiplication = 3) to reach a target BLER of $ 10^{-4} $; RM(3,7)-code; BI-AWGN channel.

For the RM(3,7)-code, we compare the complexity of the iterative decoding algorithms with error-rate performance close to ML by counting the number of computing operations required to decode one RM codeword. The first column of Table <ref> gives the list of the operations we use.[Note that these operations differ from the ETSI basic operations, as we are more interested in hardware than in software implementations.] Furthermore, as non-trivial multiplication is significantly more complex than the other considered operations, we introduce a weighting factor for multiplication $ w_\mathrm{mul}=3 $ (equivalent to the number of full-adders in a 4+1 bit fixed-point implementation) to make the comparison more fair. For all decoders, we assume that the box-plus operation is implemented as

\begin{align}
L_1 \boxplus L_2 &= \sgn(L_1) \cdot \sgn(L_2) \cdot \min(|L_1|,|L_2|) \nonumber  \\
&\quad+ f_{+}(|L_1+L_2|) - f_{+}(|L_1-L_2|),
\end{align}

where $ f_{+}(|x|) = \log\LB1+\exp(-|x|)\RB$ is a correction term that can be well-approximated by a short LUT. Furthermore, CN are assumed to be efficiently implemented using the box-minus operator as

\begin{equation}
L_{j\to i} = \bigboxplus_{i' \neq i} L_{i'\to j} = \LB \bigboxplus_{i'} L_{i'\to j} \RB \boxminus L_{i\to j},
\end{equation}

with $ L_1 \boxminus L_2 = \sgn(L_2) \cdot L_1 + f_{-}(|L_1+L_2|) - f_{-}(|L_1-L_2|) $ and $ f_{-}(|x|) = \log(1-\exp(-|x|)) $ which is again implemented as a LUT as proposed in [24]. The remaining columns of Table <ref> list the number of operations of each type required for the basic building blocks of the described iterative decoding algorithms, namely box-plus evaluations, CN and VN updates, the ML-in-the-list decision and the stopping condition that is used in BPL decoding. Neural-BP, the pruned neural-BP and MWPC-BP decoding use non-trivial multiplications with the corresponding weights before the VN evaluations.

Basic operations and their usage in iterative decoding. aFor BP with weights (MWPC-BP, NBP, D1, D3).

Operation     Weight     2-input $ \boxplus $     CN (deg. $ D $)     VN (deg. $ D $)     ML out of $ M $     FFG BP Stopping

$ \sgn(x)\cdot\sgn(y)$     1     1     $ D-1 $     0     0     $ m \cdot N/2 + 2N-1 $

$ \sgn(x)\cdot y$     1     1     $ 2D-1 $     0     $ MN $     0

$ \min(|x|,|y|) $     1     1     $ D-1 $     0     0     0

$ \max(x,y) $     1     0     0     0     $ M-1 $     0

$ f_{\pm}(|x|) $ (LUT)     1     2     $ 4D-2 $     0     0     0

$ x+y $,  $ x-y $     1     4     $ 8D-4 $     $ 2D $     $ M(N-1) $     0

$ x\cdot y $     3     0     0     [$ D+1 $]a      0     0

Weighted total     -     9     $ 16D-9 $     $ 2D $  [$ +3D+3 $]a      $ 2MN-1 $     $ m \cdot N/2 + 2N-1 $

Fig. <ref> shows the total number of weighted operations to decode one codeword of the RM(3,7)-code. We can see that out of all methods, neural-BP using the full overcomplete $ \Hm $-matrix has the highest complexity. The corresponding pruned decoders $ D_1 $ and $ D_3 $ result in approximately 3% of that complexity. MWPC-BP is computationally more expensive, as it uses more parity-check equations and more iterations are required to achieve a good error-rate performance. It has to be noted, however, that we only list the complexity of iterative decoding, not of (adaptively) obtaining the parity-check equations. Hence, the overall complexity of MWPC-BP is higher than the presented number. MBBP has roughly half the complexity of MWPC-BP, while Aut-32-BP without stopping condition has twice the complexity of MWPC-BP. However, when a ($ \Gm $-matrix-based) stopping condition is used, the average number of iterations of Aut-BP is significantly reduced. To illustrate this, we measure the average required number of iterations until convergence for both $ M=8 $ and $ M=32 $ with respect to the SNR of the AWGN channel, while $ N_\mathrm{it,max} = 200$. At an SNR of 3.65 dB, corresponding to the BLER of $ 10^{-4} $, each decoder of the Aut-32-BP ensemble requires an average of 4.55 iterations, making Aut-BP the least complex decoder of the compared algorithms (see Fig. <ref>), without losing any error-rate performance. Aut-8-BP requires an SNR of 3.84 dB to reach this BLER performance, however, reducing the complexity again by a factor of 4, using only 3.96 iterations on average. Note that even though the ML-in-the-list decision can be only made after all constituent decoders are terminated, terminated decoders can already start decoding the next received vector (e.g., in a super-scalar implementation).

It is also worth noting here that the approaches proposed in [16] can also profit from early stopping. However, the effect is less significant since the majority of check node evaluations are performed in the first two iterations.
Moreover, the regular structure of the FFG may result in more preferable implementations of Aut-BP compared to the random memory access patterns observed in conventional iterative decoders.

§ CONCLUSION

In this work, we propose an automorphism-based iterative decoding algorithm for RM codes.
We present near-ML error-rate performance for the RM(3,7)-code operating only $0.05$ dB away from the ML bound at BLER of $10^{-4}$.
Furthermore, we report a decoder complexity comparison for the RM(3,7)-code from an operation level perspective.
To the best of our knowledge, our proposed iterative Aut-BP decoders using the RM code automorphism group as permutations are the best iterative decoders reported in literature thus far in terms of error-rate performance.

[1]
M. Geiselhart, A. Elkelesh, M. Ebada, S. Cammerer, and S. ten Brink,
“Automorphism Ensemble Decoding of Reed–Muller Codes,” IEEE Trans.
Commun., 2021.

[2]
D. E. Muller, “Application of Boolean Algebra to Switching Circuit Design
and to Error Detection,” Transactions of the I.R.E. Professional
Group on Electronic Computers, vol. EC-3, no. 3, pp. 6–12, 1954.

[3]
I. Reed, “A class of multiple-error-correcting codes and the decoding
scheme,” Transactions of the IRE Professional Group on Information
Theory, vol. 4, no. 4, pp. 38–49, Sep. 1954.

[4]
E. Arıkan, “Channel Polarization: A Method for Constructing
Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels,”
IEEE Trans. Inf. Theory, vol. 55, no. 7, pp. 3051–3073, Jul. 2009.

[5]
N. Stolte, “Rekursive Codes mit der Plotkin-Konstruktion und ihre
Decodierung,” Ph.D. dissertation, Technische Universität Darmstadt,
Jan. 2002. [Online]. Available:

[6]
E. Abbe, A. Shpilka, and A. Wigderson, “Reed–Muller Codes for Random
Erasures and Errors,” IEEE Trans. Inf. Theory, vol. 61, no. 10, pp.
5229–5252, 2015.

[7]
S. Kudekar, S. Kumar, M. Mondelli, H. D. Pfister, E. Şaşoǧlu, and
R. Urbanke, “Reed–Muller Codes Achieve Capacity on Erasure Channels,”
IEEE Trans. Inf. Theory, vol. 63, no. 7, pp. 4298–4316, 2017.

[8]
I. Dumer and K. Shabunov, “Soft-Decision Decoding of Reed-Muller Codes:
Recursive Lists,” IEEE Trans. Inf. Theory, vol. 52, no. 3, pp.
1260–1266, Mar. 2006.

[9]
I. Tal and A. Vardy, “List Decoding of Polar Codes,” IEEE Trans. Inf.
Theory, vol. 61, no. 5, pp. 2213–2226, May 2015.

[10]
M. Ye and E. Abbe, “Recursive projection-aggregation decoding of
Reed-Muller codes,” IEEE Trans. Inf. Theory, pp. 1–1, 2020.

[11]
M. Lian, C. Häger, and H. D. Pfister, “Decoding Reed–Muller Codes Using
Redundant Code Constraints,” in IEEE Inter. Symp. Inf. Theory
(ISIT), Jun. 2020.

[12]
M. Bossert and F. Hergert, “Hard- and Soft-Decision Decoding Beyond the
Half Minimum Distance—An Algorithm for Linear Codes,” IEEE Trans.
Inf. Theory, vol. 32, no. 5, pp. 709–714, 1986.

[13]
T. Hehn, J. B. Huber, S. Laendner, and O. Milenkovic, “Multiple-Bases
Belief-Propagation for Decoding of Short Block Codes,” in IEEE Inter.
Symp. Inf. Theory (ISIT), Jun. 2007, pp. 311–315.

[14]
E. Santi, C. Häger, and H. D. Pfister, “Decoding Reed-Muller Codes
Using Minimum-Weight Parity Checks,” in IEEE Inter. Symp. Inf. Theory
(ISIT), Jun. 2018, pp. 1296–1300.

[15]
E. Nachmani, E. Marciano, L. Lugosch, W. J. Gross, D. Burshtein, and
Y. Be’ery, “Deep Learning Methods for Improved Decoding of Linear
Codes,” IEEE J. Sel. Topics Sig. Process., vol. 12, no. 1, pp.
119–131, Feb. 2018.

[16]
A. Buchberger, C. Häger, H. D. Pfister, L. Schmalen, and A. G. i Amat,
“Pruning Neural Belief Propagation Decoders,” in IEEE Inter. Symp.
Inf. Theory (ISIT), Jun. 2020.

[17]
F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting
Codes, ser. North-Holland Mathematical Library.1em plus 0.5em minus
0.4emNorth-Holland Pub. Co., 1977, no. 16.

[18]
G. D. Forney, “Codes on Graphs: Normal Realizations,” IEEE Trans.
Inf. Theory, vol. 47, no. 2, pp. 520–548, Feb. 2001.

[19]
A. Elkelesh, M. Ebada, S. Cammerer, and S. ten Brink, “Belief Propagation
List Decoding of Polar Codes,” IEEE Commun. Lett., vol. 22, no. 8,
pp. 1536–1539, Aug. 2018.

[20]
N. Doan, S. A. Hashemi, M. Mondelli, and W. J. Gross, “On the
Decoding of Polar Codes on Permuted Factor Graphs,” in IEEE Global
Commun. Conf. (GLOBECOM), Dec. 2018.

[21]
T. Hehn, O. Milenkovic, S. Laendner, and J. B. Huber, “Permutation
Decoding and the Stopping Redundancy Hierarchy of Cyclic and Extended Cyclic
Codes,” IEEE Trans. Inf. Theory, vol. 54, no. 12, pp. 5308–5331,

[22]
I. Dimnik and Y. Be'ery, “Improved Random Redundant Iterative HDPC
Decoding,” IEEE Trans. Commun., vol. 57, no. 7, pp. 1982–1985, Jul.

[23]
M. Helmling, S. Scholl, F. Gensheimer, T. Dietz, K. Kraft, S. Ruzika, and
N. Wehn, “Database of Channel Codes and ML Simulation Results,”
<www.uni-kl.de/channel-codes>, 2019.

[24]
T. Clevorn and P. Vary, “The box-minus operator and its application to
low-complexity belief propagation decoding,” in IEEE 61st Veh.
Technol. Conf., vol. 1, May 2005, pp. 687–691.


# Asymptotic Normality for the Size of Graph Tries built from M-ary Tree
Labelings

Michael Fuchs and Tsan-Cheng Yu
Department of Mathematical Sciences
National Chengchi University
Taipei 116
Taiwan Both authors were partially supported by grant
MOST-109-2115-M-004-003-MY2.

###### Abstract

Graph tries are a new and interesting data structure proposed by Jacquet in
2014. They generalize the classical trie data structure which has found many
applications in computer science and is one of the most popular data structure
on words. For his generalization, Jacquet considered the size (or space
requirement) and derived an asymptotic expansion for the mean and the variance
when graph tries are built from $n$ independently chosen random labelings of a
rooted $M$-ary tree. Moreover, he conjectured a central limit theorem for the
(suitably normalized) size as the number of labelings tends to infinity. In
this paper, we verify this conjecture with the method of moments.

##  1 Introduction

Tries, proposed by de la Briandais in 1959 and named by Fredkin in 1961, are
one of the most important data structures on words. They admit many variants
and have found numerous applications; see, e.g., [6], [7] or the recent
comprehensive book of Jacquet and Szpankowski [13] for in-depth discussions on
their applicability.

We briefly recall the definition of tries which are rooted trees with leaves
holding the data that contains infinite strings over a finite alphabet
${\mathcal{A}}$ of size $A=|{\mathcal{A}}|$ as keys. The trie is then an
$A$-ary tree which is recursively built from $n$ given keys as follows. For
$n=1$, the sole key is placed into the root. For $n\geq 2$, the root is an
(empty) internal node and all keys are distributed to the $A$ subtrees of the
root according to their first letter; then, the construction of the subtrees
proceeds recursively by considering the keys with the first letters removed;
see Figure 1 for an example.

Note that the above procedure yields the same trie regardless of the order of
the $n$ keys. This follows, e.g., from the observation that if one considers
the rooted infinite $A$-ary tree with edges labeled by the letters of
${\mathcal{A}}$ (such that each node has an edge to a child for each letter
from ${\mathcal{A}}$), then a node of this $A$-ary tree is an internal node of
the trie if and only if there are at least two keys with prefixes equal to the
sequences of letters from the root of the $A$-ary tree to the node.

In order to understand the performance of tries, it is often assumed that the
keys are generated by some random process. The simplest of these random
processes assumes that the letters of the keys are independent random
variables with an identical probability distribution on the alphabet
${\mathcal{A}}$, i.e., ${\mathbb{P}}(\alpha)=p_{\alpha}$ for
$\alpha\in{\mathcal{A}}$ where the probabilities $p_{\alpha}$ satisfy
$0<p_{\alpha}<1$ and

$\sum_{\alpha\in{\mathcal{A}}}p_{\alpha}=1.$

This random model has been used in most of the studies on tries despite it
being an oversimplification; see [13]. One reason for this is that it captures
many of the phenomena observed in more realistic models, e.g., Markov models
(see Leckey et al. [15] and references therein).

$K_{4}$$K_{2}$$K_{5}$$K_{1}$$K_{3}$$\alpha$$\gamma$$\alpha$$\beta$$\gamma$$\beta$$\beta$$\gamma$$K_{1}=\gamma\alpha\beta\beta\cdots$;$K_{2}=\gamma\beta\cdots$;$K_{3}=\gamma\alpha\beta\gamma\cdots$;$K_{4}=\alpha\cdots$;$K_{5}=\gamma\gamma\cdots$.
Figure 1: A trie built from five keys with letters from the alphabet
${\mathcal{A}}=\\{\alpha,\beta,\gamma\\}$.

An important shape parameter for tries is the number of internal nodes because
it is a measure for the space requirement. If the trie is built from $n$
random keys, we denote the size by $S_{n}$.

Moments of $S_{n}$ have been studied in many papers, one of the earliest of
which is the paper of Jacquet and Régnier [11] (the study of the size over a
binary alphabet $\\{0,1\\}$ with $p_{0}=p_{1}=1/2$ goes back even further).
Mean and variance have been shown in [11] to be of linear order:

${\mathbb{E}}(S_{n})\sim P_{E}(\log_{a}n)n\qquad\text{and}\qquad{\rm
Var}(S_{n})\sim P_{V}(\log_{a}n)n,\qquad(n\rightarrow\infty),$

where $a>1$ is a suitable constant and $P_{E}(x),P_{V}(x)$ are computable
$1$-periodic functions; see Section 2 for more details. In addition, also a
central limit theorem was proved in [11] (see also [7] and Neininger and
Rüschendorf [17]):

$\frac{S_{n}-{\mathbb{E}}(S_{n})}{\sqrt{{\rm
Var}(S_{n})}}\stackrel{{\scriptstyle d}}{{\longrightarrow}}N(0,1),$

where $\stackrel{{\scriptstyle d}}{{\longrightarrow}}$ denotes convergence in
distribution and $N(0,1)$ is the standard normal distribution.

Recently, Jacquet [9] introduced a fascinating new generalization of tries
which he called graph tries (or G-tries for short). This generalization is
built from keys which instead of being strings are now (edge) labelings of a
fixed rooted (infinite) graph $G$. (The classical trie is recovered by
choosing as $G$ the one-sided infinite path graph.) The concept works for any
$G$, however, we will restrict our attention to $M$-ary trees in this paper;
see Figure 2 for an example of a labeling of a $2$-ary tree with letters from
the alphabet ${\mathcal{A}}=\\{\alpha,\beta,\gamma\\}$.

$\cdots$$\cdots$$\cdots$$\cdots$$\cdots$$\cdots$$\cdots$$\cdots$$\alpha$$\gamma$$\beta$$\beta$$\alpha$$\alpha$$\gamma$$\gamma$$\gamma$$\alpha$$\gamma$$\beta$$\alpha$$\gamma$$(L_{1})$
Figure 2: A labeling of a $2$-ary tree with labels from the alphabet
${\mathcal{A}}=\\{\alpha,\beta,\gamma\\}$.

A G-trie is now built from $n$ labelings of the $M$-ary tree as follows. First
consider the rooted infinite $M\times A$-ary tree whose nodes correspond to
the paths in the $M$-ary tree with all possible labelings, e.g., the root in
this $M\times A$-ary tree corresponds to the empty path with an empty labeling
and the children of the root correspond to all paths of length $1$ from the
root in the $M$-ary tree with all possibilities of assigning labels to these
paths. Then, a node in this $M\times A$-ary tree is contained in the G-trie if
and only if the path together with its labeling corresponding to the node
occurs in at least two of the $n$ given labelings; see Figure 3 for an
example.

$\cdots$$\cdots$$\cdots$$\alpha$$\beta$$\gamma$$\beta$$(L_{2})$$\cdots$$\cdots$$\cdots$$\cdots$$\beta$$\gamma$$\alpha$$\alpha$$\beta$$\beta$$(L_{3})$$\alpha$$\gamma$$\alpha$
Figure 3: A G-trie (right) built from the three labelings $L_{1}$ (from Figure
2)$,L_{2},$ and $L_{3}$ of a $2$-ary tree with letters from the alphabet
${\mathcal{A}}=\\{\alpha,\beta,\gamma\\}$. For instance, the node of depths
$2$ in the G-trie arises from the paths of length $2$ in $L_{1}$ and $L_{3}$
which are labeled by $\gamma\alpha$.

As for the classical trie, we assume that all the labels are chosen
independently with ${\mathbb{P}}(\alpha)=p_{\alpha}$ for
$\alpha\in{\mathcal{A}}$ where the probabilities $p_{\alpha}$ are as above.
Moreover, we are again interested in the space requirement, i.e., the number
of (internal) nodes of a G-trie built from $n$ random labelings which (with a
slight abuse of notation) we also denote by $S_{n}$.

Mean and variance of $S_{n}$ were investigated in [9]. In order to explain the
results, we need some notation. First, we order the probabilities of the
letters of ${\mathcal{A}}$ as $p_{1},\ldots,p_{A}$. Next, throughout this
work, we assume that

$\sum_{j=1}^{A}p_{j}^{2}<\frac{1}{M}$ (1)

because otherwise ${\mathbb{E}}(S_{n})=\infty$ for $n\geq 2$; see [9] where
(1) was called the non-explosive case. Finally, let $\rho$ be the the unique
real root with

$\sum_{j=1}^{A}p_{j}^{\rho}=\frac{1}{M}.$

Note that $1\leq\rho<2$ because we are in the non-explosive case. Also,
$\sigma=1$ only for the classical trie.

Using this notation, it was shown in [9] that

${\mathbb{E}}(S_{n})\sim P_{E}(\log_{a}n)n^{\rho},\qquad(n\rightarrow\infty),$
(2)

where $a>1$ is a suitable constant and $P_{E}(x)$ is a computable 1-periodic
function (depending on $p_{1},\ldots,p_{A}$) which will be given in Section 2.
Moreover, for the variance,

${\rm Var}(S_{n})\sim\begin{cases}P_{V}(\log_{a}n)n^{\rho},&\text{if}\
p_{j}=1/A\ \text{for}\ 1\leq j\leq A;\\\
P_{V}(\log_{a}n)n^{2\rho-1},&\text{otherwise},\end{cases}\qquad(n\rightarrow\infty),$
(3)

where $a$ is as above and $P_{V}(x)$ is another computable 1-periodic function
(also depending on $p_{1},\ldots,p_{A}$) which again will be given in Section
2.

The above results are interesting because they show that the size of a G-trie
if $\rho>1$ and in the non-uniform case (i.e., the case where we do not have
$p_{j}=1/A$ for $1\leq j\leq A$) exhibits a very different behavior compared
to the size of a classical trie (which is the case $\rho=1$). More precisely,
mean and variance are in the above cases of a different order since
$2\rho-1>\rho$.

Nevertheless, even in the cases were the variance has a larger order than the
mean, the standard deviation is still of a smaller order. Consequently, in
[9], a central limit theorem was conjectured. The main result of this paper is
the verification of this conjecture.

######  Theorem 1.

For the size $S_{n}$ of a random G-trie built from $n$ labelings of an $M$-ary
tree, we have the central limit theorem:

$\frac{S_{n}-{\mathbb{E}}(S_{n})}{\sqrt{{\rm
Var}(S_{n})}}\stackrel{{\scriptstyle d}}{{\longrightarrow}}N(0,1).$

This result is interesting because central limit theorems for shape parameters
of discrete random structures arising from computer science which have a
variance which is significantly larger than the mean are rare; the only other
example with a similar behavior for mean and variance can be found in Flajolet
et al. [5]. Also, in both these examples, most standard methods for proving a
central limit theorem do not seem to work (see, e.g., Remark 4 in Section 4),
leaving only the (more technical) method of moments as a feasible approach;
see [5] and Section 30 of Billingsley [1].

We conclude the introduction by giving a sketch of the proof of our main
result and at the same time outlining the structure of the paper. First, from
the definition of random G-tries, $S_{n}$ satisfies

$S_{n}\stackrel{{\scriptstyle
d}}{{=}}\sum_{i=1}^{M}\sum_{j=1}^{A}S_{B_{j}^{(i)}}^{(i,j)}+1,\qquad(n\geq
2),$ (4)

where $S_{0}=S_{1}=0$, $S_{n}^{(i,j)}\stackrel{{\scriptstyle d}}{{=}}S_{n}$
for $1\leq i\leq M,1\leq j\leq A$, and $(B_{1}^{(i)},\ldots,B_{A}^{(i)})$ are
independent multinomial distributed random vectors with parameter
$(n,p_{1},\ldots,p_{A})$ for $1\leq i\leq M$. This follows from the fact that
$S_{n}$ is additive in the sense that it can be computed by first computing it
for the subtrees of the root (this gives the terms $S_{B_{j}^{(i)}}^{(i,j)}$),
adding up these contributions, and then increasing this sum by $1$ in order to
include the root.

By taking moments on both sides of (4), we see that all (central and non-
central) moments satisfy a recurrence of the form

$a_{n}=M\sum_{j=1}^{A}\sum_{k=0}^{n}\binom{n}{k}p_{j}^{k}(1-p_{j})^{n-k}a_{k}+b_{n},\qquad(n\geq
2),$ (5)

where $a_{0}=a_{1}=0$ and $b_{n}$ with $n\geq 2$ is a given sequence called
toll-sequence.

In [9], the above recurrence for the mean and variance was (asymptotically)
solved by using complex-analytic tools such as Mellin transform and analytic
depoissonization (for background on these tools see Flajolet et al. [2] and
Jacquet and Szpankowski [12]). The results from [9] (in a less precise form)
were given above; more detailed version will be given in the next section.
Moreover, in the next section, we will also give some results concerning the
recurrence (5) which exhibits a treshold phenomena: for toll-sequences which
have a growth order smaller than $n^{\rho}$, $a_{n}$ grows like $n^{\rho}$
(small toll-sequence case); for toll-sequences which have a growth order
larger than $n^{\rho}$, $a_{n}$ grows like $b_{n}$ (large toll-sequence case).
Here, the large toll-function case will turn out to be crucial for us since
for the computation of moments of third and higher order of $S_{n}$ we will be
in this case. In fact, if $\rho>1$ and in the non-uniform case, even the
variance falls into the large toll-function case and we will re-derive in this
situtation the result from [9] in the next section by elementary tools (i.e.,
tools which are not based on complex analysis).

Then, in Section 3 and Section 4, we will compute higher moments of $S_{n}$
again by elementary tools starting from the third moment. The reason why we
will consider the uniform case and non-uniform case separately is that these
cases behave very differently. In the uniform case, we will see that the
computation of the third moment is basically enough to understand the limiting
behavior of $S_{n}$ because with our arguments, the assumptions of the
contraction method from [17] can be verified which then immediately implies
our desired central limit theorem (this was already suggested in [9]).
Alternatively, we can also use the method of moments which will be done in
Section 3 as well. On the other hand, in the non-uniform case, the use of the
contraction method is not obvious (see Remark 4 in Section 4) and it seems
that only the method of moments works in this case. Technical details for this
case are more demanding than in the uniform case and will be given in Section
4.

Finally, in Section 5, we will discuss some extensions of our main theorem and
in Section 6 we will give some concluding remarks.

##  2 Preliminaries

This section contains some preliminary results which will be used in the
latter sections. Moreover, as mentioned in the introduction, we will recall in
more detail the results for the mean and the variance of the size of G-tries
from [9]. For the sake of clarity, we will divide the section into four
paragraphs.

### Recurrences for Moments.

Let $\mu_{n}:={\mathbb{E}}(S_{n})$. Then, by taking expectations on both sides
of (4), we obtain that

$\mu_{n}=M\sum_{j=1}^{A}\sum_{k=0}^{n}\binom{n}{k}p_{j}^{k}(1-p_{j})^{n-k}\mu_{k}+1,\qquad(n\geq
2)$

with $\mu_{0}=\mu_{1}=0$. Note that this is (5) with $b_{n}=1$ for $n\geq 2$.

Next, we consider central moments. First, note that (4) implies that

$\left(S_{n}-\mu_{n}\right)\stackrel{{\scriptstyle
d}}{{=}}\sum_{i=1}^{M}\sum_{j=1}^{A}\left(S_{B_{j}^{(i)}}^{(i,j)}-\mu_{B_{j}^{(i)}}\right)+\Delta_{n,{\mathbf{B}}^{(1)},\ldots,{\mathbf{B}}^{(M)}},$
(6)

where ${\mathbf{B}}^{(i)}:=(B_{1}^{(i)},\ldots,B_{A}^{(i)})$ for $1\leq i\leq
M$ and

$\Delta_{n,{\bf B}^{(1)},\ldots,{\bf
B}^{(M)}}:=1-\mu_{n}+\sum_{i=1}^{M}\sum_{j=1}^{A}\mu_{B_{j}^{(i)}}.$ (7)

Set

$A_{n}^{(m)}:={\mathbb{E}}\left(S_{n}-\mu_{n}\right)^{m}.$

Taking expectations of the $m$-th power on both sides of (6), conditioning on
${\mathbf{B}}^{(i)}$ on the right-hand side, and expanding gives

$A_{n}^{(m)}=M\sum_{j=1}^{A}\sum_{k=0}^{n}\binom{n}{k}p_{j}^{k}(1-p_{j})^{n-k}A_{j}^{(m)}+B_{n}^{(m)},\qquad(n\geq
2)$ (8)

with $A_{0}^{(m)}=A_{1}^{(m)}=0$ and

$B_{n}^{(m)}:=\sum_{{\mathbf{k}}^{(1)},\ldots,{\mathbf{k}}^{(M)}}\left(\prod_{i=1}^{M}\pi_{n,{\mathbf{k}}^{(i)}}\right)\sum_{\boldsymbol{\ell}^{(1)},\ldots,\boldsymbol{\ell}^{(M)},\ell}\binom{m}{\boldsymbol{\ell}^{(1)},\ldots,\boldsymbol{\ell}^{(M)},\ell}\left(\prod_{i=1}^{M}\prod_{j=1}^{A}A_{k_{j}^{(i)}}^{(\ell_{j}^{(i)})}\right)\Delta_{n,{\mathbf{k}}^{(1)},\ldots,{\mathbf{k}}^{(M)}}^{\ell},$

where the first sum runs over all
${\mathbf{k}}^{(i)}=(k_{1}^{(i)},\ldots,k_{A}^{(i)})\in\\{0,\ldots,n\\}^{A}$
with $k_{1}^{(i)}+\cdots+k_{A}^{(i)}=n$ for $1\leq i\leq M$ and the second sum
runs over all
$\boldsymbol{\ell}^{(i)}=(\ell_{1}^{(i)},\ldots,\ell_{A}^{(i)})\in\\{0,\ldots,m-1\\}^{A}$
for $1\leq i\leq M$ and $0\leq\ell\leq m$ such that

$\ell+\sum_{i=1}^{M}\sum_{j=1}^{A}\ell_{j}^{(i)}=m.$ (9)

Moreover,

$\pi_{n,{\mathbf{k}}^{(i)}}=\binom{n}{k_{1}^{(i)},\ldots,k_{A}^{(i)}}p_{1}^{k_{1}^{(i)}}\cdots
p_{A}^{k_{A}^{(i)}}=:\binom{n}{{\bf k}^{(i)}}{\bf p}^{{\bf k}^{(i)}},$

where ${\bf p}:=(p_{1},\ldots,p_{A})$,

$\binom{m}{\boldsymbol{\ell}^{(1)},\ldots,\boldsymbol{\ell}^{(M)},\ell}:=\binom{m}{\ell_{1}^{(1)},\ldots,\ell_{A}^{(M)},\ell},$

and $\Delta_{n,{\mathbf{k}}^{(1}),\ldots{\mathbf{k}}^{(M)}}$ is the $\Delta$
from (7) but with ${\mathbf{B}}^{(i)}$ replaced by ${\mathbf{k}}^{(i)}$ for
$1\leq i\leq M$. Note that this shows that the central moments indeed satisfy
a recurrence of type (5). (This was claimed at the end of the introduction.)

### Asymptotic Expansions for Mean and Variance.

In this paragraph, we will recall more detailed versions of the result for the
mean (2) and variance (3) as given in [9]. In order to state these results, we
need the complex roots of the function

$P(s):=1-M\sum_{j=1}^{A}p_{j}^{s}$

which satisfy $\Re(s)\leq\rho$. We introduce two notations for the solution
set:

${\mathcal{S}}_{\rho}:=\\{s\ :\ P(s)=0\ \text{and}\
\Re(s)=\rho\\}\quad\text{and}\quad{\mathcal{S}}_{(\rho-1,\rho]}:=\\{s\ :\
P(s)=0\ \text{and}\ \Re(s)\in(\rho-1,\rho]\\}.$

A great deal about these sets is known; see the deep study of Flajolet et al.
[3] for a slightly restricted setting which, however, carries over to the
solution set of $P(s)$, too.

First, the structure of the set ${\mathcal{S}}_{\rho}$ depends on a property
of the ratios $\log p_{i}/\log p_{j}$.

  * (i)

If the ratios $\log p_{i}/\log p_{j}$ are rational for all $1\leq i,j\leq A$,
then

${\mathcal{S}}_{\rho}=\left\\{s=\rho+\frac{2k\pi i}{\log a}\ :\
k\in{\mathbb{Z}}\right\\},$

where $a>1$ is such that $p_{j}=a^{-e_{j}}$ for suitable positive integers
$e_{j}$ for all $1\leq j\leq A$. This is called the periodic case.

  * (ii)

If at least one of the ratios $\log p_{i}/\log p_{j}$ is irrational for $1\leq
i,j\leq A$, then ${\mathcal{S}}_{\rho}=\\{\rho\\}$. This is called the
aperiodic case.

Secondly, the roots in
${\mathcal{S}}_{(\rho-1,\rho]}\setminus{\mathcal{S}}_{\rho}$ behave in more a
chaotic way, however, they still exhibit some regularities. For instance, the
roots are all simple, are uniformly separated, $1/P(z)$ is bounded provided
that $z$ stays uniformly far away from the roots, etc.; see [3] for more
properties.

Using the above sets, we can now give more detailed versions of (2) and (3).

######  Proposition 1 (Jacquet [9]).

For the mean of the size $S_{n}$ of a random G-trie built from $n$ labelings
of an $M$-ary tree, we have

${\mathbb{E}}(S_{n})=\sum_{\beta\in{\mathcal{S}}_{(\rho-1,\rho]}}G_{E}(\beta)n^{\beta}+{\mathcal{O}}(n^{\rho-1}),$
(10)

where the sum and all its term-by-term derivatives are absolute convergent and

$G_{E}(s)=\frac{(1-s)\Gamma(-s)}{M\sum_{j=1}^{A}p_{j}^{s}\log p_{j}}.$ (11)

In particular,

${\mathbb{E}}(S_{n})\sim\sum_{\beta\in{\mathcal{S}}_{\rho}}G_{E}(\beta)n^{\beta}.$
(12)

######  Remark 1.

By setting $a=e$ in the aperiodic case, we recover (2) with an infinitely
divisible periodic function $P_{E}(x)$.

######  Proposition 2 (Jacquet [9]).

For the variance of the size $S_{n}$ of a random G-trie built from $n$
labelings of an $M$-ary tree, we have the following when $\rho>1$.

  * (i)

In the uniform case, we have

${\rm
Var}(S_{n})\sim\sum_{\beta\in{\mathcal{S}}_{\rho}}G_{V}(\beta)n^{\beta},$ (13)

where $G_{V}(s)$ is a computable function and the sum and all its term-by-term
derivates are absolute convergent.

  * (ii)

In the non-uniform case, we have

${\rm
Var}(S_{n})\sim\left(\frac{M-1}{MP(2\rho-1)}-1\right)\left(\sum_{\beta\in{\mathcal{S}_{\rho}}}\beta
G_{E}(\beta)n^{\beta-1}\right)^{2}n,$ (14)

where $G_{E}(x)$ is given in (11).

######  Remark 2.

  * (i)

By again setting $a=e$ in the aperiodic case, we recover (3) with an
infinitely divisible periodic function $P_{V}(x)$.

  * (ii)

No explicit expression for $G_{V}(s)$ was given in [9] where the corrected
Poissonized variance approach from [6] was used to prove (13). In fact, this
approach is capable of giving an explicit (albeit messy) expression for
$G_{V}(s)$.

  * (iii)

A similar result also holds for $\rho=1$ (i.e. for classical tries); see,
e.g., [6] and [11].

In addition to the above results, it was claimed in [9] that the mean is of
order $n^{\rho}$ and the variance is of order $n^{\rho}$ in the uniform case
and of order $n^{2\rho-1}$ in the non-uniform case (for $\rho>1$). Note that
this is not obvious from the expressions above. In fact, we have not been able
to locate the proofs of these claims in [9]. However, we will need these facts
(in particular those for the variances) since we will normalize by the right-
hand side of (13) and (14) in the proof of our claimed limit law. Therefore,
we will give detailed proofs of these claims (amongst other things) in the
next two paragraphs.

### Small Toll-Sequence Case.

As explained at the end of the introduction, the recurrence (5) exhibits a
treshold phenomena. We will give more details in this and the next paragraph.
We start with the small toll-sequence case.

First, we point out that it would be possible to prove for the recurrence (5)
that $a_{n}\sim P(\log_{a}n)n^{\rho}$ whenever $b_{n}$ is small compared to
$n^{\rho}$, e.g., $b_{n}={\mathcal{O}}(n^{\rho-\epsilon})$ where $\epsilon>0$.
(Note that (2) then immediately follows from this.) Here, $P(x)$ is a
1-periodic function and $a>1$ is as above. However, we do not need such a
result in this paper because the small toll-sequence case is just used for the
computation of the mean in the general case and the variance for (i) $\rho=1$
and (ii) in the uniform case with $\rho>1$ which was already done in [9] with
complex-analytic tools that have the additional advantage that they yield
precise knowledge of $P(x)$. (Such precise results do not easily follow in the
more general situation above.)

Instead, we will recall a result from Schachinger [18] (or more precisely, its
extension from [7] and Lee [16]) which shows that if $b_{n}\geq 0$, then
either $a_{n}$ is constant zero are it grows at least as $n^{\rho}$.

######  Proposition 3 (Schachinger [18]).

Assume that the sequence $a_{n}$ satisfies (5) with a toll-sequence $b_{n}$
with (i) $b_{n}\geq 0$ and (ii) there exist an $n_{0}\geq 2$ with
$b_{n_{0}}>0$. Then,

$a_{n}=\Omega(n^{\rho}).$

From this, we have the following corollary.

######  Corollary 1.

The periodic functions $P_{E}(x)$ for the mean and $P_{V}(x)$ for the variance
in the uniform case and in the non-uniform case with $\rho=1$ are positive.

_Proof._ The claim about $P_{E}(x)$ is an immediate consequence of Proposition
3.

As for $P_{V}(x)$ note that the variance of $S_{n}$ satisfies (5) with

$b_{n}=\sum_{{\bf k}^{(1)},\ldots{\bf
k}^{(M)}}\left(\prod_{i=1}^{M}\pi_{n,{\bf k}^{(i)}}\right)\Delta_{n,{\bf
k}^{(1)},\ldots,{\bf k}^{(M)}}^{2};$ (15)

see (8). This toll-sequence is easily seen to satisfy the assumptions from
Proposition 3. Thus,

${\rm Var}(S_{n})=\Omega(n^{\rho})$

which in the uniform case and in the non-uniform case with $\rho=1$ shows that
$P_{V}(x)>0$.

In fact, the positivity claim for $P_{E}(x)$ can also be proved directly from
the explicit expression for $P_{E}(x)$ which follows from (11) and (12). This
second proof uses ideas from Javanian [14] which she introduced to establish a
similar claim for a related parameter.

Second proof that $P_{E}(x)>0$. First, note that from (12), we have

$P_{E}(x)=\sum_{\beta\in{\mathcal{S}}_{\rho}}G_{E}(\beta)e^{(\beta-\rho)(\log
a)x}.$

In the aperiodic case, this sum consists of just one term which is easily seen
to be positive.

Thus, we concentrate in the sequel on the periodic case where the above sum
becomes

$P_{E}(x)=\sum_{k=-\infty}^{\infty}c_{k}e^{2\pi kix}$

with $c_{k}$ given by (11) as

$c_{k}=\frac{(1-\rho-\chi_{k})\Gamma(-\rho-\chi_{k})}{M\sum_{j=1}^{A}p_{j}^{\rho+\chi_{k}}\log
p_{j}}=\frac{\Gamma(2-\rho-\chi_{k})}{M\left(-\sum_{j=1}^{A}p_{j}^{\rho}\log
p_{j}\right)(\rho+\chi_{k})},$

where $\chi_{k}=2\pi ki/(\log a)$ and we have used that $p_{j}^{\chi_{k}}=1$
for $1\leq j\leq A$.

Therefore, it suffices to show that

$\sum_{k=-\infty}^{\infty}\frac{\Gamma(2-\rho-\chi_{k})}{\rho+\chi_{k}}e^{2\pi
kix}$

is positive. In order to establish this claim, observe that

$\displaystyle\frac{\Gamma(2-\rho-\chi_{k})}{\rho+\chi_{k}}e^{2\pi kix}$
$\displaystyle=\frac{e^{2\pi
kix}}{\rho+\chi_{k}}\int_{0}^{\infty}e^{-t}t^{1-\rho-\chi_{k}}{\rm d}t$
$\displaystyle=e^{2\pi
kix}\int_{0}^{\infty}(1-(t+1)e^{-t})t^{-1-\rho-\chi_{k}}{\rm d}t$
$\displaystyle=\int_{-\infty}^{\infty}f(e^{u})e^{-\rho u}e^{2\pi
kix-u\chi_{k}}{\rm d}u$ $\displaystyle=(\log
a)\int_{-\infty}^{\infty}f\left(e^{(x-v)(\log a)}\right)e^{-\rho(x-v)(\log
a)}e^{2\pi kiv}{\rm d}v,$

where $f(t)=1-(t+1)e^{-t}$ is a positive function on $(0,\infty)$.

Note that the last integral in the computation above is a Fourier transform.
Thus, by the Poisson summation formula

$\sum_{k=-\infty}^{\infty}\frac{\Gamma(2-\rho-\chi_{k})}{\rho+\chi_{k}}e^{2\pi
kix}=(\log a)\sum_{v=-\infty}^{\infty}f\left(e^{(x-v)(\log
a)}\right)e^{-\rho(x-v)(\log a)}$

which is clearly positive and thus the claim is proved.

### Large Toll-Sequence Case.

In this paragraph, we will consider (5) with toll-sequences which grow faster
than $n^{\rho}$. This large-toll sequence case will be crucial for the
computation of central moments of $S_{n}$ beyond the second moment and will
also enable us to re-prove (14).

We will show the following asymptotic transfer result.

######  Proposition 4.

Assume that the sequence $a_{n}$ satisfies (5) with a toll-sequence $b_{n}$
with $b_{n}\sim cn^{\alpha},$ where $\alpha>\rho$ and $c\in{\mathbb{R}}$.
Then,

$a_{n}\sim\frac{cn^{\alpha}}{P(\alpha)}.$

######  Remark 3.

  * (i)

In order to accommodate the case $c=0$, we use (from now on) the convention
that $a_{n}\sim cb_{n}$ means that $a_{n}=cb_{n}+o(b_{n})$ (i.e., if $c=0$,
the symbol $a_{n}\sim cb_{n}$ means that $a_{n}=o(b_{n})$, whereas for $c\neq
0$, the symbol has the usual meaning).

  * (ii)

This proposition can also be applied term-by-term to
$b_{n}\sim\sum_{\beta}G(\beta)n^{\beta}$ provided that this sum runs over a
discrete set of $\beta$’s with $\beta>\rho$ and that it as well as all its
term-by-term derivatives are absolute convergent.

The proof of the above proposition follows by extending the method of proof of
Proposition 2 in Hubalek et al. [8]. For the convenience of the reader (and
because this proposition will be crucial for the proof of Theorem 1), we will
give a detailed sketch.

First, we need a solution of (5).

######  Lemma 1.

Assume that the sequence $a_{n}$ satisfies (5). Then,

$a_{n}=\sum_{\ell=0}^{\infty}M^{\ell}\sum_{k_{1}+\cdots+k_{A}=\ell}\binom{\ell}{\bf
k}\sum_{i=2}^{n}\binom{n}{i}\left(1-{\bf p}^{{\bf k}}\right)^{n-i}\left({\bf
p}^{{\bf k}}\right)^{i}b_{i},$ (16)

where ${\bf k}=(k_{1},\ldots,k_{A})$, $\binom{\ell}{{\bf k}}$ denotes the
multinomial coefficient, and ${\bf p}^{{\bf
k}}:=\prod_{j=1}^{A}p_{j}^{k_{j}}$.

_Proof._ Consider the Poisson-generating functions (as formal power series):

$\tilde{f}(z):=e^{-z}\sum_{n=0}^{\infty}\frac{a_{n}}{n!}z^{n}\qquad\text{and}\qquad\tilde{g}(z):=e^{-z}\displaystyle\sum_{n=2}^{\infty}\frac{b_{n}}{n!}z^{n}.$

Then, from (5), we have

$\tilde{f}(z)=M\sum_{j=1}^{A}\tilde{f}(p_{j}z)+\tilde{g}(z).$

Iterating this functional equation gives

$\tilde{f}(z)=M^{k+1}\sum_{k_{1}+\cdots+k_{A}=k+1}{{k+1}\choose{{\bf
k}}}\tilde{f}({\bf p}^{{\bf
k}}z)+\sum_{\ell=0}^{k}M^{\ell}\sum_{k_{1}+\cdots+k_{A}=\ell}{{\ell}\choose{{\bf
k}}}\tilde{g}({\bf p}^{{\bf k}}z).$

By multiplying both sides by $e^{z}$, then taking the $n$-th derivative of
both sides and setting $z=0$, we have

$\displaystyle a_{n}=M^{k+1}$
$\displaystyle\sum_{k_{1}+\cdots+k_{A}=k+1}{{k+1}\choose{{\bf
k}}}\sum_{i=2}^{n}{{n}\choose{i}}\left(1-{\bf p}^{{\bf
k}}\right)^{n-i}\left({\bf p}^{{\bf k}}\right)^{i}a_{i}$
$\displaystyle+\sum_{\ell=0}^{k}M^{\ell}\sum_{k_{1}+\cdots+k_{A}=\ell}{{\ell}\choose{{\bf
k}}}\sum_{i=2}^{n}{{n}\choose{i}}\left(1-{\bf p}^{{\bf
k}}\right)^{n-i}\left({\bf p}^{{\bf k}}\right)^{i}b_{i}.$

From this the claimed result follows since

$\displaystyle M^{k+1}$
$\displaystyle\sum_{k_{1}+\cdots+k_{A}=k+1}{{k+1}\choose{{\bf
k}}}\sum_{i=2}^{n}{{n}\choose{i}}\left(1-{\bf p}^{{\bf
k}}\right)^{n-i}\left({\bf p}^{{\bf k}}\right)^{i}a_{i}$
$\displaystyle={\mathcal{O}}\left(M^{k}\sum_{k_{1}+\cdots+k_{A}=k+1}{{k+1}\choose{{\bf
k}}}\left({\bf p}^{{\bf
k}}\right)^{2}\right)={\mathcal{O}}\left(\left(M\sum_{j=1}^{A}p_{j}^{2}\right)^{k}\right)$

approaches 0 as $k\rightarrow\infty$.

Proof of Proposition 4. We will split the sum in $k_{1},k_{2},\ldots,k_{A}$ in
(16) into three cases: $n\displaystyle{\bf p}^{{\bf k}}\leq 1$, $1\leq
n\displaystyle{\bf p}^{{\bf k}}\leq\log n$, and $n\displaystyle{\bf p}^{{\bf
k}}\geq\log n.$

Case 1: $n{\bf p}^{{\bf k}}\leq 1$. We first estimate the last sum on the
right-hand side of (16). Uniformly for $\ell\geq 0$ with
$k_{1}+\cdots+k_{A}=\ell$, we have

$\displaystyle\sum_{i=2}^{n}{{n}\choose{i}}\left(1-{\bf p}^{{\bf
k}}\right)^{n-i}\left({\bf p}^{{\bf
k}}\right)^{i}b_{i}={\mathcal{O}}\left(\sum_{i=2}^{n}\frac{i^{\alpha}}{i!}\left(n{\bf
p}^{{\bf k}}\right)^{i}\right)={\mathcal{O}}\left(\left(n{\bf p}^{{\bf
k}}\right)^{2}\right)={\mathcal{O}}\left(\left(n{\bf p}^{{\bf
k}}\right)^{\rho+\epsilon}\right),$

for $\epsilon>0$ such that $\rho+\epsilon\leq\min\\{2,\alpha\\}$. Then,

$\displaystyle\sum_{\ell=0}^{\infty}M^{\ell}\sum_{\begin{subarray}{c}k_{1}+\cdots+k_{A}=\ell\\\
n{\bf p}^{{\bf k}}\leq 1\end{subarray}}$ $\displaystyle{{\ell}\choose{{\bf
k}}}\sum_{i=2}^{n}{{n}\choose{i}}\left(1-{\bf p}^{{\bf
k}}\right)^{n-i}\left({\bf p}^{{\bf k}}\right)^{i}b_{i}$ $\displaystyle=\ $
$\displaystyle{\mathcal{O}}\left(\sum_{\ell=0}^{\infty}M^{\ell}\sum_{\begin{subarray}{c}k_{1}+\cdots+k_{A}=\ell\\\
n{\bf p}^{{\bf k}}\leq 1\end{subarray}}{{\ell}\choose{{\bf k}}}\left(n{\bf
p}^{{\bf k}}\right)^{\rho+\epsilon}\right).$ (17)

Let

$\hat{p}:=\text{min}\\{p_{1},\cdots,p_{A}\\}.$

Then, for any $\ell\geq 0$ with $k_{1}+\cdots+k_{A}=\ell$ and $n{\bf p}^{{\bf
k}}\leq 1$, we have $\ell\geq-(\log n)/(\log\hat{p})$. Thus,

$\displaystyle(\ref{np<1})$
$\displaystyle={\mathcal{O}}\left(n^{\rho+\epsilon}\sum_{\ell\geq-(\log
n)/(\log\hat{p})}\left(M\sum_{j=1}^{A}p_{j}^{\rho+\epsilon}\right)^{\ell}\right)$
$\displaystyle={\mathcal{O}}\left(n^{\rho+\epsilon-\frac{\log\left(M\sum_{j=1}^{A}p_{j}^{\rho+\epsilon}\right)}{\log\hat{p}}}\right)=o(n^{\alpha}).$

Case 2: $1\leq n{\bf p}^{{\bf k}}\leq\log n$. Again, we will start with the
last sum on the right-hand side of (16). Uniformly, for $\ell\geq 1$ with
$k_{1}+\cdots+k_{A}=\ell$, we have

$\sum_{i=2}^{n}{{n}\choose{i}}\left(1-{\bf p}^{{\bf k}}\right)^{n-i}\left({\bf
p}^{{\bf k}}\right)^{i}b_{i}={\mathcal{O}}\left((1-{\bf p}^{{\bf
k}})^{n}\sum_{i=2}^{n}\frac{i^{\alpha}}{i!}\left(\frac{n{\bf p}^{{\bf
k}}}{1-{\bf p}^{{\bf k}}}\right)^{i}\right).$ (18)

Next, by a standard application of the Laplace method or the saddle point
method (see Chapter VIII and Appendix B.6 in [4]),

$\sum_{j\geq 0}\frac{j^{\alpha}}{j!}x^{j}={\mathcal{O}}(x^{\alpha}e^{x}),$

for $x\geq 1$. Thus,

$(\ref{1<np<logn})={\mathcal{O}}\left((1-{\bf p}^{{\bf k}})^{n}\left(n{\bf
p}^{{\bf k}}\right)^{\alpha}\exp\left(\frac{n{\bf p}^{{\bf k}}}{1-{\bf
p}^{{\bf k}}}\right)\right)={\mathcal{O}}\left(\left(n{\bf p}^{{\bf
k}}\right)^{\alpha}\right).$

The remaining proof proceeds as in Case 1:

$\displaystyle\sum_{\ell=0}^{\infty}M^{\ell}\sum_{\begin{subarray}{c}k_{1}+\cdots+k_{A}=\ell\\\
1\leq n{\bf p}^{{\bf k}}\leq\log n\end{subarray}}$
$\displaystyle{{\ell}\choose{{\bf
k}}}\sum_{i=2}^{n}{{n}\choose{i}}\left(1-{\bf p}^{{\bf
k}}\right)^{n-i}\left({\bf p}^{{\bf k}}\right)^{i}b_{i}$ $\displaystyle=\ $
$\displaystyle{\mathcal{O}}\left(n^{\alpha}\sum_{\ell\geq\hat{\ell}(n)}\left(M\sum_{j=1}^{A}p_{j}^{\alpha}\right)^{\ell}\right)=o(n^{\alpha}),$

where $\hat{\ell}(n)=-(\log(n/\log n))/(\log\hat{p})$.

Case 3: $n{\bf p}^{\bf k}\geq\log n$. Also in this case, we will start with
the last sum on the right-hand side of (16), where now, we will use the local
limit theorem of the binomial distribution: for $0<p<1$,

$\binom{n}{i}p^{i}(1-p)^{i}=\frac{e^{-t^{2}/2}}{\sqrt{2\pi
np(1-p)}}\left(1+{\mathcal{O}}\left(\frac{t^{3}+1}{\sqrt{np(1-p)}}\right)\right)$

uniformly for $t=o((p(1-p)n)^{1/6})$, where $i=np+t\sqrt{np(1-p)}$; see Lemma
4 in [8]. Moreover, we will also apply the tail estimates for the binomial
distribution from Lemma 5 in [8]. Using these tools, a standard application of
the Laplace method gives:

$\sum_{i=2}^{n}\binom{n}{i}\left(1-{\bf p}^{\bf k}\right)^{n-i}\left({\bf
p}^{\bf k}\right)^{i}b_{i}\sim c\left(n{\bf p}^{\bf k}\right)^{\alpha}$

uniformly for $\ell\geq 0$ with $k_{1}+\cdots+k_{A}=\ell$ and $n{\bf p}^{\bf
k}\geq\log n$. Thus,

$\displaystyle\sum_{\ell=0}^{\infty}M^{\ell}\sum_{\begin{subarray}{c}k_{1}+\cdots+k_{A}=\ell\\\
n{\bf p}^{{\bf k}}\geq\log n\end{subarray}}$ $\displaystyle{{\ell}\choose{{\bf
k}}}\sum_{i=2}^{n}{{n}\choose{i}}\left(1-{\bf p}^{{\bf
k}}\right)^{n-i}\left({\bf p}^{{\bf k}}\right)^{i}b_{i}$ $\displaystyle\sim\ $
$\displaystyle
cn^{\alpha}\sum_{\ell=0}^{\infty}M^{\ell}\sum_{\begin{subarray}{c}k_{1}+\cdots+k_{A}=\ell\\\
n{\bf p}^{{\bf k}}\geq\log n\end{subarray}}{{\ell}\choose{{\bf k}}}\left({\bf
p}^{\bf k}\right)^{\alpha}\sim\frac{cn^{\alpha}}{P(\alpha)},$

where in the last step, we used the estimates from Case 1 and Case 2.

Finally, the claimed result follows by combining the three cases.

In the next two sections, we will see that Proposition 4 can be used to
compute central moments of $S_{n}$ of order three and higher. In fact, it can
be used to compute the variance in the non-uniform case with $\rho>1$ as well
which gives an alternative proof of (14). We will do this next.

First recall that the variance of $S_{n}$ satisfies (5) with toll-sequence
$b_{n}$ given by (15) which can be re-written into

$b_{n}={\mathbb{E}}\left(\Delta_{n,{\mathbf{B}}^{(1)},\ldots,{\mathbf{B}}^{(M)}}\right)^{2}.$
(19)

We will start by deriving the asymptotics of this toll-sequence. Therefore,
denote by $E_{j}^{(i)}$ the event that $|B_{j}^{(i)}-p_{j}n|\leq p_{j}n^{2/3}$
and let $E:=\bigcap_{i,j}E_{j}^{(i)}$. On $E^{c}$, the contribution of the
mean on the righ-hand side of (19) to $b_{n}$ is exponentially small due to
the Chernoff bound for the tail of the binomial distribution. On the other
hand, on $E_{j}^{(i)}$, we obtain by using (10) and Taylor series expansion:

$\left(\mu_{B_{j}^{(i)}}|E_{j}^{(i)}\right)=\sum_{\beta\in{\mathcal{S}}_{(\rho-1,\rho]}}G_{E}(\beta)\left(p_{j}n\right)^{\beta}+\sum_{\beta\in{\mathcal{S}_{(\rho-1,\rho]}}}\beta
G_{E}(\beta)\left(p_{j}n\right)^{\beta-1}\left(B_{j}^{(i)}-p_{j}n\right)+{\mathcal{O}}(n^{\rho-1}).$

Thus, on $E$, we have

$\left(\Delta_{n,{\mathbf{B}}^{(1)},\ldots,{\mathbf{B}}^{(M)}}|E\right)=\sum_{\beta\in{\mathcal{S}}_{(\rho-1,\rho]}}\beta
G_{E}(\beta)\sum_{i=1}^{M}\sum_{j=1}^{A}\left(p_{j}n\right)^{\beta-1}\left(B_{j}^{(i)}-p_{j}n\right)+{\mathcal{O}}(n^{\rho-1})$
(20)

since

$-\sum_{\beta\in{\mathcal{S}}_{(\rho-1,\rho]}}G_{E}(\beta)n^{\beta}+\sum_{\beta\in{\mathcal{S}}_{(\rho-1,\rho]}}G_{E}(\beta)M\sum_{j=1}^{A}\left(p_{j}n\right)^{\beta}=-\sum_{\beta\in{\mathcal{S}}_{(\rho-1,\rho]}}G_{E}(\beta)n^{\beta}P(\beta)=0.$

Consequently, again on $E$,

${\mathbb{E}}\left(\left(\Delta_{n,{\mathbf{B}}^{(1)},\ldots,{\mathbf{B}}^{(M)}}\right)^{2}|E\right)=M{\mathbb{E}}\left(\sum_{\beta\in{\mathcal{S}}_{\rho}}\beta
G_{E}(\beta)\sum_{j=1}^{A}\left(p_{j}n\right)^{\beta-1}\left(B_{j}^{(1)}-p_{j}n\right)\right)^{2}+o(n^{2\rho-1}).$

Notice that

$\displaystyle{\mathbb{E}}\Bigg{(}\sum_{\beta\in{\mathcal{S}}_{\rho}}\beta
G_{E}(\beta)$
$\displaystyle\sum_{j=1}^{A}\left(p_{j}n\right)^{\beta-1}\left(B_{j}^{(1)}-p_{j}n\right)\Bigg{)}^{2}$
$\displaystyle={\mathbb{E}}\left(\sum_{\beta\in{\mathcal{S}}_{\rho}}\beta
G_{E}(\beta)n^{\beta-1}\sum_{j=1}^{A}p_{j}^{\rho-1}\left(B_{j}^{(1)}-p_{j}n\right)\right)^{2}$
$\displaystyle=\left(\sum_{\beta\in{\mathcal{S}}_{\rho}}\beta
G_{E}(\beta)n^{\beta-1}\right)^{2}{\mathbb{E}}\left(\sum_{j=1}^{A}p_{j}^{\rho-1}\left(B_{j}^{(1)}-p_{j}n\right)\right)^{2},$
(21)

where we used that $p_{j}^{\beta}=p_{j}^{\rho}$ for all
$\beta\in{\mathcal{S}}_{\rho}$ and $1\leq j\leq A$. Next,

$\displaystyle{\mathbb{E}}\left(\sum_{j=1}^{A}p_{j}^{\rho-1}\left(B_{j}^{(1)}-p_{j}n\right)\right)^{2}$
$\displaystyle=\sum_{j_{1}=1}^{A}\sum_{j_{2}=1}^{A}p_{j_{1}}^{\rho-1}p_{j_{2}}^{\rho-1}{\mathbb{E}}\left(B_{j_{1}}^{(1)}-p_{j_{1}}n\right)\left(B_{j_{2}}^{(1)}-p_{j_{2}}n\right)$
$\displaystyle=\left(\sum_{j=1}^{A}p_{j}^{2\rho-1}(1-p_{j})-\sum_{j_{1}\neq
j_{2}}p_{j_{1}}^{\rho}p_{j_{2}}^{\rho}\right)n$ (22)
$\displaystyle=\frac{M-1-MP(2\rho-1)}{M^{2}}n$ (23)

since

$\sum_{j=1}^{A}p_{j}^{2\rho-1}=\frac{1-P(2\rho-1)}{M}$

and

$\sum_{j=1}^{A}p_{j}^{2\rho}+\sum_{j_{1}\neq
j_{2}}p_{j_{1}}^{\rho}p_{j_{2}}^{\rho}=\left(\sum_{j=1}^{A}p_{j}^{\rho}\right)^{2}=\frac{1}{M^{2}}.$

Collecting everything and recalling that the contribution to $b_{n}$ of the
expectation on the righ-hand side of (19) on $E^{c}$ is exponentially small,
we obtain that

$b_{n}={\mathbb{E}}\left(\Delta_{n,{\mathbf{B}}^{(1)},\ldots,{\mathbf{B}}^{(M)}}\right)^{2}\sim\frac{M-1-MP(2\rho-1)}{M}\left(\sum_{\beta\in{\mathcal{S}}_{\rho}}\beta
G_{E}(\beta)n^{\beta-1}\right)^{2}n.$

From this (14) follows by applying Proposition 4.

The last thing we want to discuss in this section is the positivity of
$P_{V}(x)$ in the non-uniform case.

######  Lemma 2.

The periodic function $P_{V}(x)$ for the variance in the non-uniform case with
$\rho>1$ is positive.

_Proof._ First observe that the coefficient of $n$ in (22) can be
alternatively written as

$\sum_{j=1}^{A}p_{j}^{2\rho-1}(1-p_{j})-\sum_{j_{1}\neq
j_{2}}p_{j_{1}}^{\rho}p_{j_{2}}^{\rho}=\sum_{1\leq j_{1}<j_{2}\leq
A}p_{j_{1}}p_{j_{2}}\left(p_{j_{1}}^{\rho-1}-p_{j_{2}}^{\rho-1}\right)^{2}$

which shows that this coefficient and consequently also the coefficient of
(14) is positive.

Thus, in order to show the claimed positivity of $P_{V}(x)$, it suffices to
show that $Q(x)$ with

$\sum_{\beta\in{\mathcal{S}}_{\rho}}\beta
G_{E}(\beta)n^{\beta-1}=Q(\log_{a}n)n^{\rho-1}$

is positive. To do this, we argue as in the second proof that $P_{E}(x)>0$
above.

First, from (11) and (12), we have

$Q(x)=\frac{1}{M\left(-\sum_{j=1}^{A}p_{j}^{\rho}\log
p_{j}\right)}\sum_{\beta\in{\mathcal{S}}_{\rho}}\Gamma(2-\beta)e^{(\beta-\rho)(\log
a)x}.$

In the aperiodic case, the claim is easy; in the periodic case, it is
sufficient to prove that

$\sum_{k=-\infty}^{\infty}\Gamma(2-\rho-\chi_{k})e^{2\pi kix}$

is positive, where $\chi_{k}=2k\pi i/(\log a)$. This follows from

$\Gamma(2-\rho-\chi_{k})e^{2\pi kix}=(\log
a)\int_{-\infty}^{\infty}e^{-e^{(x-v)(\log a)}}e^{-\rho(x-v)(\log a)}e^{2\pi
kiv}{\rm d}v,$

which follows by a similar computation as in the second proof of the positive
of $P_{E}(x)$, and another application of the Poisson summation formula.

##  3 Size: Uniform Case

We assume throughout this section that $\rho>1$ and that we are in the uniform
case even though the arguments below also work for $\rho=1$ (both in the
uniform and non-uniform case). However, the latter situation is already
covered by previous work; see the introduction.

We first note that in the uniform case, the solution set of $P(s)=1-MA^{1-s}$
becomes much easier. Clearly, $\rho=1+\log_{A}M$ and thus

${\mathcal{S}}_{\rho}=\left\\{s=1+\log_{A}M+\frac{2k\pi i}{\log M}\ :\
k\in{\mathbb{Z}}\right\\}.$

Also note that there are no zeros of $P(s)$ with $\Re(s)<\rho$. As a
consequence, (20) becomes

$\displaystyle\left(\Delta_{n,{\bf B}^{(1)},\ldots,{\bf B}^{(M)}}|E\right)$
$\displaystyle=\left(\sum_{\beta\in{\mathcal{S}}_{\rho}}\beta
G_{E}(\beta)n^{\beta-1}\right)\left(\sum_{i=1}^{M}\sum_{j=1}^{A}A^{1-\rho}\left(B_{j}^{(i)}-\frac{n}{A}\right)\right)+{\mathcal{O}}(n^{\rho-1})$
$\displaystyle={\mathcal{O}}(n^{\rho-1})=o(n^{\rho/2})$ (24)

since

$A^{1-\rho}\sum_{i=1}^{M}\sum_{j=1}^{A}\left(B_{j}^{(i)}-\frac{n}{A}\right)=A^{1-\rho}\left(Mn-
Mn\right)=0$

and $\rho-1<\rho/2$. (Because we are in the non-explosive case.)

We now consider the third moment which satisfies (8) with

$B_{n}^{(3)}=3MA{\mathbb{E}}\left(A_{B_{1}^{(1)}}^{(2)}\Delta_{n,{\bf
B}^{(1)},\ldots,{\bf B}^{(M)}}\right)+{\mathbb{E}}\left(\Delta_{n,{\bf
B}^{(1)},\ldots,{\bf B}^{(M)}}\right)^{3}.$

From (24) and the result for the variance (Proposition 2), we have

${\mathbb{E}}\left(A_{B_{1}^{(1)}}^{(2)}\Delta_{n,{\bf B}^{(1)},\ldots,{\bf
B}^{(M)}}\right)=o(n^{3\rho/2}),$

where we used that the contribution of the mean on $E^{c}$ is exponentially
small. Likewise,

${\mathbb{E}}\left(\Delta_{n,{\bf B}^{(1)},\ldots,{\bf
B}^{(M)}}\right)^{3}=o(n^{3\rho/2}).$

Thus, $B_{n}^{(3)}=o(n^{3\rho/2})$ and by Proposition 4,

$A_{n}^{(3)}=o(n^{3\rho/2}).$

From the above simple argument, we also get a proof of Theorem 1 for the
uniform case via the contraction method.

Proof of Theorem 1 in the uniform case. We apply Corollary 5.2 in [17] to (4)
which implies the claimed result upon checking the conditions of this
corollary the most important of which is:

${\mathbb{E}}|\Delta_{n,{\bf B}^{(1)},\ldots,{\bf
B}^{(M)}}|^{3}=o(n^{3\rho/2}).$

This condition immediately follows from (24).

Alternatively, we can compute higher moments which also leads to a proof of
Theorem 1 by applying the Fréchet-Shohat theorem to the following proposition.

######  Proposition 5.

For $m\geq 0$,

$A_{n}^{(m)}\sim
g_{m}\left(\sum_{\beta\in{\mathcal{S}}_{\rho}}G_{V}(\beta)n^{\beta}\right)^{m/2},$

where $g_{m}$ denotes the $m$-th moment of the standard normal distribution,
i.e.,

$g_{m}:=\begin{cases}m!/(2^{m/2}(m/2)!),&\text{if}\ m\ \text{is even};\\\
0,&\text{if}\ m\ \text{is odd}.\end{cases}$

_Proof._ We use induction on $m$. First note that $m=0$ and $m=1$ are trivial,
$m=2$ is contained in Proposition 2-(i), and $m=3$ was proved above. Next,
assume that the statement is true for all $m^{\prime}<m$. We are going to
proof it for $m$.

First, consider $B_{n}^{(m)}$ which is given by

$B_{n}^{(m)}=\sum_{\boldsymbol{\ell}^{(1)},\ldots,\boldsymbol{\ell}^{(M)},\ell}\binom{m}{\boldsymbol{\ell}^{(1)},\ldots,\boldsymbol{\ell}^{(M)},\ell}{\mathbb{E}}\left(\left(\prod_{i=1}^{M}\prod_{j=1}^{A}A_{B_{j}^{(i)}}^{(\ell_{j}^{(i)})}\right)\Delta_{n,{\mathbf{B}}^{(1)},\ldots,{\mathbf{B}}^{(M)}}^{\ell}\right).$

Note that by (24) and the induction hypothesis, whenever $\ell\geq 1$,

${\mathbb{E}}\left(\left(\prod_{i=1}^{M}\prod_{j=1}^{A}A_{B_{j}^{(i)}}^{(\ell_{j}^{(i)})}\right)\Delta_{n,{\mathbf{B}}^{(1)},\ldots,{\mathbf{B}}^{(M)}}^{\ell}\Big{|}E\right)=o\left(n^{(\ell+\sum_{i=1}^{M}\sum_{j=1}^{A}\ell_{j}^{(i)})/2}\right)=o(n^{m/2}),$

where we used (9). Thus, from the exponential smallness of the above
expectation on $E^{c}$, we have

${\mathbb{E}}\left(\left(\prod_{i=1}^{M}\prod_{j=1}^{A}A_{B_{j}^{(i)}}^{(\ell_{j}^{(i)})}\right)\Delta_{n,{\mathbf{B}}^{(1)},\ldots,{\mathbf{B}}^{(M)}}^{\ell}\right)=o(n^{m/2})$

which means (in view of the claimed result) that the main contribution to
$B_{n}^{(m)}$ comes from the terms with $\ell=0$. For these terms, again by
the induction hypothesis and (9) together with Taylor series expansion:

${\mathbb{E}}\left(\left(\prod_{i=1}^{M}\prod_{j=1}^{A}A_{B_{j}^{(i)}}^{(\ell_{j}^{(i)})}\right)\Big{|}E\right)\sim\left(\sum_{\beta\in{\mathcal{S}}_{\rho}}G_{V}(\beta)\left(\frac{n}{A}\right)^{\beta}\right)^{m/2}\left(\prod_{i=1}^{M}\prod_{j=1}^{A}g_{\ell_{j}^{(i)}}\right)$

and this asymptotic again holds with the conditioning on $E$ removed.
Consequently,

$\displaystyle\sum_{\boldsymbol{\ell}^{(1)},\ldots,\boldsymbol{\ell}^{(M)}}$
$\displaystyle\binom{m}{\boldsymbol{\ell}^{(1)},\ldots,\boldsymbol{\ell}^{(M)}}{\mathbb{E}}\left(\left(\prod_{i=1}^{M}\prod_{j=1}^{A}A_{B_{j}^{(i)}}^{(\ell_{j}^{(i)})}\right)\right)$
$\displaystyle\sim\left(\sum_{\beta\in{\mathcal{S}}_{\rho}}G_{V}(\beta)n^{\beta}\right)^{m/2}A^{-\rho
m/2}\sum_{\boldsymbol{\ell}^{(1)},\ldots,\boldsymbol{\ell}^{(M)}}\binom{m}{\boldsymbol{\ell}^{(1)},\ldots,\boldsymbol{\ell}^{(M)}}\left(\prod_{i=1}^{M}\prod_{j=1}^{A}g_{\ell_{j}^{(i)}}\right)$
$\displaystyle\sim g_{m}P(\rho
m/2)\left(\sum_{\beta\in{\mathcal{S}}_{\rho}}G_{V}(\beta)n^{\beta}\right)^{m/2},$

where in the first step we used that $A^{-\beta}=A^{-\rho}$ for
$\beta\in{\mathcal{S}}_{\rho}$ and in the second step:

$\sum_{\boldsymbol{\ell}^{(1)},\ldots,\boldsymbol{\ell}^{(M)}}\binom{m}{\boldsymbol{\ell}^{(1)},\ldots,\boldsymbol{\ell}^{(M)}}\left(\prod_{i=1}^{M}\prod_{j=1}^{A}g_{\ell_{j}^{(i)}}\right)=g_{m}((MA)^{m/2}-MA)=g_{m}A^{-\rho
m/2}P(\rho m/2)$

which is trivial if $m$ is odd (since all terms are zero) and follows easily
from the multinomial theorem if $m$ is even. Moreover, we used that
$MA=A^{\rho}$ in the last step.

Finally, by applying Proposition 4, we obtain that

$A_{n}^{(m)}\sim
g_{m}\left(\sum_{\beta\in{\mathcal{S}}_{\rho}}G_{V}(\beta)n^{\beta}\right)^{m/2}$

which proves the claim.

##  4 Size: Non-Uniform Case

We assume throughout this section that $\rho>1$ and that we are in the non-
uniform case.

The proof of Theorem 1 follows from the the following proposition and the
Fréchet-Shohat Theorem.

######  Proposition 6.

For $m\geq 0$,

$A_{n}^{(m)}\sim g_{m}c^{m/2}\left(\sum_{\beta\in{\mathcal{S}}_{\rho}}\beta
G_{E}(\beta)n^{\beta-1}\right)^{m}n^{m/2},$

where

$c:=\frac{M-1}{MP(2\rho-1)}-1$

and $g_{m}$ denotes the $m$-th moment of the standard normal distribution.

_Proof._ The proof is by induction of $m$. The claim is trivial for $m=0$ and
$m=1$ and was proved for $m=2$ in Section 2. Therefore, we assume that the
claim is true for all $m^{\prime}<m$. We are going to establish it for $m$.

First, consider $B_{n}^{(m)}$ which as in proof of Proposition 5 is given by

$B_{n}^{(m)}=\sum_{\boldsymbol{\ell}^{(1)},\ldots,\boldsymbol{\ell}^{(M)},\ell}\binom{m}{\boldsymbol{\ell}^{(1)},\ldots,\boldsymbol{\ell}^{(M)},\ell}{\mathbb{E}}\left(\left(\prod_{i=1}^{M}\prod_{j=1}^{A}A_{B_{j}^{(i)}}^{(\ell_{j}^{(i)})}\right)\Delta_{n,{\mathbf{B}}^{(1)},\ldots,{\mathbf{B}}^{(M)}}^{\ell}\right).$

Recall the definition of the events $E_{j}^{(i)}$ in the derivation of the
variance from Section 2. On $E_{j}^{(i)}$, by induction hypothesis and Taylor
series expansion, we have

$\displaystyle\left(A_{B_{j}^{(i)}}^{(\ell_{j}^{(i)})}|E_{j}^{(i)}\right)$
$\displaystyle\sim
g_{\ell_{j}^{(i)}}c^{\ell_{j}^{(i)}/2}\left(\sum_{\beta\in{\mathcal{S}}_{\rho}}\beta
G_{E}(\beta)\left(p_{j}n\right)^{\beta-1}\right)^{\ell_{j}^{(i)}}(p_{j}n)^{\ell_{j}^{(i)}/2}$
$\displaystyle\sim
g_{\ell_{j}^{(i)}}p_{j}^{(\rho-1/2)\ell_{j}^{(i)}}c^{\ell_{j}^{(i)}/2}\left(\sum_{\beta\in{\mathcal{S}}_{\rho}}\beta
G_{E}(\beta)n^{\beta-1}\right)^{\ell_{j}^{(i)}}n^{\ell_{j}^{(i)}/2},$

where we used that $p_{j}^{\beta}=p_{j}^{\rho}$ for
$\beta\in\mathcal{S}_{\rho}$ and $1\leq j\leq A$. Consequently,

$\displaystyle{\mathbb{E}}$
$\displaystyle\Bigg{(}\Bigg{(}\prod_{i=1}^{M}\prod_{j=1}^{A}A_{B_{j}^{(i)}}^{(\ell_{j}^{(i)})}\Bigg{)}\Delta_{n,{\mathbf{B}}^{(1)},\ldots,{\mathbf{B}}^{(M)}}^{\ell}\Big{|}E\Bigg{)}$
$\displaystyle\sim\left(\prod_{i=1}^{M}\prod_{j=1}^{A}g_{\ell_{j}^{(i)}}p_{j}^{(\rho-1/2)\ell_{j}^{(i)}}\right)c^{(m-\ell)/2}\left(\sum_{\beta\in{\mathcal{S}}_{\rho}}\beta
G_{E}(\beta)n^{\beta-1}\right)^{m-\ell}n^{(m-\ell)/2}{\mathbb{E}}\left(\Delta_{n,{\mathbf{B}}^{(1)},\ldots,{\mathbf{B}}^{(M)}}^{\ell}|E\right),$
(25)

where we used (9). Next, from (20),

${\mathbb{E}}\left(\Delta_{n,{\mathbf{B}}^{(1)},\ldots,{\mathbf{B}}^{(M)}}^{\ell}|E\right)\sim\left(\sum_{\beta\in{\mathcal{S}}_{\rho}}\beta
G_{E}(\beta)n^{\beta-1}\right)^{\ell}{\mathbb{E}}\left(\sum_{i=1}^{M}\sum_{j=1}^{A}p_{j}^{\rho-1}\left(B_{j}^{(i)}-p_{j}n\right)\right)^{\ell},$
(26)

where we used a similar computation as in (21). By expanding the last
expectation, we obtain that

${\mathbb{E}}\left(\sum_{i=1}^{M}\sum_{j=1}^{A}p_{j}^{\rho-1}\left(B_{j}^{(i)}-p_{j}n\right)\right)^{\ell}=\sum_{{\bf
k}}\binom{\ell}{{\bf
k}}\prod_{i=1}^{M}{\mathbb{E}}\left(\sum_{j=1}^{A}p_{j}^{\rho-1}\left(B_{j}^{(1)}-p_{j}n\right)\right)^{k_{i}},$

where ${\bf k}=(k_{1},\ldots,k_{M})$ such that $\sum_{i=1}^{M}k_{i}=\ell$.
Now, from the central limit theorem for the multinomial distribution, we have
in distribution and with convergence of all moments:

$\frac{\sum_{j=1}^{A}p_{j}^{\rho-1}\left(B_{j}^{(1)}-p_{j}n\right)}{\sqrt{n}}\stackrel{{\scriptstyle
d}}{{\longrightarrow}}N\left(0,\frac{P(2\rho-1)c}{M}\right),$

where the variance was computed in (23). Thus,

${\mathbb{E}}\left(\sum_{i=1}^{M}\sum_{j=1}^{A}p_{j}^{\rho-1}\left(B_{j}^{(i)}-p_{j}n\right)\right)^{\ell}\sim\left(\frac{P(2\rho-1)c}{M}\right)^{\ell/2}n^{\ell/2}\sum_{{\bf
k}}\binom{\ell}{{\bf k}}\left(\prod_{i=1}^{M}g_{k_{i}}\right).$

Note that

$\sum_{{\bf k}}\binom{\ell}{{\bf
k}}\left(\prod_{i=1}^{M}g_{k_{i}}\right)=g_{\ell}M^{\ell/2}$

which is trivial if $\ell$ is odd and follows from the multinomial theorem if
$\ell$ is even. Consequently,

${\mathbb{E}}\left(\sum_{i=1}^{M}\sum_{j=1}^{A}p_{j}^{\rho-1}\left(B_{j}^{(i)}-p_{j}n\right)\right)^{\ell}\sim
g_{\ell}\left(P(2\rho-1)c\right)^{\ell/2}n^{\ell/2}.$

Now, plugging this into (26) and (26) in turn into (25), we obtain that

$\displaystyle{\mathbb{E}}\Bigg{(}\Bigg{(}\prod_{i=1}^{M}\prod_{j=1}^{A}$
$\displaystyle
A_{B_{j}^{(i)}}^{(\ell_{j}^{(i)})}\Bigg{)}\Delta_{n,{\mathbf{B}}^{(1)},\ldots,{\mathbf{B}}^{(M)}}^{\ell}\Big{|}E\Bigg{)}$
$\displaystyle\sim\left(\prod_{i=1}^{M}\prod_{j=1}^{A}g_{\ell_{j}^{(i)}}p_{j}^{(\rho-1/2)\ell_{j}^{(i)}}\right)g_{\ell}P(2\rho-1)^{\ell/2}c^{m/2}\left(\sum_{\beta\in{\mathcal{S}}_{\rho}}\beta
G_{E}(\beta)n^{\beta-1}\right)^{m}n^{m/2}$

and the same holds without the conditioning on $E$ since the conditional
expectation conditioned on the complement of $E$ is exponentially small.
Plugging this into the expression for $B_{n}^{(m)}$ gives

$B_{n}^{(m)}\sim dc^{m/2}\left(\sum_{\beta\in{\mathcal{S}}_{\rho}}\beta
G_{E}(\beta)n^{\beta-1}\right)^{m}n^{m/2},$

where

$d=\sum_{\boldsymbol{\ell}^{(1)},\ldots,\boldsymbol{\ell}^{(M)},\ell}g_{\ell}\binom{m}{\boldsymbol{\ell}^{(1)},\ldots,\boldsymbol{\ell}^{(M)},\ell}\left(\prod_{i=1}^{M}\prod_{j=1}^{A}g_{\ell_{j}^{(i)}}p_{j}^{(\rho-1/2)\ell_{j}^{(i)}}\right)P(2\rho-1)^{\ell/2}=g_{m}P((\rho-1/2)m).$

which is trivial if $m$ is odd and follows from the multinomial theorem if $m$
is even. Overall,

$B_{n}^{(m)}\sim
g_{m}P((\rho-1/2)m)c^{m/2}\left(\sum_{\beta\in{\mathcal{S}}_{\rho}}\beta
G_{E}(\beta)n^{\beta-1}\right)^{m}n^{m/2}.$

Finally, applying Proposition 4 gives

$A_{n}^{(m)}\sim g_{m}c^{m/2}\left(\sum_{\beta\in{\mathcal{S}}_{\rho}}\beta
G_{E}(\beta)n^{\beta-1}\right)^{m}n^{m/2}.$

This concludes the proof of the induction step.

######  Remark 4.

From the above proof, we see that

${\mathbb{E}}\left(\Delta_{n,{\bf B}^{(1)},\ldots,{\bf
B}^{(M)}}^{3}\right)\sim
g_{3}(P(2\rho-1)c)^{3/2}\left(\sum_{\beta\in{\mathcal{S}}_{\rho}}\beta
G_{E}(\beta)n^{\beta-1}\right)^{3}n^{3/2}=o\left(n^{3(\rho-1/2)}\right)$

since $g_{3}=0$. In order to be able to apply the contraction method in the
non-uniform case, we would need

${\mathbb{E}}|\Delta_{n,{\bf B}^{(1)},\ldots,{\bf
B}^{(M)}}|^{3}=o\left(n^{3(\rho-1/2)}\right),$

however, it is not clear how to prove this (provided that this even holds).

##  5 Extensions

The method we used to prove Theorem 1 has some generality and can be applied
to other additive parameters of G-tries as well. In this section, we will
briefly discuss two such classes of parameters.

### External Nodes containing Keys and Empty External Nodes.

The G-trie built from $n$ random keys can be completed by adding external
nodes so that all internal nodes of the G-trie have outdegree $MA$. Some of
these external nodes will contain data and some not where an external node is
of the first type if and only if the path with its labeling represented by the
node can be found in exactly one of the $n$ keys.

Denote by $K_{n}$ and $R_{n}$ the external nodes of type 1 and type 2. Note
that $K_{n}=n$ if $\rho=1$ and this is the only case where one of these random
variables is deterministic. Clearly, $K_{n}$ and $R_{n}$ both satisfy the
recurrence (4) with the only difference that the initial conditions are
different: $K_{0}=0$ and $K_{1}=1$ for $K_{n}$ and $R_{0}=1$ and $R_{1}=0$ for
$R_{n}$. In fact, we can more generally define

$N_{n}:=\alpha R_{n}+\beta K_{n}+\gamma S_{n},$

where $\alpha,\beta,\gamma\geq 0$ with at least one of them positive. Then,

$N_{n}\stackrel{{\scriptstyle
d}}{{=}}\sum_{i=1}^{M}\sum_{j=1}^{A}N_{B_{j}^{(i)}}^{(i,j)}+\gamma,\qquad(n\geq
2),$

where notation is as in the introduction and $N_{0}=\alpha$ and $N_{1}=\beta$.

Using the tools from [9] and from this paper, the following result holds for
$N_{n}$.

######  Theorem 2.

We have,

${\mathbb{E}}(N_{n})\sim Q_{E}(\log_{a}n)n^{\rho},\qquad(n\rightarrow\infty),$

and

${\rm Var}(N_{n})\sim\begin{cases}Q_{V}(\log_{a}n)n^{\rho},&\text{if}\
p_{j}=1/A\ \text{for}\ 1\leq j\leq A;\\\
Q_{V}(\log_{a}n)n^{2\rho-1},&\text{otherwise},\end{cases}\qquad(n\rightarrow\infty),$

where $a>1$ and $Q_{E}(x),Q_{V}(x)$ are computable 1-periodic function.
Moreover,

$\frac{N_{n}-{\mathbb{E}}(N_{n})}{\sqrt{{\rm
Var}(N_{n})}}\stackrel{{\scriptstyle d}}{{\longrightarrow}}N(0,1).$

### Leaves and Patterns.

Another class of examples arises from counting patterns, e.g., the number of
leaves in a G-trie. We use this number as guiding example, although more
general patterns can be considered as well.

Denote by $L_{n}$ the number of leaves of a G-trie built from $n$ random keys,
e.g., $L_{n}=2$ for the G-trie in Figure 3. Clearly, $L_{n}$ is additive since
it satisfies the recurrence:

$L_{n}\stackrel{{\scriptstyle
d}}{{=}}\sum_{i=1}^{M}\sum_{j=1}^{A}L_{B_{j}^{(i)}}^{(i,j)}+T_{n},\qquad(n\geq
2),$

where $L_{0}=0$ and $L_{1}=1$ and

$T_{n}=\begin{cases}1,&\text{if}\ B_{j}^{(i)}\in\\{0,1\\}\ \text{for all}\
1\leq i\leq M\ \text{and}\ 1\leq j\leq A;\\\ 0,&\text{otherwise}.\end{cases}$

Again the tools from [9] and this paper can be applied to obtain the following
result.

######  Theorem 3.

We have,

${\mathbb{E}}(L_{n})\sim H_{E}(\log_{a}n)n^{\rho},\qquad(n\rightarrow\infty),$

and

${\rm Var}(L_{n})\sim\begin{cases}H_{V}(\log_{a}n)n^{\rho},&\text{if}\
p_{j}=1/A\ \text{for}\ 1\leq j\leq A;\\\
H_{V}(\log_{a}n)n^{2\rho-1},&\text{otherwise},\end{cases}\qquad(n\rightarrow\infty),$

where $a>1$ and $H_{E}(x),H_{V}(x)$ are computable 1-periodic function.
Moreover,

$\frac{L_{n}-{\mathbb{E}}(L_{n})}{\sqrt{{\rm
Var}(L_{n})}}\stackrel{{\scriptstyle d}}{{\longrightarrow}}N(0,1).$

##  6 Conclusion

In this paper we considered G-tries which are interesting new data structures
that were recently proposed by Jacquet who computed the mean and variance of
the size of a G-trie. Moreover, he conjectured a central limit theorem (see
the conclusion of [9]) which we proved in this paper by applying the method of
moments. This shape parameter is interesting because its mean and variance in
the non-classical and non-uniform case behave very different from the
classical case: it is one of the few known examples of a shape parameters of
discrete random structures arising from computer science with a variance of a
considerable larger asymptotic order than the mean yet still a central limit
theorem holds. The proof of the central limit theorem for this parameter seems
to lie outside (or at the boundary) of most established methods leaving only
the method of moments as last weapon as demonstrated in this paper.

The approach in this paper (based on an asymptotic transfer of the underlying
recurrence and computation of all moments as in [8]) has some generality and,
together with the analytic tools used by Jacquet in [9], can be applied to
other additive shape parameters of G-tries as well in order to obtain similar
central limit theorem phenomena. Moreover, it can also be applied to some non-
additive shape parameters such as the insertion cost which was also discussed
by Jacquet in [9]. However, this example is less interesting because mean and
variance have the same order and thus, as in the uniform case from Section 3,
the contraction method can easily be applied to prove a central limit theorem
(this was already pointed out in [9]).

In this paper we considered G-tries where the underlying graph G is an $M$-ary
tree. Thus, an interesting question is how about the size (and other shape
parameters) for G-tries with a general (acyclic) graph G? For this situation,
Jacquet in [9] computed the mean, however, even the computation of the
variance seems to be a considerable challenge; see the recent paper of Jacquet
and Magner [10].

## References

  * [1] P. Billingsley. Probability and Measure, Wiley Series in Probability and Mathematical Statistics, third edition, John Wiley & Sons, Inc., New York, 1995.
  * [2] P. Flajolet, X. Gourdon, P. Dumas (1995). Mellin transforms and asymptotics: harmonic sums, Theoret. Comput. Sci., 144:1-2, 3–58.
  * [3] P. Flajolet, M. Roux, B. Vallée (2010). Digital trees and memoryless sources: from arithmetics to analysis, Discrete Math. Theor. Comput. Sci. Proc., Proceedings of the 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA’10), 233–260.
  * [4] P. Flajolet and R. Sedgewick. Analytic Combinatorics, Cambridge University Press, Cambdrige, 2009.
  * [5] P. Flajolet, W. Szpankowski, B. Vallée (2006). Hidden word statistics, J. ACM, 53:1, 147–183.
  * [6] M. Fuchs, H.-K. Hwang, V. Zacharovas (2014). An analytic approach to the asymptotic variance of trie statistics and related structures, Theor. Comput. Sci., 527, 1–36 (2014).
  * [7] M. Fuchs and C.-K. Lee (2014). A general central limit theorem for shape parameters of $m$-ary tries and PATRICIA tries, Electron. J. Combin., 21:1, 26 pages.
  * [8] F. Hubalek, H.-K. Hwang, W. Lew, H. Mahmoud, H. Prodinger (2002). A multivariate view of random bucket digital search trees, J. Algorithms, 44:1, 121–158.
  * [9] P. Jacquet (2014). Trie structure for graph sequences, Discrete Math. Theor. Comput. Sci. Proc., Proceedings of the 25th International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA’14), 73–84.
  * [10] P. Jacquet and A. Magner (2015). Variance of size in regular graph tries, Proceedings of the Twelfth Workshop on Analytic Algorithmics and Combinatorics (ANALCO), 97–104.
  * [11] P. Jacquet and M. Régnier (1988). Normal limiting distribution of the size of tries, In Performance87 (Brussels, 1987), North-Holland, Amsterdam, 209–223.
  * [12] P. Jacquet and W. Szpankowski (1998). Analytical de-Poissonization and its applications, Theoret. Comput. Sci. 201:1-2, 1–62.
  * [13] P. Jacquet and W. Szpankowski. Analytic Pattern Matching: From DNA to Twitter, Cambridge University Press, 1st Edition, 2015.
  * [14] M. Javanian (2018). Protected node profile of tries, Discrete Math. Theor. Comput. Sci., 20:1, Paper 12.
  * [15] K. Leckey, R. Neininger, W. Szpankowski. A limit theorem for radix sort and tries with Markovian input, submitted.
  * [16] C.-K. Lee. Probabilistic Analysis of Additive Shape Paramters in Random Digital Trees, National Chiao Tung University, PhD thesis, 2014.
  * [17] R. Neininger and L. Rüschendorf (2004). A general limit theorem for recursive algorithms and combinatorial structures, Ann. Appl. Probab., 14:1, 378–418.
  * [18] W. Schachinger (1995). On the variance of a class of inductive valuations of data structures for digital search, Theoret. Comput. Sci., 144, 251–275.