|
|
|
|
|
|
|
xÎX. It will be helpful in approaching this calculation (and in later discussions) to more carefully classify the schemata. A schema will be said to be defined on the set of positions {i1, . . ., ih} at which  . If  has k elements and we consider all schemata over V, i.e.,  , then there are kh distinct schemata defined on any given set of h £ l positions. Moreover, for any given set of h positions, every  is an instance of one of these kh schemata. That is, the set of schemata defined on a given set of positions partitions  , and each distinct set of positions gives rise to a different partition of . (For example, if V = {0, 1} and l = 4, the set of schemata defined on position 1 is  , where  abbreviates  etc. It is clear that every element in  begins either with the symbol 0 or else the symbol 1, hence the given set partitions . Similarly the set defined on position 2,  , partitions , and the set defined on positions 2 and 4,  is still a different partition of , a refinement of the one just previous.) There are  distinct ways of choosing h positions {1 £ i1 < i2 < ××××< ih£ l} along the l-tuple, and h can be any number between 1 and l. Thus there are  distinct partitions induced on a by these sets of schemata. It follows that any sequence of N trials of will be simultaneously distributed over each of these partitions. That is, each of the 2l sets of schemata defined on the 2l distinct choices of positions receives N trials. |
|
|
|
|
|
|
|
|
On the assumption that elements of are tried at random, uniformly (elements equally likely) and independently, we can use the Poisson distribution to determine the number of schemata receiving at least n < N trials. The basic parameter required is the average number of trials per schema for any set of schemata defined on h positions. The value of this parameter is just N/khsince there are khschemata defined on a fixed set of h positions. The Poisson distribution then gives |
|
|
|
|
|
|
|
|
as the proportion of schemata defined on the positions i1, . . ., ihand receiving at least n out of the N trials. |
|
|
|
|
|
|
|
|
This can be directly generalized to give a lower bound in the case where the distribution over is no longer uniform. Let  designate the fraction of schemata defined on i1, . . ., ih for which the probability of a trial is at least  , let gh be the proportion of the sets of schemata defined on h positions for which  and, finally, let g0 = minhgh. Then the expression above, by a simple manipulation, yields |
|
|
|
|
|
