Abstract. Motivated by the problem of the evolution of DNA sequences, Stuart Kauffman and Simon Levin (1987) introduced a model in which fitnesses were assigned to strings of 0's and 1's of length N based on the values observed in a sliding window of length K+1. When K > 0 the landscape is quite complicated with many local maxima. Its properties have been extensively investigated by simulation but little is known rigorously about its properties except in the case K=N-1. Here, we prove results about the number of local maxima, their heights, and the height of the global maximum. Our main tool is the theory of (substochastic) Harris chains.
Get a copy of the paper in Postscript
To illustrate our results we will show simulation results for the case N=96, K=1, with the uniform distribution. 96 may not sound very large but 296 is about 1029 so one has to do something slightly more sophisticated that go trhough the space and check each point to see if it is a local maximum. The first three graphs are for 1000 repetitions. In these and the fourth situation our results show that there is a central limit theorem for the quantity of interest.
Heights of randomly chosen local maxima, one from each run.
Heights of the global maximum.
Log base 2 of the number of local maxima. Note that the number ranges from a few hundred to tens of millions.
This graph shows the heights of local maxima in one simulation run. Note that in contrast to the first three cases the fit to the normal is very good.
This graph shows the joint distribution of the heights of the local maxima. Note that althpough two typical points in the space differ by 48 units, the furthest local maximum is 43 units from the global maximum. Here the shading indicates the number of local maxima in each category and the distance from the global maximum.