text:
\section{Introduction}

In his lectures in the summer of 1960 at Michigan State University,
Alfred R\'enyi discussed several problems related to random sets \cite{renyi}.
Among them there was a problem regarding recovering a labeling of 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, R\'enyi'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 $\phi$ from $X$ to a set $A$ of labels
(necessarily with equal cardinality $n$), and a query takes the form of a subset $B \subseteq A$.
The response to a query $B$ is $\phi^{-1}(B) \subseteq X$.

Our contribution in this paper is a precise analysis of several parameters of R\'enyi'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 $ {\frak{P}}_0 = X$ consisting of a single class (all objects).  Inductively,
if $ {\frak{P}}_{j-1}$ corresponds to the partition induced by the first $j-1$ queries, then $ {\frak{P}}_j$ is constructed from $ {\frak{P}}_{j-1}$ by splitting
each element of $ {\frak{P}}_{j-1}$ into at most two disjoint subsets: those objects that are contained in the preimage of the $j$th query set $B_j$ 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
\emph{partition refinement tree}) in which the $j$th level, for $j \geq 0$, corresponds
to the partition resulting from $j$ queries; a node in a given level corresponds to an element of the
partition associated with that level.  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~\ref{QuerySequenceExample} for an illustration.
\begin{example}[Demonstration of partition refinement]
	\label{QuerySequenceExample}
    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:

	    \tikzstyle{level 1}=[level distance=1.0cm, sibling distance=2.5cm]
	    \tikzstyle{level 2}=[level distance=1.0cm, sibling distance=1.5cm]

	    \tikzstyle{bag} = [rectangle, minimum width=3pt,inner sep=0pt]
	    \tikzstyle{end} = [circle, minimum width=3pt,fill, inner sep=0pt]

    \begin{minipage}{0.5\textwidth}
    \begin{enumerate}
    	\item
        	$B_1 = \{b, d\} \mapsto \{1, 5\}$
        \item
        	$B_2 = \{a, b, d\} \mapsto \{1, 3, 5\}$,
        \item
        	$B_3 = \{a, c, d\} \mapsto \{1, 3, 4\}$,

    \end{enumerate}
    \end{minipage}
    \vspace{20pt}
    \begin{minipage}{0.5\textwidth}

	    \begin{tikzpicture}[grow=down]

	    \node[bag]{\{1, 2, 3, 4, 5\}}

	    	child{

	            node[bag]{\{2,3,4\}}
	        	child{
	            	node[bag]{\{2,4\}}
                    child{

                        node[rectangle,draw]{2}
                    }
                    child{

                        node[rectangle,draw]{4}
                    }
	            }

	            child{
	            	node[rectangle,draw]{3}
	            }
	        }

	        child{
	            node[bag]{\{1,5\}}
                child{

	                node[bag,right]{\{1, 5\}}

			        	child{
			            	node[rectangle,draw]{5}
			                edge from parent
			                node[above]{}
			            }

			            child{
			            	node[rectangle,draw]{1}
			                edge from parent
			                node[above]{}
			            }
                }
	        };
	\end{tikzpicture}
	\label{QuerySequenceExampleDiagram}

    \end{minipage}
    Each level $j\geq 0$ of the tree depicts the partition $ {\frak{P}}_j$, where a right child node
    corresponds to the subset of objects in the parent set which are contained in the
    response to the $j$th query.  Singletons are only explicitly depicted in the first
    level in which they appear.  We can determine the labels of all objects using the tree
    and the sequence of queries: for example, to determine the label of the object $3$, we
    traverse the tree until we reach the leaf corresponding to $3$.  This indicates that
    the label corresponding to $3$ is in the singleton set
    \[
        \neg B_1 \cap B_2 = \{a,c,e\} \cap \{a, b, d\} = \{a\}.
    \]
    Note that leaves of the tree always correspond to singleton sets.

\end{example}
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 \emph{asymmetric case}) and we \emph{ignore inconclusive queries}.  In particular, if a candidate query fails to non trivially 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 non trivially.
See Example~\ref{QuerySequenceIgnoreExample}.
\begin{example}[Ignoring inconclusive queries]
	\label{QuerySequenceIgnoreExample}
    Continuing Example~\ref{QuerySequenceExample}, the query $B_2$ 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, $B_2' = \phi(\{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 $B_2$ is ignored in the final query
    sequence.

    \begin{minipage}{0.5\textwidth}
    \begin{enumerate}
    	\item
        	$B_1 = \{b, d\} \mapsto  \{1,5\}$
        \item
        	$B_2' = \{a,d\} \mapsto \{1,3\}$
        \item
        	$B_3 = \{a, c, d\} \mapsto \{1, 3, 4\}$.
    \end{enumerate}
    \end{minipage}
    \begin{minipage}{0.5\textwidth}
    	\vspace{12pt}
 	    \tikzstyle{level 1}=[level distance=1.0cm, sibling distance=2.5cm]
	    \tikzstyle{level 2}=[level distance=1.0cm, sibling distance=1.5cm]

	    \tikzstyle{bag} = [rectangle, minimum width=3pt,inner sep=0pt]
	    \tikzstyle{end} = [circle, minimum width=3pt,fill, inner sep=0pt]
 	    \begin{tikzpicture}[grow=down]

	    \node[bag]{\{1, 2, 3, 4, 5\}}

	    	child{

	            node[bag]{\{2,3,4\}}
	        	child{
	            	node[bag]{\{2,4\}}

                    child{
                    	node[rectangle,draw]{2}
                    }

                    child{
                    	node[rectangle,draw]{4}
                    }
	            }

	            child{
	            	node[rectangle,draw]{3}
	            }
	        }

	        child{
	            node[bag]{\{1,5\}}

	        	child{
	            	node[rectangle,draw]{5}
	                edge from parent
	                node[above]{}
	            }

	            child{
	            	node[rectangle,draw]{1}
	                edge from parent
	                node[above]{}
	            }
	        };
	\end{tikzpicture}
    \end{minipage}

\end{example}
We study three parameters of this random process: $H_n$, the number of such queries
needed to recover the entire labeling; $F_n$, the number needed before at
least one element is recovered;
and $D_n$, the number needed to recover an element selected uniformly
at random.  Our objective is to present precise probabilistic estimates
of these parameters.

The symmetric version (i.e., $p=1/2$) of the problem (with a variation) was discussed by Pittel
and Rubin in \cite{pittelrubin1990}, where they analyzed the typical value of $H_n$.
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 more 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 \cite{pittelrubin1990} 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 R\'enyi brings some surprises.  For the
symmetric model ($p=1/2$) Pittel and Rubin \cite{pittelrubin1990} were
able to prove that the number of necessary queries is with high probability
(whp) (see Theorem~\ref{HeightTheorem})
\begin{eqnarray}
	\label{e1}
	H_n = \log_{2} n +\sqrt{2\log_{2} n} +o(\sqrt{\log n}).
\end{eqnarray}
In this paper, we develop a different method that could be used to re-establish this result
{and} prove that for $p > 1/2$ the number
of queries grows whp as
\begin{eqnarray}
	\label{e2}
    H_n = \log_{1/p} n +\frac{1}{2}\log_{p/q} \log n  +o(\log \log  n),
\end{eqnarray}
where $q:=1-p$.
Note a phase transition in the second term.  Moreover, this result is perhaps interesting in the sense that, for $p > 1/2$, $H_n$ exhibits the second-order
behavior that Pittel and Rubin stated that they fully expected but did not find in the $p=1/2$ case \cite{pittelrubin1990}.
We show that another  phase transition, also in the second term, occurs in the asymptotics for $F_n$
(see Theorem~\ref{FillupTheorem}):
\begin{eqnarray}
\label{e3}
    F_n = \left\{ \begin{array}{ll}
           \log_{1/q} n - \log_{1/q}\log\log n + o(\log\log\log n)     &      p > q \\
        \log_{2} n - \log_2\log n + o(\log\log n)                   &      p = q = 1/2.
    \end{array}   \right.
\end{eqnarray}
We also state in Theorem~\ref{DepthCorollary} some interesting probabilistic behaviors
of $D_n$.
We have $D_n/\log n  \to 1/h(p)$ (in probability)
where $h(p) := -p\log p - q\log q$, but we do not have almost sure
convergence.

We establish these results in a novel way by considering first the \emph{external profile}
$B_{n,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 \cite{magnerPhD2015,magnerspa2015}, but the present paper requires
really nontrivial extensions).
The external profile at level $k$ is
the number of bijection elements revealed by the $k$th query (one may also define the \emph{internal} profile
at level $k$ as the number of non-singleton elements of the partition immediately after the $k$th 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[D_n=k]= {\mathbb{E}}[B_{n,k}]/n$,
$H_n = \max\{k : ~ B_{n,k} > 0\}$, and $F_n = \min\{k : ~ B_{n,k} > 0\} - 1$.

We now discuss our new results concerning the probabilistic
behavior of the external profile.
We establish in \cite{magnerspa2015,magnerPhD2015} precise asymptotic expressions for the
expected value and variance of $B_{n,k}$ in the \emph{central range}, that is,
with $k \sim \alpha\log n$, where, for any fixed $\epsilon > 0$,
$\alpha \in (1/\log(1/q) + \epsilon, 1/\log(1/p) - \epsilon)$
(the left and right endpoints of this interval as $\epsilon \to 0$ are associated
with $F_n$ and $H_n$, respectively).  Specifically,
it was shown that both the mean and the variance
are of the same (explicit) polynomial order of growth
(with respect to $n$).
More precisely, expected value and variance grow
for $k\sim\alpha \log n$ as
$$
H(\rho(\alpha), \log_{p/q}(p^kn)) ~  \frac{n^{\beta(\alpha)}}{\sqrt{C \log n}}
$$
where $\beta(\alpha)\leq 1$ and $\rho(\alpha)$ are
complicated functions of $\alpha$,
$C$ is an explicit constant, and $H(\rho, 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 Poisson generating function of $ {\mathbb{E}}[B_{n,k}]$.
Finally, in \cite{magnerspa2015} we prove a central limit theorem;
that is,
${(B_{n,k} -  {\mathbb{E}}[B_{n,k}])}/{\sqrt{ {\mathrm{Var}}[B_{n,k}]}} \to  {\mathcal{N}}(0,1) $
where $ {\mathcal{N}}(0,1)$ represents the standard normal distribution.

In order to establish the most interesting results claimed in the present paper
for $H_n$ and $F_n$, the analysis sketched above does not suffice: we need to estimate the
mean and the variance of the external profile \emph{beyond} the range
$\alpha \in (1/\log(1/q) + \epsilon, 1/\log(1/p) - \epsilon)$; in particular,
for $F_n$ and $H_n$ we need expansions at the left and right side (as $\epsilon \to 0$), respectively, of this range.

Having described most of our main results, we mention an important equivalence
pointed out by Pittel and Rubin \cite{pittelrubin1990}.
They observed that their version of the R\'enyi process
resembles the construction of a digital tree
known as a PATRICIA trie\footnote{We recall that a trie is a binary digital tree, where
data that are represented by binary strings are stored at leaves of the tree according
to finite prefixes of the corresponding binary strings in a minimal way such that all
appearing prefixes are different. A PATRICIA trie is a trie in
which non-branching paths are \emph{compressed}; that is, there are no unary paths.}
\cite{knuth1998acp,szpa2001Book}. In fact,
the authors of \cite{pittelrubin1990} show that $H_n$ is probabilistically
equivalent to the height (longest path) of a PATRICIA trie built from
$n$ binary strings 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 \emph{Bernoulli model with bias $p$}); the equivalence is true more generally, for $p \geq 1/2$.
It is easy to see that
$F_n$ is equivalent to the fillup level (depth of the deepest full level),
$D_n$ to the typical depth (depth of a randomly chosen leaf), and $B_{n,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.
\begin{lemma}[Equivalence of the R\'enyi problem with those of PATRICIA tries]
	\label{EquivalenceLemma}
    Any parameter (in particular, $H_n, F_n, D_n$, and $B_{n,k}$) of the R\'enyi 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 \geq 1/2$.
\end{lemma}
\begin{proof}

    In a nutshell, we
    couple a random PATRICIA trie and the sequence of queries from the R\'enyi 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$ (in fact, always isomorphic), so that parameters defined in terms of
    either tree structure are equal in distribution.

    More precisely, we start with $n$ independent infinite binary strings $S_1, \ldots, S_n$
    generated according to a memoryless source with bias $p$, where each string corresponds, in a way to
    be made precise below, to a
    unique element of the set of labels (for simplicity, we assume that $A = [n]$, and
    $S_j$ is associated to the object $j$, for $j \in [n]$; intuitively, $S_j$ encodes the decision, for each
    query, of whether or not to include $j$).  These induce a PATRICIA trie $T$,
    and our goal is to show that we can simulate a R\'enyi process using these strings,
    such that the corresponding tree $T_R$ is isomorphic to $T$ as a rooted plane--
    oriented tree (see Example~\ref{QuerySequenceIgnoreExample}).  The basic idea is as follows:
    we maintain for each string $S_j$ an
    index $k_j$, initially set to $1$.  Whenever the R\'enyi 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 $S_{j,k_j} = 1$, and then increment $k_j$ 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.
\end{proof}
Thus, our results on these parameters for the R\'enyi 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
\cite{jansonszpa1996} and in the solution to R\'{e}nyi's problem which we study here
\cite{pittelrubin1990, devroye1992}).

Similarly, the version of the R\'enyi 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 relevant 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 \cite{park2008}.  The expected profiles
of digital search trees (another common digital tree with connections to Lempel-Ziv parsing) in both cases were analyzed in \cite{drmotaszpa2011}, and
the variance for the asymmetric case was treated
in \cite{kazemi2011}.  Some aspects of trie and PATRICIA trie profiles
(in particular, the concentration of their distributions) were
studied using probabilistic methods in \cite{devroye2004, devroye2002}.
The depth in PATRICIA for the symmetric model was analyzed in
\cite{devroye1992,knuth1998acp} while for the asymmetric model in
\cite{szpa1990}. The leading asymptotics for the PATRICIA height
for the symmetric Bernoulli model was first analyzed by Pittel
\cite{Pittel85} (see also \cite{szpa2001Book} for suffix trees).
The two-term expression for the height of PATRICIA for the symmetric model
was first presented in \cite{pittelrubin1990} as discussed above
(see also \cite{devroye1992}).  To our knowledge, precise asymptotics
beyond the leading term for the height and fillup level have not been given
in the asymmetric case for either tries or digital search trees.
Finally, in \cite{magnerPhD2015,magnerspa2015}, 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 previous analysis,
but the analyses for $H_n$ and $F_n$ 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 \cite{park2008} and followed in \cite{drmotaszpa2011}.
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 (\ref{pg1}) 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
$B_{n,k}$, $H_n$, $F_n$, and $D_n$, along with sketches
of the derivations.  Complete proofs for $H_n$ (and a roadmap for
the proof for $F_n$) are
provided in Section~\ref{Proofs}. Section~\ref{sec:depo} provides some
background on the depoissonization step.  Finally, Section~\ref{secmiracle}
details a surprising series identity which arises in the analysis of $H_n$,
leading to significant complications.

\section{Main Results}
\label{MainResults}

In this section, we formulate precisely R\'enyi's problem and
present our main results.
Our goal is to provide precise asymptotics for three natural parameters
of the R\'enyi problem on $n$ objects with each label in a given
query being included with probability $p \geq 1/2$:
the number $F_n$ of queries needed before at least a single element of the bijection can be identified,
the number $H_n$ needed to recover the bijection
in its entirety, and the number $D_n$ 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 R\'enyi.

We recall that we can express
$F_n$, $H_n$, and $D_n$ in terms of the {\it profile} $B_{n,k}$
(defined as the number of bijection elements revealed by the $k$th query)
\begin{equation}
    F_n = \min\{k : ~ B_{n,k} > 0\} - 1, \
    H_n = \max\{k : ~ B_{n,k} > 0\},  \
    \Pr[D_n = k] = \frac{ {\mathbb{E}}[B_{n,k}]}n.  \label{eqrel2}
\end{equation}
Using the first and second moment methods, we can then obtain upper and lower bounds
on $H_n$ and $F_n$ in terms of the moments of $B_{n,k}$:
\begin{eqnarray}
\label{eq-h}
    \Pr[H_n>k] \leq \sum_{j>k}  {\mathbb{E}}[B_{n,j}],  \ \ \  \ \
    \Pr[H_n<k] \leq \frac{ {\mathrm{Var}}[B_{n,k}]}{ {\mathbb{E}}[B_{n,k}]^2},
\end{eqnarray}
and
\begin{eqnarray}
\label{eq-f}
    \Pr[F_n > k] \leq \frac{ {\mathrm{Var}}[B_{n,k}]}{ {\mathbb{E}}[B_{n,k}]^2}, \quad
    \Pr[F_n < k] \leq  {\mathbb{E}}[B_{n,k}].
\end{eqnarray}
The analysis of the distribution of $D_n$ reduces simply to that of $ {\mathbb{E}}[B_{n,k}]$,
as in (\ref{eqrel2}).

Having reduced the analyses of $F_n, H_n$, and $D_n$ to that of the moments of $B_{n,k}$,
we now explain our approach to the latter analysis, starting in Section~\ref{BasicFactsSection} with a review of the work
done in \cite{magnerPhD2015}.
We will then show in
Section~\ref{MainResultsSection} how the present paper
requires extensions far beyond \cite{magnerPhD2015,magnerspa2015}
to give new results on the quantities of interest in the R\'enyi problem.
\subsection{Basic facts for the analysis of $B_{n,k}$}
\label{BasicFactsSection}
Here we recall some facts, worked out in detail in \cite{magnerPhD2015}, which will form the
starting point of the analysis in the present paper.
In order to derive our main results,
we need proper asymptotic information about $ {\mathbb{E}}[B_{n,k}]$ and $ {\mathrm{Var}}[B_{n,k}]$ at the boundaries of this region.

We start by deriving a recurrence for the average profile,
which we denote by $\mu_{n,k} :=  {\mathbb{E}}[B_{n,k}]$. It satisfies
\begin{eqnarray}
    \label{muRecurrence}
    \mu_{n,k} = (p^n + q^n)\mu_{n,k} + \sum_{j=1}^{n-1} { n\choose j } p^j q^{n-j} (\mu_{j,k-1} + \mu_{n-j,k-1})
\end{eqnarray}
for $n\geq 2$ and $k \geq 1$, with some initial/boundary conditions;
most importantly, $\mu_{n,k} = 0$ for $k \geq n$ and any $n$.
Moreover, $\mu_{n,k} \leq 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 \leq j \leq 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 $p^n + q^n$),
then the partition element splitting constraint on the queries applies,
the potential query is ignored as {\it inconclusive},
and the contribution is $\mu_{n,k}$.

The tools that we use to solve this recurrence (for details see \cite{magnerPhD2015,magnerspa2015})
are similar to those of the analyses for digital trees \cite{szpa2001Book}
such as tries and digital search trees (though the analytical details
differ significantly).  We first derive a functional equation for the
Poisson transform
$\Po{G}_k(z) = \sum_{m \geq 0} \mu_{m,k}\frac{z^m}{m!}e^{-z}$ of
$\mu_{n,k}$, which gives
\[
    \Po{G}_k(z) = \Po{G}_{k-1}(pz) + \Po{G}_{k-1}(qz) + e^{-pz}(\Po{G}_k -
\Po{G}_{k-1})(qz) + e^{-qz}(\Po{G}_{k} - \Po{G}_{k-1})(pz).
\]
This we write as
\begin{eqnarray}
\label{pg1}
    \Po{G}_k(z) = \Po{G}_{k-1}(pz) + \Po{G}_{k-1}(qz) + \Po{W}_{k,G}(z),
\end{eqnarray}
and at this point the goal is to determine asymptotics for
$\Po{G}_k(z)$ as $z\to\infty$ in a cone around the positive real axis.
When solving (\ref{pg1}), $\Po{W}_{k,G}(z)$ significantly complicates the analysis because it has
no closed-form Mellin transform (see below).
Finally, depoissonization \cite{szpa2001Book} will allow us to directly transfer the
asymptotic expansion for $\Po{G}_k(z)$ back to one for $\mu_{n,k}$ since
$\mu_{n,k}$ is well approximated by $\Po{G}_k(n)$.

To convert (\ref{pg1}) to an equation that is easier to handle,
we use the \emph{Mellin transform}
\cite{Flajolet95mellintransforms}, which, for a function
$f: {\mathbb{R}} \to  {\mathbb{R}}$ is given by
\[
    \Me{f}(s) = \int_{0}^\infty z^{s-1} f(z) \dee{z}.
\]
Using the Mellin transform identities and defining $T(s) = p^{-s} + q^{-s}$, we end up with an expression
for the Mellin transform $\Me{G_k}(s)$ of $\Po{G}_k(z)$ of the form
\[
    \Me{G_k}(s) = \Gamma(s+1)A_k(s)( p^{-s} + q^{-s})^k=
    \Gamma(s+1)A_k(s) T(s)^k,
\]
where $A_k(s)$ is an infinite series arising from the contributions
coming from the function $\Po{W}_{k,G}(z)$, and the fundamental strip of
$\Po{G}_k(z)$ contains
$(-k-1, \infty)$. It involves  unknown
$\mu_{m,j} - \mu_{m,j-1}$ for various $m$ and $j$
(see  \cite{magnerPhD2015,magnerknesslszpa2014}), that is:
\begin{eqnarray}
    \label{A_kFormula}
    A_k(s)
    = \sum_{j=0}^k T(s)^{-j} \sum_{m \geq j} T(-m)(\mu_{m,j} - \mu_{m,j-1})\frac{\Gamma(m+s)}{\Gamma(s+1)\Gamma(m+1)}.
\end{eqnarray}
Locating and characterizing the singularities
of $\Me{G_k}(s)$ then becomes important. In \cite{magnerspa2015} it is
shown that   for any $k$, $A_k(s)$ is entire, with zeros at
$s \in  {\mathbb{Z}} \cap [-k, -1]$, so that $\Me{G_k}(s)$ is meromorphic,
with possible simple poles at the negative integers less than $-k$.
The fundamental strip of $\Po{G}_k(z)$ then contains $(-k-1, \infty)$.

We then must asymptotically invert the Mellin transform to recover $\Po{G}_k(z)$.  The Mellin inversion
formula for $\Me{G_k}(s)$ is given by
\begin{eqnarray}
    \label{MellinInversionFormula}
    \Po{G}_k(z) = \frac{1}{2\pi i} \int_{\rho - i\infty}^{\rho + i\infty}
z^{-s}\Me{G_k}(s)\dee{s}
    = \frac{1}{2\pi i} \int_{\rho - i\infty}^{\rho + i\infty}
z^{-s}\Gamma(s+1)A_k(s)T(s)^k\dee{s},
\end{eqnarray}
where $\rho$ is any real number inside the fundamental strip
associated with $\Po{G}_k(z)$.

\subsection{Main results via extension of the analysis of $B_{n,k}$}
\label{MainResultsSection}
Having explained the relevant functional equations and the integral representation (\ref{MellinInversionFormula})
for $\Po{G}_k(z)$, we now move on to describe the main results of this paper.
For Theorem~\ref{HeightTheorem} and \ref{FillupTheorem} we start with a sketch of the derivation
whereas the proof of Theorem~\ref{DepthCorollary} is given immediately.
The complete proof of Theorem~\ref{HeightTheorem} and a roadmap for Theorem~\ref{FillupTheorem}, both for the case $p>q$,
 is given in Section~\ref{Proofs}.

\subsubsection{Result on $H_n$}
\label{HeightSketch}
Our first aim is to derive two-term expansions for the typical values of $H_n$ and $F_n$.  To do this for, e.g., $H_n$,
we define, for $p \geq q$,
\[
    k_* = \log_{1/p} n + \psi_*(n),
\]
where $\psi_*(n) = o(\log n)$ is a function to be determined.  We also define
\begin{eqnarray}
    \label{PsiLDefinition}
    \psi_L(n) = (1-\epsilon)\psi_*(n) &&        k_L = \log_{1/p} n + \psi_L(n) \\
    \psi_U(n) = (1+\epsilon)\psi_*(n) &&        k_U = \log_{1/p} n + \psi_U(n),
    \label{PsiUDefinition}
\end{eqnarray}
for arbitrarily small $\epsilon > 0$.
We require that $\psi_*(n)$ be such that
\begin{eqnarray}
    \label{PhaseTransitionExpr}
     {\mathbb{E}}[B_{n,k_L}] \to \infty,       &&
     {\mathbb{E}}[B_{n,k_U}] \to 0,
\end{eqnarray}
and a proper upper bound for $ {\mathrm{Var}}[B_{n,k_L}]$
(see Lemma~\ref{VarianceLemma}). However, in order to make the
following pre-analysis more transparent we will not dwell on the variance.

To determine a candidate for $\psi_*(n)$, we start with the inverse
Mellin integral
representation for $\Po{G}_{k_*}(n)$:
\begin{eqnarray}
    \Po{G}_{k_*}(n)
    = \frac{1}{2\pi i} \int_{\rho - i\infty}^{\rho + i\infty} J_{k_*}(n, s)\dee{s},
    \label{InverseMellinIntegral}
\end{eqnarray}
where we define
\begin{eqnarray}
\nonumber
    J_k(n, s)
    &=& n^{-s}T(s)^k\Gamma(s+1)A_k(s) \\
    &=& \sum_{j=0}^k n^{-s}T(s)^{k-j}\sum_{m \geq j} T(-m)(\mu_{m,j} - \mu_{m,j-1
})\frac{\Gamma(m+s)}{\Gamma(m+1)}.
\label{eq-j}
\end{eqnarray}
Note that by depoissonization (see Section~\ref{sec:depo} and \cite{jacquetszpa1997})
we have
\[
\mu_{n,k_*} = \Po{G}_{k_*}(n) - \frac n2 \Po{G}''_{k_*}(n) + O(n^{-1+\epsilon}).
\]
Indeed, because of the exponential decay of $A_k(s)\Gamma(s+1)$
along vertical lines, the entire integral
is at most of the same order as the integrand on the real axis (we justify this more carefully in Section~\ref{HProof}). Furthermore, since the second derivative has an additional factor
$s(s+1)n^{-2}$ in the integrand we will get a similar bound for $\frac n2 \Po{G}''_{k_*}(n)$ which
is just $\rho^2/n$ times the corresponding bound for $\Po{G}_{k_*}(n)$ and, thus, negligible
in comparison to $\Po{G}_{k_*}(n)$.

In this proof roadmap we focus on estimating the
integrand $J_{k_*}(n, \rho)$, $\rho \in  {\mathbb{R}}$, as precisely as possible.
Using Lemma~\ref{KnesslLemma}, we find (see (\ref{eqfirstesti})
in Section~\ref{HProof}) that the $j$th term in the representation (\ref{eq-j}) of $J_{k_*}(n,\rho)$ is of
order
\begin{eqnarray}\label{eqjthterm}
n^{-\rho} T(\rho)^{k_*-j} p^{j^2/2 + O(j\log j)},
\end{eqnarray}
where $\rho < 0$
and $T(\rho) = p^{-\rho} + q^{-\rho}$. Hence, by setting $j_0 = -\log_{1/p} T(\rho)$
we have
\begin{eqnarray}\label{eqJk*bound}
J_{k_*}(n, \rho) = O\left( n^{-\rho} T(\rho)^{k_*} p^{-j_0^2/2 + O(j_0\log j_0)} \right).
\end{eqnarray}
Next we have to choose $\rho \in  {\mathbb{R}}_-$ that minimizes this upper bound.
Here we distinguish between the symmetric case $p = q = 1/2$ and the case $p> q$.

In the symmetric case we have $T(\rho) = 2^{\rho +1}$ and $j_0 = -\rho-1$ and, thus,
\[
J_{k_*}(n, \rho) = O\left( n^{-\rho} 2^{(\rho+1)(\log_2 n +
\psi_*(n))+\rho^2/2 + O(|\rho|\log |\rho|)} \right).
\]
Consequently by disregarding the error term $O(|\rho|\log |\rho|)$ the optimal choice
of $\rho$ is $\rho = -\psi_*(n)$ which gives the upper bound
\[
J_{k_*}(n, \rho) = O\left( 2^{\log_2 n - \psi_*(n)^2/2 + O(|\psi_*(n)|\log |\psi_*(n)|)} \right).
\]
Hence, the threshold for this upper bound is $\psi_*(n) = \sqrt{2\log_2 n}$. In particular it also follows that
\[
J_{k_U}(n, \rho) = O\left( 2^{-(2\epsilon+\epsilon^2)\log_2 n  + O(\sqrt{\log n} \log\log n )} \right),
\]
where $k_U = \log_{1/p} n + (1+\epsilon)\sqrt{2\log_2 n}$. We also note that we get the same bound
if $\rho = -\psi_*(n) + O(1)$.

In the case $p> q$ we have to be slightly more careful. Nevertheless we can start with the
upper bound (\ref{eqJk*bound}) and obtain
\[
J_{k_*}(n, \rho) = O\left( p^{ ( \rho- \log_{1/p} T(\rho))\log_{1/p}n - \psi_*(n) \log_{1/p} T(\rho) - (\log_{1/p} T(\rho))^2/2
  + O(j_0\log j_0)  }   \right).
\]
 From the representation
$T(\rho) = p^{-\rho}( 1+ (p/q)^\rho)$ we obtain
\[
\log_{1/p} T(\rho) = \rho + \frac{ (p/q)^\rho }{\log(1/p)} + O\left(  (p/q)^{2\rho} \right).
\]
It is clear that we have to choose $\rho < 0$ that tends to $-\infty$ if $n\to\infty$.
Hence, $\log_{1/p} T(\rho) = \rho + o(1)$ and consequently a proper choice for $\rho$ is
the solution of the equation
\begin{eqnarray*}
    \frac{\partial}{\partial \rho} \left(
    - \frac{ (p/q)^\rho }{\log(1/p)} \log_{1/p}n - \psi_*(n) \rho  -
    \frac{\rho^2}2 \right)
    = \frac{ (p/q)^\rho \log(p/q)}{\log(1/p)} \log_{1/p}n- \psi_*(n) -\rho = 0.
\end{eqnarray*}
Actually this gives $\rho < - \psi_*(n)$ and, thus,
\[
\rho = - \log_{p/q}\log n + O(\log\log\log n).
\]
With this choice the upper bound for $J_{k_*}(n, \rho)$ writes as
\begin{eqnarray}
J_{k_*}(n, \rho) = O\left( p^{ (\psi_*(n)+\rho)/\log(p/q) - \psi_*(n) \rho - \frac{\rho^2}2
  + O(j_0\log j_0)  }   \right)
= O\left( p^{ - \psi_*(n) \rho - \frac{\rho^2}2
  + O(j_0\log j_0)  }   \right).
  \label{MyEqn}
\end{eqnarray}
This implies that the threshold for this upper bound is given by
\[
\psi_*(n) = -\frac \rho 2 = \frac 12 \log_{p/q} \log n + O(\log\log\log n).
\]
In particular, if we replace $\psi_*(n)$ by
$\psi_U(n) = \frac 12(1+\epsilon)  \log_{p/q} \log n$ we obtain
\begin{eqnarray} \label{HeightMaxContribution0}
J_{k_U}(n, \rho) = O\left( p^{ \epsilon(\log_{p/q} \log n)^2/2 +
O(\log\log n \log\log \log n) }   \right)
\end{eqnarray}
and for
$\psi_L(n) = \left(1 -\epsilon\right) \frac 12 \log_{p/q} \log n$,
\begin{eqnarray} \label{HeightMaxContribution}
J_{k_L}(n, \rho) = O\left( p^{ -\epsilon(\log_{p/q} \log n)^2/2 + O(\log\log n \log\log \log n }   \right).
\end{eqnarray}

The above pre-analysis suggests asymptotic estimates for $\Po{G}_k(n)$ and, thus, by
depoissonization estimates for $\mu_{n,k}$, which imply a two-term expansion for $H_n$.
The complete proof of this result is given in Section~\ref{HProof}.
In summary, we formulate below our first main result.

\begin{theorem}[Asymptotics for $H_n$]
    \label{HeightTheorem}
    With high probability,
    \begin{eqnarray*}
        H_n = \left\{ \begin{array}{ll}
                \log_{1/p} n + \frac 12\log_{p/q}\log n + o(\log\log n) &
                p > q \\
                \log_{2} n + \sqrt{2\log_2 n} + o(\sqrt{\log n}) &
                p = q
        \end{array}   \right.
    \end{eqnarray*}
for large $n$.
\end{theorem}

\subsubsection{Result on $F_n$}
We take a similar approach for the derivation of $F_n$, with some differences.  We set
\begin{eqnarray*}
    k_* = \log_{1/q} n + \phi_*(n)
\end{eqnarray*}
with
\begin{eqnarray*}
    \phi_L(n) = (1+\epsilon)\phi_*(n),      &&
    \phi_U(n) = (1-\epsilon)\phi_*(n),
\end{eqnarray*}
and $k_L$ and $k_U$, respectively, defined with $\phi_L$ (respectively, $\phi_U$) in place of $\phi_*$.
The derivation of an estimate for the $j$th term of $J_{k_*}(n, \rho)$, $\rho\in {\mathbb{R}}$, is similar to that in Section~\ref{HeightSketch},
except now the asymptotics of $\Gamma(\rho+1)$ play a role (this is reflected in the proof, where $\Gamma(\rho+1)$ determines
the location of the saddle points of the integrand).  We find that the $j$th term is at most $q^{\lambda_j(n, \rho)}$,
where
\begin{eqnarray}
    \lambda_j(n, \rho) = \rho(j - \phi_*(n)) + (j - \phi_*(n) - \log_{1/q} n)\log_{1/q}(1 + (q/p)^{\rho}) - \rho\log_{1/q} \rho + O(\rho).
    \label{OptimalNu}
\end{eqnarray}
Optimizing over $j$ gives $j = 0$.
The behavior with respect to $\rho$ depends on whether or not $p=q$, because $\log_{1/q}(1 + (q/p)^\rho) = 1$ when $p=q$
and is dependent on $\rho$ otherwise.  Taking this into account and minimizing over all $\rho$ gives an optimal value of
\begin{eqnarray*}
     \rho =
     \left\{\begin{array}{ll}
        2^{-\phi_*(n) - 1/\log 2}       &  p=q=1/2, \\
        \log_{p/q}\log n                & p > 1/2.
     \end{array} \right.
\end{eqnarray*}
Note that this corresponds to the real part of the saddle points in the proof.
Plugging this into (\ref{OptimalNu}), setting the resulting expression equal to $0$, and solving for $\phi_*(n)$ gives
\begin{eqnarray*}
    \phi_*(n) =
    \left\{\begin{array}{ll}
        -\log_2\log n + O(1)    & p=q=1/2 \\
        -\log_{1/q}\log\log n   & p > 1/2.
    \end{array} \right.
\end{eqnarray*}

This heuristic derivation suggests that  the following theorem holds.
More details are given in Section~\ref{FProof}.
\begin{theorem}[Asymptotics for $F_n$]
    \label{FillupTheorem}
    With high probability,
    \begin{eqnarray*}
        F_n =
        \left\{\begin{array}{ll}
            \log_{1/q} n - \log_{1/q}\log\log n + o(\log\log\log n)  &
            p > q \\
            \log_{2} n - \log_2\log n + o(\log\log n) &
            p = q
        \end{array} \right.
    \end{eqnarray*}
for large $n$.
\end{theorem}
\subsection{Result on $D_n$}
We move to  our results concerning $D_n$.  To state them, we first need to observe that there is a natural
way to define the sequence $\{D_n\}_{n\geq 0}$ on a single probability space, so that we may ask whether
or not $D_n$, properly normalized, converges almost surely, and to what limiting value.  This common space
is defined by appealing to the correspondence between the sequence of R\'enyi problem queries and the growth
of a random PATRICIA trie.  For each $n \geq 0$, we define a tree $T_n$ which is a PATRICIA trie constructed
on $n$ strings (equivalently, a terminating sequence of R\'enyi queries recovering a bijection between two sets
of $n$ elements): $T_0$ is an empty tree, and $T_{n+1}$ is constructed from $T_n$ by generating an independent
string of i.i.d. $ {\mathrm{Bernoulli}}(p)$ random variables and inserting this string into $T_n$.  Then, for each $n$,
$D_n$ is the depth of a leaf chosen uniformly at random (and independent of everything else) from the leaves
of $T_{n}$.

With this construction in mind, we have the following result about the
convergence of $D_n$.  Its proof combines known facts about the profile
with the new ones proved here, as well as
a proof technique that was used before in, e.g., \cite{Pittel85}.

\begin{theorem}[Asymptotics of $D_n$]
    \label{DepthCorollary}
    For $p > 1/2$, the normalized depth $D_n/\log n$ converges in probability to $1/h(p)$
    where $h(p) := -p\log p - q\log q$ is the entropy of a $ {\mathrm{Bernoulli}}(p)$ random variable, but not
    almost surely. In fact,
    \begin{eqnarray}
        \label{D_nNoAlmostSure}
        \liminf_{n\to\infty} D_n/\log n = 1/\log(1/q), &&
        \limsup_{n\to\infty} D_n/\log n = 1/\log(1/p)
    \end{eqnarray}
almost surely.
\end{theorem}

\begin{proof}
The fact that $D_n/\log n$ converges in probability to $1/h(p)$ follows directly from the
central limit theorem for $D_n$ given in \cite{szpa2001Book}.

Next we show that (\ref{D_nNoAlmostSure}) holds.
Clearly $F_n \le D_n \le H_n$. Now let us consider the following
    sequences of events: $A_n$ is the event that $D_n = F_n+1$, and $A'_n$ is the event that $D_n = H_n$.
    We note that all elements of the sequences are independent, and $\Pr[A_n] \ge 1/n$, $\Pr[A'_n] \geq 1/n$.  This
    implies that $\sum_{n=1}^\infty \Pr[A_n] = \sum_{n=1}^\infty \Pr[A'_n] = \infty$, so that the Borel-Cantelli
    lemma tells us that both $A_n$ and $A'_n$ occur infinitely often almost surely.

In the next step we show that, almost surely, $F_n/\log n \to 1/\log(1/q)$
    and $H_n/\log n \to 1/\log(1/p)$. Then (\ref{D_nNoAlmostSure}) is proved.
    We cannot apply the Borel-Cantelli lemmas directly, because the relevant sums do not converge.  Instead, we apply the following trick:
    we observe that both $(F_n)$ and $(H_n)$ 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 (\ref{D_nNoAlmostSure}).

    We illustrate this idea more precisely for $H_n$.  By our analysis above, we know that
    \[
        \Pr[|H_n/\log n - 1/\log(1/p)| > \epsilon] = O(e^{-\Theta(\log\log n)^2}).
    \]
    Then we fix $t$, and we define $n_{r,t} = 2^{t^2 2^{2r}}$.
    On this subsequence, by the probability
    bound just stated, we can apply the Borel-Cantelli lemma to conclude
    that $H_{n_{r,t}}/\log(n_{r,t}) \to 1/\log(1/p) \cdot (t+1)^2/t^2$
    almost surely.  Moreover, for every $n$, we can choose $r$ such
    that $n_{r,t} \leq n \leq n_{r,t+1}$.
    Then
    \[
        H_n/\log n \leq H_{n_{r,t+1}}/\log n_{r,t},
    \]
    which implies
    \[
        \limsup_{n\to\infty} \frac{H_n}{\log n} \leq
        \limsup_{r\to\infty} \frac{H_{n_{r,t+1}}}{\log n_{r,t+1}}
        \frac{\log n_{r,t+1}}{\log n_{r,t}}
        = \frac{1}{\log(1/p)} \cdot \frac{(t+1)^2}{t^2}.
    \]
    Taking $t \to \infty$, this becomes $1/\log(1/p)$, as desired.
    The argument for the $\liminf$ is similar,
    and this establishes the almost sure convergence of $H_n$.
    The derivation is entirely similar for $F_n$.
  \end{proof}

\section{Proof of Theorems~\ref{HeightTheorem}  and  \ref{FillupTheorem}}
\label{Proofs}

We give a detailed proof of Theorem~\ref{HeightTheorem} and indicate the
main lines of the proof of Theorem~\ref{FillupTheorem}.
We also concentrate just on the case $p>q$.
The proof of the symmetric case can be done by the same techniques
(properly adapted) but it just reproves the result by Pittel and Rubin \cite{pittelrubin1990}.

\subsection{Proof of Theorem~\ref{HeightTheorem}}
\label{HProof}

\subsubsection{A-Priori Bounds for $\mu_{n,k}$}

For the analysis of the profile around the height level, we need precise information
about $\mu_{n,k}$ with $n\to\infty$ when $k$ close to $n$.  This is captured in the following lemma, which
first appeared in a similar form in \cite{magnerknesslszpa2014}.

We consider $\mu_{n,k}$ where $k$ is close to $n$, so we set $k = n-\ell$
and represent it as
\[
\mu_{n,k} = \mu_{n,n-\ell} = n! C_*(p) p^{(n-\ell)(n-\ell+1)^2/2}q^{n-\ell} \xi_{\ell}(n),
\]
where
\[
        C_*(p) = \prod_{j=2}^\infty (1-p^j - q^j)^{-1} \cdot (1 + (q/p)^{j-2}),
\]
$\xi_1(1) = 1/C_*(p)$ and for $n > \ell \ge 1$
\begin{equation}\label{eqxirec}
        \xi_{\ell}(n)(1-p^n-q^n) =
     \sum_{J=1}^\ell \frac{\xi_{\ell+1-J}(n-J)}{J!}q^{-1}p^{\ell-n}(p^{n-J}q^{J} + p^{J}q^{n-J}).
\end{equation}
Note that $\xi_\ell(n) = 0$ for $n\le \ell$.  The above formulas were first derived in \cite{magnerknesslszpa2014}.

\begin{lemma}[Asymptotics for $\mu_{n,k}$, $k\to\infty$ and $n$ near $k$]
    \label{KnesslLemma}
    \label{KNESSLLEMMA}
    \label{mu_mjUpperBoundLemma}
    Let $p \geq q$.
\par\noindent
{\rm (i)} {\rm Precise estimate: }
    For every fixed $\ell \ge 1$ and $n\to\infty$
    \begin{eqnarray*}
        \mu_{n,n-\ell} \sim n! C_*(p) p^{(n-\ell)^2/2 + (n-\ell)/2}q^{n-\ell} \xi_{\ell},
    \end{eqnarray*}
    where the sequence $\xi_\ell$, $\ell\ge 1$ satisfies the recurrence
    \begin{equation}\label{eqexrec2}
      \xi_\ell
        = q^{-1}p^{\ell} \sum_{J=1}^\ell \frac{\xi_{\ell+1-J}}{J!} (q/p)^{J}
     \end{equation}
    with $\xi_1 = 1$. Furthermore we have (for some positive constant $C$)
 \begin{equation}\label{eqxiapprox}
|\xi_{\ell+1-J}(n-J)-\xi_{\ell+1-J}| \le C(p^{n-\ell-1} + (q/p)^{n-\ell-1})/(\ell-J)!,
\end{equation}
\par\noindent
{\rm (ii)} {\rm Upper bound: }
    We have $\xi_\ell(n) \le C_1/(\ell-1)!$ for some constant $C_1$ and, thus, for $1\le k< n$
    (and some constant $C$)
    \begin{eqnarray}
        \mu_{n,k}
        \leq C\frac{n!}{(n-k-1)!}p^{(k^2 + k)/2 }q^{k}.
        \label{mu_mjUpperBound}
    \end{eqnarray}
\end{lemma}

\begin{proof}
    From the recurrence (\ref{eqxirec}) it follows easily that for each
$\ell\ge 1$ the limit $ \xi_\ell = \lim_{n\to\infty} \xi_\ell(n)$
exists by (\ref{mu_mjUpperBound}), and in particular
for $\ell =1$ we have $\xi_1 = 1$.
   Clearly this limits satisfy the recurrence (\ref{eqexrec2}).

Next we show by induction a uniform upper bound of the form
$\xi_\ell(n) \le C_1/(\ell-1) !$
The induction step for $n>\ell > \ell_1$ runs as follows (where $C_1$ and  $\ell_1$ is appropriately chosen such
that the upper bound is true for $\ell \le \ell_1$ and that
$2/(q \ell_1(1-p^{\ell_1}-q^{\ell_1}) \le 1$):
\begin{eqnarray*}
\xi_\ell(n) &\le& \frac{C_1}{1-p^n-q^n} \left( \sum_{J=1}^{\ell} \frac{p^{\ell-J}q^{J-1}}{J!(\ell-J)!} +
\sum_{J=1}^{\ell} \frac{p^{\ell+J-n}q^{n-J-1}}{J!(\ell-J)!}  \right) \\
&\le& \frac{C_1}{\ell!(1-p^n-q^n)}
\left( \frac 1{q} \sum_{J=0}^{\ell} {\ell \choose J} p^{\ell-J}q^{J} +
\frac{(q/p)^{n-\ell}}{q} \sum_{J=0}^{\ell}   {\ell\choose J} p^{J}q^{\ell-J}  \right) \\
&\le& \frac{C_1}{(\ell-1)!} \frac 1{\ell_1(1-p^{\ell_1}-q^{\ell_1})}
\frac 2q
\le \frac{C_1}{(\ell-1)!}.
\end{eqnarray*}
In a similar way we obtain the approximation estimate (\ref{eqxiapprox}). We give a full proof in Section~\ref{KnesslLemmaProof}.
\end{proof}

\subsubsection{Upper bound on $H_n$}
Now we set
\begin{eqnarray}\label{eqkUdef}
k = k_U = \log_{1/p} n + \psi_U(n) = \log_{1/p} n +
\frac 12\left(1 +\epsilon\right)\log_{p/q}\log n
\end{eqnarray}
just as in (\ref{PsiUDefinition}).
We will first estimate the value of $J_k(n, s)$ (which is defined in (\ref{eq-j}))
for $s = \rho' = - 2\psi(n) + O(1)\in  {\mathbb{Z}}^{-} - 1/2$ (i.e., the set $\{ -3/2, -5/2, ... \}$),
as hinted at in Section~\ref{MainResults}.

\begin{lemma}\label{LeJest}
Suppose that $p>q$, that $\epsilon> 0$, that $k_U$ is given by (\ref{eqkUdef}), and
that $\rho' = \lfloor \rho \rfloor + \frac 12$, where $\rho = - \log_{p/q} \log n + O(\log\log \log n)$
is the solution of the equation
\[
 \frac{ (p/q)^\rho \log(p/q)}{\log(1/p)} \log_{1/p}n+ \psi_U(n) +\rho = 0.
\]
Then we have for $k \ge k_U$
\begin{eqnarray}
    J_{k}(n, \rho') = O\left( T(\rho')^{k-k_U} p^{ \epsilon
(\log_{p/q} \log n)^2/2 + O(\log\log n \cdot \log\log \log n) }   \right).
    \label{anm1}
\end{eqnarray}
\end{lemma}

\begin{proof}
First we observe that the assumption $\rho' \in  {\mathbb{Z}}^{-} - 1/2$  with $|\rho'| \to \infty$ assures that
for all $m\ge 0$ we have $\left| \Gamma(m+\rho')/\Gamma(m+1) \right| \leq 1$.
Next by (\ref{mu_mjUpperBound}) of Lemma~\ref{mu_mjUpperBoundLemma}
we have $\mu_{m,j} = O\left( m^{j+1} p^{j^2/2 + O(j)}\right)$
which implies that
\[
\sum_{m\ge j} T(-m) \mu_{m,j} = O\left( p^{j^2/2 + O(j\log j)} \right).
\]
Hence, the $j$th term in the representation  (\ref{eq-j}) of  $J_k(n, \rho')$ can be estimated by
\begin{eqnarray}
&& \left| n^{-\rho'}T(\rho')^{k-j}
\sum_{m \geq j} T(-m)(\mu_{m,j} - \mu_{m,j-1})
\frac{\Gamma(m+\rho')}{\Gamma(m+1)}\right| \label{eqfirstesti}\\
&&\le n^{-\rho'}T(\rho')^{k-j}
\sum_{m \geq j} T(-m)(\mu_{m,j} +\mu_{m,j-1})
= O\left(n^{-\rho'}T(\rho')^{k-j}  p^{j^2/2 + O(j\log j)}   \right).  \nonumber
\end{eqnarray}
Thus, we have shown (\ref{eqJk*bound}) which implies (\ref{anm1})
for $k = k_U$ (see (\ref{HeightMaxContribution0})).
However, it is easy to extend it to larger $k$ (since equation (\ref{MyEqn})
holds for generic $k_* = k$ and the given choice of $\rho$).
Actually we get uniformly for $k\ge k_U$
\[
J_k(n, \rho') = O\left( T(\rho')^{k-k_U}
p^{ \epsilon (\log_{p/q} \log n)^2/2 + O(\log\log n \log\log \log n) }   \right)
\]
for large $n$.
\end{proof}

Our next goal is to evaluate the integral (\ref{InverseMellinIntegral})
and to obtain a bound for $\mu_{n,k}$.
\begin{lemma}\label{LeJest2}
Suppose that $p>q$, that $\epsilon> 0$, and that $k_U$ and $\rho'$
are given as in Lemma~\ref{LeJest}.
Then we have (for some $\delta> 0$)
\begin{equation}
\mu_{n,k} =
  O\left( T(\rho')^{k-k_U} p^{ \epsilon (\log_{p/q} \log n)^2/2 + O((\log\log n)^{1-\delta}) } \right)
  + O(n^{-1+\epsilon})
    \label{mu_nkUBound}
\end{equation}
uniformly for $k \ge k_U$.
\end{lemma}

\begin{proof}
Letting $\mathcal{C}$ denote the vertical line $\Re(s) = \rho'$, we
evaluate the integral (\ref{InverseMellinIntegral})
by splitting it into an inner region $\mathcal{C}^I$
and outer tails $\mathcal{C}^O$:
\[
    \mathcal{C}^I = \{\rho' + it :~ |t| \leq e^{(\log\log n)^{2-\delta}}\}, \quad
    \mathcal{C}^O = \{\rho' + it :~ |t| > e^{(\log\log n)^{2-\delta}}\},
\]
where $0<\delta < 1$ is some fixed real number.  The inner region we evaluate by showing that it is of the same order as
the integrand on the real axis, and the outer tails are shown to be negligible by the exponential decay of the $\Gamma$ function.

It is easily checked that
$|n^{-s}T(s)^{k-j}\Gamma(m+s)| \leq n^{-\rho'}T(\rho')^{k-j} |\Gamma(m+\rho')|$
when $\Re(s) = \rho'$ (and any value for $\Im(s)$).  Thus,
\begin{eqnarray*}
    |J_k(n, s)|
    \leq  T(\rho')^{k-k_U}  \sum_{j=0}^k n^{-\rho'}T(\rho')^{k_U-j}\sum_{m\geq j} T(-m)|\mu_{m,j} - \mu_{m,j-1}| \frac{|\Gamma(m+\rho')|}{\Gamma(m+1)},
\end{eqnarray*}
which can be upper bounded as in the proof of Lemma~\ref{LeJest}.  Multiplying by the length of the contour, we  find
\begin{eqnarray*}
    \left|\int_{\mathcal{C}^I} J_k(n, s)\dee{s}\right|
    = O\left( T(\rho')^{k-k_U} p^{ \epsilon (\log_{p/q} \log n)^2/2 + O((\log\log n)^{2-\delta}) } \right).

\end{eqnarray*}

We use the following standard bound on the $\Gamma$ function: for $s = \rho' + it$, provided that $|\mathrm{Arg}(s)|$ is less
than and bounded away from $\pi$ and $|s|$ is sufficiently large, we have
\[
    |\Gamma(s)|
    \leq C|t|^{\rho' - 1/2} e^{-\pi|t|/2}.
\]
This is applicable on $\mathcal{C}^O$, and we again use the fact that $|T(s)| \leq T(\rho')$ and $|\mu_{m,j} - \mu_{m,j-1}| \leq m$,
which yields an upper bound of the form
\begin{eqnarray*}
\left| \sum_{m \geq j} T(-m)(\mu_{m,j} - \mu_{m,j-1})  \frac{\Gamma(m+s)}{\Gamma(m+1)}  \right|
& =& O\left( \sum_{m \geq j} T(-m) m \frac{|t|^{m+\rho' - 1/2}e^{-\pi|t|/2})}{\Gamma(m+1)} \right) \\
&=& O\left( p|t|^{\rho' + 1/2}e^{-\pi|t|/2} e^{p|t|}   \right),
\end{eqnarray*}
where we have used the inequality
\begin{eqnarray*}
    |t|^{\rho' - 1/2}e^{-\pi|t|/2} \sum_{m \geq j} \frac{m(p|t|)^{m}}{m!}
    \leq p|t|^{\rho' + 1/2}e^{-\pi|t|/2} e^{p|t|} = e^{-\Theta(|t|)},
\end{eqnarray*}
uniformly in $j$, by our choice of $|t|$.

Furthermore, since $T(\rho')< 1$ we have
\[
	\sum_{j=0}^k n^{-\rho'}T(\rho')^{k-j} = O(n^{-\rho'})

    = e^{O(\log n \log\log n)}.
\]
Hence, integrating this on $\mathcal{C}^O$ gives
\begin{eqnarray*}
    \left| \int_{\mathcal{C}^O} J_k(n, s) \dee{s} \right|
    &=& O\left( T(\rho')^{k-k_U}  e^{O(\log n \log \log n)}  e^{-\Theta( e^{(\log\log n)^{2-\delta}})} \right)\\
& =&  O\left( T(\rho')^{k-k_U} e^{-\Theta( e^{(\log\log n)^{2-\delta}})} \right).
\end{eqnarray*}
Adding these together gives
\begin{eqnarray*}
    \Po{G}_{k}(n)
    &\leq &\left| \int_{\mathcal{C}^I} J_{k_U}(n, s)\dee{s} + \int_{\mathcal{C}^O} J_{k_U}(n, s)\dee{s} \right| \\
    & = & O\left( T(\rho')^{k-k_U} p^{ \epsilon (\log_{p/q} \log n)^2/2 + O((\log\log n)^{2-\delta}) } \right).
\end{eqnarray*}
Similarly we get a bound for $\Po{G''}_{k}(n)$:
\begin{eqnarray*}
    \Po{G''}_{k}(n) =
     O\left( {\rho'}^2 T(\rho')^{k-k_U} p^{ \epsilon (\log_{p/q} \log n)^2/2 + O((\log\log n)^{2-\delta}) } \right).
\end{eqnarray*}
Hence by depoissonization (see (\ref{eqDep3.3}) from Section~\ref{sec:depo}) we get
\[
\mu_{n,k} = O\left( T(\rho')^{k-k_U} p^{ \epsilon (\log_{p/q} \log n)^2/2 + O((\log\log n)^{2-\delta}) } \right)
+ O(n^{-1+\epsilon})
\]
as needed.
\end{proof}

Our original goal was to bound the tail $\Pr[H_n > k_U]$ by the following sum
which we split into two parts:
\[
    \Pr[H_n > k_U] \le  \sum_{k \geq k_U} \mu_{n,k}
    = \sum_{k = k_U}^{\ceil{(\log n)^2}} \mu_{n,k} + \sum_{k=\ceil{(\log n)^2} + 1}^n \mu_{n,k}.
\]
The initial part can be bounded using (\ref{mu_nkUBound}), and the final part we handle using (\ref{mu_mjUpperBound}) in
Lemma~\ref{mu_mjUpperBoundLemma}.
Indeed, since $T(\rho') < 1$ the first sum can be bounded by
\[
    \sum_{k=k_U}^{\ceil{(\log n)^2}}\mu_{n,k}
    \leq
    e^{-\Theta(\epsilon(\log\log n)^2)} .
\]
The second sum is at most
\[

    \sum_{k=\ceil{(\log n)^2}+1}^{n}  \mu_{n,k}
    \leq ne^{-\Theta((\log n)^4)} \\
    =  e^{-\Theta((\log n)^4)}.
\]
Adding these upper bounds together shows that
$
    \Pr[H_n > k_U] = e^{-\Theta(\epsilon(\log\log n)^2)} \to 0,
$
as desired.

\subsubsection{Upper bound on the variance of the profile}

We consider now the case
\begin{equation}\label{eqkLdef}
k = k_L = \log_{1/p} n + \psi_L(n) = \log_{1/p} n + \psi(n), \ \ \ \
\psi(n)=\frac 12 \left(1 -\epsilon \right) \log_{p/q}\log n
\end{equation}
and start with an upper bound for the variance of the profile $ {\mathrm{Var}}[B_{n,k}]$.
\begin{lemma}\label{VarianceLemma}
Suppose that $p>q$, that $\epsilon> 0$, and that $k_L$ is given by (\ref{eqkLdef}).
Then we have
\begin{eqnarray}
 {\mathrm{Var}}[B_{n,k}] &=
  O\left( p^{-\epsilon (\log_{p/q} \log n)^2/2 + O((\log\log n)^{2-\delta}) } \right).
    \label{VarB_nkUBound}
\end{eqnarray}
\end{lemma}

\begin{proof}
The proof technique here is the same as for the proof of the upper bound on $\mu_{n,k}$.

    Our goal is to upper bound the expression
    \[
        \Po{V}_k(n) = \sum_{n\ge 0} \mathbb{E}[B_{n,k}^2] \frac{n^n}{n!}e^{-n} - \tilde G_k(n)^2
        = \frac{1}{2\pi i} \int_{\rho' - i\infty}^{\rho' + i\infty} J^{(V)}_k(n, s)\dee{s},
    \]
    where
    \begin{eqnarray*}
        J^{(V)}_k(n, s)
        = n^{-s}T(s)^k\Gamma(s+1)B_k(s),
    \end{eqnarray*}
    and
    \begin{eqnarray*}
        B_k(s)
        = 1 - (s+1) 2^{-(s+2)} + \sum_{j=1}^k T(s)^{-j} \frac{\Me{W_{j,V}}(s)}{\Gamma(s+1)},
    \end{eqnarray*}
    with \cite{magnerPhD2015}
    \begin{eqnarray*}
        \Me{W_{j,V}}(s)
        &=& \sum_{m \geq j} \frac{\Gamma(m+s)}{m!} \left[  \right.
        \left.T(-m) ( c_{m,j} - c_{m,j-1} + \mu_{m,j} - \mu_{m,j-1}) \right.\\
            &&\left. + T(s)2^{-(s+m)} \sum_{\ell=0}^m \mu_{\ell,j-1}\mu_{m-\ell,j-1} \right. \\
            &&\left.+ 2\sum_{\ell=0}^m \mu_{\ell,j-1} \mu_{m-\ell,j-1} p^\ell q^{m-\ell}
            - 2^{-(m+s)} \sum_{\ell=0}^m \mu_{\ell,j}\mu_{m-\ell,j}
        \right] .
    \end{eqnarray*}

    As above we need a bound on the moments of $B_{m,j}$ for $m$ sufficiently
    close to $j$: for $\mu_{m,j} =  {\mathbb{E}}[B_{m,j}]$, this is (\ref{mu_mjUpperBound}) in Lemma~\ref{mu_mjUpperBoundLemma}.  It turns out that $c_{m,j} =  {\mathbb{E}}[B_{m,j}(B_{m,j}-1)]$
    satisfies a similar recurrence as $\mu_{m,j}$ (see \cite{magnerspa2015})
and also similar inequality: for $j\to\infty$ and $m> j$,
    \begin{eqnarray*}
        c_{m,j} \leq \frac{m!}{(m-j-1)!} p^{j^2/2 + O(j)}.
    \end{eqnarray*}
    The proof is by induction and follows along the same lines as that of the upper bound in Lemma~\ref{mu_mjUpperBoundLemma}.
    Using this, we can upper bound the inverse Mellin integral as in the upper bound for $\tilde G_k(n)$.
In particular it follows that
\[
\tilde V_{k_L}(n) = O\left(  p^{ -\epsilon(\log_{p/q} \log n)^2/2 + O((\log\log n)^{2-\delta}) }       \right)
\]
and similarly we have
\[
\tilde V_{k_L}''(n) = O\left( {\rho'}^2 n^{-2} p^{ -\epsilon(\log_{p/q} \log n)^2 + O((\log\log n)^{2-\delta})  }  \right),
\]
where $\rho'=-\log_{p/q}\log n + O(\log\log\log n)$.
With the help of depoissonization, see (\ref{eqVarest}), we thus obtain (\ref{VarB_nkUBound}).
\end{proof}

\subsubsection{ Lower bound on $H_n$ }
\label{H_nLowerBoundSection}

The most difficult part of the proof of Theorem~\ref{HeightTheorem} is to prove a lower bound for
the expected profile.
\begin{lemma}\label{LemunkLbound}
Suppose that $p>q$, that $\epsilon> 0$, and that $k_L$ is given by (\ref{eqkLdef}).
Then we have
\begin{eqnarray}
\mu_{n,k_L} = \Omega\left( p^{ -\epsilon(\log_{p/q} \log n)^2/2 +
O(\log\log n \log\log \log n) }   \right).
    \label{eqEB_nkLBound}
\end{eqnarray}
\end{lemma}

By combining Lemma~\ref{VarianceLemma} and Lemma~\ref{LemunkLbound} it immediately follows that
\[
\Pr[H_n < k_L] \le \frac{ {\mathrm{Var}}[B_{n,k_L}]}{ \mu_{n,k_L}^2}   \to 0
\]
which proves the lower bound on $H_n$.

The plan to prove Lemma~\ref{LemunkLbound} is as follows:
we evaluate the inverse Mellin integral exactly by a residue computation.  This results in a nested
summation, which we simplify using the binomial theorem and the series of the
exponential function. From this representation we will then detect
several terms that contribute to the leading term in the asymptotic expansion.

\begin{lemma}\label{Lelower-1}
Suppose that $\rho < 0$ but not an integer. Then we have
\begin{eqnarray}
    \Po{G}_k(n)
    = \sum_{j=0}^k \sum_{m \ge j} \kappa_{m,j}\left( \mu_{m,j}-\mu_{m,j-1}\right),
    \label{G_kExplicitFormHLowerBound}
\end{eqnarray}
where
\begin{eqnarray}\label{eqkapparep}
    \kappa_{m,j}
    = \frac{T(-m)n^m}{m!}
    \sum_{\ell= (-\ceil{m+\rho} + 1)  {~\lor~} 0}^{\infty} \frac{(-n)^{\ell}}{\ell!} T(-m-\ell)^{k-j}
\end{eqnarray}
and $x  {~\lor~} y$ denotes the maximum of $x$ and $y$.
\end{lemma}

\begin{proof}
By shifting the line of integration and collecting residues we have
\[
\frac 1{2\pi i} \int_{\rho-i\infty}^{\rho + i\infty}
n^{-s}T(s)^{k-j} \Gamma(m+s)\, ds =
\sum_{\ell \ge \max\{0, - m - \rho\} }
\frac{n^{m + \ell} (-1)^\ell }{\ell!} T(-\ell- m)^{k-j},
\]
where the remaining integral after shifting by any finite amount
becomes $0$ in the limit as a result of the superexponential decay
of the $\Gamma$ function on the points $1/2 - j$ for positive integer $j$.
Hence the lemma follows.
\end{proof}

We now choose $\rho$ as $\rho = -j^*-1$ and set $j_0 = \lfloor j^* + \frac 12 \rfloor$, where
$j^*$ is the root of the equation
\begin{eqnarray}\label{eqj0def}
 (q/p)^{j*}(k_L-j^*) =  \frac {\log(1/p)}{\log(p/q)}(j^* -  \psi_L(n)),
\end{eqnarray}
where $\psi_L(n) = \frac 12 \left( 1 - \epsilon\right) \log_{p/q}\log n$.

In particular, let us define
\begin{eqnarray}
	\overline r_0 := (q/p)^{j_0} (k_L - j_0), && \overline r_1 := \frac{\log(1/p)}{\log(p/q)}(j_0 - \psi_L(n)).
\end{eqnarray}
Then it follows that
\begin{eqnarray}\label{eqj0def-app1}
 \sqrt{q/p} \overline r_1
 \le \overline r_0
 \le \sqrt{p/q} \overline r_1.
\end{eqnarray}
If $j> j_0$ and $m\ge j$ then we certainly have $(-\ceil{m+\rho} + 1)
 {~\lor~} 0 = 0$,
whereas for $j=j_0$ we have $(-\ceil{j_0+\rho} + 1)  {~\lor~} 0 = 1$.

Asymptotically we have $j^* = \log_{p/q}\log n -\log_{p/q}\log\log n + O(1)$. Hence we also have
$j_0 = \log_{p/q}\log n -\log_{p/q}\log\log n + O(1)$ and
$\rho = - \log_{p/q}\log n -\log_{p/q}\log\log n + O(1)$.

In what follows we will encounter several different asymptotic behaviors. In particular we
will show that
\begin{eqnarray}
\tilde G_k(n) &=&
D(p) C_*(p) p^{j_0(j_0+1)/2} q^{j_0-1} n^{j_0} p^{j_0(k-j_0)} e^{\overline r_0} \Phi\left( \frac{\overline r_1 - \overline r_0}{\sqrt{\overline r_0}} \right)
\label{eqasymrel}\\
&+& C_*(p) p^{j_0(j_0+1)/2} q^{j_0-1} n^{j_0} p^{j_0(k-j_0)}  \frac{{\overline r_0}^{\overline r_1}}{\Gamma(\overline r_1+1)}
\left( C(p, \overline r_0/\overline r_1, \langle \overline r \rangle) + o(1)    \right) \nonumber
\end{eqnarray}
where
$\langle x \rangle = x - \lfloor x \rfloor$ denotes the fractional part of a real number $x$, and
\begin{eqnarray} \label{eqDefAp}
D(p) = \sum_{L,M \ge 0} \xi_{L+1}\frac{(-1)^{M}}{M!} p^{((L+M)^2 + L-M)/2} q^{-L-M}
\end{eqnarray}
and $C(p,u,v)$ is a certain function in $p,u,v$ that is strictly positive (see below).
Here and elsewhere, $\Phi$ denotes the distribution function of the normal distribution.

Since ${{\overline r_0}^{\overline r_1}}/{\Gamma(\overline r_1+1)} = O(e^{\overline r_0}/\sqrt{\overline r_0} )$.
Thus, the first term seems to be the asymptotically leading one. However, it turns out
that $D(p) \equiv 0$ (as we will prove in Section~\ref{secmiracle}) so it follows that
\begin{eqnarray} \label{eqpositive}
\tilde G_k(n) \ge C(p)
 p^{j_0(j_0+1)/2} q^{j_0-1} n^{j_0} p^{j_0(k-j_0)}  \frac{{\overline r_0}^{\overline r_1}}{\Gamma(\overline r_1+1)}
\end{eqnarray}
for some constant $C(p) > 0$. Note also that this lower bound implies
(\ref{eqEB_nkLBound}) since by definition $\sqrt{q/p}\, \overline r_0  \le \overline r_1 \le  \sqrt{p/q}\, \overline r_0$ so that
$e^{-\overline r_0} {{\overline r_0}^{\overline r_1}}/{\Gamma(\overline r_1+1)} = e^{\Omega(\log\log n)}$.

The calculations for proving (\ref{eqasymrel}) are quite involved, in particular
the proof of positivity of $C(p,u,v)$. So we will only present a part of the
calculations and refer for a full proof to the appendix.

In what follows we will have some
error terms that are smaller by a factor $p^{j_0}$ or $(q/p)^{j_0}$ compared to the
asymptotic leading term. However, it is easy to check that for $\frac 12 < p < 1$ we have $p^{j_0} = o(E)$ and $(q/p)^{j_0}= o(E)$,
where $E: = e^{-\overline r_0} {{\overline r_0}^{\overline r_1}}/{\Gamma(\overline r_1+1)}$
so that they will not influence the asymptotic leading term.

For $j\le j_0$ and $j\le m\le j_0$ we  have
\begin{eqnarray*}
\kappa_{m,j} =  \frac{T(-m)n^m}{m!} \sum_{r=0}^{k-j} {k-j \choose r}
p^{m(k-j-r)} q^{mr}
\left(  e^{-np^{k-j-r}q^r} - \sum_{\ell\le j_0-m} \frac{(-n)^\ell}{\ell!} (p^{k-j-r}q^{r})^\ell   \right)
\end{eqnarray*}
and  otherwise
\begin{eqnarray*}
\kappa_{m,j} =  \frac{T(-m)n^m}{m!} \sum_{r=0}^{k-j_0} {k-j \choose r}
p^{m(k-j-r)} q^{mr)}   e^{-np^{k-j-r}q^r}.
\end{eqnarray*}

In view of the above discussion we can thus replace the term $T(-m)$ (in $\kappa_{m,j}$) by $p^m$;
the resulting sum will be denoted by $\overline \kappa_{m,j}$.
We can also replace $\mu_{m,j} - \mu_{m,j-1}$ by
\[
\overline \nu_{m,j} := - C_*(p) m! p^{j(j-1)/2} q^{j-1} \xi_{m-j+1}  .
\]
By a careful look we thus obtain
\begin{equation}
 \Po{G}_k(n) =
     \sum_{j=0}^k \sum_{m \ge j} \overline\kappa_{m,j} \overline \nu_{m,j}
    + O\left( n^{j_0} T(-j_0)^{k-j_0}p^{j_0(j_0+1)/2}q^{j_0} \left( p^{j_0} + (q/p)^{j_0} \right) \right). \label{G_kExplicitFormHLowerBound-2}
\end{equation}

In order to analyze the sum representation (\ref{G_kExplicitFormHLowerBound-2}) we split it
into several parts:
\[
T_1 :=  \sum_{j> j_0} \sum_{m\ge j}  \overline\kappa_{m,j} \overline \nu_{m,j}, \quad
T_2 :=  \sum_{j\le  j_0} \sum_{m > j_0} \overline \kappa_{m,j} \overline \nu_{m,j}, \quad
T_3 :=  \sum_{j\le  j_0} \sum_{m=j}^{j_0} \overline \kappa_{m,j} \overline \nu_{m,j}.
\]
Note that the exponential function $e^{-np^{k-j-r}q^r}
= e^{-(q/p)^{r-r_1(j)}}$ behaves completely differently
for $r\le r_1(j)$ and for $r> r_1(j)$
where $r_1(j) = (j- \psi(n))\frac{\log(1/p)}{\log(p/q)}$.
Hence it is convenient to split $T_3$ into three parts $T_{30} + T_{31}+T_{32}$, where the $T_{30}$ and $T_{31}$ correspond
to the terms with $r\le r_1(j)$ and $T_{32}$ for those with $r> r_1(j)$.
$T_{30}$ involves the exponential function $e^{-np^{k-j-r}q^r}$ whereas
$T_{31}$ takes care of the polynomial sum
$\sum_{\ell\le j_0-m} \frac{(-n)^\ell}{\ell!} (p^{k-j-r}q^{r})^\ell$.

For notational convenience we set
\begin{equation}\label{eqF0-0}
F_0 :=  p^{j_0(j_0+1)2} q^{j_0-1} n^{j_0} p^{j_0(k-j_0)} \frac{ \overline r_0^{\overline r_1}} {\Gamma(\overline r_1 +1)}.
\end{equation}

We recall that
\[
T_1 = - C_*(p) \sum_{j> j_0} \sum_{m\ge j} p^{j(j-1)/2} q^{j-1} \xi_{m-j+1} p^m n^m
\sum_{r=0}^{k-j} {k-j \choose r} p^{m(k-j-r)} q^{mr}
e^{-n p^{k-j-r} q^r}.
\]
We use now the substitutions $j=j_0 + J$ and $m = j+ L = j_0 + J + L$,
where $J > 0$ and $L\ge 0$. Furthermore by using approximation
${k-j \choose r} \sim (k-j)^r/r! \sim (k-j_0)^r/r!$ we obtain
\begin{eqnarray*}
T_1 &\sim & - C_*(p)  p^{j_0(j_0+1)2} q^{j_0-1} n^{j_0} p^{j_0(k-j_0)}
\sum_{J > 0} \sum_{L\ge 0} p^{J (J+1)/2} q^{J} \xi_{L+1} p^L \\
&&\qquad \times \sum_{r} \frac{ {\overline r_0}^r } {r!}  (q/p)^{(L+J)(r-r_1(j))} e^{-(q/p)^{r-r_1(j)}} \\
&\sim&  - C_*(p)F_0  \cdot\sum_{J > 0} p^{J (J+1)/2} q^{J}
\left( \frac {\overline r_0}{\overline r_1} \right)^{J \frac{\log(1/p)}{\log(p/q)}}
  \sum_{L\ge 0} 	\xi_{L+1} p^L \\
&&\qquad \times
\sum_r (q/p)^{(L+J)(r-r_1(j))} \left( \frac {\overline r_0}{\overline r_1} \right)^{r-r_j(j)}   e^{-(q/p)^{r-r_1(j)}},
\end{eqnarray*}
where $F_0$ is given in (\ref{eqF0-0}).
Thus, if we define (with the implicit notation $q = 1-p$)
\begin{eqnarray}
C_1(p,u,v) &=& \sum_{J > 0} p^{J (J+1)/2} q^{J}
u^{J \frac{\log(1/p)}{\log(p/q)}}
  \sum_{L\ge 0} 	\xi_{L+1} p^L \label{eqC1puv-0}   \\
&&\qquad \times
\sum_{R\in \mathbb{Z}} \left( (q/p)^{(L+J)} u \right)^{R - v -J\frac{\log(1/p)}{\log(p/q)}}   e^{-(q/p)^{R - v -J\frac{\log(1/p)}{\log(p/q)}}}  \nonumber
\end{eqnarray}
we obtain
\[
T_1 \sim - C_*(p)\,F_0\,  C_1\left( p, \frac{\overline r_0}{\overline r_1}, \langle \overline r_1 \rangle \right).
\]
Note that we have substituted $r-r_1(j)$ by
\begin{eqnarray*}
r - r_1(j) &=& (r-\lfloor \overline r_1 \rfloor) - \langle \overline r_1 \rangle  + (\overline r_1 - r_1(j)) \\
&=& R - v - J\frac{\log(1/p)}{\log(p/q)}.
\end{eqnarray*}

Similarly we obtain $T_2 \sim - C_*(p)\,F_0\,  C_2\left( p, \frac{\overline r_0}{\overline r_1}, \langle \overline r_1 \rangle \right)$,
where
\begin{eqnarray}
C_2(p,u,v) &=& \sum_{J \le 0} p^{J (J+1)/2} q^{J}
u^{J \frac{\log(1/p)}{\log(p/q)}}
  \sum_{L> -J} 	\xi_{L+1} p^L \label{eqC2puv-0}   \\
&&\qquad \times
\sum_{R\in \mathbb{Z}} \left( (q/p)^{(L+J)} u \right)^{R - v -J\frac{\log(1/p)}{\log(p/q)}}   e^{-(q/p)^{R - v -J\frac{\log(1/p)}{\log(p/q)}}},  \nonumber
\end{eqnarray}
and
$T_{30} \sim - C_*(p)\,F_0\,  C_{30}\left( p, \frac{\overline r_0}{\overline r_1}, \langle \overline r_1 \rangle \right),$
where
\begin{eqnarray}
C_{30}(p,u,v) &=& \sum_{J \le 0} p^{J (J+1)/2} q^{J}
u^{J \frac{\log(1/p)}{\log(p/q)}}
  \sum_{L=0}^{-J} 	\xi_{L+1} p^L \label{eqC30puv-0}   \\
&&\qquad \times
\sum_{R\in \mathbb{Z}, R - v -J\frac{\log(1/p)}{\log(p/q)}\le 0 }
\left( (q/p)^{(L+J)} u \right)^{R - v -J\frac{\log(1/p)}{\log(p/q)}}   e^{-(q/p)^{R - v -J\frac{\log(1/p)}{\log(p/q)}}},  \nonumber
\end{eqnarray}
and $T_{32} \sim - C_*(p)\,F_0\,  C_{32}\left( p, \frac{\overline r_0}{\overline r_1}, \langle \overline r_1 \rangle \right)$,
where
\begin{eqnarray}
C_{32}(p,u,v) &=& \sum_{J \le 0} p^{J (J+1)/2} q^{J}
u^{J \frac{\log(1/p)}{\log(p/q)}}
  \sum_{L=0}^{-J} 	\xi_{L+1} p^L  \nonumber  \\
&&\qquad \times
\sum_{R\in \mathbb{Z}, R - v -J\frac{\log(1/p)}{\log(p/q)} > 0 }
\left( (q/p)^{(L+J)} u \right)^{R - v -J\frac{\log(1/p)}{\log(p/q)}} \label{eqC32puv-0}  \\
&& \qquad \qquad \times \left(  e^{-(q/p)^{R - v -J\frac{\log(1/p)}{\log(p/q)}}}
- \sum_{\ell=0}^{-J-L} \frac{(-1)^\ell}{\ell!} (q/p)^{(R - v -J\frac{\log(1/p)}{\log(p/q)})\ell}
  \right). \nonumber
\end{eqnarray}

Finally we deal with $T_{31}$.
First of all we regroup the summation by setting $m=j_0-M$, $j=j_0-M-L$, and $\ell = M-K$ which
gives
\begin{eqnarray*}
T_{31} &=& C_*(p) p^{j_0(j_0+1)/2} q^{j_0-1} n^{j_0} p^{j_0(k-j_0)}  \sum_{K\ge 0} \left( \frac qp \right)^{K\overline r_1} \\
&&\times  \sum_{L\ge 0, \, M\ge K} \xi_{L+1}\frac{(-1)^{M-K}}{(M-K)!} p^{((L+M)^2 + L-M)/2-K(L+M)} q^{-L-M} \\
&& \times \quad \sum_{r\le r_1(j_0-M-L)} {k-j_0+M+L \choose r } \left( \frac qp \right)^{(j_0-K)r}.
\end{eqnarray*}
We single out the case $K=0$ (and consider only the sum over $K,M,r$) which
we write as
\begin{eqnarray*}
D(p) C_*(p) \sum_{r\le \overline r_1} {k-j_0+L+M \choose r } \left( \frac qp \right)^{j_0r} + S_0,
\end{eqnarray*}
where $D(p)$ is given by (\ref{eqDefAp}) and
\begin{eqnarray*}
S_0&:=&  - C_*(p)\sum_{L,M \ge 0} \xi_{L+1}\frac{(-1)^{M}}{M!} p^{((L+M)^2 + L-M)/2} q^{-L-M} \\
&& \qquad \times \sum_{r_1(j_0-M-L)< r \le \overline r_1} {k-j_0+L+M \choose r } \left( \frac qp \right)^{j_0r}.
\end{eqnarray*}
Note that
\[
\sum_{r\le \overline r_1} {k-j_0+L+M \choose r } \left( \frac qp \right)^{j_0r}
= e^{\overline r_0} \Phi\left( \frac{\overline r_1 - \overline r_0}{\sqrt{\overline r_0}} \right)
\left( 1 + O\left( \frac{\log\log n}{\log n} (L+M) \right)\right),
\]
where $\Phi$ denotes the distribution function of the normal distribution.

Thus, if we set
\begin{eqnarray*}
S_K&=& C_*(p)p^{j_0(j_0+1)2} q^{j_0-1} n^{j_0} p^{j_0(k-j_0)}   \left( \frac qp \right)^{K\overline r_1} \\
&&\qquad \times  \sum_{L\ge 0, \, M\ge K} \xi_{L+1}\frac{(-1)^{M-K}}{(M-K)!} p^{((L+M)^2 + L-M)/2-K(L+M)} q^{-L-M} \\
&&\qquad \qquad \times \sum_{r\le r_1(j_0-M-L)} {k-j_0+M+L \choose r } \left( \frac qp \right)^{(j_0-K)r}.
\end{eqnarray*}
then we have
\[
T_{31} = D(p) C_*(p) e^{\overline r_0} \Phi\left( \frac{\overline r_1 - \overline r_0}{\sqrt{\overline r_0}} \right) (1+o(1))
-S_0 + \sum_{K\ge 1} S_K.
\]

In the same way as above we obtain
$S_0 \sim - C_*(p)\,F_0\,  C_{31,0}\left( p, \frac{\overline r_0}{\overline r_1}, \langle \overline r_1 \rangle \right)$,
where
\begin{eqnarray}
C_{31,0}(p,u,v) &=&
\sum_{L,M \ge 0} \xi_{L+1}\frac{(-1)^{M}}{M!} p^{((L+M)^2 + L-M)/2} q^{-L-M} \label{eqC310puv-0}     \\
&&\qquad \times
\sum_{-(M+L) \frac{\log(1/p)}{\log(p/q)} +v \le R \le 0 } u^{R-v}.
\nonumber
\end{eqnarray}
It is also convenient to rewrite this also as a sum over $J = -M-L\le 0$ and $0\le L \le -J$:
\begin{eqnarray}
C_{31,0}(p,u,v) &=&
\sum_{J\le 0}\sum_{L=0}^{-J} \xi_{L+1}\frac{(-1)^{-J-L}}{(-J-L)!} p^{ J(J+1)/2 + L} q^{J} \label{eqC310puv-2-0}     \\
&&\qquad \times
\sum_{ J \frac{\log(1/p)}{\log(p/q)} +v \le R \le 0 } u^{R-v}.
\nonumber
\end{eqnarray}
For $K\ge 1$ the terms $S_K$ can be approximated by
$S_K \sim C_*(p)\,F_0\,  C_{31,K}\left( p, \frac{\overline r_0}{\overline r_1}, \langle \overline r_1 \rangle \right)$,
where
\begin{eqnarray}
C_{31,K}(p,u,v) &=&
\sum_{J\le -K} \sum_{L=0}^{-J-K} \xi_{L+1}\frac{(-1)^{-J-L-K}}{(-J-L-K)!} p^{J(J+1)/2 + L +JK} q^{J} \nonumber     \\
&&\qquad \times
\sum_{R\le v+J \frac{\log(1/p)}{\log(p/q)} }
 \left( u \left(\frac qp\right)^{-K} \right)^{R-v}.
\label{eqC31Kpuv-2-0}
\end{eqnarray}

Summing up, if we set
\[
C(p,u,v) = - C_1(p,u,v)-C_2(p,u,v)-C_{30}(p,u,v)-C_{32}(p,u,v)-C_{31,0}(p,u,v)+ \sum_{K\ge 1} C_{31,K}(p,u,v)
\]
and by observing that $D(p) = 0$ (see Section~\ref{secmiracle}) we have:

\begin{lemma}
With the notation from above we have
\[
\tilde G_k(n) =
C_*(p) p^{j_0(j_0+1)/2} q^{j_0-1} n^{j_0} p^{j_0(k-j_0)}  \frac{{\overline r_0}^{\overline r_1}}{\Gamma(\overline r_1+1)}
\left( C(p, \overline r_0/\overline r_1, \langle \overline r \rangle) + o(1)    \right).
\]
\end{lemma}

It remains to show that $C(p,u,v)$ is strictly positive for $\frac 12 < p < 1$, $\sqrt{q/p} \le u \le \sqrt{p/q}$, $0\le v < 1$.
Since the representation of $C(p,u,v)$ is quite involved we will use the following strategy. We do an asymptotic analysis
for $p\to \frac 12$ and $p\to 1$ and fill out the remaining interval, $0.51 \le p \le 0.97$ by a numerical analysis
(together with upper bounds for the derivatives). Due to space limitations we present here only a short version of
the (very involved) considerations. A full version can be found in the appendix.

We start with the behavior for $p\to \frac 12$.
\begin{lemma}\label{Lepto1/2}
Set $p/q = e^{\eta}$ and $\tilde u = \frac 1\eta \log u$.
Then for $\eta \to 0+$ (which is equivalent to $p\to \frac 12$) we have uniformly for $\tilde u \in [-\frac 12, \frac 12]$ and $v\in [0,1)$
\begin{equation}\label{eqLepto1/2}
C(p,u,v) \sim \frac 1\eta h(\tilde u),
\end{equation}
where $h(\tilde u)$ is a continuous and positive function.

In particular we have $C(p,u,v) > 0$ for $\frac 12 < p \le 0.51$.
\end{lemma}

\begin{proof}
We single out the function $C_1(p,u,v)$ and start with the sum over $R$. The first observation is that for $\eta \to 0$ we can replace the
sum by an integral, that is, we have for fixed integers $L,J$, as $\eta\to 0$,
\begin{eqnarray*}
&& \sum_{R\in \mathbb{Z}} \left( (q/p)^{(L+J)} u \right)^{R - v -J\frac{\log(1/p)}{\log(p/q)}}   e^{-(q/p)^{R - v -J\frac{\log(1/p)}{\log(p/q)}}} \\
&&\sim \int_{-\infty}^\infty
\left( (q/p)^{(L+J)} u \right)^{t}   e^{-(q/p)^{t}} \, dt  = \frac 1\eta \int_{-\infty}^\infty e^{-\left(M - \tilde u \right) t} e^{-e^{-t}}\, dt.
\end{eqnarray*}
This also implies that the leading asymptotic term does not depend on $v$.
Further note that $\tilde M = M - \frac 1\eta \log u = L+J - \tilde u \ge \frac 12$ so that the integral converges
and by using the substitution $w = e^{-t}$ we obtain
\[
\int_{-\infty}^\infty e^{-\tilde M t} e^{-e^{-t}}\, dt
= \int_0^\infty w^{\tilde M -1} e^{-w}\, dw = \Gamma(\tilde M).
\]
This finally shows that, as $p\to \frac 12$ (or equivalently as $\eta = \log(p/q) \to 0$),
\begin{equation}\label{eqC1asymp}
C_1(p,u,v) \sim \frac 1\eta
\sum_{J > 0} 2^{-J (J+1)/2 - J + J\tilde u}
  \sum_{L\ge 0} 	\xi_{L+1}(1/2)\, 2^{-L}\, \Gamma\left( J + L - \tilde u\right).
\end{equation}

Similarly we can handle the other terms and obtain the asymptotic representation (\ref{eqLepto1/2}).
Since the function $h(\tilde u)$ is explicit (as a series expansion) and continuously differentiable
in $\tilde u$ we can use a simple numerical analysis (together with upper bounds for the derivative
$h'(\tilde u)$) in order to show that $h(\tilde u) > 0$ for $\tilde u \in [-\frac 12, \frac 12]$.

Finally by taking care also on error terms (which were neglected in the above analysis) it also
follows that $C(p,u,v) > 0$ for $\frac 12 < p \le 0.51$.
\end{proof}

The situation for $p\to 1$ is more delicate in the analysis, however, positivity follows then immediately.
\begin{lemma}\label{Lepto1}
Set $\overline c(v) = \max\{v-v^2/2,(1-v^2)/2\}$. Then we have, as $p\to1$ uniformly
for $\sqrt{q/p} \le u \le \sqrt{p/q}$, $0\le v < 1$
\begin{equation}\label{eqLepto1}
C(p,u,v) \ge \exp\left( \overline c(v) \frac{\log^2 (1-p)}{\log 1/p}(1 + o(1)) \right).
\end{equation}
In particular we have $C(p,u,v) > 0$ for $0.97\le p < 1$.
\end{lemma}

\begin{proof}
We just consider the most interesting case, namely the sum $\sum_{K\ge 1} C_{31,K}(p,u,v)$ and
assume for a moment that $v> 0$. We set
\[
I_0:= \left[ - v\left( \frac{\log q}{\log p}-1\right) , 0 \right) \cap \mathbb{Z}
\]
and for $M\ge 1$
\[
I_M:= \left[ - (v+M)\left(\frac{\log q}{\log p}-1\right) , - (v+M-1)\left(\frac{\log q}{\log p}-1\right) \right) \cap \mathbb{Z}
\]
If $J\in I_M$ we have, as $p\to 1$,
\[
\sum_{R\le v+ J \frac{\log(1/p)}{\log(p/q)}} \left( u (q/p)^{-K} \right)^{R-v} \sim
\left( u (q/p)^{-K} \right)^{-M-v}.
\]
Since
\[
\sum_{L=0}^{-J-K} \xi_{L+1} p^L \frac{(-1)^{-J-K-L}}{(-J-K-L)!} = [z^{-J-K}] \prod_{j\ge 0} \frac{e^{qp^jz} -1}{qp^j z} e^{-z} = [z^{-J-K}] e^{z/2 + O(qz^2) - z}
\]
we get
\begin{eqnarray*}
C_{31,K,M}&:=& \sum_{J\in I_M,\, J \le -K} p^{J(J+1)/2 +JK}q^J  \sum_{R\le v+ J \frac{\log(1/p)}{\log(p/q)} }
 \left( u \left(\frac qp\right)^{-K} \right)^{R-v} \\
&&\qquad \times\sum_{L=0}^{-J-K} \xi_{L+1}p^{L} \frac{(-1)^{-J-L-K}}{(-J-L-K)!}     \\
&\sim &  \sum_{J\in I_M,\, J \le -K}  p^{J(J+1)/2 +JK}q^J
 \left( u \left(\frac qp\right)^{-K} \right)^{-M-v} [z^{-J-K}] e^{z/2 + O(qz^2) - z}
\end{eqnarray*}
and consequently if we sum over $K\ge 1$
\begin{eqnarray*}
\sum_{K\ge 1} C_{31,K,M} &\sim &  u^{-M-v}
\sum_{J\in I_M} p^{J(J+1)/2}q^J \sum_{K=1}^{-J} p^{JK}(q/p)^{K(M+v)} [z^{-J-K}] e^{z/2 + O(qz^2) - z} \\
& =  &  u^{-M-v}
\sum_{J\in I_M} p^{J(J+1)/2}q^J \sum_{K=1}^{-J} p^{JK}(q/p)^{M(1+v)} [z^{-J-K}] e^{z/2 + O(qz^2) - z}.
\end{eqnarray*}
We observe that (for $J\in I_M$)
\begin{eqnarray*}
 &&\sum_{K=1}^{-J} p^{JK}(q/p)^{K(M+v)} [z^{-J-K}] e^{z/2 + O(qz^2) - z}
 = [z^{-J}] \frac{p^{J}(q/p)^{M+v}z}{1- p^{J}(q/p)^{M+v}z } e^{z/2 + O(qz^2) - z} \\
 &&\qquad \sim   p^{-J^2}(q/p)^{-J(M+v)} e^{z_M/2 + O(q z_M^2) - z_M},
\end{eqnarray*}
where $z_M = p^{-J}(q/p)^{-M-v}$. Note that $z_M$ varies between $1$ and $1/q$ if $J\in I_M$.
However, it will turn out that the asymptotic leading terms will come from $J$ close to
$- (v+M)\frac{\log q}{\log p}$ which means that $z_M$ asymptotically $1$ and, thus,  the last
exponential term is asymptotically $e^{-1/2}$. The reason is that the term
\[
p^{J(J+1)/2}q^J p^{-J^2}(q/p)^{-J(M+v)} = p^{-J^2/2} q^{J(1-M-v)} p^{J(\frac 12 +M+v)}
\]
has its absolute minimum for $J$ close to $- (v+M-1)\frac{\log q}{\log p}$ and for $J\in I_M$
it gets maximal for $J$ close to $- (v+M)\frac{\log q}{\log p}$, in particular if
\[
J = J_{v,M} := - \left\lfloor (M+v) \left( \frac{\log q}{\log p} -1 \right) \right\rfloor.
\]
Thus, we obtain
\begin{eqnarray*}
\sum_{K\ge 1} C_{31,K,M} &\sim &  e^{-\frac 12} u^{-M-v} p^{-J_{v,M}^2/2} q^{J_{v,M}(1-M-v)} p^{J_{v,M}(\frac 12 +M+v)} \\
&=& e^{ \frac{\log^2 q}q \left( M+v- \frac 12 (M+v)^2 \right) + O(\log^2 q)  }.
\end{eqnarray*}
Since $(M+v) - \frac 12 (M+v)^2 \le 0$ for $M\ge 2$ (and $0\le v < 1$) it is clear that only the first two
terms corresponding to $M=0$ and $M=1$ are relevant
Hence, we obtain
\[
\sum_{K\ge 1} C_{31,K} \sim
e^{ \frac{\log^2 (1-p)}{\log(1/p)} \left( v- \frac 12 v^2 \right) + O(\log^2 (1-p))  }
+ e^{ \frac{\log^2 (1-p)}{\log(1/p)} \frac 12 \left( 1- v^2  \right) + O(\log^2 (1-p))  }.
\]
Acually this kind of representation also holds for $v= 0$.

The other terms can be handled in a similar way. Actually $C_1,C_2, C_{32}, C_{31,0}$ are of
smaller order, whereas $C_{30}$ has (almost) a comparable order of magnitude.

Finally, by taking error terms into account it follows that $C(p,u,v)$ is positive for
$0.97 \le p < 1$.
\end{proof}

Thus, it remains to consider $C(p,u,v)$ for $0.51 \le p \le 0.97$. As mentioned above we
do here a numerical analysis. For example, for the following sample valued we obtain:

\begin{center}
\begin{tabular}{llll}
\hline
$p$ & $u$ & $v$ & $C(p, u, v)$ \\
\hline
0.51 & 1.00 & 0.20 & 17.6603002053593  \\
0.51 & 1.00 & 0.40 & 17.6630153331822 \\
0.51 & 1.00 & 0.60 & 17.6610407898646 \\
0.51 & 1.00 & 0.80 & 17.6856832509155 \\
0.60 & 0.90 & 0.60 & 1.49524800151569 \\
0.60 & 1.00 & 0.20 & 1.08391296918222 \\
0.60 & 1.00 & 0.60 & 1.08391297098683 \\
0.60 & 1.00 & 0.80 & 1.08391297046200 \\
0.60 & 1.10 & 0.20 & 0.834656789094941 \\
0.60 & 1.20 & 0.60 & 0.673917281982084 \\
0.70 & 1.00 & 0.60 & 0.232497954955319 \\
0.80 & 1.00 & 0.60 & 0.0287161523336721 \\
0.85 & 1.00 & 0.60 & 0.00237172764900606 \\
0.93 & 1.00 & 0.60 & 1.87317294616045 $\times  10^{15}$ \\
0.97 & 0.50 & 0.60 & 9.17733198126610 $\times  10^{72}$ \\
0.97 & 1.00 & 0.60 & 6.05478107453485 $\times 10^{72}$ \\
0.97 & 5.00 & 0.60 & 2.30524156812013 $\times 10^{72}$ \\
\hline
\end{tabular}
\end{center}

A more detailed analysis can be found in the appendix.

\subsection{Proof of Theorem~\ref{FillupTheorem}}
\label{FProof}

The analysis of $F_n$ runs along the same lines as for $H_n$. As already mentioned
we will give only a roadmap of the proof since it is actually much easier than
that of $H_n$.

\subsubsection{Lower bound on $F_n$}

The lower bound on $F_n$ can be proven in two different ways. We can either use
the inverse Mellin transform integral for $\tilde G_k(n)$
\[
k = k_L = \log_{1/q}\log n - (1+\epsilon)\log_{1/q}\log\log n
\]
evaluated at
$\rho = \log_{p/q}\log n$. This leads to ${\rm Pr}[F_n < k] \le \mu_{n,k} \to 0$.

Alternatively we can use the correspondence between the R\'enyi process
and the random PATRICIA trie construction, along with the relationship between PATRICIA tries
and standard tries.  Because of the path compression step in the construction of a PATRICIA trie
from a trie, the fillup level for a PATRICIA trie is always greater than or equal to the fillup
level for the associated trie.  Furthermore, it is known (see \cite{park2008}) that the fillup level
in random tries for $p > 1/2$ is, with high probability,
\begin{eqnarray*}
    \log_{1/q} n - \log_{1/q}\log\log n + o(\log\log\log n).
\end{eqnarray*}
Thus, with high probability, this is also a lower bound for the $F_n$ that we study.

\subsubsection{Upper bound on $F_n$}

The upper bound proof for $F_n$ follows along similar lines to
the lower bound for $H_n$.
We set
\[
    k = k_U = \log_{1/q} n - (1-\epsilon)\log_{1/q}\log\log n,
\]
and our goal is to show that $ {\mathrm{Var}}[B_{n,k}] = o( {\mathbb{E}}[B_{n,k}]^2)$.
First we get an upper bound for $ {\mathrm{Var}}[B_{n,k}]$ in the same way as in the case of $H_n$
(via inverse Mellin transform and Depoissonization) of the form
\[
 {\mathrm{Var}}[B_{n,k}] = O\left(q^{-\epsilon \log_{p/q}\log n \cdot \log{1/q} \log\log n (1 + o(1))}\right).
\]

In order to obtain a corresponding lower bound for $\mu_{n,k} = {\mathbb{E}}[B_{n,k}]$ we
use again the explicit representation
\begin{equation}
    \label{PoGkFillupExpression}
    \Po{G}_k(n) = \sum_{j = 0}^k \sum_{m \geq j} \kappa_{m,j} (\mu_{m,j} - \mu_{m,j-1}),
\end{equation}
where
\begin{eqnarray}
    \kappa_{m,j}
    &=& \frac{T(-m)n^m}{m!} \sum_{\ell=0}^\infty \frac{(-n)^{\ell}}{\ell!} T(-m-\ell)^{k-j} \nonumber \\
    &=& \frac{T(-m)}{m!} \sum_{r=0}^{k-j} { {k-j}\choose r} (np^r q^{k-j-r})^m \exp(-np^r q^{k-j-r}). \label{eqkapparep2}
\end{eqnarray}
We note that, because $\rho > 0$, there are no contributions from poles, so that the $\ell$-sum begins with $0$, in
contrast to (\ref{eqkapparep}) which leads to the simplified form (\ref{eqkapparep2}).

Our derivation suggests that the main contribution to (\ref{PoGkFillupExpression}) comes from the terms $j = O(1)$ and $m = \rho \cdot p/q + O(1)$.  In this range,
the difference $\mu_{m,j} - \mu_{m,j-1}$ is estimable by the following
lemma from \cite{magnerknesslszpa2014} (see part (i) of Theorem 2.2 of
that paper).
\begin{lemma}[Precise asymptotics for $\mu_{m,j}$ when $j = O(1)$ and $m\to\infty$]
    \label{MuJO1Lemma}
    For $p > q$, $m \to \infty$, and $j = O(1)$, we have
    \[
        \mu_{m,j} \sim mq^j (1 - q^j)^{m-1}.
    \]
\end{lemma}
Note, in particular, that $\mu_{m,j} - \mu_{m,j-1}$ is strictly positive in this range.  Applying this lemma, some algebra is required to
show that the contribution of the $(m,j)$th term, with $m = \rho \cdot p/q + O(1)$ and $j = O(1)$, is
\begin{equation}
    \label{DominantTermFillup}
    q^{-\epsilon \log_{p/q}\log n \cdot \log_{1/q}\log\log n (1 + o(1))}.
\end{equation}
To complete the necessary lower bound on the entire sum (\ref{PoGkFillupExpression}), we consider also the following sums:
\begin{eqnarray}
    \sum_{j=0}^{j'}\sum_{m = j}^{m'} \kappa_{m,j} (\mu_{m,j} - \mu_{m,j-1}) \quad\mbox{and}\quad
    \sum_{j > j'}\sum_{m \geq j} \kappa_{m,j} (\mu_{m,j} - \mu_{m,j-1}),
\end{eqnarray}
where $j'$ and $m'$ are sufficiently large fixed positive numbers.  We note that the terms that are not covered by any of these
sums may be disregarded, since by Lemma~\ref{MuJO1Lemma} they are non-negative.

It may be shown that both sums are smaller than the dominant term (\ref{DominantTermFillup}) by a factor of $e^{-\Theta(\rho)}$,
both by upper bounding terms in absolute value and using the trivial bound $|\mu_{m,j} - \mu_{m,j-1}| \leq 2m$.

We thus arrive at
\begin{equation}\label{eqmunkfilluplevel}
\mu_{n,k} \ge  q^{-\epsilon \log_{p/q}\log n \cdot\log_{1/q}\log\log n (1 + o(1)}.
\end{equation}
Since this tends to $\infty$ with $n$, combining this with the upper bound for the variance
yields the desired upper bound on $\Pr[F_n > k]$, which establishes the upper bound on $F_n$.

\section{Depoissonization}\label{sec:depo}

\subsection{Analytic Depoissonization}

The Poisson transform $\tilde G(z)$ of a sequence
$g_n$ is defined by $\tilde G(z) = \sum_{n\ge 0} g_n \frac{z^n}{n!} e^{-z}$.
If the sequence $g_n$ is {\it smooth enough} then we usually have
$g_n \sim \tilde G(n)$ (as $n\to\infty$) which we call {\it Depoissonization}.
In \cite{jacquetszpa1997} a theory for {\it Analytic Depoissonization} is developed. For example,
the basic theorem (Theorem 1) says that if
\begin{eqnarray}\label{eqDep1}
|\tilde G(z)| \le B |z|^\beta
\end{eqnarray}
for $|z|> R$ and $|\arg(z)| \le \theta$ (for some $B> 0$, $R>0$, and $0< \theta < \pi/2$)
and
\begin{eqnarray}\label{eqDep2}
|\tilde G(z)e^z| \le A e^{\alpha|z|}
\end{eqnarray}
for $|z|> R$ and $\theta <|\arg(z)| \le \pi$ (for some $A> 0$ and $\alpha < 1$) then
\begin{eqnarray}\label{eqDep3}
g_n = \tilde G(n) + O(n^{\beta-1}).
\end{eqnarray}
Actually this expansion can be made
more precise by taking into account derivatives of $\tilde G(z)$.
For example, we have
\begin{eqnarray}\label{eqDep3.2}
g_n = \tilde G(n) - \frac n2 \tilde G''(n)+  O(n^{\beta-2}).
\end{eqnarray}

In \cite[Lemmas 1 and 18]{magnerspa2015} it is shown that $\tilde G_k(z) = \sum_{n\ge 0} \mu_{n,k} \frac{z^n}{n!} e^{-z}$
satisfies (\ref{eqDep1}) with $\beta = 1+ \epsilon$ for any $\epsilon> 0$ and
(\ref{eqDep2}) for some $\alpha < 1$ uniformly for
all $k\ge 0$. Thus, it follows uniformly for all $k\ge 0$
\begin{eqnarray}\label{eqDep3.3}
\mu_{n,k} = \tilde G_k(n)  - \frac n2 \tilde G_k''(n)+  O(n^{\epsilon-1}).
\end{eqnarray}
The estimate (\ref {eqDep3}) is not sufficient for our purposes
(it only works if $\mu_{n,k}$ grows at least polynomially as in the
{\it central range}). For the boundary region, where
$k \sim \log_{1/p} n$ or $k \sim \log_{1/q} n$ we have to use (\ref{eqDep3.3}) which means
that we have to deal with
derivatives of $\tilde G_k(z)$, too.

\subsection{Poisson Variance}

Next we discuss how the variance of a random variable can be handled with the help
of the Poisson transform. First we assume that $\tilde G(z)$ is the Poisson transform
of the expected values $\mu_n =  {\mathbb{E}}[X_n]$ or a sequence of random variables.
Furthermore we set
\[
\tilde V(z) = \sum_{n\ge 0}  {\mathbb{E}}[X_n^2]  \frac{z^n}{n!} e^{-z} - \tilde G(z)^2
\]
which we denote the Poisson variance. This is not the Poisson transform of the variance.
However, since we usually have $ {\mathbb{E}}[X_n^2] \sim V(n) + G(n)^2$ and $ {\mathbb{E}}[X_n] \sim G(n)$
it is expected that $ {\mathrm{Var}}[X_n] \sim V(n)$. Actually this can be made precise with the
help of (\ref{eqDep3.2}). Suppose that $\tilde G(z)$ and  $\tilde V(z)$ satisfy the
property (\ref{eqDep1}) and that $\tilde G(z)$ and  $\tilde V(z) + \tilde G(z)^2$ the
property (\ref{eqDep2}). Then it follows that
\[
 {\mathbb{E}}[X_n] = \tilde G(n) - \frac n2 \tilde G''(n)+  O(n^{\beta-2})
\]
and
\[
 {\mathbb{E}}[X_n^2] = \tilde V(n) + \tilde G(n)^2 - \frac n2 \tilde V''(n)
- n (\tilde G'(n))^2 - n \tilde G(n)\tilde G''(n) +  O(n^{\beta-2})
\]
from which it follows that
\begin{eqnarray}
 {\mathrm{Var}}[X_n] &= \tilde V(n) - \frac n2 \tilde V''(n) - n (\tilde G'(n))^2 +
\frac 14 n^2  (\tilde G''(n))^2 \nonumber \\
&+ O(n^{2\beta -4}) +  O( n^{\beta-2} \tilde G(n)) +  O( n^{\beta} \tilde G''(n)).
\label{eqVarest}
\end{eqnarray}
In particular in our case we know that the Poisson transform
$\tilde G_k(z)$ (of the sequence $\mu_{n,k} =  {\mathbb{E}}[B_{n,k}]$) and the
corresponding Poisson variance $\tilde V_k(z)$ satisfy the assumptions
for $\beta =1 + \epsilon$ (for every fixed $\epsilon> 0$), see
\cite{magnerspa2015}. Thus we also obtain (\ref{eqVarest}) in the
present context.

\section{An Unexpected Identity}\label{secmiracle}

In this final section we prove that $D(p) = 0$ which seems to be a new
(and unexpected) identity.\footnote{The following simple proof is due to
Gleb Pogudin (Univ. Linz).}

\begin{lemma}\label{LeDp=0}
Suppose that $|p|<1$ and $q = 1-p$ and set
\begin{eqnarray} \label{eqDefAp-0}
D(p) = \sum_{L,M \ge 0} \xi_{L+1}\frac{(-1)^{M}}{M!} p^{((L+M)^2 + L-M)/2} q^{-L-M},
\end{eqnarray}
where $\xi_{\ell} = \xi_\ell(p)$ is recursively defined by $\xi_1 = 1$ and
    \begin{equation}\label{eqexrec2-0}
      \xi_\ell
        = q^{-1}p^{\ell} \sum_{J=1}^\ell \frac{\xi_{\ell+1-J}}{J!} (q/p)^{J}.
     \end{equation}
Then
\begin{equation}\label{eqLeDp=0}
D(p) =  0.
\end{equation}
\end{lemma}

\begin{proof}
By setting $L+M = n$ then we can rewrite $D(p)$ as
\[
D(p) = \sum_{n\ge 0} p^{ n\choose 2} \sum_{L=0}^{n} \xi_{L+1} (p/q)^L \frac{(-1)^{(n-L)}}{(n-L)!} q^{-(n-L)}.
\]
Since the recurrence (\ref{eqexrec2-0}) for $\xi_\ell$ can be rewritten to
\[
X(z) = \sum_{L\ge 0} \xi_{L+1} z^L = \prod_{j\ge 0} \frac{e^{qp^j z} -1 }{qp^j z}
\]
we thus obtain
\[
D(p) = \sum_{n\ge 0} p^{ n\choose 2} [z^n] X((p/q)z) e^{-z/q} =
\sum_{n\ge 0} p^{ n\choose 2} [z^n] \prod_{j\ge 0} \frac{e^{(p-1)p^j z} - e^{-p^j z }}{p^{j+1} z}.
\]
Hence, if we set $f(z) = \frac 1{pz} \left( e^{(p-1)z} - e^{-z} \right)$,
$F(z) = f(z) f(pz) f(p^2z)\cdots$,  and $F_n = [z^n] F(z)$
then $D(p) = 0$ is equivalent to $\sum_{n\ge 0} F_n p^{n\choose 2} = 0$.

We next set $g(z) = e^{-z}$, $h(z) = (e^z-1)/z$, and $q(z) = (1-e^{-z})/z$. Then
we have $f(z) = g(z)h(pz)$ and $q(z) = g(z)h(z)$ which implies the representation
\[
F(z) = \prod_{j\ge 0} g(p^j z) h(p^{j+1} z) = g(z) \prod_{j\ge 1} g(p^j z) h(p^{j} z) = g(z) \prod_{j\ge 1} q(p^j z).
\]
Hence, if we set  $Q(z) = q(z) q(pz) q(p^2z)\cdots$,  and $Q_n = [z^n] Q(z)$ then we also have
\[
F(z) = g(z) Q(pz) = (1-zq(z)) Q(pz) = Q(pz) - z Q(z) = \sum_{n\ge 0} Q_n(p^n z - z^{n+1}).
\]
So, finally, if we use the substitution $z^n \mapsto p^{n\choose 2}$ and the property ${ n+1 \choose 2} = {n\choose 2} + n$,
we immediately see that every summand vanishes. This proves $D(p) = 0$.
\end{proof}

\section{Appendix}
\section{Extension of Lemma~\ref{KnesslLemma}}
\label{KnesslLemmaProof}

We prove here an extended version of Lemma~\ref{KnesslLemma}
and provide a more detailed analysis of the quantities $\xi_{\ell}(n)$ and $\xi_\ell$.

\begin{lemma}
    \label{KnesslLemma1}
    \label{KNESSLLEMMA1}
    \label{mu_mjUpperBoundLemma1}
    Let $p \geq q$.
    For $n\to\infty$ and $1\le k < n$ with $\log^2 (n-k) = o(k)$,
$$
        \mu_{n,k}
        = (n-k)^{3/2 + \frac{\log q}{\log p}}
\frac{n!}{(n-k)!}p^{k^2/2 + k/2}q^{k} \cdot
\exp\left( -\frac{\log^2(n-k)}{2\log(1/p)} \right)\Theta(1).
$$
\end{lemma}

    We first work out the case $p> q$. The case $p=q = \frac 12$ is slightly easier and
    will be discussed below.

    We recall the definition of the quantity
$
        S_\ell(n) = \mu_{n,n-\ell}.
$

With this notation the quantities $\xi_\ell(n)$ are defined by
    \begin{equation}
        S_\ell(n) = n! C_*(p) p^{(n-\ell)^2/2 + (n-\ell)/2}q^{n-\ell} \xi_{\ell}(n).
        \label{S_ellDefinition}
    \end{equation}
where
$$
        C_*(p) = \prod_{j=2}^\infty (1-p^j - q^j)^{-1} \cdot (1 + (q/p)^{j-2}).
$$
By defintion and simple computation
 we have $\xi_{1}(n) \sim 1$ and $\xi_{2}(n) \sim 1/2$.

    Our task now is to determine the asymptotic behavior of
$\xi_{\ell}(n)$ as $\ell\to\infty$.  From the recurrence (\ref{muRecurrence})
for $\mu_{n,k}$, we can derive a corresponding one for $\xi_\ell(n)$:
    \begin{equation}
        \xi_{\ell}(n)(1-p^n-q^n) =
     \sum_{J=1}^\ell \frac{\xi_{\ell+1-J}(n-J)}{J!}q^{-1}p^{\ell-n}(p^{n-J}q^{J}
+ p^{J}q^{n-J}).
    \label{eqxielln-rec}
    \end{equation}
    Note that this recurrence uniquely defines $\xi_\ell(n)$ given
$\xi_1(1) = 1/C_*(p)$.  First the recurrence provides $\xi_1(n)$ for all $n\ge 2$.
Then we get $\xi_2(3)$  (recall that $\xi_2(1) = \xi_2(2) = 0$)
and recursively $\xi_2(n)$ for $n\ge 4$; etc.

    From this recurrence it follows immediatly that for each $\ell\ge 1$ the limit
    $\xi_\ell = \lim_{n\to\infty} \xi_\ell(n)$
    exists. Clearly this limits satisfy the recurrence
$$
        \xi_\ell
        = q^{-1}p^{\ell} \sum_{J=1}^\ell \frac{\xi_{\ell+1-J}}{J!} (q/p)^{J}
$$
    which we will analyze separately in the sequel.

\subsection{A-priori bounds for $\xi_\ell(n)$}

    We will first prove an a-priori bound for $\xi_\ell(n)$ and also an error bound for
    the difference $\xi_\ell(n) - \xi_\ell$:
    \begin{equation}
    \xi_\ell(n) = O\left( \frac 1{\ell !} \right), \qquad
    \xi_\ell(n) = \xi_\ell + O\left( \frac{p^{n-\ell} +
(q/p)^{n-\ell}}{(\ell-1)!} \right),
    \label{eqxielln-est}
    \end{equation}
    where the implied constants depend on $p$.
    Both inequalities can be shown by induction by applying it recursively to
    (\ref{eqxielln-rec}). Note first that (\ref{eqxielln-rec}) is only relevant
    for $n> \ell$ since $\xi_\ell(n) = 0$ for $n\le \ell$.

    We choose $\ell_0 \ge 1$ in a way that
\[
\frac{p^{\ell_0}/q(e^{q/p}-1) + (q/p)^{\ell_0}/q(e^{p/q}-1)}{1-p^{\ell_0}-q^{\ell_0}}
\le 1.
\]
and let $C_0$ be an upper bound for $\xi_\ell(n)$ for $\ell < \ell_0$ and
all $n \ge 1$.  Then it follows by induction that $\xi_\ell(n) \le C_0$
for all $\ell \ge 1$ and $n\ge 1$.
We just have to observe that for $n> \ell \ge \ell_0$
\begin{eqnarray*}
\xi_\ell(n) &\le& \frac{C_0}{1-p^n-q^n} \left( \sum_{J=1}^{\ell}
\frac{p^{\ell-J}q^{J-1}}{J!} +
\sum_{J=1}^{\ell} \frac{p^{\ell+J-n}q^{n-J-1}}{J!}  \right) \\
&\le & \frac{C_0}{1-p^n-q^n} \left( \frac{p^\ell}q (e^{q/p}-1) +
\frac 1q \left( \frac qp \right)^n  (e^{p/q}-1) \right) \\
&\le & \frac{C_0}{1-p^{\ell_0}-q^{\ell_0}} \left( \frac{p^{\ell_0}}q (e^{q/p}-1) +
\frac 1q\left( \frac qp \right)^{\ell_0}  (e^{p/q}-1) \right) \\
&\le C_0.
\end{eqnarray*}

Next we prove the first inequality of (\ref{eqxielln-est}).
Here we fix $\ell_1$ in a way that
\[
\frac 1{(\ell_1+1)(1-p^{\ell_1}-q^{\ell_1})} \left( \frac 1{pq} +
\frac 1{q^2} \right) \le 1
\]
and set $C_1 = C_0 \ell_1!$. Then we automatically have
$\xi_\ell(n) \le C_1/\ell!$ for $\ell \le \ell_1$ and
$n\ge 1$.  Furthermore we obtain by induction for $n>\ell > \ell_1$
\begin{eqnarray*}
\xi_\ell(n) &\le& \frac{C_1}{1-p^n-q^n} \left( \sum_{J=1}^{\ell}
\frac{p^{\ell-J}q^{J-1}}{J!(\ell+1-J)!} +
\sum_{J=1}^{\ell} \frac{p^{\ell+J-n}q^{n-J-1}}{J!(\ell+1-J)!}  \right) \\
&\le & \frac{C_1}{(\ell+1)!(1-p^n-q^n)} \\
&\times &\left( \frac 1{pq} \sum_{J=0}^{\ell+1}
{\ell+1 \choose J} p^{\ell+1-J}q^{J} + \frac{(q/p)^{n-\ell}}{q^2}
\sum_{J=0}^{\ell+1}   {\ell+1 \choose J} p^{J}q^{\ell+1-J}  \right) \\
&\le & \frac{C_1}{\ell!} \frac 1{(\ell_1+1)(1-p^{\ell_1}-q^{\ell_1})}
\left( \frac 1{pq} + \frac{1}{q^2} \right) \\
&\le & \frac{C_1}{\ell!}.
\end{eqnarray*}

Finally we deal with the second inequality of (\ref{eqxielln-est}).
Since
\[
\xi_1(n) = \prod_{j> n} \frac{1-p^j-q^j}{1 + (q/p)^{j-2}}
\]
it is certainly true for $\ell =1$. Now it is an easy exercise to verify it
for $\ell=2$, $\ell = 3$ etc.
by adapting possibly the implicit constant for each $\ell$.
For sufficiently large $\ell \ge \ell_2$ we can do a common inductive step
because of the following calculations:
\begin{eqnarray*}
&&|\xi_\ell(n) - \xi_\ell| \\
&\le &
\left| \frac 1{1-p^n-q^n}\sum_{J=1}^\ell \frac{\xi_{\ell+1-J}(n-J)}{J!}q^{-1}
p^{\ell-n}(p^{n-J}q^{J} + p^{J}q^{n-J})
- q^{-1}p^{\ell} \sum_{J=1}^\ell \frac{\xi_{\ell+1-J}}{J!} (q/p)^{J}  \right| \\
&\le& \left| \frac 1{1-p^n-q^n}\sum_{J=1}^\ell \frac{|\xi_{\ell+1-J}(n-J)-
\xi_{\ell+1-J}|}{J!}q^{-1}p^{\ell-n}(p^{n-J}q^{J} + p^{J}q^{n-J}) \right| \\
&+& \left| \frac 1{1-p^n-q^n}\sum_{J=1}^\ell \frac{\xi_{\ell+1-J}}{J!}p^{\ell-J}q^{J-1}
- \sum_{J=1}^\ell \frac{\xi_{\ell+1-J}}{J!} p^{\ell-J}q^{J-1}   \right| \\
&+& \left| \frac 1{1-p^n-q^n}\sum_{J=1}^\ell
\frac{\xi_{\ell+1-J}}{J!}p^{J+\ell-n}q^{n-J-1} \right| \\
 &=& D_1 + D_2 + D_3.
\end{eqnarray*}
By assumption  we have
\[
|\xi_{\ell+1-J}(n-J)-\xi_{\ell+1-J}| \le C(p^{n-\ell-1} + (q/p)^{n-\ell-1})/(\ell-J)!,
\]
where we can assume without loss of generality that $C\ge 1$.
So we can estimate $D_1$ by
\begin{eqnarray*}
D_1 &\le&  \frac C{1-p^n-q^n}\sum_{J=1}^\ell \frac{p^{n-\ell-1} +
(q/p)^{n-\ell-1}}{J!(\ell-J)!}q^{-1}p^{\ell-n}(p^{n-J}q^{J} + p^{J}q^{n-J}) \\
&\le & \frac C{\ell!(1-p^n-q^n)} \left( \frac{p^{n-\ell}}{pq} +
\frac{p(q/p)^{n-\ell}}{q^2} \right)
\left(  1  + (q/p)^{n-\ell} \right) \\
&\le& \frac{C p^{n-\ell}}{(\ell-1)!} \frac 2{pq(1-p^n-q^n)\ell} +
\frac{C (q/p)^{n-\ell}}{(\ell-1)!} \frac {2p}{q^2(1-p^n-q^n)\ell}.
\end{eqnarray*}
Furthermore by using the inequality $\xi_\ell \le C_1/\ell!$ and
the assumption $C\ge 1$ we obtain
$$
D_2 = \frac{p^n+q^n}{1-p^n-q^n} \xi_\ell
\le \frac{C p^{n-\ell}}{(\ell-1)!} \frac {2C_1}{(1-p^n-q^n)\ell}
$$
and
\begin{eqnarray*}
D_3 &\le& \frac {C_1}{1-p^n-q^n} \sum_{J=1}^\ell
\frac{p^{-n} q^{n-1} }{J!(\ell-J)!} p^J q^{\ell-J} \\
&\le& {C_1 (q/p)^n}{\ell! q(1-p^n-q^n)} \\
&\le & \frac{C (q/p)^{n-\ell}}{(\ell-1)!} \frac {C_1}{q(1-p^n-q^n)\ell}.
\end{eqnarray*}
Hence, if $\ell \ge l_2$, where $\ell_2$ satisfies
\[
\frac 1{\ell_2(1-p^{\ell_2}-q^{\ell_2})} \left( \frac 2{pq} + 2C_1 \right) \le 1
\]
and
\[
\frac 1{\ell_2(1-p^{\ell_2}-q^{\ell_2})} \left( \frac {2p}{q^2} +
\frac{C_1}q \right) \le 1 ,
\]
we obtain the second inequality of (\ref{eqxielln-est})
for all $\ell\ge 1$ and $n\ge 1$.

\subsection{Asymptotics for $\xi_\ell$}

    In order to obtain asymptotics for $\xi_\ell$ we use the
Poisson transform of $\ell! \xi_{\ell}$
(\emph{not} of $\xi_{\ell}$), which we denote by
    $\Po{\xi}(z)$.  The functional equation is

$$
        \Po{\xi}(z) = \Po{\xi}(pz) \frac{1-e^{-qz}}{pqz}.
$$
    This may be iterated and  produces the explicit formula
    \begin{equation}
        \Po{\xi}(z) = z\prod_{j=0}^\infty \left( \frac{1 - e^{-qp^jz}}{qp^jz} \right),
        \label{PoXiFormula}
    \end{equation}
    which also shows that $\Po{\xi}(z)$ is entire.  Cauchy's integral formula then gives
$$
        \ell!\cdot \xi_{\ell}
        = \frac{1}{2\pi i} \oint_{\mathcal{C}} \frac{e^{z}}{z^\ell}
\prod_{j=0}^\infty \left( \frac{1 - e^{-qp^jz}}{qp^jz} \right)\dee{z},
$$
    for a simple, closed contour $\mathcal{C}$ encircling the origin.
Actually we use the circle contour $|z| = \ell$.
    It follows then in precisely the same way as in
\cite{jacquetszpa1997} that for $\ell \to \infty$,
    \begin{equation}
        \xi_{\ell}
        \sim \frac{\Po{\xi}(\ell)}{\ell!} = \frac{1}{(\ell-1)!}
        \exp\left[ \sum_{j=0}^\infty
\log\left( \frac{1-e^{-qp^j\ell}}{qp^j\ell} \right) \right].
        \label{sum1}
    \end{equation}

    Our next task is to justify the this step which can be seen
as a depoissonization step.  Let us first study the asymptotic
behavior of $\Po{\xi}(\ell)$

   We reindex the sum by setting $j = \floor{\log_{1/p} \ell} + J$, so
that, for a fixed $J$, $p^j\ell = O(1)$ as $\ell\to\infty$.
    Then $j = \log_{1/p}\ell + J - \fracpart{\log_{1/p}(\ell)}$,
where $\fracpart{x}$ denotes the fractional
    part of $x$.  Defining $\alpha_{\ell} = \fracpart{\log_{1/p}\ell}$, we get
$$
              \Po{\xi}(\ell)= \ell \exp\left[
            \sum_{J=-\floor{\log_{1/p}\ell}}^{\infty}
\log\left( \frac{1-e^{-qp^Jp^{-\alpha_\ell}}}{qp^Jp^{-\alpha_\ell}} \right).
        \right]
$$

    The sum then becomes
    \begin{eqnarray}
        &&\sum_{J=-\floor{\log_{1/p}\ell}}^{\infty}
\log\left( \frac{1-e^{-qp^Jp^{-\alpha_\ell}}}{qp^Jp^{-\alpha_\ell}} \right)
        =  \nonumber \\
        &&\sum_{J=0}^\infty \log \left(
\frac{1-e^{-qp^Jp^{-\alpha_\ell}}}{qp^Jp^{-\alpha_\ell}} \right)
        + \sum_{J=1}^\floor{\log_{1/p} \ell} \left[
\log(1-e^{-qp^{-J}p^{-\alpha_\ell}}) - \log q + \alpha_\ell \log p +
J\log p \right] \nonumber \\
        &\sim& \floor{\log_{1/p} \ell}[\alpha_\ell \log p - \log q] +
\floor{\log_{1/p} \ell} (\floor{\log_{1/p}\ell} + 1)
\frac{1}{2} \log p \label{nonSummation} \\
        &+& \sum_{J=1}^\infty \log(1-e^{-qp^{-J}p^{-\alpha_\ell}}) +
\sum_{J=0}^\infty \log \left( \frac{1-e^{-qp^Jp^{-\alpha_\ell}}}{qp^Jp^{-\alpha_\ell}}
\right). \nonumber
    \end{eqnarray}
    The expression (\ref{nonSummation}) can be rewritten as
    \begin{eqnarray*}
        &&(\log_{1/p} \ell - \alpha_\ell)(\alpha_\ell \log p - \log q) +
\frac{1}{2}\log p(\log_{1/p} \ell - \alpha_\ell) (\log_{1/p} \ell + 1 - \alpha_\ell) \\
        &=& \frac{1}{2}(\log_{1/p} \ell)^2 \log p + (\log_{1/p} \ell)
(-\log q + \frac{1}{2}\log p) - \alpha^2_\ell \log p \\
&+& \frac{1}{2}(\log p)\alpha_\ell(\alpha_\ell - 1)
        + \alpha_\ell \log q,
    \end{eqnarray*}
    so that, finally,
         \begin{eqnarray*}
        \Po{\xi}(\ell)& =& \ell \prod_{J=0}^\infty \left(
\frac{1 - e^{-qp^Jp^{-\alpha_\ell}}}{qp^Jp^{-\alpha_\ell}} \right)
        \prod_{J=1}^\infty (1-e^{-qp^{-J}p^{-\alpha_\ell}}) \\
        & &\qquad \times \exp\left[ -\frac{\log^2 \ell}{2\log(1/p)} \right]
\ell^{1/2+\log q / \log p}
        \exp\left[-\frac{\alpha_\ell(\alpha_\ell + 1)}{2}\log p \right]
e^{-\alpha_\ell \log q} \\
        &=&  \ell^{3/2+\log q / \log p} \exp\left[ -\frac{\log^2 \ell}{2\log(1/p)}
\right] \Theta(1).
    \end{eqnarray*}

It remains to check proper growth conditions on $\Po{\xi}(z)$ which can be directly
used to justify the depoissonization step. Actually we show that we have similiar
properties as (\ref{eqDep1}) and (\ref{eqDep2}). First we show that
\begin{equation}\label{eqDep1-new}
\Po{\xi}(z) = O\left(  |z|^{3/2+\log q / \log p}
        \exp\left[ -\frac{\log^2 |z|}{2\log(1/p)} \right] \right)
\end{equation}
uniformly for $\Re(z) \ge \eta$, where $\eta> 0$ is fixed.
We set $j' = \lfloor \log |z|/\log(1/p) \rfloor$. Since
$(1- e^{-w})/w = 1 + O(w)$ it directly follows that
\[
\prod_{j=j'+1}^{\infty} \left( \frac{1 - e^{-qp^jz}}{qp^jz} \right) = O(1).
\]
Furthermore, if $\Re(z) \ge \eta$ it follows that
$|1 - e^{-qp^jz}| \le 1 + e^{-qp^j \eta}$ which implies that
$\prod_{j=0}^{j'} \left( {1 - e^{-qp^jz}} \right) = O(1)$.
Hence we obtain (\ref{eqDep1-new})).
\[
\Po{\xi}(z) = O\left( |z|\, q^{-j'-1} p^{-j'(j'+1)/2} |z|^{-j'}\right)
= O\left(  |z|^{3/2+\log q / \log p}
        exp\left[ -\frac{\log^2 |z|}{2\log(1/p)} \right]   \right).
\]
It also follows (by considering Cauchy's formula as in \cite{jacquetszpa1997}) that
all derivatives have similar extimates:
\begin{equation}\label{eqDep1-new-der}
\Po{\xi}^{(k)}(z) = O\left( k! |z|^{3/2+\log q / \log p-k}
        \exp\left[ -\frac{\log^2 |z|}{2\log(1/p)} \right] \right)
\end{equation}
uniformly for $\Re(z) \ge \eta$.

It remains to prove a condition of the form (\ref{eqDep2}):
    \begin{equation}\label{eqDep2-new}
        |e^{z}\Po{\xi}(z)|
        \leq Ce^{\alpha|z|},
    \end{equation}
    for some positive constants $C$ and $\alpha$ with
$\alpha < 1$, for $\theta\le |\mathrm{Arg}(z)| \le \pi$
    We will choose $\theta$ such that $\cos(\theta) < 1/2$.
    which we require in order to prove the desired bound for
$z$ outside the cone but with $\Re(z) > 0$.
This can be proved following the steps of \cite{magnerspa2015}, and we leave
details for the reader.`

\begin{comment}
    Then the product in (\ref{PoXiFormula}) is bounded as follows:
we first split it exactly as above, with the same choice of $j'$
    The bounding of the final product is then exactly as before,
yielding a factor of $O(1)$.
    The initial product may be estimated as follows:
    \begin{eqnarray*}
        \left|\prod_{j=0}^{j'} \left( \frac{1 - e^{-qp^j z}}{qp^jz} \right)\right|
        &=& O(1) \left| \prod_{j=0}^{j'} (1 - e^{-qp^j z}) \right|  \\
        &\leq& O(1) \prod_{j=0}^{j'} (e^{qp^j |\Re(z)|} + 1)        \\
        &\leq& O(1)2^{j'} \prod_{j=0}^{j'} e^{qp^j |\Re(z)|} \\
        &<& O(1)2^{j'} \exp\left( q|\Re(z)| \sum_{j=0}^\infty p^j \right) \\
        &=& O(1)2^{j'} e^{|\Re(z)|}.
    \end{eqnarray*}
    Here, the first equality follows by bounding the denominator,
taking into account our choice of $j'$.  The first inequality is by the
triangle inequality and upper bounding $-\Re(z) \leq |\Re(z)|$.  The
    second inequality is from noting that $1 \leq e^{qp^j |\Re(z)|}$,
then taking the resulting factor of $2^{j'+1}$ out of the product.
The third inequality is by extending the sum in the exponent to infinity,
    and the final equality is using the fact that $\sum_{j=0}^\infty p^j = 1/(1-p)= 1/q$.

    This upper bound gives us a bound of
$$
        |e^z||\Po{\xi}(z)|
        = e^{\Re(z)} |\Po{\xi}(z)|
        \leq O(1)|z| 2^{j'} e^{\Re(z) + |\Re(z)|}.
$$
    Now, if $\Re(z) < 0$, then the exponent becomes exactly $0$.
If, on the other hand, $\Re(z) > 0$, then we note that
$$
        \Re(z) + |\Re(z)| = 2\Re(z) = 2\cos(\mathrm{Arg}(z))|z|
        \leq 2\cos(\theta)|z|
        < \alpha'|z|,
$$
    for some $\alpha' < 1$.  Here, the final inequality is by our
choice of $\theta$ so that $\cos(\theta) < 1/2$.
    By our choice of $j'$, $2^{j'}$ is of at most polynomial growth
with respect to $|z|$, so that we may choose
    $\alpha \in (\alpha', 1)$ for which
$$
        |e^{z}\Po{\xi}(z)|
        \leq O(1)e^{\alpha|z|},
$$
    as desired.
\end{comment}

Finally by using (\ref{eqDep1-new}) and (\ref{eqDep2-new})
together with the method used in
\cite{jacquetszpa1997} we obtain that
\begin{eqnarray*}
\ell! \xi_\ell &=& \Po{\xi}(\ell) +
O\left(  \ell^{1/2+\log q / \log p}
        \exp\left[ -\frac{\log^2 \ell}{2\log(1/p)} \right] \right) \\
        &= &\Po{\xi}(\ell) \left( 1 + O(\ell^{-1}) \right).
\end{eqnarray*}
This completes the depoissonization proof for $\Po{\xi}(z)$.

Summing up we obtain
\begin{eqnarray*}
\xi_\ell(n) &= &\frac{\Po{\xi}(\ell)}{\ell!}  \left( 1 + O(\ell^{-1}) \right)+
O\left( \frac{p^{n-\ell} + (q/p)^{n-\ell}}{(\ell-1)!} \right) \\
&=& \frac{\Po{\xi}(\ell)}{\ell!} \Theta(1)
\end{eqnarray*}
if $\log^2 \ell = o(n-\ell)$.
Hence, plugging this into (\ref{S_ellDefinition}) and setting $k=n-\ell$, we arrive at
    \begin{eqnarray*}
        \mu_{n,k} =
        \frac{n!}{(n-k)!} p^{k^2/2 + k/2}q^k (n-k)^{3/2+\frac{\log q}{\log p}}
            \exp\left( -\frac{\log^2(n-k)}{2\log(1/p)}  \right) \Theta(1),

    \end{eqnarray*}
    if $\log^2(n-k)) = o(k)$.

\subsection{The Symmetric case $p = q = \frac 12$}

If $p = q = \frac 12$ we can process almost in the same way as above.
Most importantly the recurrence for $\xi_\ell(n)$ simplifies to
\[
\xi_\ell(n)(1 - 2^{1-n}) = \sum_{J=1}^\ell \frac{\xi_{\ell+1-J}}{J!} 2^{2-\ell}.
\]
Similarly to the above it now follows that
$\xi_\ell(n) = \xi_\ell + O(2^{-(n-\ell)}/(\ell-1)!)$,
where $\xi_\ell = \lim_{n\to\infty} \xi_\ell(n)$.
Furthermore the Poisson generating function
$\Po{\xi}(z)$ of $\ell! \xi_\ell$ is now given by
\[
\Po{\xi}(z) = z^2 \prod_{j=1}^\infty \frac{1-e^{-z/2^j}}{z/2^j}.
\]
By using the same techniques aa above it, thus, follows that
\[
\xi_\ell = \frac{\ell^{5/2}}{\ell !}
\exp\left( -\frac{\log^2\ell}{2\log 2}  \right) \Theta(1).
\]
and consequently
    \begin{eqnarray*}
        \mu_{n,k} =
         \frac{n!}{(n-k)!} 2^{-k^2/2 - 3k/2} (n-k)^{5/2}
            \exp\left( -\frac{\log^2(n-k)}{2\log 2}  \right) \Theta(1),
    \end{eqnarray*}
    if $\log^2(n-k)) = o(k)$. This is consistent with the case $p > q$.

\subsection{Uniform bounds for $p\to 1$}.

We finally provide upper bounds for $\xi_\ell$ that are uniform as $p\to 1$.
(Actually we show more or less that (\ref{sum1}) gives also an upper bound.)

For convenience we work with $\xi_{\ell+1}$ instead of $\xi_\ell$ and recall that
the generating function is given by
\[
X(z) = \sum_{\ell \ge 0} \xi_\ell z^\ell = \prod_{j\ge 0} \frac{e^{qp^jz} -1}{qp^j z}.
\]
First suppose that $|z| \le 1/(1-p) = 1/q$ Then we have $|qp^j z|\le 1$ for all $j\ge 0$
and by using the approximation $e^x = 1 + x + x^2/2 + O(x^3)$ we directly obtain
the uniform representation
\begin{equation}\label{eqxiappr0}
X(z) = \sum_{\ell \ge 0} \xi_\ell z^\ell = e^{z/2 + O(qz^2)}. \qquad  (|qz| \le 1)
\end{equation}
This representation can be also used to obtain asymptotics for $\xi_{\ell+1} = \xi_{\ell+1}(p)$
if $\ell \le 1/(1-p) = 1/q$. We just apply a usual saddle point asymptotics on the circle
$|z| = \ell$ on the Cauchy integral
\[
\xi_{\ell +1} = \frac 1{2\pi i} \int_{|z|= \ell} X(z) z^{-ell-1}\, dz
\]
to obtain
\begin{equation}\label{eqxiappr}
\xi_{\ell+1}(p) = \frac 1{2^{\ell(1+O(q\ell)))} \ell!} \qquad (\ell \le 1/q).
\end{equation}
In particular if $\ell$ is fixed then (\ref{eqxiappr}) implies that $\xi_{\ell+1}(1) = 1/(2^\ell \ell!)$.

If $|zq|\ge 1$ then the situation is different. Here we restrict to the case of positive real $z$,
since this is sufficient to obtain upper bounds. We define $j_0$ by
\[
j_0 = \left\lceil \frac{\log(q z)}{\log(1/p)} \right\rceil
\]
and distinguish between the case $j\ge j_0$ and $j< j_0$. In the first case we $qp^j z \le 1$ so that
\[
\prod_{j\ge j_0} \frac{e^{qp^jz} -1}{qp^j z} = e^{p^{j_0} z/2 + O(p^{2j_0} q z^2) } = e^{O(1/q)}.
\]
We note that the implicit constant can be chosen to be arbitrarily close to $\frac 12 + \frac 16 = \frac 23$.
For the remaining product we have
\[
\prod_{j < j_0} \frac{e^{qp^jz} -1}{qp^j z} \le \prod_{j < j_0} \frac{e^{qp^jz}}{qp^j z} \le \frac{ e^{z(1-p^{j_0})}}{(qz)^{j_0} p^{j_0(j_0-1)/2}  } \le
e^{z - \frac 1q - \frac{\log^2(qz)}{2\log(1/p)}}
\]
Thus we obtain
\begin{equation}\label{eqxiappr2}
X(z) \le e^{z - \frac{\log^2(qz)}{2\log(1/p)}}. \qquad  (qz > 1).
\end{equation}
From this estimate we obtain, by the way, a uniform estimate for
\begin{equation}\label{eqxiappr3}
\xi_{\ell+1} \le \frac {X(\ell)}{\ell^\ell} \le \frac{C}{\ell!}
\end{equation}
uniformly for $\frac 12 \le p \le 1$.

redpajama_set_name: RedPajamaArXiv