\documentstyle[11pt]{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}
\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\med{\medskip\parsec}
\def\ll{\ell}
\def\l{\lambda}
\def\eps{\varepsilon}
\def\pr{{\rm \Pr}}
\def\lg{\langle}
\def\rg{\rangle}
\def\n{\eta}
\def\ss{w}
\def\eps{\varepsilon}
\def\GG{\Gamma}
\def\D{{\bf D}}
\def\X{\{X_k\}}
\def\Xs{\langle X, w\rangle}
\def \XXs{\langle {\bf X} , \sigma\rangle}
\def\L{{\cal L}}
%\def\F{{\cal F}_{\sigma}}
%\def\C{{\cal C}}
\def\W{{\cal W}}
%\def\A{{\cal A}}
\def\F{{\cal F}}
\def\B{{\cal A}}
\def\C{{\cal B}}
\def\A{\Sigma}
\def\P{{\bf P}}
\def\v{V}
\def\S{{\cal S}}
\def\U{{\cal U}}
\def\ts{\widetilde{s}}
\def\Wk{{\W_{k}}}
\def\lf{\lfloor}
\def\rf{\rfloor}
\def\ol{\overline}
\def\T{{\cal T}}
\def\la{\langle}
\def\ra{\rangle}
\vsize=8.5in
\voffset=-0.7in
\hoffset=-0.5in
\date{}
\begin{document}
\begin{center}
{\bf PROBABILISTIC MODELING OF DATA STRUCTURES ON WORDS:}\\
{\bf A Reply to Professor Andersson's Letter}
\par
\medskip
\parsec
\end{center}
\par
\bigskip\bigskip\bigskip
\begin{singlespace}
\noi
\begin{tabular}{lll}
Peter Kirschenhofer&Helmut Prodinger&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\\
A-1040 Vienna &A-1040 Vienna &W. Lafayette, IN 47907\\
Austria&Austria&U.S.A.\\
\end{tabular}
\footnotetext{This research was supported by
the NSF Grant INT-8912631, and in part by
AFOSR grant 90-0107, by the NSF grant
CCR-9201078 and NCR-9206315,  
and by grant R01 LM05118 from the National Library of Medicine.}
\bigskip\bigskip\bigskip
\begin{center}
{\bf Abstract}
\end{center}
\par
\bigskip
Professor Arne Andersson's Letter-to-the-Editor concerning our paper
``On the Balance Property of Patricia Tries: External Path Length 
Viewpoint" {\it Theor. Comp. Sci.}, 68, 1989 motivated us 
to present some thoughts about probabilistic analysis of data
structures on words. The intention of this note 
is to discuss potential advantages
and disadvantages of probabilistic analyses, and in particular
to provide a proper interpretation of probabilistic results.
This can only be achieved after building a {\it suitable} probabilistic
model for a {\it given} set of data. We describe a sequence of
probabilistic models with an increasing generality that can be applied
to the analysis of algorithms on words. Finally, we discuss a few
theoretical results to indicate that our findings from the above cited paper
hold true under more general probabilistic assumptions.

\end{singlespace}
\renewcommand{\thefootnote}{\arabic{footnote}}
\setcounter{footnote}{0}
\big
{\bf 1. PROBABILISTIC MODELS}
\par
\medskip
It is important to realize that the expected size and shape of
the data structures on words depends upon the various probabilistic
assumptions on the words (strings).
Primarily, there are three considerations:
\begin{itemize}
\item Characteristics of the alphabet; that is, the distribution
on the alphabet $\Sigma$ that determines how the
symbols are selected to form a string;
\item Statistical dependency between words; that is, whether or not
the words are statistically dependent;
\item Number of words; that is, whether the number $n$ of words is fixed or
a random variable.
\end{itemize}
\par
We now discuss these considerations and present a few basic
probabilistic models for data structures on words,
in particular tries and suffix trees (cf. \cite{ahu}, \cite{axa}).
To recall, a trie is a digital tree built from a set of keys
(strings, sequences) $X_1, \ldots, X_n$. Every key is a sequence
of symbols from an alphabet. A suffix tree is a trie built from
suffixes of a {\it single} string (key, sequence) $X$. To
simplify our further presentation, we write $X$  or $\X_{k=1}^\infty$
as a generic notation for a sequence of symbols from a given alphabet
$\Sigma$.

The {\it Bernoulli model} is characterized by the following probabilistic
assumptions:
\begin{itemize}
\item[(A)] {\sc Bernoulli Model}\parsec
The symbols of the alphabet occur independently of one another;
thus, a key $X=x_1 x_2 x_3 \ldots$ can be described as the outcome 
of an infinite sequence of
Bernoulli trials in which $\pr\{x_j = {\omega}_i\} = p_i$ and 
$\sum_{i=1}^V p_i = 1$, where $\omega_i\in \Sigma$ and $V$ is the
size of $\Sigma$.
If $p_1=p_2= \ldots = p_V = 1/V$, then the model is called
{\it symmetric};
otherwise, it is {\it asymmetric}.
\item[(B)] The number of strings (keys)  is fixed at $n$.
\end{itemize}
If the following assumption is added to (A) and (B), then
such a model is called {\it independent} Bernoulli model, and it
is often used  to analyze independent tries.
\begin{itemize}
\item[(C)] {\sc Independent Model} \parsec
The words are statistically independent; that is,
knowing a particular
string does not give information about the other strings.
\end{itemize}
\par
In the analysis of tries, assumption (B) leads to quite
complicated functional and/or differential-functional equations
(cf. \cite{flajolet1}, \cite{fr}, \cite{fs}, \cite{gonnet}, \cite{jr},
\cite{KiP}, \cite{knuth1}, \cite{knuth}, \cite{mahmoud},
\cite{spa3}).
They can be drastically simplified if (B) is replaced by the
following assumption.
\begin{itemize}
\item[(B1)] {\sc Poisson Model}\parsec
The number of strings is a random variable $N$ that has a
Poisson distribution.
\end{itemize}

The Bernoulli model is a good model when keys are transformed into
a random stream of bits through a hashing function. However, in many
other applications,
assumption (A) is not very realistic.  For instance,
if the strings
are words from the English language, then there certainly
is a dependence among
the symbols of the alphabet.  As an example, $h$ is much
more likely to follow an $s$
than a $b$.  When this is the case, assumption (A) can
be replaced by
\begin{itemize}
\item[(A1)] {\sc Markovian Model} \parsec
There is a Markovian dependency between consecutive symbols in
a key; that is, the probability $p_{ij} = \pr\{X_{k+1} = {\omega}_j |
X_k = {\omega}_i\}$
describes the conditional probability of sampling symbol
${\omega}_j\in \Sigma$ immediately after symbol ${\omega}_i\in \Sigma$.
\end{itemize}

Note that all the models discussed so far have independent
strings and are useful for
studying tries and PATRICIA tries but not the suffix and PAT trees
(i.e., a compact suffix tree; cf. \cite{gonnet}).  In
the case of suffixes, the strings involved are substrings
of a given word so they are clearly dependent.
To model this situation, we replace assumption (C) by the following one.
\begin{itemize}
\item[(C1)] {\sc Dependent Model}\parsec
The strings are dependent; i.e., knowledge of one
key gives information about other strings.
\end{itemize}

There are two further generalizations of the Markovian model, namely
the {\it mixing model} and
the {\it stationary model}.
These models are defined as follows. 
\begin{itemize}
\item[(A2)] {\sc Mixing Model}\parsec
The sequence $\X_{k=1}^\infty$ satisfies
the so called {mixing condition}, that is,
there exist two constants
$0<c_1\leq c_2$ and an integer $d$ such that for all
$1 \leq m \leq m+d \leq n$ the following holds
\begin{equation}
c_1 \pr\{\B\}\pr\{\C\} \leq \pr \{\B \C\} \leq c_2 \pr\{\B\}\pr\{\C\}
\label{e5}
\end{equation}
with $\B \in \F_{1}^m$ and $\C \in \F_{m+d}^\infty$ where
$\F_m^n$ is a $\sigma$-field generated by $\X_{k=m}^n$ for $m\leq n$.
\end{itemize}

In some statements of results one may
need a stronger form of the above mixing
condition which is defined in sequel.
\begin{itemize}
\item[(A3)] {\sc Strong Mixing Model}\parsec
The sequence $\X_{k=1}^\infty$ satisfies the so
called {\it strong $\alpha$-mixing condition} if
(\ref{e5}) is replaced by
\begin{equation}
(1-\alpha(d)) \pr\{\B\}\pr\{\C\} \leq \pr \{\B \C\} \leq
(1+\alpha(d))\pr\{\B\}\pr\{\C\}
\label{e6}
\end{equation}
where the function $\alpha(d)$  is such that $\alpha (d) \con 0$
as $d \con \infty$.
\end{itemize}
In words, model (A2) says that the dependency
between two substrings of a given key, say 
$\X_{k=1}^m$ and $\X_{k=m+d}^\infty$, is rather weak
(note that when the sequence $\X$ is i.i.d., then $ \pr \{\B \C\} =
\pr\{\B\}\pr\{\C\}$). Assumption (A3) says that this dependency
is weaker and weaker as $d$ becomes larger. The ``quantity'' of
dependency
is characterized by $\alpha(d)$.

The most general probabilistic model that can
provide some useful results, is the stationary model.
This model is widely used in coding and communications, most
notably in data compression (cf. \cite{spa4}, \cite{wz}).
\begin{itemize}
\item[(A4)] {\sc Stationary Model}\parsec
The sequence $\X_{k=1}^\infty$ of letters from a finite
alphabet is a {\it stationary and ergodic} sequence of random
variables.
\end{itemize}

To explain how the stationary model works, we need to introduce
some notations. Let $X_m^n =(X_m,\dots,X_n)$ for $m<n$, and let
for every $n \geq 1$ the $n$th order probability
distribution for $\X$ be
$$P( X_1^n)=\pr \{X_k=x_k, ~ 1\leq k \leq n ,~ x_k\in {\cal A}\} ~.  $$
In the stationary model, this probability does not depend on time-shift,
that is, if $\tau$ is an integer, then for every $n$ and $\tau$
the following holds
$$P(X_{1+\tau}^{n+\tau})=P( X_1^n) ~.$$

For PATRICIA tries and compact suffix trees (i.e., PAT trees)
another assumption which strengthens (A3) is often useful.
\begin{itemize}
\item[(P)] {\sc Contractive Mixing Model} \parsec
Let $\omega_i\in \Sigma$ for $1\leq i\leq n$,  and define
$P(\omega_1, \ldots, \omega_n)=\pr\{X_1=\omega_1, \ldots, X_n=\omega_n\}$.
Then, for PAT trees we shall require the following condition
\begin{equation}
P(\omega_1, \ldots, \omega_n) \leq \rho P(\omega_1, \ldots, \omega_{n-1})
\label{e7}
\end{equation}
for some $0< \rho < 1$.
\end{itemize}

Finally, the most general probabilistic model makes no
assumption regarding the probabilistic nature of keys 
$X_1, \ldots, X_n$. Then, however, a chance 
for any interesting results is very dim. Does this model reflect
practical situations? We doubt.

In passing, we should mention one more model, which might be
called the {\it worst-case model}. In this case, we assume that 
for a {\it given} algorithm (not necessary a problem!) the whole
probability mass is concentrated on one (pathological) input that returns
the maximum value of the parameter under consideration, say
the external path length. Note, however, that such a distribution
depends on the algorithm (and the problem) itself.
\big
{\bf 2. SOME RESULTS}
\par
\medskip
In the discussed paper \cite{kps2} we have 
established the asymptotic expansion for the variance of the external 
path length in a PATRICIA tree 
(see \cite{kps1} for similar results for tries)
in the {\it symmetric} Bernoulli model. So far, an 
extension of this result to
an asymmetric Bernoulli model have failed, however, Jacquet and R\'{e}gnier
\cite{jr} proved that the limiting distribution for the  
external path length is normal with the variance $O(n\log n)$
(but the constant hidden in $O(\cdot)$ was not found in \cite{jr}).
As a simple consequence of our result in \cite{kps2}, we showed
that the external path length $L_n$ almost surely behaves
like $n\log_2n$; more precisely $L_n/n\log_2n \con 1$ (a.s.) as
$n \con \infty$. This result is weaker than our main finding in 
\cite{kps2}, and in fact
it holds in a much more general probabilistic setting.

Indeed, Shields \cite{shields1} proved
in the Markovian model that the
external path length in a {\it suffix tree}
(hence, also in tries) asymptotically converges to
$(1/h)n\log n$ (a.s.)  where $h$ is the entropy of the alphabet
(precisely: $L_n/n\log n \con 1/h$ (a.s.) as $n \con \infty$).
This is also true for PAT trees and PATRICIA (cf. \cite{spa7}).
(Note that $h=\log 2$ for the binary symmetric model.)
However, Shields \cite{shields1} showed also that the above result
does {\it not} hold in general (e.g., in stationary model).

Probably, for independent tries (and PATRICIA) Shields' finding
can be extended to the mixing model (but not to the general stationary model
as already noted by Shields \cite{shields1}). 
Pittel proved in \cite{pittel1} that in the mixing model 
the typical depth $D_n$ (i.e., the length of a path from the
root to a randomly selected external node) behaves
asymptotically as $D_n/\log n \con 1/h$ in probability (pr.). 
For the Markovian model
(more precisely: the strong mixing model with the coefficient
of mixing $\alpha(d)$ from (A3) decaying exponentially fast) 
Szpankowski \cite{spa7}
extended Pittel's result to
suffix trees (and PAT trees). Since the external path length
is the sum of depths, one should expect that it converges
(a.s.) to $(1/h)n\log n$ even in the mixing model.
(Some caution is adviced in extending the convergence in probability results
of $D_n$ to almost sure convergence of the external path length. 
In fact, as observed by Pittel \cite{pittel1} and
Szpankowski \cite{spa4} (cf. \cite{spa7} and \cite{wz}) 
$D_n/\log n$ does not converge (a.s.) to $1/h$ but rather oscillates
between two constants. Nevertheless, the sum of depths, that is, the
external path, should converge (a.s) to $1/h$.) 
In summary, the conclusions in
our paper \cite{kps2} were restricted to the Bernoulli symmetric model,
even if it was later assessed that they hold under weaker probabilistic
assumptions.

In passing, we should mention that probabilistic modeling provides
good insights into the behavior of algorithms and data structures 
only when applied to a {\it set} of inputs, not a 
{\it particular} instant of input. 
 
\begin{singlespace}

\begin{thebibliography}{99}
\bibitem{ahu}
A.V. Aho, J.E. Hopcroft and J.D. Ullman,
{\it The Design and Analysis of Computer Algorithms },
Addison-Wesley (1974).
\bibitem{axa}
A. Apostolico,
The Myriad Virtues of Suffix Trees,
{\it Combinatorial Algorithms on Words},
85-96, Springer-Verlag, ASI F12 (1985).
\bibitem{lawler}
W. Chang, E. Lawler,
Approximate String Matching in Sublinear Expected Time,
{\it Proc. of 1990 FOCS}, 116-124 (1990).
\bibitem{flajolet1}
P. Flajolet,
On the Performance Evaluation of extendable Hashing and Trie
Searching, {\it Acta Informatica}, 20, 345-369 (1983).
\bibitem{fr}
P. Flajolet and B. Richmond,
Generalized Digital Trees and Their Difference-Differential Equations,
{\it Random Structures and Algorithms}, 3,  1992, in press.
\bibitem{fs}
P. Flajolet and R. Sedgewick,
Digital Search Trees Revisited,
{\it SIAM J. Computing}, 15, 748-767  (1986).
\bibitem{gonnet}
G.H. Gonnet and R. Baeza-Yates,
{\it Handbook of Algorithms and Data Structures},
Addison-Wesly, Workingham (1991).
\bibitem{jr}
P. Jacquet and M. R\'{e}gnier,
Normal Limiting Distribution for the Size and the External
Path Length of Tries,
INRIA TR-827, (1988).
\bibitem{KiP}
P. Kirschenhofer and H. Prodinger,
Further Results on Digital Search Trees,
{\it Theoretical Computer Science}, 58, pp. 143-154  (1988).
\bibitem{kps1}
P. Kirschenhofer, H. Prodinger and  W. Szpankowski,
On the Variance of the External Path Length in a Symmetric Digital Trie,
{\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{knuth1}
D. Knuth,
{\it The Art of Computer Programming. Searching. Fundamental Algorithm },
vol. I, Addison-Wesley, Reading (1967).
\bibitem{knuth}
D. Knuth,
{\it The Art of Computer Programming. Sorting and Searching },
vol. III, Addison-Wesley (1973).
\bibitem{mahmoud}
H. Mahmoud,
{\it Evolution of Random Search Trees}, John Wiley \& Sons,
(1992).
\bibitem{pittel1}
B. Pittel,
Asymptotic Growth of a Class of Random Trees,
{\it Annals of Probability },
18, 414 - 427 (1985).
\bibitem{shields1}
P. Shields,
Entropy and Prefixes,
{\it Annals of Probability}, 20, 403-409 (1992).
\bibitem{spa3}
W. Szpankowski,
Patricia tries again revisited,
{\it Journal of the ACM}, 37, 691-711 (1991).
\bibitem{spa4}
W. Szpankowski,
Asymptotic Properties of Data Compression and Suffix Trees,
{\it IEEE Trans. Information Theory}, submitted.
\bibitem{spa7}
W. Szpankowski,
A Generalized  Suffix Tree and Its (Un)Expected Asymptotic Behaviors,
{\it SIAM J. Computing}, to appear.
\bibitem{waterman}
M. Waterman, {\it Mathematical Methods for DNA Sequences},
CRC Press Inc., Boca Raton, (1991).
\bibitem{wz}
A. Wyner and J. Ziv,
Some Asymptotic Properties of the Entropy of a Stationary Ergodic 
Data Source with Applications to Data Compression,
{\it IEEE Trans. Information Theory},
35, 1250-1258  (1989).
\end{thebibliography}

\end{singlespace}

\end{document}
