The Symbolic Computation of Functions of Sequences over Finite Alphabets with Given Transition Probabilities by Sequence Length Independent Algorithms
Jackson, D.M.; Horowitz, Ellis
A special case of the problem discussed in this paper occurs in connection with non-statistical classification and is introduced from this point of view. The special case concerns the computation of expectations of statistical functions of the "distance" between pairs of fixed length sequences over a binary alphabet with given a priori state transition probabilities. The general problem involves an extension to alphabets of arbitrary order and the comparison of an arbitrary number of fixed length sequences. Given a set of sequences, it is shown that for a large class of functions exact computation may be carried out by an algorithm whose computation time is independent of the length of the sequences. It is further shown that results for all functions of this class may be derived from a small number of basis functions. Two methods for computing basis functions are given. Basis functions for the commonly encountered special case involving pairs of binary sequences are given explicitly.
computer science; technical report
Previously Published As