Next: Probabilistic evolution matrix Up: Probabilistic de Bruijn Previous: determinant

# Correlations

One application of the probabilistic -stage de Bruijn matrix is to finding the probability of encountering one n-block in the vicinity of another; depending upon the direction, the basic probabilities are obtained by multiplying a vector of n-block probabilities by the matrix of the corresponding handedness to get the probabilities of a shifted block. Powers of the matrix would then yield blocks shifted to greater and greater distances, giving some importance to knowing about the behaviour of such powers. The degeneracy of the largest eigenvalue and the size of the second largest eigenvalue are the quantities which determine the limiting behaviour of powers and how rapidly their limits are reached.

If the largest eigenvalue is non-degenerate, which will be assured if none of the links has zero probability, then both the dominant eigenvalue and its normalized eigenvector will be unique. The second largest eigenvalue governs the exponential approach to equilibrium, which will be the more rapid the smaller the eigenvalue. In general a slow approach to equilibrium is associated with a large bias. Unfortunately the commonest estimators of eigenvalues tend to estimate either the largest eigenvalue, or else the smallest by first inverting the matrix, but not any of the others.

There is a certain informal expectation that if a block is long enough, probabilities will not be much affected by dropping the final cell, especially if comparative probabilities are considered. Illustrating this concept with a fairly short sequence of three cells, we might expect to find

There is no real justification for such an assumption, but it gives an alternative viewpoint to the equivalent equation

which says that we should multiply the probabilities for the two sequences ab and bc because the presence of both is required to form the sequence abc, but that the probability of b should be divided out because it is common to both sequences and thus counted twice when they are joined.

As yet, the source of the block probabilities which enter into the formation of an actual probabilistic de Bruijn matrix has not been discussed; only the fact that that they ought to satisfy the Kolmogorov consistency conditions. One way to obtain them would be to to look for probabilities which were self consistent with respect to evolution; the context in which to do this is the probabilistic version of the reduced evolution matrix.

Next: Probabilistic evolution matrix Up: Probabilistic de Bruijn Previous: determinant

Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx