\magnification=1200
\hsize=4in
\nopagenumbers
\noindent
%
%
{\bf Charles Knessl and Wojciech Szpankowski}
%
%
\medskip
\noindent
%
%
{\bf A Note on the Asymptotic Behavior of the Heights in $b$-Tries for
$b$ Large}
%
%
\vskip 5mm
\noindent
%
%
%
%
We study the limiting distribution of the height in a generalized trie
in which external nodes are capable to store up to $b$ items
(the so called $b$-tries).
We assume that such a tree is built from $n$ random strings (items)
generated by an unbiased memoryless source. In this paper, we discuss
the case when $b$ and $n$ are both large. We shall
identify five regions of the height distribution that should be
compared to three regions obtained for {\it fixed} $b$. We prove that
for most $n$,
the limiting distribution
is concentrated at the single point $k_1=\lfloor \log_2 (n/b)\rfloor +1$
as $n,b\to \infty$. We observe that
this is quite different than the
height distribution for fixed $b$, in which case the limiting distribution
is of an extreme value type concentrated around $(1+1/b)\log_2 n$.
We derive our results by analytic methods, namely generating functions and
the saddle point method. We also present some numerical verification of
our results.

\bye

.
