PATTERN DEFINITION AND INFERENCE WITH STOCHASTIC PROCESSES
B. Lesche · Cybernetics & Systems · 1987
We define the pattern content of a limited sequence { an}n-1}N_ of zeros and ones of length N by a probability measure µ on the space of infinite sequences of zeros and ones. The measure µ. is given by a program ρ and a programmable automaton A. The measure that describes the pattern content of a given sequence { an}n-1}N is defined as one that minimizes a positive definite potential U. U is a linear combination of the negative logarithm of the probability of the observed finite sequence { an}n-1}N according to µρ and the complexity Cρ of the program ρ.Cρ Cy is related to the number of bits necessary to write ρ. The automaton A is constructed in such a way that the empty program ρ0 that contains no statements defines the apriori probabilities µρ0 ({an}n-1}N)=2 − N. A sequence is defined to be completely random if its optima program is ρ0. The optimal measure µρ of a sequence { an}n-1}N It can be used to make probabilistic predictions for an n > N. This defines a new concept of probability, which is not related to a relative frequency interpretation. In special cases, however, it can be related to relative frequencies. Verification and disproof of that sort of probabilistic statement is defined by survival and death of a program when N increases. In practice the optimal program for a given sequence can be found by evolutionary techniques.