Probabilistic Modelling of Data Structures on Words
Abstract.
Professor Arne Andersson's Letter-to-the-Editor concerning our paper
"On the Balance Property of Patricia Tries: External Path Length
Viewpoint" 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.
helmut@gauss.cam.wits.ac.za,
Peter.Kirschenhofer@tuwien.ac.at,
spa@cs.purdue.edu,
This paper is available in the Tex, Dvi, and PostScript format.
(Back to List of Papers)