Rigorous results for the NK model

• 成果类型: Article
• 署名作者: Durrett, R; Limic, V
• 署名单位: Cornell University; University of British Columbia
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/aop/1068646364
• 发表日期: 2003
• 页码: 1713-1753
• 关键词: rugged landscapes; markov-chains; EVOLUTION; walks

摘要

Motivated by the problem of the evolution of DNA sequences, Kauffman and Levin 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 greater than or equal to 1, the landscape is quite complicated with many local maxima. Its properties have been extensively investigated by simulation but until our work and the independent investigations of Evans and Steinsaltz little was 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.