Hamming fitness is Binomial

• By Hamming fitness we mean one of the many common fitness functions where fitness is given by, running multiple tests.

  At the end of each test the actual output is compared with the target output for that test. The bigger the difference the worse the fitness.

  With Hamming fitness the difference is given by counting number of output bits which are different from the target.

  The total fitness value is given by summing the difference for each test.

• In the large reversible program limit, each permutation is equally likely. So for a given input each output is also equally likely.

  If the output is $m$ bits wide, then all values $0..2^{m}-1$ are equally likely and the Hamming distance (to any target value) is $\frac{1}{2}m$

• The complete output $N2^{N}$ bits must be a permutation. But we are only testing a fraction ($m$ bits of $N$) of the output lines and only $2^{n}$ of $2^{N}$ test cases.

• provided the number of outputs is small compared to the total number of wires, one each test, we may treat each output bit produced by a long random reversible program as being as likely to be set as to be clear.

  The fitness function tests $m2^{n}$ bits so the fitness is Binomial distributed with mean $\frac{1}{2}m2^{n}$ and standard deviation $\frac{1}{2}\sqrt{m2^{n}}$

  The chance of perfect solution is $2^{-m2^{n}}$

  The Binomial distribution can be approximated by the Normal distribution.