
\documentstyle[12pt]{article}
\newtheorem{Proposition}{Proposition}
\newtheorem{Theorem}{Theorem}
\newtheorem{Lemma}{Lemma}
\newenvironment{pic}[1]%
{\input{#1}\begin{figure}\centerline{\box\graph}\vspace*{\bigskipamount}}%
{\end{figure}}
\renewcommand{\thefootnote}{\fnsymbol{footnote}}
\renewcommand{\baselinestretch}{1.3}
\newenvironment{comment}{\setbox0=\vbox\bgroup}{\egroup}
\newcommand{\con}{\rightarrow}
\newcommand{\cd}{\mbox{$\stackrel{d}{\rightarrow}$}}
\newcommand{\cp}{\mbox{$\stackrel{p}{\rightarrow}$}}
\newcommand{\ed}{\mbox{$ \ \stackrel{d}{=}$ \ }}
\newcommand{\ep}{\varepsilon}
\newcommand{\FF}{{\cal F}}
\newenvironment{singlespace}
{\def\baselinestretch{1.0}\large\normalsize}{\par}
\newenvironment{singlespace2}
{\def\baselinestretch{1.0}
\large
\normalsize
}{\par\vskip -1mm}


\setlength{\textheight}{8.5in}
\setlength{\textwidth}{6in}
\def\noi{\noindent}
\def\lf{\lfloor}
\def\rf{\rfloor}
\def\eod{\vrule height 6pt width 5pt depth 0pt}
\def\parsec{\par\noindent}
\def\big{\bigskip\parsec}
\def\t{\widetilde}
\def\half{{1\over 2}}
\def\med{\medskip\parsec}
\def\binom Nk{{N \choose k}}
\def\C{{\cal C}}
\def\n{\eta}
\def\ss{\sigma}
\def\pr{{\rm Pr}}
\def\w{\omega}
\def\l{\ell}
\def\b{{\bf b}}
\def\d{\delta}
\def\eps{\varepsilon}
\def\GG{\Gamma}
\def\w{\omega}
\def\wo{\omega'}
\def\TL{\widetilde{L}}
\def\Tl{\widetilde{l}}
\def\TW{\widetilde{W}}
\def\Tw{\widetilde{w}}
\def\TT{\widetilde{T}}
\def\Tt{\widetilde{t}}
\def\TR{\widetilde{R}}
\def\Tr{\widetilde{r}}
\def\TM{\widetilde{M}}
\def\Tm{\widetilde{m}}
\def\sech{\text{sech}}
\vsize=8.5in
\voffset=-0.7in
\hoffset=-0.7in

\begin{document}
\begin{center}
{\bf MULTIDIMENSIONAL DIGITAL SEARCHING AND SOME NEW PARAMETERS
IN TRIES}
\par
\medskip
\parsec
\today
\end{center}
\par
\bigskip\bigskip\bigskip
\begin{singlespace}
\noi
\begin{tabular}{lll}
Peter Kirschenhofer\footnotemark&Helmut Prodinger\footnotemark&Wojciech Szpankowski\footnotemark\\
Dept. of Algebra\&Discrete Math.&Dept. of Algebra\&Discrete Math.&Dept. of Computer Science\\
Technical University of Vienna&Technical University of Vienna&Purdue University\\
Vienna A-1040&Vienna A-1040&W. Lafayette, IN 47907\\
Austria&Austria&U.S.A.\\
\end{tabular}
\footnotetext[1]{$^\dagger$This work was supported by Fonds zur F\"{o}rderung der
Wissenschaftlichen Forschung Project P7497-TEC}
%\footnotetext{This work is supported by Fonds zur F\"{o}rderung der
%Wissenschaftlichen Forschung Project P7497-TEC}
\footnotetext{Support for this research was provided  in part by
NSF Grant INT-8912631, CCR-9201078 and NCR-9206315, in part by
AFOSR grant 90-0107, NATO Grant 0057/89,
and  grant R01 LM05118 from the National Library of
Medicine.}
\bigskip\bigskip\bigskip
\begin{center}
{\bf Abstract}
\end{center}
\par
\bigskip
Multidimensional digital searching ($M$-d tries) is analyzed 
from the view point of partial match retrieval. 
Our first result extends the analysis of Flajolet
and Puech of the average cost of retrieval 
under the Bernoulli model
to biased probabilities
of symbols occurrences in a key. The second main finding concerns
the variance of the cost of the retrieval in the unbiased case. This
variance is of order $O(N^{1-s/M})$ where $N$ is the number of records stored
in a $M$-d trie, and $s$ is the number of specified components in a query
of size $M$. For $M=2$ and $s=1$ we present a detailed analysis of the
variance, which identifies the constant at $\sqrt{N}$. 
This analysis,
which is the central part of our paper, requires certain series 
transformation identities which go back to Ramanujan.
In the Appendix we provide a Mellin transform approach to these results.

\end{singlespace}

\vfill
\clearpage
\renewcommand{\thefootnote}{\arabic{footnote}}
\setcounter{footnote}{0}
\big
{\bf  1. INTRODUCTION}
\par
\medskip
Multidimensional searching is 
an important algorithmic concept in modern
computer science. In particular, retrieval of multidimensional
data found applications in the design of data base systems and
graphics. Bentley \cite{bentley} and Rivest \cite{rivest} are
founding fathers of multidimensional searching, namely digital
$M$-d trees and $M$-d search trees. An early description of
these structures can be found in volume three of Knuth's book
\cite{knuth}, and a more detailed discussion is
in the book of Mahmoud \cite{mahmoud}.
Several applications of multidimensional searching
are discussed in the paper of Flajolet and Puech \cite{fla-puech},
which also presents a thorough analysis of partial match
retrieval for multidimensional data. 
\par
In this paper we concentrate on $M$-d digital trees (i.e., 
M-dimensional tries) and partial match retrieval in such a 
data structure. 
In general, a {\it trie} stores a set of, say, $N$ items, which
are represented by keys from $\Sigma^\infty$, the set of all
infinite 
sequences over a finite alphabet $\Sigma$.
A trie is composed of branching nodes, also called  {\it internal nodes}, and
{\it external nodes} that store the keys. In addition,  we assume that
every external node is able to store only one key.
The branching policy at any level,
say $k$, is based on the $k$-th symbol of a key. For
example, for a binary alphabet $\Sigma =\{0,1\}$,
if the $k$-th symbol in a key is ``0", then we branch-out left in the trie,
otherwise we go to the right. This process terminates when for the first time
we encounter a different symbol between a key that is currently
inserted into the trie and all other
keys already in the trie. Then, this new key is stored in a newly
generated external node.
In other words, the access path from the root to an external node (a leaf of
a trie) is the minimal 
unique prefix of the information contained in this external
node.
(Cf. also
\cite{ahu},  \cite{kps1}, \cite{kps2}, \cite{knuth}, \cite{mahmoud}).
\par
The $M$-d {\it tries} are built in a similar manner, however, this time
a key is an $M$-dimensional tuple. 
Let the $i$th key be
$K_i=(K_{i1},\ldots, K_{iM})$, where $K_{ij}\in\Sigma^\infty$,
and $1\leq i\leq N$. 
Now we produce for each $1\leq i\leq N$ one sequence $\widetilde{K}_i
\in\Sigma^\infty$ by regular shuffling of the components 
$K_{i1},\ldots, K_{iM}$, and use
these new composite keys
$\widetilde{K}_1, \ldots , \widetilde{K}_N$ to construct  a regular
trie. More precisely, let $K_i=(K_{i1} ,\ldots, K_{iM})$ and
$K_{i\l}=(k_{i\l}^1, k_{i\l}^2, \dots )$ where $k_{i\l}^m\in \Sigma$
for $1\leq \l \leq M$ and $m\geq 1$. Then, the new $i$th key is
$\widetilde{K}_i=(k_{i1}^1k_{i2}^1\cdots  k_{iM}^1 k_{i1}^2 k_{i2}^2 \cdots 
k_{iM}^2 \cdots )$. In passing, we note that the statistics of
the composite keys are the same as the original keys provided the
keys are statistically independent.
\par
A {\it partial match query\/} $q=(q_1,\dots,q_M)$,
$q_j\in\Sigma^\infty\cup\{*\}$, asks for all records 
$(r_1,\dots,r_M)$ with $r_j=q_j$ for all specified components $q_j$ of the
query. 
For example, $q=(S_1,*,S_2)$ asks for all records with (specified)
first component
$S_1$, unspecified second component and (specified)
third component $S_2$.
Because of the construction of the $M$-d tries 
it is convenient to transform
a given query $q$ into a one-dimensional {\it search sequence\/}
$\sigma=\sigma(q)\in\left(\Sigma\cup\{*\}\right)^\infty$
by regular shuffling, too.
That is, the first
symbol of $\sigma$ comes from the first symbol of the first component
of $q$ (if the first component is unspecified $*$, then we put $*$ in
$\sigma$ too), the second symbol of $\sigma$ originates from the first symbol
of the second component of $q$, and so on modulo $M$. The search sequence
is used to search for external nodes in an $M$-d trie that satisfy
the pattern, where 
``$*$" means to proceed in all directions.
The {\it cost of a query} is defined as the number of internal
nodes visited during such a search.
\par
The cost of a query depends on the search sequence $\sigma$. 
In fact, this
sequence specifies a subtree in a trie, and can be considered
as a new parameter that characterizes the trie. For example, if
a query consists only of specified patterns, then the query defines
a specific 
path (depth) in the trie. This path may be of various shapes depending
on the search sequence. Indeed, if  $\Sigma=\{0,1\}$ and
$\sigma=(1111 \cdots)$, 
then the query
finds the right-most internal nodes, and the cost of the query is the
length of such a path; the length of a ``zig-zag" path can be
computed by evaluating the cost of the following search sequence
$\sigma=(0101\cdots)$, etc. 
On the other hand, if the query consists of only
unspecified components $*$, then the cost of the query is equivalent
to the size of the underlying trie. Finally, with a mixture of
specified and unspecified components, the cost of a query represents
the size of a subtree of the trie.

In the following, for  simplicity of presentation,
 we restrict ourselves to the binary alphabet 
$\Sigma=\{0,1\}$. We adopt the following
{\it probabilistic model}: Symbols from the alphabet are generated
independently, and 0 and 1 occur with probabilities $p_0$ and $p_1=1-p_0$
respectively ({\it Bernoulli model}).
In  \cite{fla-puech} Flajolet and Puech -- using ingenious techniques from complex analysis
and differential equations -- presented a very detailed evaluation
of the {\it expected} cost of a query, assuming equal probabilities
for symbol occurrences. Observe that in this unbiased instance the
expected cost of a fixed query $q$ does not depend on the distribution
of the zeroes and ones in the search sequence $\sigma=\sigma(q)$, but only
on its {\it search pattern} $\w\in\{S,*\}^M$: 
If we substitute each specified
element of $\sigma$ by $S$, we obtain a sequence in $\{S,*\}^\infty$
which has period $M$ (since $\sigma$ was constructed by regular
shuffling from $q$), and we denote its prefix of length $M$ by $\w$.

In this paper we extend Flajolet and Puech's result into two directions.
First, we consider the expected cost in the {\it biased case}, that is, when
probabilities of symbol occurrences are not identical. We investigate
two aspects of this problem, namely the 
{\it deterministic} instance of {\it fixed
search sequences} $\sigma$ as well as the average cost for random
queries with a {\it fixed search pattern} $\w$, where we assume that the
specified components of the query satisfy the same Bernoulli statistics
as the keys of the trie ({\it nondeterministic instance}).
Our motivation for studying the biased case is mainly to 
see the impact of
(e.g. slightly) different probabilities
on the order of the cost. It turns out that this order varies only mildly
if $p_0$ is not too close to either 0 or 1 (compare the table in
Section 2). This result matches well with some other analyses
for  biased trie-like structures
 by Fayolle, Flajolet and Hofri \cite{ffh}, and
Jacquet \cite{jacquet}.


More importantly, we
also analyze the {\it variance} of the cost 
in the unbiased case for  $M=2$,
which already requires rather sophisticated mathematical techniques.
We shall show that this variance 
is of order $O(\sqrt{N})$, which implies
the convergence {\it in probability} of the cost to its average value.
We also conjecture that for general $M$ the variance is
of order $O(N^{1-s/M})$ where
$s$ is the number of specified components in a query. 
We point out that this can be difficult to prove, especially if
one needs to identify the constant at $N^{1-s/M}$.
\par
This paper is organized as follows. In the next section we present
our main results, and discuss some consequences of them. All proofs
are delayed till Section 3. The asymptotic analysis 
is based on solving
some recurrences equation through generating function approach,
and obtaining asymptotics of some alternating sums through the
usage of Rice's formula (cf. \cite{fla-sed}) or the
Mellin transform approach (cf. \cite{spa1}). The main difficulty in
this analysis lies in proving that some coefficients in the
asymptotics of the variance are equal to zero. 
These kind
of problems were already tackled by us in \cite{kps1} and \cite{kps2}.
However, this time the difficulty is one step higher. 
More precisely, during the course of our analysis we require transformation
results for $F(x)=\sum_{k\geq 1} e^{-kx}/(1+e^{-2kx})$ and related functions.
It turns out that by a very general formula of Ramanujan (cf. \cite{berndt})
we have $F(x)=\pi/4x -1/4+\pi F(\pi^2/x)/x$ for $x>0$. In the Appendix
we give an outline of a Mellin transform proof for
this and similar transformation results.
\big
{\bf 2. MAIN RESULTS}
\par
\medskip
In this section we present our main results concerning the expected cost
of a query.  We start with the {\it nondeterministic case} of random
queries, with fixed search pattern $\w\in\{S,*\}^M$, where we assume
that the specified components $S$ of the query are generated in the same
manner as the keys stored in the trie, namely 0's and 1's chosen
independently with probabilities $p_0$ resp. $p_1=1-p_0$.

Let $\w^{(k)}$ denote the cyclic shift to the left by $k$ positions of
$\w$. Then 
$\w=\w^{(M)}$.
We also write 
$\w^\prime=\w^{(1)}$. 
Let $H_N^\w(z)$ be the probability generating function of the cost of
a random query with search pattern $\w$. Then the following recurrence
holds for $N\geq 2$:
\begin{equation}
H_N^\w(z)=\left\{\begin{array}{ll}
\med
z\sum_{k=0}^N {N\choose k} p_0^kp_1^{N-k} H_k^{\w^{\prime}}(z) 
H_{N-k}^{\w^{\prime}}(z) & \w=*\dots \\
\medskip
z\sum_{k=0}^N {N\choose k} p_0^kp_1^{N-k} 
\left(p_0H_k^{\w^{\prime}}(z)+p_1H_{n-k}^{\w^{\prime}}(z) \right)&
\w=S\dots
 \label{e1a}
\end{array}
\right.
\end{equation}
and $H_0^\w(z)=H_1^\w(z)=1$. (Compare the detailed arguments in
 \cite{fla-puech} for the symmetric case.)

The expected cost $l_n^\w$ is the first derivative of $H_N^\w(z)$
at $z=1$. Therefore we have 
\begin{equation}
l_N^\w=1+\sum_{k=0}^N {N\choose k} p_0^kp_1^{N-k}
\{ \d(0,x_1)l_k^{\w^{\prime}}+\d(1,x_1)l_{N-k}^{\w^{\prime}} \} ~, 
\label{e3a}
\end{equation}
$l_0^\w=l_1^\w=0$,
where $\w=(x_1,x_2,\dots,x_M)$ and
\begin{equation}
\d(b,x)=\left\{\begin{array}{ll}
p_b&\mbox{if $x=S$,}\\
1 &\mbox{if $x=*$,}
\end{array}
\right.    
\qquad b\in\{0,1\}.
 \label{e4a}
\end{equation}

Since $\w=\w^{(M)}$, recurrence (\ref{e3a}) can be solved by iteration,
and the following asymptotic result holds (compare Section 3 for all
details).

\med
{\bf Theorem 1.1}. 
{\it Let $\w=(x_1,x_2,\dots,x_M)\in\{S,*\}^M$ 
and denote by $s_j$ the number of specified components $S$ in
$(x_1,\dots,x_j)$, with $s=s_M$. Then the expected cost
$l_N^\w$ of a random query $q$ with search pattern $\w$ fulfills
for large $N$

{\rm (i)}  if $s=M$ (all components specified)
\begin{equation}
l_N^\w= {\log N \over -\left(p_0\log p_0+p_1\log p_1\right)} +O(1) ~, 
\label{e4stern}
\end{equation} 

{\rm (ii)} if $0<s<M$
\begin{equation}
l_N^\w\sim
N^{\kappa_0}\left({
\Gamma(-\kappa_0)(1-\kappa_0)\sum\limits_{j=0}^{M-1}\left(p_0^{1+\kappa_0}+
p_1^{1+\kappa_0}\right)^{s_j}
\left(p_0^{\kappa_0}+
p_1^{\kappa_0}\right)^{j-s_j}
\over
s{p_0^{1+\kappa_0}\log p_0+p_1^{1+\kappa_0}\log p_1
\over
p_0^{1+\kappa_0}+p_1^{1+\kappa_0}}
+(M-s)
{p_0^{\kappa_0}\log p_0+p_1^{\kappa_0}\log p_1
\over
p_0^{\kappa_0}+p_1^{\kappa_0}}
}+\xi(N)
\right)
\label{e4sternstern}
\end{equation}
where $0<\kappa_0<1$ is the unique real solution of the equation
\begin{equation}
\left(p_0^{1+\kappa_0}+p_1^{1+\kappa_0}\right)^s
\left(p_0^{\kappa_0}+p_1^{\kappa_0}\right)^{M-s}
=1,
\end{equation}
and $\xi(N)$ is an oscillating function which is
zero if ${\log p_0\over \log p_1}$ is irrational.
}

Observe that for $s=M$ $\ l_N^\omega$
is the same as the  average depth of a randomly selected
external node (\cite{knuth}, 
\cite{mahmoud}). The denominator $h=-p_0\log p_0-p_1\log p_1$
is the entropy.


For the reader's convenience we present a table of exponents
$\kappa_0=\kappa_0(p_0,{s\over M})$:

\bigskip
\begin{center}
\begin{tabular}[h]{|c||c|c|c|c|c|}\hline
$p\bigg\backslash {s\over M}$ &${1\over 4}$&${1\over 3}$&${1\over 2}$&
${2\over 3}$&${3\over 4}$\\ \hline\hline
${1\over 10}$&0.838&0.779&0.648&0.492&0.398\\ \hline
${1\over 5}$ &0.799&0.727&0.574&0.405&0.314\\ \hline
${1\over 4}$&0.784&0.708&0.549&0.380&0.290\\ \hline
${1\over 3}$&0.765&0.685&0.521&0.352&0.266\\ \hline
${1\over 2}$&0.750&0.667&0.500&0.333&0.250\\ \hline
\end{tabular}
\end{center}

\medskip

We note that the exponent $\kappa_0$ varies substantially with $s/M$,
while the variation of $\kappa_0$ with respect to $p$ is rather small.

In the {\it deterministic case} we ask for the expected cost of a fixed
query $q$ with associated query sequence $\sigma=(x_1,x_2,\dots)
\in\{0,1,*\}^\infty$. This time we have the following equations
for the probability generating
functions
\begin{equation}
H_N^\sigma(z)=\left\{\begin{array}{ll}
\med
z\sum_{k=0}^N {N\choose k} p_0^kp_1^{N-k} H_k^{\sigma^{\prime}}(z) 
H_{N-k}^{\sigma^{\prime}}(z) & \sigma=*\sigma^\prime \\
\medskip
z\sum_{k=0}^N {N\choose k} p_0^kp_1^{N-k} H_k^{\sigma^{\prime}}(z) &
\sigma=0\sigma^\prime \\ 
\medskip
z\sum_{k=0}^N {N\choose k} p_0^kp_1^{N-k} H_{N-k}^{\sigma^{\prime}}(z) &
\sigma=1\sigma^\prime ~, \label{e2}
\end{array}
\right.
\end{equation}
and for the expected cost
\begin{equation}
l_N^\sigma=1+\sum_{k=0}^N {N\choose k} p_0^kp_1^{N-k}
\{ \varepsilon(0,x_1)l_k^{\sigma^{\prime}}+
\varepsilon(1,x_1)l_{N-k}^{\sigma^{\prime}} \} ~, 
\label{e3aa}
\end{equation}
where $\sigma=(x_1,x_2,\dots)$ and, for $b\in\{0,1\}$, $x\in\{0,1,*\}$
\begin{equation}
\varepsilon_{b,x}=\left\{\begin{array}{ll}
1&\mbox{if $x=*$}\\
1&\mbox{if $x\in\{0,1\}$,\  $b=x$}\\
0&\mbox{if $x\in\{0,1\}$,\  $b\neq x$\ .}
\end{array}
\right.     \label{e1aa}
\end{equation}

In general, (\ref{e3aa}) can be solved by iteration, 
but the asymptotic behavior of the solution will depend heavily on the
structure of the  0,1--pattern of $\sigma$ (observe that the $*$--pattern
has period $M$). In the case where $\sigma$ is periodic with period $k$
similar analytic techniques as in the nondeterministic case can be applied.
Since the structure of the result is quite similar to  Theorem 1.1., we
only give the exponent of $N$ in case (ii).

\med
{\bf Theorem 1.2}. 
{\it Let $\sigma\in\{0,1,*\}^\infty$ be a fixed search sequence of
period $k$ with $n_a$ symbols $a\in\{0,1,*\}$ per period.
Then, for large $N$, 

{\rm (i)}  
\begin{equation}
l_N^\sigma\sim {k\log N \over
-n_0\log p_0-n_1\log p_1}
 +O(1),\qquad\mbox{if $n_*=0$,\quad and}
\end{equation} 

{\rm (ii)} 
\begin{equation}
l_N^\sigma\sim N^{\kappa_0}
\cdot \left(C(\sigma,p_0)+\xi_1(N)\right),\qquad\mbox{if $n_*>0$},
\end{equation}
 where 
$0<\kappa_0<1$ is the unique  solution of 
\begin{equation}
p_0^{\kappa_0n_0}p_1^{\kappa_0n_1}\left(p_0^{\kappa_0}+p_1^{\kappa_0}
\right)^{n_*}
=1.
\end{equation}
}



The next result is our main finding and it
concerns the variance of the cost in the case where
at least one  component of the  query is unspecified. This analysis is much
more intricate, as demonstrated in our papers \cite{kps1}, \cite{kps2}
that are devoted to the variance of the external path length in
a trie and PATRICIA respectively. Therefore, 
hereafter we assume only the symmetric alphabet, that is, 
``0" and ``1" occur
with equal probability $0.5$. 
Observe that under this assumption the nondeterministic cost model 
coincides with the deterministic one. Now (\ref{e1a}) reads
\begin{equation}
H_N^\w(z)=\left\{\begin{array}{ll}
\med
z\sum_{k=0}^N {N\choose k} 2^{-N} H_k^{\w^{\prime}}(z)
H_{N-k}^{\w^{\prime}}(z) & \w=*\dots\ , \\
\medskip
z\sum_{k=0}^N {N\choose k} 2^{-N} H_k^{\w^{\prime}}(z) &
\w=S\dots \ .
\end{array}
\right.  \label{e7}
\end{equation}
\par
If the cost of the query $\w$ is denoted by $C_N^\w$, then the
variance ${\rm var}~C_N^\w$ can be evaluated according to
the following formula
\begin{equation}
{\rm var}~C_N^\w=\left.{d^2 \over dz^2} H_N^\w(z)\right|_{z=1}+
l_N^\w-(l_N^\w)^2,\qquad l_N^\w=E\,C_N^\w ~.
\label{e8}
\end{equation}
\par
The evaluation of the second factorial moment of $C_N^\w$
leads to very tedious algebraic manipulations, although the main idea
behind it is not too complicated.
In the following we restrict our investigations to the case of $M=2$.
As shown in Section 3, the analysis of
the centralized moments in this case is a rather sophisticated one. 
\big
{\bf Theorem 2}. 
{\it
{\rm (i)} For $\w=(*,S)$ we have asymptotically
\begin{equation}
{\rm var}~C_N^{\w}\sim \sqrt{N} \Big( A_1+ \tau_1(\log_2 \sqrt{N})\Big),
\qquad A_1
\simeq 2.09184~, \label{e9}
\end{equation}
where the constant $A_1$ can be expressed analytically as
\begin{eqnarray}
A_1&=&{7\sqrt{\pi}(1+\sqrt{2})\over 2L}-2\sqrt{\pi}\left(
{1\over L}\left[{73+25\sqrt{2} \over 16\sqrt{2}}-{4\over 3\sqrt{3}} 
\right] \right. 
\nonumber \\
&+& {2\over L}\sum_{\l\geq 2}{1/2 \choose \l} 
{(\l-1)(\l+\half)(1+2^{-\l})
2^{-\l} \over 1-2^{\half -\l}} \Bigg) ~, \label{e10}
\end{eqnarray}
with $L=\log 2$, and $\tau_1(x)$ is a continuous periodic function of period 
1, mean 0 and $|\tau_1(x)|<5\cdot 10^{-3}$.
\parsec
For $\w=(S,*)$ we have
\begin{equation}
{\rm var}~C_N^{\w}\sim \sqrt{N}\Big({A_1\over \sqrt 2}
 +  \tau_2(\log_2 \sqrt{N}) \Big),\qquad {A_1\over \sqrt 2} 
\simeq 1.47916~, \label{e11}
\end{equation}
where 
$\tau_2(x)$ is again of period 1, mean 0 and $|\tau_2(x)|<5\cdot 10^{-3}$.
\med
{\rm (ii)} The cost of the query $\w$ converges in probability to
$EC_N^\w=\l_N^\w$, that is, the following holds
\begin{equation}
\lim_{N \con \infty} \pr\{\mid C_N^\w/l_N^\w -1\mid > \eps \}=0 
\label{e13}
\end{equation}
for any $\eps>0$.}  

\med
{\bf Remarks}.
\med
(i) {\it Periodic Fluctuations}. The Fourier coefficients of $\tau_1$
and $\tau_2$ can be computed too, but we omit them here since the expressions
are rather complicated. 
Estimating these coefficients we obtain the upper bounds for the
amplitudes.
\med
(ii) {\it Proof of Theorem 2(ii)}. We just note that part (ii) of
Theorem 2 follows directly from part (i) and Chebyshev's inequality.
\med
(iii) {\it Extensions}. Our results can be extended in many
directions. For example, it is easy to see that they hold for
$V$-ary symmetric tries, that is, when $\Sigma=\{1,2, \cdots , V\}$.
It may be interesting to extend our Theorem 2 to an asymmetric alphabet,
and it is even more challenging to assume some dependency among
symbols in the alphabet $\Sigma$. Finally, one may replace the
regular tries by other digital structures such as Patricia tries and
digital search trees. Some preliminary results in this direction
are reported in \cite{kp}.
Also, a rigorous analysis of suffix trees with partial match retrieval 
might be of some interest.

\big
{\bf 3. ANALYSIS}
\par
\medskip
In this section we prove Theorems 1.1, 1.2 and 2. 
\med
{\bf 3.1 The Expected Cost in the Asymmetric Case}
\par
\medskip

Let us consider the nondeterministic case at first.

We start our analysis from  the
recurrence equation  (\ref{e3a}) for the average cost $l_N^\w$ of 
a random query with search pattern $\w=(x_1,\dots,x_M)\in\{S,*\}^M$. 
Let $L^\w(z)$ be the 
exponential generating function of the cost, that is,
$L^\w(z)=\sum_{N=0}^\infty l_N^\w z^N/N!~$. Then recurrence (\ref{e3a})
can be transformed into the following functional equation
$$L^\w(z)=\d(0,x_1)L^{\w^{\prime}}(zp_0)e^{p_{1}z}
+\d(1,x_1)L^{\w^{\prime}}(zp_1)e^{p_{0}z} +b(z) ~,$$
where $b(z)=e^z-1-z$. Introducing the transform $\t{L}^\w(z)=e^{-z}L^\w(z)$
we reduce the above to 
$$
\t{L}^\w(z)=\d(0,x_1)\t{L}^{\w^{\prime}}(zp_0)+
\d(1,x_1)\t{L}^{\w^{\prime}}(zp_1) +\t{b}(z) ~,
$$
with $\t{b}(z)=e^{-z}b(z)$. Using  the fact that $\w=\w^{(M)}$, 
we obtain after $M$ iterations
\begin{eqnarray}
\t{L}^\w(z)&=&\sum_{\b\in\Theta_{M}} \d(b_1,x_1) \cdots \d(b_M,x_M)\,
\t{L}^\w(zp_{b_{1}} \cdots p_{b_{M}}) \nonumber\\
 &+&\sum_{j=0}^{M-1}
\sum_{\b\in\Theta_{j}} \d(b_1,x_1) \cdots \d(b_j,x_j)\, \t{b}(zp_{b_{1}} 
\cdots p_{b_{j}}) ~,\label{e1mond}
\end{eqnarray}
where $\Theta_j=\{0,1\}^j$.
This functional equation is easy to solve. Comparing the coefficients
of $\t{L}^\w(z)$ at $z^N/N!$ we get
\begin{equation}
\t{l}_N^\w={(-1)^N (N-1)\sum_{j=0}^{M-1} \sum_{\b\in\Theta_{j}} 
\prod_{i=1}^j 
\d(b_i,x_i)p_{b_{i}}^N \over 1-\sum_{\b\in\Theta_{M}} \prod_{i=1}^M 
\d(b_i,x_i) p_{b_{i}}^N } ~.
\nonumber
\end{equation}
From the definition of $\delta(b_i,x_i)$ it follows  that
$$
\sum_{\b\in\Theta_{j}}\prod_{i=1}^j 
\d(b_i,x_i) p_{b_{i}}^N =
\left(p_0^{1+N}+p_1^{1+N}\right)^{s_j}\left(p_0^N+p_1^N\right)
^{j-s_j}=:P(N;s_j)
$$
where $s_j$ is the number of components $S$ among $(x_1,\dots,x_j)$.
Therefore, with $s=s_M$,
\begin{equation}
\t{l}_N^\w={(-1)^N (N-1)\sum_{j=0}^{M-1} P(N;s_j)
\over 1-
P(N;s)},\qquad N\ge 1
 ~.
\label{e15}
\end{equation}
To recover the original average cost $l_N^\w$ we note that
$l_N^\w=\sum_{k=1}^N {N \choose k}
\t{l}_k^\w$.
\par
The asymptotics of $l_N^\w$ can now be obtained  by a 
Mellin transform approach (cf. \cite{spa1})
or 
Rice's formula (compare Section 3.2).
In particular, using \cite{spa1} we translate $l_N^\w$ into
the following Mellin-like integral
$$
l_N^\w = {1\over 2\pi i} \int_{-3/2-i \infty}^{-3/2+i \infty}
{\Gamma(z) N^{-z} (z+1)\sum_{j=0}^{M-1} 
P(-z;s_j)
\over 1-
P(-z;s)
} dz  \cdot\left(1+O({1\over N})\right) ~.$$
Shifting the contour of integration to the right and
computing the residues of the integrand we finally
obtain Theorem 1.1. Note that in the case 
$s=M$ there is a double
pole at $z=0$ which produces the logarithm function in Theorem 1.1(i).
In the case $0<s<M$ the dominating pole is a simple  pole at $z=-\kappa_0$.
Additional simple poles occur at the nonreal zeroes of the denominator.
It can be shown that nonreal zeroes at $-\kappa_0+iy_k$ 
occur if and only if
${\log p_1\over\log p_0}$ is rational (compare 
the similar reasoning in \cite{jacquet}).
They constitute the fluctuating function $\xi(N)$.
It is easy to prove that $0<\kappa_0<1$.

In the deterministic case of a fixed query sequence $\sigma=(x_1,x_2,\dots)
\in\{0,1,*\}^\infty$ we iterate recurrence (\ref{e3aa}), observe
$$
\sum_{b\in\Theta_j}\prod_{i=1}^j\varepsilon(b_i,x_i)
p_{b_i}^N=p_0^{Nn_0(\sigma_j)}p_1^{Nn_1(\sigma_j)}
\left(p_0^N+p_1^N\right)^{n_*(\sigma_j)}=:Q(N,\sigma_j).
$$
where $\sigma_j=(x_1,x_2,\dots,x_j)$ and get the solution
\begin{equation}
\t{l}_N^\sigma=(-1)^N(N-1)\sum_{j\ge0}Q(N,\sigma_j).
\label{e2herz}
\end{equation}
For general $\sigma$ a suitable analytic continuation of
$\sum_{j\ge0}Q(z,\sigma_j)$ will not exist, but there is one
for instance if
$\sigma$ has period $k$. Then
$$
\sum_{j\ge0}Q(z,\sigma_j)=
{\sum_{j=0}^{k-1}Q(z,\sigma_j)\over 1-Q(z,\sigma_k)}
$$
is meromorphic and we obtain Theorem 1.2 by the same method as Theorem 1.1.

\med
{\bf 3.2 The Analysis of the Variance in the Symmetric Case}
\par
\medskip
We first consider $\w=(*,S)$, $S\in\{0,1\}$. 
Before attacking 
the second factorial moment of the cost $C_N^\w$
we perform a more precise evaluation of the
average cost $l_N^\w$. 

From (\ref{e15}) we have
\begin{equation}
l^\omega_N=\sum_{k=1}^N\binom Nk(-1)^k f(k)\,\quad \mbox{with}\quad 
f(z)=\frac{(z-1)(1+2^{1-z})}{1-2^{1-2z}}~.
\label{e17}
\end{equation}
\par
The alternating sum can be treated by the following
lemma.
\med
{\bf Lemma}. (Rice's method, cf. \cite{fla-sed}, \cite{kps1}, \cite{kps2})
{\it Let $\C$ be a path surrounding the points
$\{j,j+1, \ldots , N\}$, and $f(z)$ be an analytical continuation of
$f(k)$ inside $\C$. Then
\begin{equation}
\sum_{k=j}^N {N \choose k} (-1)^k f(k) = - {1 \over 2\pi i}
\int_{\C} [N;z] f(z) dz ~,
\label{e18}
\end{equation}
where
\begin{equation}
[N;z]= {\Gamma(-z)\Gamma(N+1) \over \Gamma(N+1-z)}={(-1)^{N-1} N! \over
z(z-1) \cdots (z-N)} ~.
\label{e19}
\end{equation}}
\par
\medskip
Extending the contour of the integration it can be shown that under
suitable growth conditions for $f(z)$ the alternating sum in (\ref{e18})
equals $\sum\mbox{Res}([N;z]f(z))+O(N^c)$, where the sum is taken over
all residues with real part greater than $c$ that are different from 
$j,\dots,N$.

The function $f(z)$ in (\ref{e17}) has  single
poles at $z_k=\half+\half \chi_k$ where $\chi_k=2 \pi i k/L$ and $L=\log 2$.
Computing the residues at $z_k$ and additionally at $z=0$ (coming from
the function $[N;z]$), we finally obtain
\begin{equation}
l^\w_N= \sqrt N\left(\sqrt \pi \frac{1+\sqrt 2}{2L}
+\tau^\w\left(\log_2\sqrt{N}\right)\right) -3+o(1),
\label{e20}
\end{equation}
where the fluctuating function $\tau^\w(x)= \sum_{k\neq 0}
\tau_k^\w e^{2k\pi i x} $ has the Fourier coefficients
\begin{equation}
\tau_k^\w=\frac 1{2L}\left(1+\sqrt 2 (-1)^k\right)
\Gamma\left(\frac {-1-\chi_k}2\right)
\left(\frac {-1+\chi_k}2\right) ~.
\label{e21}
\end{equation}
\par
Now we deal with the second factorial moment. Let
$w_N^\w={\left(H_N^{\w}\right)}^{''}(1)$, and $W^\w(z)$ be its
exponential generating function. 
From now on we define $\t{A}(z)=A(z)e^{-z}$ for any function $A(z)$ 
under consideration. 
From (\ref{e7}), after differentiating it twice,
we obtain
\begin{eqnarray*}
\TW^\w(z) &=& 
2\TW^{\wo}\left(\frac z2\right)+4\TL^{\wo}\left(\frac z2\right)
+2\left(\TL^{\wo}\left(\frac z2\right)\right)^2 \\
\TW^{\wo}(z)  &=& \TW^{\w}\left(\frac z2\right)+2\TL^{\w}\left(\frac 
z2\right) ~.
\end{eqnarray*}
For simplicity of presentation, 
$\TW^\w(z)=\TR^\w(z)+\TT^\w(z)$ where
\begin{eqnarray}
\TR^\w(z)=2\TR^{\wo}\left(\frac z2\right)+4\TL^{\wo}\left(\frac z2\right),
\qquad
\TR^{\wo}(z)=\TR^{\w}\left(\frac z2\right)+2\TL^{\w}\left(\frac z2\right) 
\label{e22}
\end{eqnarray}
and
\begin{eqnarray}
\TT^\w(z)=2\TT^{\wo}\left(\frac z2\right)
+2\left(\TL^{\wo}\left(\frac z2\right)\right)^2,\qquad
\TT^{\wo}(z)=\TT^{\w}\left(\frac z2\right) ~.
\label{e23}
\end{eqnarray}
\par
The solution of the first system of recurrences, namely (\ref{e22}),
is easy.  Note that it reduces to the following functional equation
$$\TR^\w(z)=2\TR^\w\left(\frac z4\right)+4\TL^{\wo}\left(\frac z2\right)
+4\TL^{\w}\left(\frac z4\right) ~.$$
Comparing coefficients we immediately find that
\begin{equation}
\Tr_N^\w=\frac{(-1)^N(N-1)2^{2-N}}{\left(1-2^{1-2N}\right)^2}
\left[1+2^{1-N}+2^{1-2N}\right] ~.
\label{e24}
\end{equation}
\par
Now we deal with (\ref{e23}), which is more intricate. We need
a formula for 
the coefficients of
$\TM^{\wo}(z)=\left(\TL^{\wo}\left( z\right)\right)^2$
that avoids the convolution originating from the square.
But from (\ref{e1mond})
$$
\TL^{\wo}(z)=2\TL^{\wo}\left(\frac z4\right)
+\t{b}(z)+\t{b}\left(\frac z2\right) ~.
$$
Taking it to the power two, we obtain
$$
\TM^{\wo}(z)=
4\TM^{\wo}\left(\frac z4\right)
+4\left(\t{b}(z)+\t{b}\left(\frac z2\right)\right)\TL^{\wo}\left(\frac z4\right)
+\left(\t{b}(z)+\t{b}\left(\frac z2\right)\right)^2  ~,
$$
which allows to express the coefficients of $\TM^{\wo}(z)$
in the desired manner.
\par
Putting everything together we find 
after some tedious algebra that $w^\w_N=\sum_{k=2}^N\binom Nk 
(-1)^k f(k)$ with  $f(z)$ as below
\begin{eqnarray}
f(z)&=&
\frac{(z-1)2^{1-z}}{\left(1-2^{1-2z}\right)\left(1-2^{2-2z}\right)}
\left[5+2^{3-z}+2^{3-2z}+z2^{z-2}-2^z +\frac z4 +
\left(z-\frac 92\right)\left(\frac 32\right)^{z-2}\right] \nonumber \\
&+&\frac{2^{3-2z}}{\left(1-2^{1-2z}\right)\left(1-2^{2-2z}
\right)}
\sum_{l\ge 2} {z \choose l}
\frac{(l-1)(z-l-1)\left(1+2^{-l}\right)\left(1+2^{z-l}\right)2^{-l}}
{1-2^{1-2l}}  ~.
\label{e27}
\end{eqnarray}
\par
Now we can apply our Lemma to the alternating sum $w_N^\w$ to obtain
an asymptotic expansion. Note that there are two sets of poles that
contribute to the
leading terms of the asymptotics. Namely, $z_{k,1}=1+\half \chi_k$
and $z_{k,2}=\half +\half \chi_k$ where $k=0,\pm 1, \cdots~$. Easy
computations reveal finally that
\begin{eqnarray}
w^\w_N&\sim& \frac{N}{L}\left\{ 8-\frac 7{12}-2\sum_{l\ge 2}(-1)^l
\frac{\left(1+2^{-l}\right)\left(1+2^{1-l}\right)2^{-l}} {1-2^{1-2l}} 
+\tau_3(\log_2\sqrt{N}) \right\} \nonumber \\
&-&2\sqrt{\pi N}\left\{\frac 1L
\left[\frac{73}{2\sqrt 2}+\frac{25}{16} -\frac{4}{3\sqrt 3}\right] \right. 
\label{e28}
\\ 
&+&\frac 2L\sum_{l\ge 2}
{1/2 \choose l}
\frac{(l-1)\left(l+\frac 12\right)\left(1+2^{-l}\right)
2^{-l}}
{1-2^{\half -l}} +\tau_4(\log_2\sqrt{N})\bigg\}
\nonumber
\end{eqnarray}
with periodic fluctuations $\tau_3(x)$ and $\tau_4(x)$ of mean 
(i.e. zeroeth  Fourier coefficient) zero.
\par
Now we are ready to put everything together. In particular, we note
that, {\it apart from  continuous fluctuations of mean zero},
\begin{equation}
{\rm var}~C_N^\w=w_N^\w+l_N^\w -(l_N^\w)^2= BN+A_1\sqrt{N}+o(\sqrt{N}) ~,
\label{e29}
\end{equation}
where $A_1$ and $B$ are constants.  
Note that
$$
B=\frac{1}{L}\left\{
8-\frac 7{12}-2\sum_{l\ge 2}(-1)^l
\frac{\left(1+2^{-l}\right)  \left(1+2^{1-l}\right) 2^{-l}}
{1-2^{1-2l}}\right\} 
-\pi\frac{\left(1+\sqrt 2\right)^2}{4L^2}-{[(\tau^\w)^2]_0} ~,
$$
where $[(\tau^\w)^2]_0$ is the mean of the square of the periodic function
$\tau^\w(x)$ defined in (\ref{e20}). 
In the lines below we prove  that $B=0$.
As in \cite{kps1} and \cite{kps2}, we point out 
that the term $[(\tau^\w)^2]_0$
significantly contributes to the cancellation of terms in $B$.
\par
Considering the terms of order $N$, after having proved $B=0$,
the remaining fluctuating
function has to be identically equal to zero since otherwise
the variance would be negative for infinitely many values of $N$,
which is impossible. For more detailed arguments the reader is referred 
to our papers \cite{kps1} and \cite{kps2}.


To find 
a transformation for $[(\tau^\w)^2]_0$ we proceed as follows. Note that
$$
[(\tau^\w)^2]_0=2\sum_{k\ge 1}\tau_k^\w \tau_{-k}^\w
=\frac{2}{4L^2}\sum_{k\ge 1}\left(3+2\sqrt 2(-1)^k\right)
\Gamma\left(\frac {1-\chi_k}2\right)
\Gamma\left(\frac {1+\chi_k}2\right) ~.
$$
Now we use the formula (cf. \cite{abramowitz})
$\Gamma(z) \Gamma (1-z)=\pi/  \sin \pi z$
and  obtain
$$
\Gamma({1-\chi_k \over 2})\Gamma ({1+\chi_k\over 2})=
{\pi \over \sin(\pi/2+ik\pi^2/L)}=
{\pi \over \cos(ik\pi^2/L)}={\pi \over \cosh(k\pi^2/L)}=
2\pi {e^{-k\pi^{2}/L} \over 1+e^{-2k \pi^{2}/L}} ~,
$$
so that
\begin{equation}
[(\tau^\w)^2]_0=
\frac{\pi}{L^2}\sum_{k\ge 1}\left(3+2\sqrt 2(-1)^k\right)
\frac{e^{-k\pi^2/L}}{1+e^{-2k\pi^2/L}} ~.
\label{e31}
\end{equation}
Let us define two new functions
\begin{eqnarray}
F(x)=\sum_{k \ge 1}\frac{e^{-kx}}{1+e^{-2kx}}  \qquad\mbox{and}\qquad
G(x)=\sum_{k \ge 1}\frac{(-1)^{k-1}e^{-kx}}{1+e^{-2kx}} ~. \label{e33}
\end{eqnarray}
Then, (\ref{e31}) in terms of $F(x)$ and $G(x)$ becomes
\begin{equation}
[(\tau^\w)^2]_0
=\frac{3\pi}{L^2}F\left(\frac{\pi^2}{L}\right)
-\frac{2\sqrt 2 \pi}{L^2}G\left(\frac{\pi^2}{L}\right) ~. \label{e34}
\end{equation}
In order to prove $B=0$,
we use a series transformation 
for $F(x)$ and $G(x)$. We start with
$$
F(x)=\sum_{j\geq 0}(-1)^j\sum_{k\geq 1} e^{-k(2j+1)x}=\sum_{j\geq 0}
\chi(j) {1\over e^{jx}-1}
$$
where
$$
\chi(j)=\left\{
\begin{array}{ll}
0& \mbox{for $j$ even} \\
1&\mbox{for $j \equiv 1  \bmod 4$}\\
-1&\mbox{for $j \equiv 3  \bmod 4$} \\
\end{array}
\right.
$$
In \cite{berndt} on page 258 we find the following Entry 11 from
{\it Ramanujan's Notebooks}.
\med
{\it For $\alpha$, $\beta>0$ such that $\alpha \beta=\pi$ and
$y \in {\rm I\! R} $ with $|y|<\beta/2$ the following holds}
\begin{equation}
\alpha\left\{{1\over 4}\sec (\alpha y) +\sum_{k=1}^\infty
\chi(k){\cos (\alpha y k) \over e^{k\alpha^{2}}-1}\right\} =
\beta\left\{ {1\over 4} +\half \sum_{k=1}^\infty
{\cosh (2\beta y k) \over \cosh (k \beta^{2})} \right\} ~.
\label{e32a}
\end{equation}
\med
For $y=0$ this reads
$$
\alpha\left\{{1\over 4} +\sum_{k=1}^\infty 
\chi(k){1 \over e^{k\alpha^{2}}-1}\right\} = 
\beta\left\{ {1\over 4} +\half \sum_{k=1}^\infty 
{1 \over \cosh (k \beta^{2})} \right\} ~.
$$
Replacing in the above $\cosh(x)$ by the exponential functions, expanding
the geometric series and rearranging the sums we obtain
$$
\half \sum_{k\geq 1}{1\over \cosh(k \beta^2)} = \sum_{j\geq 1}
\chi(j) {1\over e^{j\beta^{2}}-1} ~,
$$
so that, taking into account the constraint $\alpha \beta=\pi$, we find
$$
\alpha \left({1\over 4}+F(\alpha^2)\right)=
\beta\left({1\over 4}+F(\beta^2)\right) ~.
$$
Now, we substitute in the above $\alpha=\sqrt{x}$ and
$\beta=\pi /\sqrt{x}$. Then,
\begin{equation}
F(x)={\pi \over 4x}-{1\over 4}+{\pi \over x}F\left({\pi^2\over x}\right)
\label{e33a}
\end{equation}
for $x>0$, which is the desired transformation result.
For $G(x)$ we observe that
$G(x)=F(x)-2F(2x)$, hence
\begin{equation}
G(x)={1\over 4}+{\pi \over x}F\left({\pi^2\over x}\right)-
{\pi \over x}F\left({\pi^2 \over 2x}\right) ~.
\label{e34a}
\end{equation}
Applying the above to (\ref{e34}) we finally obtain 
\begin{equation}
[(\tau^\w)^2]_0
=\frac{3}{4L}-\frac{\pi}{4L^2}\left(3+2\sqrt 2\right)
+\frac{3-2\sqrt 2}{L}F(L)
+\frac{2\sqrt 2}{L}F\left(\frac L2\right) ~. \label{e35}
\end{equation}

Using (\ref{e35}) $B=0$ follows by some obvious simplifications. 
 Thus, we have 
proved 
${\rm var}~C_N^\w=O(\sqrt{N})$.
The coefficient $A_1$ at $\sqrt{N}$ in (\ref{e29}) is given in Theorem
2(i) equation (\ref{e10}).
\par
The second pattern $\w=(S,*)$ can be analyzed in a similar manner as above.




We finally mention, that it is not at all obvious how to 
extend this result to the case $M\geq 3$. The reader
should note that the key arguments in our proof of Theorem 2(i)
are the transformations result (\ref{e33a}) and (\ref{e34a}). 
For $M\geq 3$ there is
no
comparable result in {\it Ramanujan's Notebooks}, and the alternative
proof presented in the Appendix relies heavily on the duplication
formula
for the gamma function, which is not suitable for $M\geq 3$.
\begin{comment}
Finally, proof of Theorem 2(i) follows the same path as above.
Algebra involved is very tedious, but the final result
(without explicit constant) is simple. In fact, intuitively
one must expect this kind of behavior, since the size of a
trie -- which dominates cost of all other partial match retrieval --
has the variance of $O(N)$, as shown in \cite{rj}.
\end{comment}
\big
{\bf APPENDIX: Mellin Transform Approach to Ramanujan-Like Series 
Identities}
\par
\medskip


Most proofs of results like 
Ramanujan's formula (\ref{e32a}) resp. 
(\ref{e33}) use the
theory of {\it modular functions} (cf. \cite{berndt}). In this appendix
we outline the  alternative approach  using {\it Mellin integrals},
a line of attack, suggested to us by P. Flajolet, that belongs to the
toolkit of analytic number theory (cf. \cite{apo2}).
\par
To prove (\ref{e33a}) we proceed as follows. Let
$$
\beta(s)=\sum_{j\geq 0} (-1)^j {1\over (2j+1)^s} ~.
$$
Using definition (\ref{e33}) of $F(x)$, we have
$$
F(x)=\sum_{k\geq 1}{e^{-kx}\over 1+e^{-2kx}}=
\sum_{j\geq 0} (-1)^j \sum_{k\geq 1}e^{-k(2j+1)x} ~,
$$
so that the Mellin transform 
$F^*(s)=\int_0^\infty F(x) x^{s-1} dx$ of $F(x)$ (cf. \cite{davis})
becomes
$$F^*(s)=\Gamma(s)\zeta(s)\beta(s) ~,$$
where $\zeta(s)$ is Riemann's zeta function \cite{abramowitz}.
By the Mellin inversion formula this yields
\begin{equation}
F(x)={1\over 2\pi i} \int_{3/2-i \infty}^{3/2+i \infty} \Gamma(s)\zeta(s)
\beta(s) x^{-s} ds ~.
\label{e38}
\end{equation}
Now we take the two residues $s=1$ and $s=0$ 
out from the above integral 
(observe that $\beta(0)=1/2$ and $\beta(1)=\pi/4$ 
(cf. \cite{abramowitz}) and apply the
the duplication formula for $\Gamma(s)$ 
to obtain
$$
F(x)=
\frac{\pi}{4x}-\frac 14+
\frac{1}{2\pi i}\int\limits_{-\frac 12-i\infty}^{-\frac 12+i\infty}
\frac{1}{\sqrt\pi}2^{s-1}\Gamma\left(\frac s2\right)\Gamma
\left(\frac {s+1}2\right)
x^{-s}\zeta(s)\beta(s)ds~.
$$
(Observe that the exponential smallness of the $\Gamma$-function along
vertical lines justifies the shifting of the line integral.)

We now use the functional equations
for $\zeta(s)$ and $\beta(s)$, namely
\begin{equation}
\Gamma\left(\frac s2\right)\zeta(s)=\pi^{s-\frac 12}
\Gamma\left(\frac {1-s}2\right)\zeta(1-s)
\label{e39}
\end{equation}
and
\begin{equation}
\beta(1-s)\Gamma\left(1-\frac s2\right)=
2^{2s-1}\pi^{-s+\frac 12}\Gamma\left(\frac{s+1}{2}\right)\beta(s) ~.
\label{e40}
\end{equation}
Identity (\ref{e39}) is Riemann's functional equation for
$\zeta(s)$, and (\ref{e40}) is an immediate consequence of
the functional equation for Hurwitz's $\zeta$-function 
$\zeta(s,a)$ (cf. \cite{apostol}), and the fact that
$$
\beta(s)=4^{-s}\left[\zeta(s,{1\over 4})-\zeta(s, {3\over 4})\right] ~.
$$
Using (\ref{e39}) and (\ref{e40}), and substituting $1-s=u$, we get
$$
F(x)=
\frac{\pi}{4x}-\frac 14+
\frac{1}{2\pi i}\int\limits_{\frac 32-i\infty}^{\frac 32+i\infty}
\pi^{1-2u}\Gamma(u)x^{u-1}\zeta(u)\beta(u)du ~.
$$
This proves (\ref{e33a}). 
\par
\medskip
Using the above scheme  {\it several other identities} can be proved.
Below we just list some of them. Define
\begin{eqnarray}
f(x)&=&\sum_{k\ge1}\frac{e^{kx}}{\left(e^{kx}-1\right)^2}=
\sum_{k\ge1}\frac{k}{e^{kx}-1}, \\
g(x)&=&\sum_{k\ge1}\frac{(-1)^{k-1}}{k\left(e^{kx}-1\right)}, \\
h(x)&=&\sum_{k\ge1}\frac{1}{k\left(e^{2k\pi x}-1\right)} ~.
\end{eqnarray}
Then, the following identities hold:
\begin{enumerate}
\item
$$
1+2\sum_{n\ge1}e^{-\pi n^2x}=\frac{1}{\sqrt x}+\frac{2}{\sqrt x}
\sum_{n\ge1}e^{-\pi n^2/x} \ \ \ \ \ \ \ \ \mbox{Jacobi's $\vartheta$--function},
$$
\item
$$
f(x)=\frac{1}{x^2}\frac{\pi^2}{6}-\frac{1}{2x}+\frac{1}{24}
-\frac{4\pi^2}{x^2}f\left(\frac{4\pi^2}{x}\right) \ \ \      
\mbox{Ramanujan \cite{berndt}},
$$
\item
$$
g(x)=\frac{\pi^2}{12x}-\frac{\log 2}{2}+\frac{x}{24}-
g\left(\frac{2\pi^2}{x}\right) \ \ \ \ \ \ \ \    
\mbox{Ramanujan \cite{berndt}},
$$
\item
$$
\ \ \ \ \ \ h(x)=\frac{\pi }{12}\left(\frac 1x-x\right)+\frac{\log x}{2}+
h\left(\frac{1}{x}\right) \ \ \ \
\mbox{Dedekind and Ramanujan \cite{berndt}}.
$$
\end{enumerate}
The latter three identities play a prominent role in the analysis of 
the variance for some parameters of tries (cf. \cite{kp1}, \cite{kps1},
\cite{kps2}).
\med
{\bf Remark}. It is fairly well known that the functional equations
for the Riemann $\zeta$-function and the 
$\vartheta$-function can be derived from each other via the
Mellin transform (see e.g., \cite{bellman}, \cite{borwein}).
Here we would like to point out the analogous $\vartheta$-like
identity that is related to the functional equation for $\beta(s)$.
Let
$$
H(x)=\sum_{j\geq 0} (-1)^j (2j+1)e^{-(2j+1)^{2}x} ~,
\qquad
\mbox{then}\qquad
H(x)={1\over 8}\left({\pi \over x}\right)^{3/2}H\left({\pi^2 \over 16x}
\right) ~.
$$
\med
{\bf ACKNOWLEDGMENTS}
\par
\medskip
We would like to thank  Philippe Flajolet, INRIA, for
his long standing support of our work, and several fruitful discussions
on the subject of this paper, as well as the anonymous referees for
several helpful remarks.

\begin{singlespace2}

\begin{thebibliography}{99}
\bibitem{abramowitz}
M. Abramowitz and I.A. Stegun,
{\it Handbook of Mathematical Functions},
Dover, New York 1970.
\bibitem{ahu}
A.V. Aho, J.E. Hopcroft and J.D. Ullman,
{\it
The Design and Analysis of Computer Algorithms,
}
Addison-Wesley, Reading Mass.  1974.
\bibitem{apostol}
T. Apostol,
{\it Introduction to Analytical Number Theory},
Springer-Verlag, New York 1976.
\bibitem{apo2}
T. Apostol,
{\it Modular Functions and Dirichlet Series in Number Theory},
Springer-Verlag, New York 1978.
%\bibitem{axa}
%A. Apostolico,
%The Myriad Virtues of Suffix Trees,
%{\it
%Combinatorial Algorithms on Words,
%}
%pp. 85--96, Springer-Verlag, ASI F12 (1985).
%\bibitem{axa-spa}
%A. Apostolico and W. Szpankowski,
%Self-Alignments in Words and Their Applications,
%{\it J. Algorithms}, 13, 446--467,  1992.

\bibitem{bellman}
R. Bellman,
{\it Analytic Number Theory -- An Introduction},
Benjamin-Cummings, London 1980.
\bibitem{bentley}
J. L. Bentley,
Multidimensional Binary Search Trees Used for Associative Searching,
{\it Communication of the ACM}, 18, 509-517, 1975.
\bibitem{berndt}
B.C. Berndt, 
{\it Ramanujan's Notebooks. Part II},
Springer-Verlag, New York 1989.
\bibitem{borwein}
J. Borwein and P. Borwein,
{\it Pi and the AGM},
John Wiley \& Sons, New York 1987.
\bibitem{davis}
B. Davis,
{\it Integral Transforms and Their Applications},
Springer-Verlag, New York 1978.
%\bibitem{dsr}
%L. Devroye, W. Szpankowski and B. Rais,
%A Note on the Height of Suffix Trees,
%{\it SIAM J. Computing}, 21, 48-53, 1992.
%\bibitem{erdos}
%P. Erd\"{o}s and P. R\'{e}v\'{e}sz,
%On the Length of the Longest Run of Heads,
%{\it Colloquia Math. Soc. J. Bolyai}, 16, 219-228, 1975.
\bibitem{ffh}
G.Fayolle, P.Flajolet and M.Hofri, On a functional equation arising
in the analysis of a protocol for a multiaccess broadcast channel,
{\it Advances in Applied Probability}, 18, 1986, 441--472.
\bibitem{fla-puech}
P. Flajolet and C. Puech,
Partial Match Retrieval of Multidimensional Data,
{\it J. of the ACM}, 33, 371-407, 1986.
\bibitem{fla-sed}
P. Flajolet and R. Sedgewick,
Digital Search Trees Revisited,
{\it SIAM J. Computing}, 15, 748-767, 1986.
%\bibitem{gordon}
%L. Gordon, M. Schilling and M. Waterman,
%An Extreme Value Theory for Long Head Runs,
%{\it Probab. Theory and Related Topics}, 72, 279-287, 1986.
%\bibitem{go}
%L. Guibas and A.M. Odlyzko,
%A Long Repetitive Patterns in Random Sequences,
%{\it Z. Wahrscheinlichkeitstheorie verw. Gebiete}, 38, 241-262, 1980.
\bibitem{henrici}
P. Henrici,
{\it Applied and Computational Complex Analysis},
John Wiley\&Sons, New York 1977.
\bibitem{jacquet}
P. Jacquet, 
{\it Contribution de l'Analyse d'Algorithmes \`a l'\'Evaluation
des Protocoles de Communications},
Th\`ese, Universit\'e de Paris Sud-Orsay, 1989.
%\bibitem{js}
%P. Jacquet and W. Szpankowski,
%Autocorrelation on Words and Its Applications, \\
%{\it J. Combinatorial Theory, Ser. A},
%to appear.
\bibitem{kp1}
P. Kirschenhofer and H. Prodinger,
On Some Applications of Formulae of Ramanujan in the Analysis of
Algorithms,
{\it Mathematika}, 38, 14-33, 1991.
\bibitem{kp}
P. Kirschenhofer and H. Prodinger,
Multidimensional Digital Searching -- Alternative Data Structures,
{\it Proc. Random Graphs'91}, John Wiley \& Sons, 1992.
\bibitem{kps1}
P. Kirschenhofer, H. Prodinger and W. Szpankowski,
On the Variance of the External Path length in a Symmetric Digital Tries,
{\it Discrete Applied Mathematics}, 25, 129-143, 1989.
\bibitem{kps2} 
P. Kirschenhofer, H. Prodinger and W. Szpankowski,
On the balance Property of Patricia Tries: External Path Length Viewpoint,
{\it Theoretical Computer Science}, 68, 1-17, 1989.
\bibitem{knuth}
D.E. Knuth, 
{\it The Art of Computer Programming. Vol. 3}, 
Addison-Wesley, Reading MA 1973.
\bibitem{mahmoud}
H. Mahmoud,
{\it Evolution of Random Search Trees},
John Wiley \& Sons, New York, 1992.
\bibitem{rj} 
M. R\'{e}gnier and P. Jacquet,
New Results on the Size of Tries,
{\it IEEE Trans. Information Theory},
35, 203-205  (1989).
\bibitem{rivest}
R. L. Rivest,
Partial-Match Retrieval Algorithm,
{\it SIAM J. Computing}, 5, 19-50, 1976.
\bibitem{spa1}
W. Szpankowski,
The Evaluation of an Alternating Sum with Applications to the
Analysis of Some Data Structures, 
{\it Information Processing Letters}, 28, 13-19, 1988.
\end{thebibliography}
\end{singlespace2}
\end{document}

