Upper bound on the evolved fitness

I also calculate an upper bound for the fitness of the evolved libraries by using a theorem from the theory of error-correcting codes (1986). Assume that we distribute the A antibodies over the space of 2^L pathogen bit strings in such a way that each antibody a_i covers a set S_i of volume V_i, corresponding to the number of pathogens up to Hamming distance d from antibody a_i. Assume that all sets S_i are disjoint and of equal size. In the best situation, there exists a Hamming distance d such that the sets S_i together exactly cover the space of 2^L pathogens. Since

$$V_i = \sum_{h=0}^d {L \choose h},$$

this yields the inequality

$$A \sum_{h=0}^d {L \choose h} \leq 2^L,$$ (2.2)

In the theory of error-correcting codes, this inequality is known as the sphere-packing or Hamming bound. The library is "perfect" if equality holds. The fitness f_u of such a perfect library is given by

$$f_u = 1 - \frac{\sum_{i=0}^d i {L \choose i}}{\sum_{i=0}^d L {L \choose i}}.$$

However, it may be that a "perfect" library cannot be constructed. That is, there is no value of d for which the A disjoint Hamming distance d-balls around the antibodies cover the space completely. In this situation, we first determine the maximum value of d for which the inequality still holds. Each antibody will cover a ball of pathogens around itself, up to Hamming distance d. The rest of the pathogen strings, that do not fall in any of the A Hamming distance d-balls around the antibodies, will be at Hamming distance d+1 from at least one of the antibodies. Thus, given this value d, the upper bound on the fitness will be given by

$$f_u = \frac{A \sum_{i=0}^d (L - i){L \choose i} + \left(2^L - A \sum_{i=0}^d {L \choose i} \right)(L - (d+1))}{L 2^L}.$$