{'fraction_non_alphanumeric': 0.048254072463173446, 'fraction_numerical': 0.016248820319231874, 'mean_word_length': 4.033457249070632, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The oscillatory distribution of distances in random tries

We investigate \Delta_n, the distance between randomly selected pairs of nodes among n keys in a random trie, which is a kind of digital tree. Analytical techniques, such as the Mellin transform and an excursion between poissonization and depoissonization, capture small fluctuations in the mean and variance of these random distances. The mean increases logarithmically in the number of keys, but curiously enough the variance remains O(1), as n\to\infty. It is demonstrated that the centered random variable \Delta_n^*=\Delta_n-\lfloor2\log_2n\rfloor does not have a limit distribution, but rather oscillates between two distributions.

1. Introduction. In this computer age that we are living in, digital data, which are represented and accessed via their composition into digits, are quite ubiquitous in science and technology. They are prevalent in computer files, telecommunication signals, DNA and so forth. Digital searching deals with the storage of information in a computer's memory and its fast recovery [9]. Various forms of digital trees are known to be super efficient for this purpose. The subject of this investigation is the trie, one popular such digital technology, initially proposed independently by De La Briandais [2] and Fredkin [4] for information retrieval.
In informatics, distances between nodes in a random combinatorial object are of prime interest, because they are indicative of the speed of communication within the structure. These distances have applications in many other fields too. For example, the collective sum of all such distances in the graph underlying a molecule is known in chemistry as the Wiener index (see [5] and [19]).
In this paper we look at the distances between distinct pairs of keys in random binary tries. The mean and variance and ultimately the asymptotic distribution (via its moment generating function) are derived by analytical methods involving the use of poissonization, as a mathematical transform, and of depoissonization, as an asymptotic inverse transform. Although the chief interest lies in studying the random tree for a fixed population of n keys, the recurrence equations involved are rather unwieldy. If a Poisson number of keys is assumed instead, the functional equations involved can asymptotically be solved by the Mellin transform and its inverse. It can then be justified that the solution is a good approximation (with quantifiable small errors) for the fixed-population problem, when the Poisson parameter is taken to be n, as n → ∞.
Analogous studies have been conducted on binary search trees (a different model of random trees), as, for example, the study of the Wiener index [14], and the study of random distances [13] and its generalization to spanning trees of subsets of nodes [15]. However, the methodology for binary search trees is essentially different from the analytic tool-kit we employ here for tries.
Assume a standard Bernoulli probability model on data. Let ∆ n be the distance between two randomly chosen keys in a trie. Two of our results concern the mean and variance, and the periodic fluctuations therein (the notation lg stands for log 2 ): where α ≈ 7.227113 is a constant explicitly found as a numerical series, and η(·) and ξ(·) are bounded functions of miniscule magnitude which are periodic in their argument. The error terms include additional small periodic functions as well. Note that the variance is O(1), a highly desirable feature in a data structure; this property indicates robustness of random digital trees in spite of the large variation in the data.
In view of the O(1) variance, one expects that if a nontrivial limit distribution were to exist, it would require only centering, but no scaling. Our main result is that a centered integer version of ∆ n does not converge in distribution to any random variable. Rather its distribution function assumes the form of a discrete staircase distribution which oscillates between two distinct fixed discrete distribution functions.
The main results have been sketched. The rest of the paper is organized in sections as follows. In Section 2 the definition of a trie is given and illustrated by an example, and the associated trie terminology is made precise. The probability distribution assumed on the data is also discussed. At the end of Section 2, notation that is used as a working language throughout OSCILLATORY DISTRIBUTION IN TRIES 3 is explained. The moments are discussed in Section 3 and the moment generating function is derived in Section 3.1. The poissonization-Mellin-inverse Mellin-depoissonization program is illustrated in this context. The residue calculation is taken up in Section 3.2. Some of the very lengthy calculations are relegated to Appendixes A and B. The first two moments are pumped out from the Mellin transform of the moment generating function. This is done thoroughly for the mean in Section 3.3 and only sketched for the variance in Section 3.4. The oscillating nature of the moment generating function elicits the nonexistence of a limit distribution. This is shown in Section 3.5 by demonstrating explicit fluctuations in the moment generating function. Section 4 concludes the paper with an interpretation of the results and a discussion of their scope.

Tries.
A trie is a digital tree structure consisting of internal nodes that have one or two children, and leaf nodes that hold data items (commonly called keys). We shall assume our data to be binary (although our methods should work well for larger alphabets too). Suppose we have n ≥ 0 keys given in their dyadic representation. Data are scaled to be in the interval [0, 1]. The trie grows by the progressive insertion of keys. If n = 0, nothing needs to be done; the insertion algorithm terminates. If n = 1, a leaf is allocated for the single key given. If n ≥ 2, an internal node is allocated as a root of the tree; keys with 0 as their most significant bit go to the left subtree, and keys with 1 to the right. Subsequently, in the subtrees the insertion algorithm is applied recursively, using the (ℓ + 1)st most significant bit of the key for branching at level ℓ. At termination, each key is stored in a leaf by itself, and the root-to-leaf paths in the tree correspond to minimal prefixes sufficient to distinguish the keys. As an illustration, suppose that n = 5 and that the data are the following: The algorithm guides X 1 , X 3 and X 4 to the left subtree, and it guides X 2 and X 5 to the right one. Then, in the left subtree X 1 and X 3 go to the left but X 4 goes to the right, whereas in the right subtree, both X 2 and X 5 go to the right. The subtree containing X 1 and X 3 is developed further into a left subtree with X 3 being a leaf node as it is the only node in the subtree, and a right subtree with X 1 contained in a leaf node as it is the only node in the subtree, and so on. The resulting trie is depicted in Figure 1, with model, L n and R n are both distributed like Bin(n, 1 2 ), a binomially distributed random variable on n independent trials and rate of success 1 2 per trial. Because of the probability distribution of the keys and the recursive action of the insertion algorithm, each of the left and the right subtree preserves the probabilistic structure of the trie. The only difference is that they are random tries constructed on L n and R n keys, respectively, instead of n.
Given L n , ∆ n can be ∆ Ln with probability Ln 2 / n 2 when both keys come from the left subtree,∆ Rn with probability Rn 2 / n 2 when both keys come from the right subtree or (δ Ln + 1) + (δ Rn + 1) with probability L n R n / n 2 when the keys come from different subtrees [here a tilded random variable indicates an independent copy (with the same distribution) of that random variable]. Hence, we have the conditional distribution with probability where the vector (∆ 1 , . . . ,∆ n ) denotes a copy of random distances independent of the vector (∆ 1 , . . . , ∆ n ); likewise, (δ 1 , . . . ,δ n ) and (δ 1 , . . . , δ n ) are vectors of independent copies of random depths. It is important to note that ∆ Ln and∆ Rn are dependent through the dependency of L n and R n , but given the value of L n (and, hence, R n ), the two are conditionally independent; the same applies to δ Ln andδ Rn .
3.1. The moment generating function. From the conditional recursion (1), we have a recurrence for the conditional moment generating function: Taking expectation of both sides, we essentially get a recurrence for the moment generating function: We observe the symmetry of the left and the right subtrees, and the fact that L n is distributed like Bin(n, 1 2 ). After multiplying by z n and summing where for any generic random variable X, φ X (t) := E[e tX ]. This gives Averaging N (z) 2 e ∆ N(z) t is just like averaging n 2 e ∆nt , except that we assume a Poisson number of keys instead of a fixed population n. As we shall see, the advantage of poissonization is that the Poisson model is amenable to the formulation of functional equations that can be asymptotically solved by the Mellin transform techniques. The various fixed-population problems are averaged over cases with Poisson probabilities as weights. The fixedpopulation asymptotics can be well approximated by their depoissonized counterparts.
When we multiply (2) throughout by e −z , we get the functional equation We want to study convergence issues of moment generating functions in a neighborhood around t = 0 (via the Mellin transform). The Mellin transform of the latter functional equation does not exist in such a neighborhood to recover the moment generating function. For example, at t = 0, the latter equation becomes and we cannot take the Mellin transform of the equation because z 2 does not have such a transform. Nevertheless, the same equation shifted down by z 2 /2 has a Mellin transform. It turns out that for general t, the factor e 2t z 2 2 is a suitable shift. Introduce this shift to get that is, where well defined for −3, −2 − 2|t| ln 2 , for |t| < 1 2 ln 2.
Proof. The bulk of this computation is in the handling of the function F (t, z), which is a squared generating function. We relegate this lengthy computation to Appendixes A and B.
Note that, for negative t, the strip −3, −2 − 2t ln 2 includes the entire strip −3, −2 , and, for all |t| < 1 2 ln 2, the Mellin transform exists in −3, −2 − 2|t| ln 2 . The inverse Mellin transform,  We employ the method of "closing the box." (This method is discussed in [12] and [18].) In this method one takes the complex integration over the line c − iM and c + iM , and then closes the box connecting the four corners c ± iM and d ± iM , for an arbitrary d > 0. The number M is chosen in such a way that no pole is crossed. For example, we can take it to be πi(2m+1) ln 2 , for integer m. The residue theorem points out that The contour integral can be written as As we let m → ∞ (hence, M → ∞), the line integrals at the top and bottom sides of the box approach 0, as the magnitude of the Γ function decreases exponentially fast with its imaginary part. Moreover, the integral at the right side of the box introduces an error term of the order of O(z −d ). Hence, (4) gives The problem has now been reduced to residue computation.

Residue computation.
We have the following residue calculations: Res and, for j = 0, Hence, for any arbitrary d > 0, We next check the conditions of the depoissonization lemma [7]. For the reader's convenience, we state this lemma.
n=0 be a sequence of real numbers. Suppose that the poissonized function P(z) = ∞ j=0 a j z j j! e −z exists and can be analytically continued as an entire function of complex z. Fix θ ∈ (0, π/2) and let S θ be the cone {z : | arg z| ≤ θ}. Suppose that there exist positive constants α < 1, β 1 , β 2 , c and z 0 such that the following conditions hold simultaneously: Then for large n, a n = P(n) + O(n c−1/2 ln n).
For the rest of the paper we restrict t to the interval [−0.1, 0.1]. For any fixed t in this range, we can think of φ n (t) as a sequence of n. It is clear that for this range of t, the poissonized function P (t, z) is O(z 2+2t/ln 2 ) inside the cone S θ , and is O(|z| 2+2t/ln 2 e |z| cos θ ) outside that cone.
By Lemma 2, E[ n 2 e ∆nt ] is the same as the poissonized version, with n replacing z. When we divide by n 2 , we get a depoissonization correction error of the order O(n 2t/ln 2−1/2 lg n) in the moment generating function. The Mellin inversion gives an error term of O(n −d ) for arbitrary d > 0. Thus, combined, the two errors cannot be brought below O(n 2t/ln 2−1/2 lg n).
Therefore, we have where [Note that the rest of the terms of κ(t, lg z) are subsumed by the O error term.] 3.3. The mean. It may be possible to determine the moments of ∆ n directly from (5). However, the error requires subtle handling owing to the presence of O terms, which cannot be differentiated without some regularity conditions. It is about the same effort to bypass these regularity conditions, and work indirectly from the Mellin transforms of the moments.
The derivative ∂ k P * (t, s)/∂t k , evaluated at t = 0, yields (a shifted version of ) the Mellin transform of the expectation of the poissonized quantity N (z) 2 ∆ k N (z) . We start with the mean (k = 1). Let e −z A(z) = E[ N (z) 2 ∆ N (z) ], and B(z) = e −z A(z)−z 2 . Taking the first derivative of P * (t, s) (cf. Lemma 1) and evaluating it at t = 0, we get well defined for −3, −2 . The inverse Mellin transform is The transform B * (s) has a double pole at s = −2, which will provide the asymptotically dominant term (the major part of the complex integration), and simple poles at s = −1 + 2πki ln 2 , for k = 0, ±1, . . . , at s = −2 + 2πji ln 2 , for j = ±1, . . . , and at s = −3, −4, . . . . The corresponding graph with the poles of B * (s) and the area where the function is well defined is depicted in Figure 3.
We use again the method of closing the box, as was done for the moment generating function, to argue that the inverse Mellin transform of B * (s) is given by the sum of the residues of poles lying to the right of the vertical line ℜs = − 5 2 and a correction term of the order O(z −d ). We have the following residues: Remark. The series in the functions η 1 and η 2 are absolutely convergent, in view of the fast asymptotic decay of the gamma function Γ(x + iy), for fixed x and increasing y-it is well known that Γ(x+iy) is O(y x−1/2 e −πy/2 ). For instance, for some positive constant K, we have Hence, for any arbitrary d > 0, The two functions η 1 and η 2 are oscillating functions of a truly ignorable magnitude. For all z, the magnitude of η 1 is bounded by 0.1426024772× 10 −4 and the magnitude of η 2 by 0.1573158429 × 10 −5 . The oscillations occur in the lower-order terms, anyway, and do not make B(z) behave in any unstable way. This means that, as a function of z, the oscillations are just "waves" of a very small amplitude, fluctuating around a "steady" component.
n! z n . So, The right-hand side in the latter relation is O(z 2+ε ), for any ε > 0, and as in the case of the moment generating function, one can check that the conditions of the depoissonization lemma [7] hold. So, in depoissonized form, the result is E n 2 ∆ n = n 2 lg n − n 2 η 2 (lg n) − n 2 ln 2 − 2γ 2 ln 2 for arbitrary ε > 0. As d > 0 is also arbitrary in the error term, we can take the error to be O(n 3/2+ε ). When we divide by n 2 , we get O(n −1/2+ε ) error term. For ease of exposition, we take ε = 0.0001 and present the error in the order O(n −0.4999 ).
Proposition 1. In a trie of n random keys following the unbiased Bernoulli model, the distance ∆ n between two randomly selected keys has the mean value where η(·) = −2η 2 (·), with η 2 (·) being the small oscillating function given in (6).
3.4. The variance. One can continue pumping moments by taking derivatives of P * (t, s). The derivation of higher moments follows the same general principles that were used for the mean: fixed-population recurrence, poissonization, asymptotic solution by the Mellin transform and its inverse, then depoissonization. However, the task becomes too daunting, even for the second moment. This combinatorial explosion phenomenon is common folklore in random graphs. Let Hence, The inverse Mellin transform is which again we handle by shifting the line of integration to the right and account for the shift by the residue of the poles introduced. The transform L * (s) has a triple pole at s = −2, which provides the asymptotically dominant term, double poles at s = −2 + 2πji ln 2 , for j = ±1, . . . , and simple poles at s = −1 + 2πki ln 2 , for k = 0, ±1, . . . and at s = −3, −4, . . . . We have the following residue contributions: where ξ 1 (·) an ξ 2 (·) are oscillating function given by and ψ(·) is the digamma function.
Hence, for any arbitrary θ > 0, Recall that L(z) is a shifted poissonized version of the problem, with a number of keys N (z) that follows a Poisson distribution with parameter z. Therefore, The depoissonization of (7) by the depoissonization lemma [7] finally gives us the second moment for the fixed population in the same form with n replacing z; the depoissonization introduces a small error of the order O(n −0.4999 ); the genesis of this particular representation of error is discussed in the paragraphs preceding Proposition 1. The entire validity of depoissonization bears on arguments similar to those discussed in some more detail prior to Proposition 1. The variance follows by subtracting the square of the mean (cf. Proposition 1). Interestingly, the lg 2 n and lg n terms both disappear, leaving behind only a O(1) function, consisting of a steady component and negligible oscillations. Theorem 1. In a trie of n random keys following the unbiased Bernoulli model, the distance ∆ n between two randomly selected keys has the variance where ξ(·) is an oscillating function given by ξ(u) = 16 ln 2 + 8γ ln 2 with η 2 (·) given in (6) and ξ 3 (·) given by The function ξ 3 in Theorem 1 is absolutely convergent, by arguments that are essentially the same as those given for the function η 1 and η 2 that appear in the mean; see the remark following (6). In fact, ξ offers only negligible oscillations; its magnitude is bounded by 0.5654042648 × 10 −4 . The arguments in [16] may suggest a way to simplify ξ. In view of the sharp O(1) variance concentration of ∆ n , a concentration law is an immediate corollary (by Chebyshev's inequality).
3.5. The oscillatory distribution. The presence of the oscillating function κ(t, lg n) in the moment generating function of ∆ n indicates that a limit distribution does not exist. In this section we make this argument more explicit. We have determined in Section 3.3 that the mean has 2 lg n leading asymptotic term. We have also seen in Section 3.4 that the variance is O(1). One then looks into the behavior of the integer random variable of ∆ * n = ∆ n − ⌊2 lg n⌋, if there is a chance for convergence. The main result of this paper answers this question in the negative.
Theorem 2. Let ∆ n be the distance between two randomly selected keys in a trie of n random keys following the unbiased Bernoulli model. Then ∆ n − ⌊2 lg n⌋ has an oscillating moment generating function, and, consequently, does not converge in distribution to any random variable.
Proof. One finds from (5) that ∆ * n has the moment generating function where Let {x} denote the fractional part of x, that is, Using this notation in (8), we find for the range |t| < 1 2 ln 2. For the rest of the proof, we restrict t to the interval [−0.1, 0.1]. For any fixed t from this range, the function H n (t) provides small ignorable oscillations around G(t), and, of course, the O(n −1/2 lg ne {2 lg n}t ) term can be made arbitrarily small. It is well known that the function {2 lg n} is dense in the interval [0, 1); see, for example, [10]. The term {2 lg n} is genuinely oscillating. Also, for t > 0, Then, for large n, the moment generating function E[e ∆ * n t ] itself comes infinitely often very close to the two functions G(t) and G(t)e t . These two "envelopes" are distinct for all values of t with the exception of that of t = 0, where both values are equal to G(0) = 1. Namely, and for nonnegative t in the range of interest, we have The latter numerical bound follows from maximizing the part outside the sum by standard calculus arguments, and working out a numerical value for the sum as was done for the mean [see the remarks following (6)]. Similarly, for negative t in the range of interest, The numerical bound is found in a manner similar to that in the case of t ≥ 0.  In principle, one can invert a moment generating function. For integer r, we have The integrals may not be easy to work through. For example, for r = 0, we have The functions G(·) and H n (·) are complicated, but it is clear that Pr(∆ * n = 0) is oscillating.
4. Discussion. Tries offer many applications in different areas, such as computer science, telecommunications and computational biology. Applications include a variety of pattern matching algorithms on words, as well as a model for analyzing the periodicities and autocorrelation between the substrings of a string. This is an area of interest to the study of DNA sequences (digital data on an alphabet of four letters) in computational biology, when the sequences are almost random.
By purely analytic methods, we investigated distances between pairs of keys in a random trie on n keys. The average value is 2 lg n (modulated by some small oscillations), the variance is O(1), and the centered distance does not have a limit distribution, but rather oscillates between two extremal values. The nonexistence of limits in the context of digital trees has been noted before in [3], who studied the height of random incomplete tries by a mix of probabilistic and analytic methods. The probabilistic behavior of other related parameters can be obtained from our results. For example, it is a corollary to our results that the Wiener index the sum of all pairs of distances (D ij is the distance between the ith and jth keys), has an average value equal to E[W n ] = n 2 lg n − ln 2 − 2γ 2 ln 2 + η 2 (lg n) n 2 + O(n 1.5001 ).
To put this result in appropriate perspective, compare with [14]. A trie is said to be complete when it is fully grown at each level (except possibly the last one). All the levels in a complete trie are filled with internal nodes, except the last two (or one) where the keys reside. Thus, in such a complete trie, the keys are at distance ⌊lg n⌋ or 1 + ⌊lg n⌋. This balance is usually a desired feature for the fast retrieval of data on average. In the complete trie, if pairs of leaves are chosen at random, both will always be at depth lg n + O(1). It can be shown by a recursive argument that the distance between a pair of keys has an asymptotic average 2 lg n and variance O(1). Thus, our results confirm that the trie is an excellent choice for random digital data; it tends to naturally balance itself, behaving rather closely as an ideally balanced complete trie.
It appears to us that the results can be extended without introducing essential difficulty to the case of data on alphabets larger than binary, which can be useful for DNA studies. The problem that can possibly be of different structure, giving an interesting offshoot, is that where the Bernoulli model is biased. In the binary case, for example, one would consider an ergodic source emitting bits of 1's with probability p = 1 2 , and 0's with probability q = 1 − p = 1 2 . Several symmetries employed in the balanced Bernoulli case cease to exist. Under a biased Bernoulli model, the functional equations obtained, both under a fixed-population model and a poissonized data model, will be markedly different. We leave this as a topic for future research.

APPENDIX A
A Mellin viewpoint of the random depth. There are several known results for the random depth derived by probabilistic methods [see [1] for exact analysis]. See also the related studies of asymptotics in [6,8,17]; these results are surveyed in [11]. However, we need the Mellin transform viewpoint of these results to plug in the functional equations arising for ∆ n .
We start from δ n |L n =      δ Ln + 1, with probability L n n , δ Rn + 1, with probability R n n .