Name
Abstract | ||
|---|---|---|
A Computational This paper contributes to the study of nonlinear dynamical systems from a computational perspective. These systems are inherently more powerful than their linear counterparts (such as Markov chains), which have had a wide impact in Computer Science, and they seem likely to play an increasing role in future. However, there are as yet no general techniques available for handling the computational aspects of discrete nonlinear systems, and even the simplest examples seem very hard to analyze. We focus in this paper on a class of quadratic systems that are widely used as a model in population genetics and also in genetic algorithms. These systems describe a process where random matings occur between parental chromosomes via a mechanism known as “crossover”: i.e., children inherit pieces of genetic material from different parents according to some random rule. Our results concern two fundamental quantitative properties of crossover systems: 1. We develop a general technique for computing the rate of convergence to equilibrium. We apply this technique to obtain tight bounds on the rate of convergence in several cases of biological and computational interest. In general, we prove that these systems are “rapidly mixing”, in the sense that the convergence time is very small in comparison with the size of the state space. 2. We show that, for crossover systems, the classical quadratic system is a good model for the behavior of finite populations of small size. This stands in sharp contrast to recent results of Arora et al and Pudlak, who show that such a correspondence is unlikely to hold for general quadratic systems. % ? \ A QDS is symmetric if the probabilities UUW= satisfy the symmet~y conditions /3UvWz = PUUUE = ~~~~~, and the reverslbdlty condltlon PUUYC. = @Wzl’t,. Symm~try of QDSS is analogous to reverslblhty of Markov chains. The above framework is quite general, and captures several important systems from the natural sciences: e.g., Bolt.zrnann’s model of an ideal gas (where the types are velocities of gas molecules, and interactions are collisions between them) [17]; the Hardy- Weinberg model of population genetics (where the types are the genotypes of some species, and interactions are matings be |
Year | DOI | Venue |
|---|---|---|
1998 | 3.0.CO;2-W" target="_self" class="small-link-text"10.1002/(SICI)1098-2418(199807)12:43.0.CO;2-W | Random Struct. Algorithms |
Keywords | Field | DocType |
population genetics | Combinatorics,Population genetics,Mathematics | Journal |
Volume | Issue | ISSN |
12 | 4 | 1042-9832 |
ISBN | Citations | PageRank |
0-89791-718-9 | 38 | 4.80 |
References | Authors | |
8 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yuval Rabani | 1 | 2265 | 274.98 |
| Yuri Rabinovicht | 2 | 38 | 4.80 |
| Alistair Sinclair | 3 | 1506 | 308.40 |