QE2013_AC-3_ECE580-2
(i)
Solution 1:
The conditions for a chromosome from H to be destroyed are:
1. It is chosen for crossover. Probability = $ \frac{1}{2} $.
2. The crossover position is not the last symbol. Otherwise only the last symbol can potentially change and the chromosome will still be in schema H. Probability = $ \frac{5}{6} $.
3. The other chromosome to crossover has a structure such that the chromosome from H will be destroyed after crossover. For example: if the other chromosome is * * * * * 1 *. This probability cannot be determined from the given information, as it depends on the distribution of other chromosomes. Therefore it has an upperbound of 1.
A chromosome from H is destroyed if and only if the 3 conditions above all occur. Therefore
$ P(destroyed)\le \frac{1}{2} \times \frac{5}{6} \times 1 = \frac{5}{12} $
The upper bound is $ \frac{5}{12} $
Solution 2:
$ D_c(H) \le p_c \frac{l(H)}{L-1} = 0.5 \times \frac{6-2}{7-1} = 0.5 \times \frac{4}{6} = 0.33 $
(ii)
Solution:
The schema will be destroyed if and only if the 2nd or 4th symbol change. Equivalently, the schema will not be destroyed if and only if both 2nd and the 4th symbols stay the same. As those events are independent:
$ P(Not\ destroyed) = P(2nd\ symbol\ does\ not\ change) \times P(4th\ symbol\ does\ not\ change) $
$ = (1-0.1)\times(1-0.1) = 0.81 $
Therefore
$ P(destroyed) = 1 - 0.81 = 0.19 $
Solution 2:
$ D_m(H) = 1 - S_m(H) = 1 - (1 - p_m)^{o(H)} = 1 - (1-0.1)^{7-5} = 1 - 0.9^2 = 0.19 $
(p. 294) lemma 14.2.3
Comment: Solution 2 uses given formulas and is much shorter. The results from (i) are different as solution 1 used 5/6 where solution 2 used 4/6. Solution 2 is the right answer.
Back to QE2013 AC-3 ECE580
