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)