A schema is a naturally defined subset of the space of fixed-length binary
strings. The Holland Schema Theorem gives a lower bound on the expected
fraction of a population in a schema after one generation of a simple genetic
algorithm. This paper gives formulas for the exact expected fraction of a
population in a schema after one generation of the simple genetic algorithm.
Holland's schema theorem has three parts, one for selection, one for crossover,
and one for mutation. The selection part is exact, whereas the crossover and
mutation parts are approximations. This paper shows how the crossover and
mutation parts can be made exact. Holland's schema theorem follows naturally as
a corollary. There is a close relationship between schemata and the
representation of the population in the Walsh basis. This relationship is used
in the derivation of the results, and can also make computation of the schema
averages more efficient. This paper gives a version of the Vose infinite
population model where crossover and mutation are separated into two functions
rather than a single "mixing" function.