SECTION 6
THE CRAMER'S RULE FORMULATION OF THE STATIONARY DISTRIBUTION
6.1 Overview
In Sections 4.3.2 and 4.3.3, the time-homogeneous two and three-operator simple
genetic algorithm Markov chains are shown to possess unique stationary distributions.
Those conclusions are established by invoking Theorem A3, which asserts that in each
case the stationary distribution is a left eigenvector of the state transition matrix and that
the additional constraint that it be a probability vector (Definition A2) makes the solution
unique. In this section, the existence and uniqueness arguments are refined into a Cram-
er's rule formulation of the solution. This development concerns the time-homogeneous
algorithms only, with a constrained to a > 0, and it appeals heavily to the foundation
provided in Appendix B.
The product of this development is an expression for the components of the station-
ary distribution vector as rational functions generated from the characteristic polynomials
of matrices derived from the state transition matrix. The derived matrices are generated
by setting selected rows of P to zero. The utility of the approach is that the form of P
suggests a mechanism for expressing the values of the characteristic polynomials. Some
key intermediate parts of the required methodology are developed in Section 9, but the
effort stops short of explicit solution. However, some very significant conclusions con-
cerning the asymptotic behavior of the algorithm are obtainable (Sections 7 and 8) from
the results developed here without explicitly solving the system.
6.2 The Stationary Distribution Description
As established in Section 4, implementation of the mutation operator with nonzero
mutation probability (i.e. a > 0) implies that for both the two and three-operator