arXiv:1605.01814v1 [math.PR] 6 May 2016

Proceedings of the 27th International Conference on Probabilistic, Combinatorial
and Asymptotic Methods for the Analysis of Algorithms
Kraków, Poland, 4-8 July 2016

Asymmetric Rényi Problem and PATRICIA
Tries
Michael Drmota1†, Abram Magner2 , Wojciech Szpankowski3‡§
1

Institute for Discrete Mathematics and Geometry, TU Wien, A-1040 Wien, Austria (email: michael.drmota@tuwien.ac.at).
Coordinated Science Lab, UIUC, Champaign, IL, USA (email: anmagner@illinois.edu)
3
Department of Computer Science, Purdue University, IN 47907, USA (email: spa@cs.purdue.edu)
2

Abstract: In 1960 Rényi asked for the number of random queries necessary to recover a hidden bijective labeling of
n distinct objects. In each query one selects a random subset of labels and asks, what is the set of objects that have
these labels? We consider here an asymmetric version of the problem in which in every query an object is chosen with
probability p > 1/2 and we ignore “inconclusive” queries. We study the number of queries needed to recover the
labeling in its entirety (the height), to recover at least one single element (the fillup level), and to recover a randomly
chosen element (the typical depth). This problem exhibits several remarkable behaviors: the depth Dn converges
in probability but not almost surely and while it satisfies the central limit theorem its local limit theorem doesn’t
hold; the height Hn and the fillup level Fn exhibit phase transitions with respect to p in the second term. To obtain
these results, we take a unified approach via the analysis of the external profile defined at level k as the number of
elements recovered by the kth query. We first establish new precise asymptotic results for the average and variance,
and a central limit law, for the external profile in the regime where it grows polynomially with n. We then extend the
external profile results to the boundaries of the central region, leading to the solution of our problem for the height
and fillup level. As a bonus, our analysis implies novel results for random PATRICIA tries, as it turns out that the
problem is probabilistically equivalent to the analysis of the height, fillup level, typical depth, and external profile of
a PATRICIA trie built from n independent binary sequences generated by a biased(p) memoryless source.
Keywords: Rényi problem, PATRICIA trie, profile, height, fillup level, analytic combinatorics, Mellin transform,
depoissonization

1 Introduction
In his lectures in the summer of 1960 at Michigan State University, Alfred Rényi discussed several problems related to random sets [21]. Among them there was a problem regarding recovering a labeling of
† M.

Drmota was supported by the Austrian Science Foundation FWF Grant No. S9604.
Magner and W. Szpankowski were supported by NSF Center for Science of Information (CSoI) Grant CCF-0939370, and in
addition by NSF Grants CCF-1524312, NIH Grant 1U01CA198941-01, and the NCN grant, grant UMO-2013/09/B/ST6/02258.
§ W. Szpankowski is also with the Faculty of Electronics, Telecommunications, and Informatics, Gdańsk University of Technology, Poland.
‡ A.

2

M. Drmota, A. Magner, and W. Szpankowski

a set X of n distinct objects by asking random subset questions of the form “which objects correspond
to the labels in the (random) set B?” For a given method of randomly selecting queries, Rényi’s original
problem asks for the typical behavior of the number of queries necessary to recover the hidden labeling.
Formally, the unknown labeling of the set X is a bijection φ from X to a set A of labels (necessarily
with equal cardinality n), and a query takes the form of a subset B ⊆ A. The response to a query B is
φ−1 (B) ⊆ X.
Our contribution in this paper is a precise analysis of several parameters of Rényi’s problem for a
particular natural probabilistic model on the query sequence. In order to formulate this model precisely,
it is convenient to first state a view of the process that elucidates its tree-like structure. In particular, a
sequence of queries corresponds to a refinement of partitions of the set of objects, where two objects are in
different partition elements if they have been distinguished by some sequence of queries. More precisely,
the refinement works as follows: before any questions are asked, we have a trivial partition P0 = X
consisting of a single class (all objects). Inductively, if Pj−1 corresponds to the partition induced by the
first j − 1 queries, then Pj is constructed from Pj−1 by splitting each element of Pj−1 into at most two
disjoint subsets: those objects that are contained in the preimage of the jth query set Bj and those that
are not. The hidden labeling is recovered precisely when the partition of X consists only of singleton
elements. An instance of this process may be viewed as a rooted binary tree (which we call the partition
refinement tree) in which the jth level, for j ≥ 0, corresponds to the partition resulting from j queries;
a node in a level corresponds to an element of that partition. A right child corresponds to a subset of a
parent partition element that is included in the subsequent query, and a left child corresponds to a subset
that is not included. See Example 1 for an illustration.
Example 1 (Demonstration of partition refinement). Consider an instance of the problem where X =
[5] = {1, ..., 5}, with labels (d, e, a, c, b) respectively (so A = {a, b, c, d, e}). Consider the following
sequence of queries:
{1, 2, 3, 4, 5}
1. B1 = {b, d} 7→ {1, 5}

{1,5}

{2,3,4}

2. B2 = {a, b, d} 7→ {1, 3, 5},

{2,4}

3. B3 = {a, c, d} 7→ {1, 3, 4},
2

{1, 5}

3
4

5

1

Each level j ≥ 0 of the tree depicts the partition Pj , where a right child node corresponds to the subset
of objects in the parent set which are contained in the response to the jth query. Singletons are only
explicitly depicted in the first level in which they appear.
In this work we consider a version of the problem in which, in every query, each label is included
independently with probability p > 1/2 (the asymmetric case) and we ignore inconclusive queries. In
particular, if a candidate query fails to nontrivially split some element of the previous partition, we modify
the query by deciding again independently whether or not to include each label of that partition element
with probability p. We perform this modification until the resulting query splits every element of the
previous partition nontrivially. See Example 2.

Asymmetric Rényi Problem

3

Example 2 (Ignoring inconclusive queries). Continuing Example 1, the query B2 fails to split the partition element {1, 5}, so it is an example of an inconclusive query and would be modified in our model
to, say, B2′ = φ({1, 3}). The resulting refinement of partitions is depicted as a tree here. Note that
the tree now does not contain non-branching paths and that B2 is ignored in the final query sequence.
{1, 2, 3, 4, 5}
1. B1 = {b, d} 7→ {1, 5}

{1,5}

{2,3,4}

2. B2′ = {a, d} 7→ {1, 3}

{2,4}

3. B3 = {a, c, d} 7→ {1, 3, 4}.
2

3

5

1

4

We study three parameters of this random process: Hn , the number of such queries needed to recover
the entire labeling; Fn , the number needed before at least one element is recovered; and Dn , the number
needed to recover an element selected uniformly at random. Our objective is to present precise probabilistic estimates of these parameters and to study the distributional behavior of Dn .
The symmetric version (i.e., p = 1/2) of the problem (with a variation) was discussed by Pittel and
Rubin in [19], where they analyzed the typical value of Hn . In their model, a query is constructed by
deciding whether or not to include each label from A independently with probability p = 1/2. To make
the problem interesting, they added a constraint similar to ours: namely, a query is, as in our model,
admissible if and only if it splits every nontrivial element of the current partition. In contrast with our
model, however, Pittel and Rubin completely discard inconclusive queries (rather than modifying their
inconclusive subsets as we do). Despite this difference, the model considered in [19] is probabilistically
equivalent to ours for the symmetric case. Our primary contribution is the analysis of the problem in the
asymmetric case (p > 1/2), but our methods of proof allow us to recover the results of Pittel and Rubin.
The question asked by Rényi brings some surprises. For the symmetric model (p = 1/2) Pittel and
Rubin [19] were able to prove that the number of necessary queries is with high probability (whp) (see
Theorem 1)
p
p
Hn = log2 n + 2 log2 n + o( log n).
(1)
In this paper, we re-establish this result using a different approach and prove that for p > 1/2 the number
of queries grows whp as
Hn = log1/p n +

1
logp/q log n + o(log log n),
2

(2)

where q := 1 − p. Note a phase transition in the second term. We show that a similar phase transition
occurs in the asymptotics for Fn (see Theorem 1):
(
log1/q n − log1/q log log n + o(log log log n) p > q
Fn =
(3)
log2 n − log2 log n + o(log log n)
p = q = 1/2.

4

M. Drmota, A. Magner, and W. Szpankowski

We then prove in Theorem 2 some interesting probabilistic behaviors of Dn . We have Dn / log n →
1/h(p) (in probability) where h(p) := −p log p − q log q, but we do not have almost sure convergence.
Moreover, Dn appropriately normalized satisfies a central limit result, but not a local limit theorem due
to some oscillations discussed below.
We establish these results in a novel way by considering first the external profile Bn,k , whose analysis
was, until recently, an open problem of its own (the second and third authors gave a precise analysis of the
external profile in an important range of parameters in [13, 15], but the present paper requires nontrivial
extensions). The external profile at level k is the number of bijection elements revealed by the kth query
(one may also define the internal profile at level k as the number of non-singleton elements of the partition
immediately after the kth query). Its study is motivated by the fact that many other parameters, including
all of those that we mention here, can be written in terms of it. Indeed, Pr[Dn = k] = E[Bn,k ]/n,
Hn = max{k : Bn,k > 0}, and Fn = min{k : Bn,k > 0} − 1.
We now discuss our new results concerning the probabilistic behavior of the external profile. We
establish in [15, 13] precise asymptotic expressions for the expected value and variance of Bn,k in the
central range, that is, with k ∼ α log n, where, for any fixed ǫ > 0, α ∈ (1/ log(1/q)+ǫ, 1/ log(1/p)−ǫ)
(the left and right endpoints of this interval are associated with Fn and Hn , respectively). Specifically,
we show that both the mean and the variance are of the same (explicit) polynomial order of growth (with
respect to n) (see Theorem 3). More precisely, we show that both expected value and variance grow for
k ∼ α log n as
nβ(α)
H(ρ(α), logp/q (pk n)) √
C log n
where β(α) ≤ 1 and ρ(α) are complicated functions of α, C is an explicit constant, and H(ρ, x) is
a function that is periodic in x. The oscillations come from infinitely many regularly spaced saddle
points that we observe when inverting the Mellin transform of the Poissonpgenerating function of E[Bn,k ].
Finally, we prove a central limit theorem; that is, (Bn,k − E[Bn,k ])/ Var[Bn,k ] → N (0, 1) where
N (0, 1) represents the standard normal distribution.
In the present paper, we exploit the expected value analysis of Bn,k in the central range to give precise
distributional information about Dn via the identity Pr[Dn = k] = E[Bn,k ]/n. Note that the oscillations
in E[Bn,k ] are the source of the peculiar behavior of Dn .
In order to establish the most interesting results claimed in the present paper for Hn and Fn , the analysis
sketched above does not suffice: we need to estimate the mean and the variance of the external profile
beyond the range α ∈ (1/ log(1/q)+ ǫ, 1/ log(1/p)− ǫ); in particular, for Fn and Hn we need expansions
at the left and right side, respectively, of this range. This, it turns out, requires a novel approach and
analysis, as discussed in detail in our forthcoming journal paper [5], leading to the announced results on
the Rényi problem in (2) and (3).
Having described most of our main results, we mention an important equivalence pointed out by Pittel
and Rubin [19]. They observed that their version of the Rényi process resembles the construction of a
digital tree known as a PATRICIA trie1 [12, 23]. In fact, the authors of [19] show that Hn is probabilistically equivalent to the height (longest path) of a PATRICIA trie built from n binary sequences generated
independently by a memoryless source with bias p = 1/2 (that is, with a “1” generated with probability p;
this is often called the Bernoulli model with bias p); the equivalence is true more generally, for p ≥ 1/2.
It is easy to see that Fn is equivalent to the fillup level (depth of the deepest full level), Dn to the typical
1

We recall that a PATRICIA trie is a trie in which non-branching paths are compressed; that is, there are no unary paths.

Asymmetric Rényi Problem

5

depth (depth of a randomly chosen leaf), and Bn,k to the external profile of the tree (the number of leaves
at level k; the internal profile at level k is similarly defined as the number of non-leaf nodes at that level).
We spell out this equivalence in the following simple claim.
Lemma 1 (Equivalence of parameters of the Rényi problem with those of PATRICIA tries). Any parameter (in particular, Hn , Fn , Dn , and Bn,k ) of the Rényi process with bias p that is a function of the partition
refinement tree is equal in distribution to the same function of a random PATRICIA trie generated by n
independent infinite binary strings from a memoryless source with bias p ≥ 1/2.
Proof. In a nutshell, we couple a random PATRICIA trie and the sequence of queries from the Rényi
process by constructing both from the same sequence of binary strings from a memoryless source. We do
this in such a way that the resulting PATRICIA trie and the partition refinement tree are isomorphic with
probability 1, so that parameters defined in terms of either tree structure are equal in distribution.
More precisely, we start with n independent infinite binary strings S1 , ..., Sn generated according to a
memoryless source with bias p, where each string corresponds to a unique element of the set of labels (for
simplicity, we assume that A = [n], and Sj corresponds to j, for j ∈ [n]). These induce a PATRICIA
trie T , and our goal is to show that we can simulate a Rényi process using these strings, such that the
corresponding tree TR is isomorphic to T as a rooted plane– oriented tree (see Example 2). The basic idea
is as follows: we maintain for each string Sj an index kj , initially set to 1. Whenever the Rényi process
demands that we make a decision about whether or not to include label j in a query, we include it if and
only if Sj,kj = 1, and then increment kj by 1.
Clearly, this scheme induces the correct distribution on queries. Furthermore, the resulting partition
refinement tree (ignoring inconclusive queries) is easily seen to be isomorphic to T . Since the trees are
isomorphic, the parameters of interest are equal in each case.
Thus, our results on these parameters for the Rényi problem directly lead to novel results on PATRICIA
tries, and vice versa. In addition to their use as data structures, PATRICIA tries also arise as combinatorial
structures which capture the behavior of various processes of interest in computer science and information
theory (e.g., in leader election processes without trivial splits [9] and in the solution to Rényi’s problem
which we study here [19, 2]).
Similarly, the version of the Rényi problem that allows inconclusive queries corresponds to results on
tries built on n binary strings from a memoryless source. We thus discuss them in the literature survey
below.
Now we briefly review known facts about PATRICIA tries and other digital trees when built over n
independent strings generated by a memoryless source. Profiles of tries in both the asymmetric and
symmetric cases were studied extensively in [16]. The expected profiles of digital search trees in both
cases were analyzed in [6], and the variance for the asymmetric case was treated in [10]. Some aspects
of trie and PATRICIA trie profiles (in particular, the concentration of their distributions) were studied
using probabilistic methods in [4, 3]. The depth in PATRICIA for the symmetric model was analyzed
in [2, 12] while for the asymmetric model in [22]. The leading asymptotics for the PATRICIA height
for the symmetric Bernoulli model was first analyzed by Pittel [17] (see also [23] for suffix trees). The
two-term expression for the height of PATRICIA for the symmetric model was first presented in [19] as
discussed above (see also [2]). Finally, in [13, 15], the second two authors of the present paper presented
a precise analysis of the external profile (including its mean, variance, and limiting distribution) in the
asymmetric case, for the range in which the profile grows polynomially. The present work relies on this

6

M. Drmota, A. Magner, and W. Szpankowski

previous analysis, but the analyses for Hn and Fn involve a significant extension, since they rely on
precise asymptotics for the external profile outside this central range.
Regarding methodology, the basic framework (which we use here) for analysis of digital tree recurrences by applying the Poisson transform to derive a functional equation, converting this to an algebraic
equation using the Mellin transform, and then inverting using the saddle point method/singularity analysis followed by depoissonization, was worked out in [6] and followed in [16]. While this basic chain is
common, the challenges of applying it vary dramatically between the different digital trees, and this is
the case here. As we discuss later (see (7) and the surrounding text), this variation starts with the quite
different forms of the Poisson functional equations, which lead to unique analytic challenges.
The plan for the paper is as follows. In the next section we formulate more precisely our problem and
present our main results regarding the external profile, height, fillup level, and depth. Sketches of proofs
are provided in the last section (the full proofs are provided in the journal version of this paper).

2 Main Results
In this section, we formulate precisely Rényi’s problem and present our main results. Our goal is to
provide precise asymptotics for three natural parameters of the Rényi problem on n objects with each
label in a given query being included with probability p ≥ 1/2: the number Fn of queries needed to
identify at least one single element of the bijection, the number Hn needed to recover the bijection in its
entirety, and the number Dn needed to recover an element of the bijection chosen uniformly at random
from the n objects. If one wishes to determine the label for a particular object, these quantities correspond
to the best, worst, and average case performance, respectively, of the random subset strategy proposed by
Rényi. We call these parameters, the fillup level Fn , the height Hn , and the depth Dn , respectively (these
names come from the corresponding quantities in random digital trees). One more parameter is relevant:
we can present a unified analysis of our main three parameters Fn , Hn , and Dn via the external profile
Bn,k , which is the number of elements of the bijection on n items identified by the kth query.
Our analysis reveals several remarkable behaviors: the depth Dn converges in probability but not almost
surely and while it satisfies the central limit theorem its local limit theorem doesn’t hold. Perhaps most
interestingly, the height Hn and the fillup level Fn exhibit phase transitions with respect to p in the second
term.
To begin, we recall the relations of Fn , Hn , and Dn to Bn,k :
Fn = min{k : Bn,k > 0} − 1

Hn = max{k : Bn,k > 0}

Pr[Dn = k] = E[Bn,k ]/n.

Using the first and second moment methods, we can then obtain upper and lower bounds on Hn and Fn
in terms of the moments of Bn,k :
Pr[Hn > k] ≤

X

E[Bn,j ],

j>k

Pr[Hn < k] ≤

Var[Bn,k ]
,
E[Bn,k ]2

and
Pr[Fn > k] ≤

Var[Bn,k ]
,
E[Bn,k ]2

Pr[Fn < k] ≤ E[Bn,k ].

The analysis of the distribution of Dn reduces simply to that of E[Bn,k ].

Asymmetric Rényi Problem

7

In the next section, we show that the fillup level Fn and the height Hn have the following precise
asymptotic expansions. Both exhibit a phase transition with respect to p in the second term. A complete
proof can be found in our journal version of this paper [5].
Theorem 1 (Asymptotics for Fn and Hn ). With high probability,
(
log1/p n + 12 logp/q log n + o(log log n)
p
Hn =
√
log2 n + 2 log2 n + o( log n)

p>q
p=q

(4)

and

Fn =

(

log1/q n − log1/q log log n + o(log log log n) p > q
log2 n − log2 log n + o(log log n)
p=q

(5)

for large n.
While the behavior of the fillup level Fn could be anticipated [18] (by comparing it to the corresponding
result in the version of Rényi’s problem allowing inconclusive queries), the behavior of the height Hn is
rather more unusual. It is difficult to compare the height result to the analogous quantity for tries or
digital search trees, because only the first term is given for p > 1/2 in the literature: for tries, it is
2
log(1/(p2 +q2 )) log n, while for digital search trees it is log1/p n, as in PATRICIA tries.
Focusing on the second term of each expression given in the theorem, this result says that the deviation
of the typical height from log1/p n is asymptotically larger when p = 1/2 than when p > 1/2. That is,
the height of the tallest fringe subtree (i.e., a subtree rooted near log1/p n) is asymptotically larger in the
symmetric case. A complete explanation of this phenomenon would likely require consideration of the
number of such subtrees (i.e., the internal profile at level log1/p n) and the number of strings participating
in each of them. In the language of the Rényi problem, this latter parameter is the number of objects that
remain unidentified after approximately log1/p n queries.
Moving to the number of questions Dn needed to identify a random element of the bijection, we have
the following theorem (note that due to the evolution process of the random PATRICIA trie, all random
variables can be defined on the same probability space).
Theorem 2 (Asymptotics and distributional behavior of Dn ). For p > 1/2, the normalized depth Dn / log n
converges in probability to 1/h(p), where h(p) := −p log p − q log q is the Bernoulli entropy function,
but not almost surely. In fact,
lim inf Dn / log n = 1/ log(1/q)
n→∞

(a.s)

lim sup Dn / log n = 1/ log(1/p).
n→∞

p
Furthermore, Dn satisfies a central limit theorem; that is, (Dn − E[Dn ])/ Var[Dn ] → N (0, 1), where
1
log n and Var[Dn ] ∼ c log n where c is an explicit constant. A local limit theorem does
E[Dn ] ∼ h(p)
p
not hold: for x = O(1) and k = h1 (log n + x κ∗ (−1) log n/h), where κ∗ (−1) is some explicit constant
and h = h(p), we obtain

 e−x2 /2
k
Pr [Dn = k] ∼ H −1; logp/q p n √
2πC log n

for an oscillating function H(−1; logp/q pk n) (see Figure 1) defined in Theorem 3 below and an explicitly
known constant C.

8

M. Drmota, A. Magner, and W. Szpankowski

Fig. 1: Plots of H(ρ, x) for ρ = −0.5, 0, 0.5.
Again, the depth exhibits a phase transition: for p = 1/2 we have Dn / log n → 1/ log 2 almost surely,
which doesn’t hold for p > 1/2. We note that some of the results on the depth (namely, the convergence
in probability and the central limit theorem) are already known (see [20]), but our contribution is a novel
derivation of these facts via the profile analysis. Qualitatively, the oscillatory behavior of the external
profile that is responsible for the lack of local limit theorem for the depth occurs also in both tries and
digital search trees.
We now explain our approach to the analysis of the moments of Bn,k in appropriate ranges (we follow
[13, 15]). For this, we take an analytic approach [8, 23]. We first explain it for the analysis relevant to
Dn , and then show how to extend it for Hn and Fn . More details can be found in the next section.
We start by deriving a recurrence for the average profile, which we denote by µn,k := E[Bn,k ]. It
satisfies
µn,k = (pn + q n )µn,k +

n−1
X
j=1


n j n−j
p q
(µj,k−1 + µn−j,k−1 )
j

(6)

for n ≥ 2 and k ≥ 1, with some initial/boundary conditions; most importantly, µn,k = 0 for k ≥ n
and any n. Moreover, µn,k ≤ n for all n and k owing to the elimination of inconclusive queries. This
recurrence arises from conditioning on the number j of objects that are included in the first query. If
1 ≤ j ≤ n − 1 objects are included, then the conditional expectation is a sum of contributions from
those objects that are included and those that aren’t. If, on the other hand, all objects are included or all
are excluded from the first potential query (which happens with probability pn + q n ), then the partition
element splitting constraint on the queries applies, the potential query is ignored as inconclusive, and the
contribution is µn,k .
The tools that we use to solve this recurrence (for details see [13, 15]) are similar to those of the analyses
for digital trees [23] such as tries and digital search trees (though the analytical
significantly).
Pdetails differ
z m −z
of µn,k ,
We first derive a functional equation for the Poisson transform G̃k (z) =
m≥0 µm,k m! e
which gives
G̃k (z) = G̃k−1 (pz) + G̃k−1 (qz) + e−pz (G̃k − G̃k−1 )(qz) + e−qz (G̃k − G̃k−1 )(pz).

Asymmetric Rényi Problem

9

This we write as
G̃k (z) = G̃k−1 (pz) + G̃k−1 (qz) + W̃k,G (z),

(7)

We contrast this functional equation with those for tries [16] and for digital search trees [6]: in tries, the
expression W̃k,G (z) does not appear, which significantly simplifies the analysis in that case. In digital
search trees, the functional equation is a differential equation, and the analysis is consequently quite
different.
At this point the goal is to determine asymptotics for G̃k (z) as z → ∞ in a cone around the positive real
axis. When solving (7), W̃k,G (z) complicates the analysis because it has no closed-form Mellin transform
(see below); we handle it via its Taylor series. Finally, depoissonization [23] will allow us to transfer the
asymptotic expansion for G̃k (z) back to one for µn,k :
n ′′
G̃ (n) + O(nǫ−1 ).
2 k

µn,k = G̃k (n) −

To convert (7) to an algebraic equation, we use the Mellin transform [7], which, for a function f : R →
R is given by
Z
∞

f ∗ (s) =

z s−1 f (z) dz.

0

Using the Mellin transform identities and defining T (s) = p−s + q −s , we end up with an expression for
the Mellin transform G∗k (s) of G̃k (z) of the form
G∗k (s) = Γ(s + 1)Ak (s)(p−s + q −s )k = Γ(s + 1)Ak (s)T (s)k ,
where Ak (s) (see (14) below) is an infinite series arising from the contributions coming from the function
W̃k,G (z):
Ak (s) =

k
X

T (s)−j

j=0

∞
X

m=j

T (−m)(µm,j − µm,j−1 )

Γ(m + s)
,
Γ(m + 1)Γ(s + 1)

(8)

where we define µm,−1 = 0 for all m. Note that it involves µm,j − µm,j−1 for various m and j (see
[13, 14]). Locating and characterizing the singularities of G∗k (s) then becomes important. We find that, for
any k, Ak (s) is entire, with zeros at s ∈ Z∩[−k, −1], so that G∗k (s) is meromorphic, with possible simple
poles at the negative integers less than −k. The fundamental strip of G̃k (z) then contains (−k − 1, ∞). It
turns out that the main asymptotic contribution comes from an infinite number of saddle points (see (10)
below) defined by the kernel T (s) = p−s + q −s .
We then must asymptotically invert the Mellin transform to recover G̃k (z). The Mellin inversion formula for G∗k (s) is given by
G̃k (z) =

1
2πi

Z

ρ+i∞

ρ−i∞

z −s G∗k (s) ds =

1
2πi

Z

ρ+i∞

z −s Γ(s + 1)Ak (s)T (s)k ds,

(9)

ρ−i∞

where ρ is any real number inside the fundamental strip associated with G̃k (z). For k in the range in
which the profile grows polynomially (that coincides with the range of interest in our analysis of Dn ), we

10

M. Drmota, A. Magner, and W. Szpankowski

evaluate this integral via the saddle point method [8]. Examining z −s T (s)k and solving the associated
saddle point equation
d
[k log T (s) − s log z] = 0,
ds
we find an explicit formula (12) below for ρ(α), the real-valued saddle point of our integrand. The
multivaluedness of the complex logarithm then implies that there are infinitely many regularly spaced
saddle points sj , j ∈ Z, on this vertical line:
sj = ρ(α) + i

2πj
.
log(p/q)

(10)

These lead directly to oscillations in the Θ(1) factor in the final asymptotics for µn,k ). The main challenge
in completing the saddle point analysis is then to elucidate the behavior of Γ(s + 1)Ak (s) for s → ∞
along vertical lines: it turns out that this function inherits the exponential decay of Γ(s + 1) along vertical
lines, and we prove it by splitting the sum defining Ak (s) into two pieces, which decay exponentially for
different reasons (the first sum decays as a result of the superexponential decay of µm,j for m = Θ(j),
which is outside the main range of interest). We end up with an asymptotic expansion for G̃k (z) as
z → ∞ in terms of Ak (s).
Finally, we must analyze the convergence properties of Ak (s) as k → ∞. We find that it converges
uniformly on compact sets to a function A(s) (see (14)) which is, because of the uniformity, entire. We
then apply Lebesgue’s dominated convergence theorem to conclude that we can replace Ak (s) with A(s)
in the final asymptotic expansion of G̃k (z). All of this yields the following theorem which is proved in
[13, 15].
Theorem 3 (Moments and limitingdistribution for Bn,k fork in the central region). Let ǫ > 0 be
1
1
+ ǫ, log(1/p)
− ǫ . Then for k = kα,n ∼ α log n:
independent of n and k, and fix α ∈ log(1/q)
(i) The expected external profile becomes

where



p
nβ(α)
E[Bn,k ] = H(ρ(α), logp/q (pk n)) · p
1 + O( log n) ,
2πκ∗ (ρ(α))α log n
ρ(α) = −

1
log
log(p/q)



α log(1/q) − 1
1 − α log(1/p)



,

β(α) = α log(T (ρ(α))) − ρ(α),

(11)

(12)

and κ∗ (ρ) is an explicitly known function of ρ. Furthermore, H(ρ, x) (see Figure 1) is a non-zero periodic
function with period 1 in x given by
X
H(ρ, x) =
A(ρ + itj )Γ(ρ + 1 + itj )e−2jπix ,
(13)
j∈Z

where tj = 2πj/ log(p/q), and
A(s) =

∞
X
j=0

T (s)−j

∞
X

n=j

T (−n)(µn,j − µn,j−1 )

φn (s)
,
n!

(14)

Asymmetric Rényi Problem
11
Qn−1
where φn (s) = j=1 (s + j) for n > 1 and φn (s) = 1 for n ≤ 1. We recall that T (s) = p−s + q −s .
Here, A(s) is an entire function which is zero at the negative integers.
(ii) The variance of the profile is Var[Bn,k ] = Θ(E[Bn,k ]).
(iii) The limiting distribution of the normalized profile is Gaussian; that is,
Bn,k − µn,k D
p
−→ N (0, 1)
Var[Bn,k ]

where N (0, 1) is the standard normal distribution.

We should point out that the unusual behavior of Dn in Rényi’s problem is a direct consequence of the
oscillatory behavior of the profile, which disappears for the symmetric case. Furthermore, for the height
and fillup level analyses we need to extend Theorem 3 beyond its original central range for α, as discussed
in the next section.

3 Proof sketches
Now we give sketches of the proofs of Theorems 1 and 2 with more details regarding the proof of Theorem 1 in the forthcoming journal version [5]. In particular, in this conference version, we only sketch
derivations for Hn and for Fn by upper and lower bounding, respectively. As stated earlier, the proof of
Theorem 3 can be found in [13, 15].

3.1 Sketch of the proof of Theorem 1
To prove our results for Hn and Fn , we extend the analysis of Bn,k to the boundaries of the central region
(i.e., k ∼ log1/p n and k ∼ log1/q n).

Derivation of Hn . Fixing any ǫ > 0, we write, for the lower bound on the height,
kL = log1/p n + (1 − ǫ)ψ(n)
and, for the upper bound,
kU = log1/p n + (1 + ǫ)ψ(n),

for a function ψ(n) = o(log n) which we are to determine. In order for the first and second mon→∞
n→∞
ment methods to work, we require µn,kL −−−−→ ∞ and µn,kU −−−−→ 0. (We additionally need that
Var[Bn,kL ] = o(µ2n,kL ), but this is not too hard to show by induction using the recurrence for Ṽk (z),
the Poisson variance of Bn,k .) In order to identify the ψ(n) at which this transition occurs, we define
k = log1/p n + ψ(n), and the plan is to estimate E[Bn,k ] via the integral representation (9) for its Poisson
transform. Specifically, we consider the inverse Mellin integrand for some s = ρ ∈ Z− + 1/2 to be set
later. This is sufficient for the upper bound, since, by the exponential decay of the Γ function, the entire
integral is at most of the same order of growth as the integrand on the real axis. We expand the integrand
in (9), that is,
Jk (n, s) :=

k
X
j=0

n−s T (s)k−j

X

m≥j

T (−m)(µm,j − µm,j−1 )

Γ(m + s)
,
Γ(m + 1)

(15)

and apply a simple extension of Theorem 2.2, part (iii) of [14] to approximate µm,j − µm,j−1 when
j → ∞ and is close enough to m:

12

M. Drmota, A. Magner, and W. Szpankowski

Lemma 2 (Precise asymptotics for µn,k , k → ∞ and n near k). Let p ≥ q. For n → ∞ with 1 ≤ k < n
and log2 (n − k) = o(k),
log q

µn,k ∼ (n − k)3/2+ log p



2
log2 (n − k)
n!
Θ(1).
pk /2+k/2 q k · exp −
(n − k)!
2 log(1/p)

(16)

Moreover, for n → ∞ and k < n, for some constant C > 0,
µn,k ≤ C

2
2
n!
pk /2+k/2+O(log(n−k) ) q k .
(n − k − 1)!

Now, we continue with the evaluation of (15). The jth term of (15) is then of order pνj (n,s) , where we
set
νj (n, s) = (j − ψ(n))2 /2 + (j − ψ(n))(s + log1/p (1 + (p/q)s ) + ψ(n) + 1)
− log1/p n log1/p (1 + (p/q)s ) + ψ(n)2 /2 + o(ψ(n)2 ).

The factor T (s)k−j ensures that the bounded j terms are negligible.
Our next goal is to find the j which gives the dominant contribution to the sum in (15); that is, the
j for which the contributions pνj (n,s) dominate. By elementary calculus, we can find the j term which
minimizes νj (n, s):
j = −(s + log1/p (1 + (p/q)s ) + 1).
Then νj (n, s) for this value of j becomes
νj (n, s) = −

(s + log1/p (1 + (p/q)s ) + ψ(n) + 1)2

2
− log1/p n log1/p (1 + (p/q)s ) + ψ(n)2 /2 + o(ψ(n)2 ).

(17)

We then minimize over all s, which requires us to split into the symmetric and asymmetric cases.
Symmetric case: When p = q = 1/2, we have log1/p (1+(p/q)s ) = log2 (2) = 1, so that the expression
for νj (n, s) simplifies, and we get s = −ψ(n) + O(1). The optimal value for νj (n, s) then becomes
νj (n, s) = − log2 n + ψ(n)2 /2 + o(ψ(n)2 ).

(18)

We have thus succeeded in finding a likely candidate for the range of j terms that contribute maximally,
as well as an upper bound on their contribution. This gives a tight upper bound on Jk (n, s) and, hence,
on G̃k (n), of Θ(2−νj (n,s) ).
Now, to find ψ(n) for which there is a phase transition in this bound from tending to ∞ to tending to 0,
we set the exponent in the above expression equal to zero and solve for ψ(n). This gives
p
− log2 n + ψ(n)2 /2(1 + o(1)) = 0 =⇒ ψ(n) ∼ 2 log2 n,
as expected.

Asymmetric Rényi Problem

13

Asymmetric case: On the other hand, when p > 1/2, the equation that we need to solve to find the
minimizing value of s for (17) is a bit more complicated, owing to the fact that log1/p (1 + (p/q)s ) now
depends on s: taking a derivative with respect to s in (17) and setting this equal to 0, after some algebra,
we must solve
−

(p/q)s log(p/q)
log1/p n − ψ(n)(1 + O((p/q)s )) − s(1 + O((p/q)s )) + O((p/q)s ) = 0
log(1/p)

(19)

for s. Here, we note that we used the approximation
log1/p (1 + (p/q)s ) =

(p/q)s
+ O((p/q)2 ),
log(1/p)

which is valid since we are looking for s → −∞.
To find a solution to (19), we first note that it implies that s < −ψ(n) (since the first term involving
log n is negative), and, if ψ(n) > 0, this implies that
−ψ(n) − s = −O(s).

(20)

The plan, then, is to use this to guess a solution s for (19), which we can then verify. The equality (20)
suggests that we replace −ψ(n) − s + O((p/q)s ) with −C · s in (19), for some constant C > 0. Then the
equation becomes
−Cs −

(p/q)s log(p/q)
log1/p n = 0.
log(1/p)

After some trivial rearrangement and multiplication of both sides by log(p/q), we get
−s log(p/q) · e−s log(p/q) = Θ(log n).
Setting W = −s log(p/q) brings us to an expression of the form that defines the Lambert W function [1]
(i.e., a function W (z) satisfying W (z)eW (z) = z).
Using the asymptotics of the W function for large z [1], we thus find that
s = − logp/q log n + O(log log log n).
Note that s → −∞, as required. This may be plugged into (17) to see that it is indeed a solution to the
equation.
Now, to find the correct choice of ψ(n) for which there is a phase transition, we plug this choice of s
into (17), set it equal to 0, and solve for ψ(n). This gives
ψ(n) = −

1
s
= logp/q log n + O(log log log n),
2
2

(21)

as desired.
Note that replacing ψ(n) in (17) with (1 + ǫ)ψ(n) yields a maximum contribution to the inverse Mellin
integral of
ǫ

JkU (n, s) = O(p 2 (logp/q log n)

2

+o((log log n)2 )

) → 0.

(22)

14

M. Drmota, A. Magner, and W. Szpankowski

When we replace ψ(n) with (1 − ǫ)ψ(n), we get
ǫ

JkL (n, s) = O(p− 2 (logp/q log n)

2

+o((log log n)2 )

),

(23)

so that the upper bound tends to infinity (in [5], we prove a matching lower bound).
The above analysis gives asymptotic estimates for G̃k (n). We then apply analytic depoissonization
[23] to get
µn,k = G̃k (n) −

n ′′
G̃ (n) + O(nǫ−1 ),
2 k

(where the second term can be handled in the same way as the first). This gives the claimed result.
Derivation of Fn . We now set k = log1/q n + ψ(n) and
kU = log1/q n + (1 − ǫ)ψ(n).

kL = log1/q n + (1 + ǫ)ψ(n),

(24)

Here, ψ(n) = o(log n) is to be determined so as to satisfy µn,kL → 0 and µn,kU → ∞. We use a technique similar to that used in the height proof to determine ψ(n), except now the Γ function asymptotics
play a role, since we will choose ρ ∈ R tending to ∞. Our first task is to upper bound (as tightly as
possible), for each j, the magnitude of the jth term of (15). First, we upper bound
T (−m)(µm,j − µm,j−1 ) ≤ 2pm µm,j ≤ 2pm m,
using the boundary conditions on µm,j . Next, we apply Stirling’s formula to get
m+ρ 
−(m+1)

m+1
m+ρ
Γ(m + ρ) p
∼ 1 + ρ/m
Γ(m + 1)
e
e
= e(m+ρ) log(m+ρ)−(m+ρ)+m+1−(m+1) log(m+1)+O(log ρ)
= exp((m + ρ) log(m + ρ) − (m + 1) log(m + 1) + O(ρ))

= exp(m log(m(1 + ρ/m)) + ρ log(ρ(1 + m/ρ)) − m log m − log m + O(ρ))
= exp(m log(1 + ρ/m) + ρ log(ρ) + ρ log(1 + m/ρ) − log m + O(ρ)).

(25)

(26)
(27)
(28)
(29)
(30)

Multiplying (25) and (30), then optimizing over all m ≥ j, we find that the maximum term of the m sum
occurs at m = ρp/q and has a value of
exp(ρ log ρ + O(ρ)).

(31)

Now, observe that when log m ≫ log ρ, the contribution of the mth term is pm+o(m) = e−Θ(m) . Thus,
setting j ′ = ρlog ρ (note that log j ′ = (log ρ)2 ≫ log ρ), we split the m sum into two parts:
′

X

m≥j

j
∞
X
X
Γ(m + ρ)
Γ(m + ρ)
Γ(m + ρ)
2pm m
=
+
2pm m
.
2p m
Γ(m + 1) m=j
Γ(m + 1)
Γ(m + 1)
′
m

m=j +1

The terms of the initial part can be upper bounded by (31), while those of the final part are upper bounded
by e−Θ(m) (so that the final part is the tail of a geometric series). This gives an upper bound of
′

j ′ eρ log ρ+O(ρ) + e−Θ(j ) = e(log ρ)

2

+ρ log ρ+O(ρ)

= eρ log ρ+O(ρ) ,

Asymmetric Rényi Problem

15

which holds for any j.
ρ
Multiplying this by n−ρ T (ρ)k−j = q ρ·(j−ψ(n))+(j−ψ(n)−log1/q n) log1/q (1+(q/p) ) gives
q ρ(j−ψ(n))+(j−ψ(n)−log 1/q n) log1/q (1+(q/p)

ρ

)−ρ log1/q ρ+O(ρ)

.

(32)

Maximizing over the j terms, we find that the largest contribution comes from j = 0. Then, just as in the
height upper bound, the behavior with respect to ρ depends on whether or not p = q, because log1/q (1 +
(q/p)ρ ) = 1 when p = q and is dependent on ρ otherwise. Taking this into account and minimizing over
1
ρ gives that the maximum contribution to the j sum is minimized by setting ρ = 2−ψ(n)− log 2 when p = q
and ρ ∼ logp/q log n otherwise. Plugging these choices for ρ into the exponent of (32), setting it equal to
0, and solving for ψ(n) gives ψ(n) = − log2 log n + O(1) when p = q and ψ(n) ∼ − log1/q log log n
when p > q. The evaluation of the inverse Mellin integral with k = kL as defined in (24) and the
integration contour given by ℜ(s) = ρ proceeds along lines similar to the height proof, and this yields the
desired result.
We remark that the lower bound for Fn may also be derived by relating it to the analogous quantity in
regular tries: by definition of the fillup level, there are no unary paths above the fillup level in a standard
trie. Thus, when converting the corresponding PATRICIA trie, no path compression occurs above this
level, which implies that Fn for PATRICIA is lower bounded by that of tries (and the typical value for
tries is the same as in our theorem for PATRICIA). We include the lower bound for Fn via the bounding
of the inverse Mellin integral because it is similar in flavor to the corresponding proof of the upper bound
(for which no short proof seems to exist).
The upper bound for Fn can similarly be handled by an exact evaluation of the inverse Mellin transform.

3.2 Proof of Theorem 2
Using Theorem 3, we can prove Theorem 2.
Convergence in probability: For the typical value of Dn , we show that
Pr[Dn < (1 − ǫ)

1
n→∞
log n] −−−−→ 0,
h(p)

Pr[Dn > (1 + ǫ)

1
n→∞
log n] −−−−→ 0.
h(p)

(33)

For the lower bound, we have
1
log n] =
Pr[Dn < (1 − ǫ)
h(p)

1
⌊(1−ǫ) h(p)
log n⌋

X

1
⌊(1−ǫ) h(p)
log n⌋

Pr[Dn = k] =

k=0

X

k=0

µn,k
.
n

We know from Theorem 3 and the analysis of Fn that, in the range of this sum, µn,k = O(n1−ǫ ). Plugging
this in, we get
1
Pr[Dn < (1 − ǫ)
log n] =
h(p)

1
⌊(1−ǫ) h(p)
log n⌋

X

O(n−ǫ ) = O(n−ǫ log n) = o(1).

k=0

The proof for the upper bound is very similar, except that we appeal to the analysis of Hn instead of
Fn .

16

M. Drmota, A. Magner, and W. Szpankowski

No almost sure convergence: To show that Dn / log n does not converge almost surely, we show that
lim inf Dn / log n = 1/ log(1/q),

lim sup Dn / log n = 1/ log(1/p).

n→∞

(34)

n→∞

n→∞

n→∞

For this, we first show that, almost surely, Fn / log n −−−−→ 1/ log(1/q) and Hn / log n −−−−→ 1/ log(1/p).
Knowing this, we consider the following sequences of events: An is the event that Dn = Fn + 1,
and A′n is the event that Dn = Hn . WePnote that all elements
P∞ of the sequences are independent, and
∞
Pr[An ], Pr[A′n ] ≥ 1/n. This implies that n=1 Pr[An ] = n=1 Pr[A′n ] = ∞, so that the Borel-Cantelli
lemma tells us that both An and A′n occur infinitely often almost surely (moreover, Fn < Dn ≤ Hn by
definition of the relevant quantities). This proves (34).
To show the claimed almost sure convergence of Fn / log n and Hn / log n, we cannot apply the BorelCantelli lemmas directly, because the relevant sums do not converge. Instead, we apply a trick which was
used in [17]. We observe that both (Fn ) and (Hn ) are non-decreasing sequences. Next, we show that, on
some appropriately chosen subsequence, both of these sequences, when divided by log n, converge almost
surely to their respective limits. Combining this with the observed monotonicity yields the claimed almost
sure convergence, and, hence, the equalities in (34).
We illustrate this idea more precisely for Hn . By our analysis above, we know that
2

Pr[|Hn / log n − 1/ log(1/p)| > ǫ] = O(e−Θ(log log n) ).
2 2r

Then we fix t, and we define nr,t = 2t 2 . On this subsequence, by the probability bound just stated,
r→∞
we can apply the Borel-Cantelli lemma to conclude that Hnr,t / log(nr,t ) −−−→ 1/ log(1/p) · (t + 1)2/t2
almost surely. Moreover, for every n, we can choose r such that nr,t ≤ n ≤ nr,t+1 . Then
Hn / log n ≤ Hnr,t+1 / log nr,t ,
which implies
lim sup
n→∞

Hnr,t+1 log nr,t+1
1
(t + 1)2
Hn
=
≤ lim sup
·
.
log n
log(1/p)
t2
r→∞ log nr,t+1 log nr,t

Taking t → ∞, this becomes 1/ log(1/p), as desired. The argument for the lim inf is similar, and this
establishes the almost sure convergence of Hn . The derivation is entirely similar for Fn .
Asymptotics for probability mass function of Dn : The asymptotic formula for Pr[Dn = k] with k as
in the theorem follows directly from the fact that Pr[Dn = k] = E[Bn,k ]/n, plugging in the expression
of Theorem 3 for E[Bn,k ].

References
[1] Milton Abramowitz and Irene A. Stegun. Handbook of Mathematical Functions with Formulas,
Graphs, and Mathematical Tables, volume 55 of National Bureau of Standards Applied Mathematics
Series. For sale by the Superintendent of Documents, U.S. Government Printing Office, Washington,
D.C., 1964.
[2] Luc Devroye. A note on the probabilistic analysis of patricia trees. Random Struct. Algorithms,
3(2):203–214, March 1992.

Asymmetric Rényi Problem

17

[3] Luc Devroye. Laws of large numbers and tail inequalities for random tries and patricia trees. Journal
of Computational and Applied Mathematics, 142:27–37, 2002.
[4] Luc Devroye. Universal asymptotics for random tries and patricia trees. Algorithmica, 42(1):11–29,
2005.
[5] Michael Drmota, Abram Magner, and Wojciech Szpankowski. Asymmetric Rényi problem and
PATRICIA tries. In preparation.
[6] Michael Drmota and Wojciech Szpankowski. The expected profile of digital search trees. J. Comb.
Theory Ser. A, 118(7):1939–1965, October 2011.
[7] Philippe Flajolet, Xavier Gourdon, and Philippe Dumas. Mellin transforms and asymptotics: Harmonic sums. Theoretical Computer Science, 144:3–58, 1995.
[8] Philippe Flajolet and Robert Sedgewick. Analytic Combinatorics. Cambridge University Press,
Cambridge, UK, 2009.
[9] Svante Janson and Wojciech Szpankowski. Analysis of an asymmetric leader election algorithm.
Electronic J. Combin, 4:1–6, 1996.
[10] Ramin Kazemi and Mohammad Vahidi-Asl. The variance of the profile in digital search trees.
Discrete Mathematics and Theoretical Computer Science, 13(3):21–38, 2011.
[11] Philippe Jacquet, Charles Knessl, and Wojciech Szpankowski. A note on a problem posed by D.
E. Knuth on a satisfiability recurrence. Combinatorics, Probability, and Computing, 23, 839-841,
2014.
[12] Donald E. Knuth. The Art of Computer Programming, Volume 3: (2nd ed.) Sorting and Searching.
Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, USA, 1998.
[13] Abram Magner. Profiles of PATRICIA Tries. PhD thesis, Purdue University, December 2015.
[14] Abram Magner, Charles Knessl, and Wojciech Szpankowski. Expected external profile of patricia
tries. Proceedings of the Eleventh Workshop on Analytic Algorithmics and Combinatorics, pages
16–24, 2014.
[15] Abram Magner and Wojciech Szpankowski. Profile of PATRICIA tries. submitted. http://www.
cs.purdue.edu/˜spa/papers/patricia2015.pdf
[16] G. Park, H. Hwang, P. Nicodème, and W. Szpankowski. Profiles of tries. SIAM Journal on Computing, 38(5):1821–1880, 2009.
[17] B. Pittel. Asymptotic growth of a class of random trees. Ann. Probab., 18:414–427, 1985.
[18] B. Pittel, Paths in a random digital tree: limiting distributions, Adv. in Applied Probability, 18, 139–
155, 1986.
[19] Boris Pittel and Herman Rubin. How many random questions are needed to identify n distinct
objects? Journal of Combinatorial Theory, Series A, 55(2):292–312, 1990.

18

M. Drmota, A. Magner, and W. Szpankowski

[20] B. Rais, P. Jacquet, and W. Szpankowski. Limiting distribution for the depth in PATRICIA tries.
SIAM Journal on Discrete Mathematics, 6(2):197–213, 1993.
[21] A. Rényi, On Random Subsets of a Finite Set, Mathematica, 3, 355-362, 1961.
[22] Wojciech Szpankowski. Patricia tries again revisited. J. ACM, 37(4):691–711, October 1990.
[23] Wojciech Szpankowski. Average Case Analysis of Algorithms on Sequences. John Wiley & Sons,
Inc., New York, NY, USA, 2001.

