RIGOROUS RESULTS FOR THE NK MODEL

Richard Durrett and Vlada Limic

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\ge 1$ 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.