where Rni,, and Rmax are the extreme values of R. (Recall that R is assumed strictly posi-
tive, so R,,ax Rni,n > 0). Eq. 4.8 can be derived by defining pA(k) as the conditional
probability of arriving in the set of absorbing states, SA', on the k0 transition given that
the k0 state is not absorbing, letting pr,, be a lower bound on pA(k), and bounding the
series for E{k^} as follows
k-1
E{kA} = k x pA(k) (1 pA())
k 1=1
k-1
Y k x n (1 pA(1)) Eq. 4.9
k 1=1
SY_ k x (1 Pmin)k- 1
k
= 1/(Pmin)2.
Next, note that a suitable bounding value on p,,n is
Pmin = MXRmin > 0. Eq. 4.10
L Mx Rmax.
The desired bound on E{kA} (Eq. 4.8) is then obtained by using Eq. 4.10 in Eq. 4.9.
It is noteworthy that the above absorbing state convergence result does not require
any assumption on the range of Rm,, Rnn. Even when the objective function exerts zero
selective pressure (i.e. Vi e S:R(i) = Rim = Rax), the finite population size still results in
convergence to an absorbing state. In the genetics parlance, this tendency is referred to as
genetic drift. It is responsible for the inevitable convergence of the one-operator simple
genetic algorithm, as discussed in Section 3.2.1.
4.3.2 A Two-Operator Algorithm (Reproduction and Mutation)
In this subsection, the nature of the state transition matrix is examined when the
mutation operator is applied with some probability in the range 0 < pm(k) < 1 (i.e.
Qk = (Pm(k),0)). Let P2(i n) and P2(m I n) be the conditional distributions of the two-
operator algorithm corresponding to the one-operator distributions defined by Eq. 4.2-4.5.
Then, P2(i I n) and P2(m I n) must account for the effect of nonzero p,. This can be