QE2013_AC-3_ECE580-1
(i)
Solution:
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} $
(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 $
Solution 2:
Since the final range is $ 1.0 $ and the initial range is $ 20 $, we can say $ \frac{2}{F_{N+1}} \le \frac{1.0}{20} or equivalently F_{N+1}} \ge 40 $ From the inequality, we get $ F_{N+1} \ge 40 , so N+1=9 $. Therefore the minimum number of iteration is N-1=7
$ \color{blue}\text{Related Problem: } $ $ \text{Find the final uncertainty range using the Fibonacci method after 6 iterations } $ $ \text{Assume the last step has the form: } 1-\rho_{N-1}=\frac{F_2}{F_3}=\frac{2}{3} \text{The initial range is 10} $
Solution:
$ \text{The reduction factor is } \frac{F_{2}}{F_{7+1}} =\frac{1}{34} \text{, So the final range is } 10 \frac{F_{2}}{F_{7+1}}= \frac{5}{17} $
