Name
Title | ||
|---|---|---|
How fast does the stationary distribution of the Markov chain modelling EAs concentrate on the homogeneous populations for small mutation rate? |
Abstract | ||
|---|---|---|
One of the main difficulties faced when analyzing Markov chains modelling evolutionary algorithms is that their cardinality grows quite fast. A reasonable way to deal with this issue is to introduce an appropriate notion of a "coarse graining" or, in mathematical language, a quotient of such a Markov chain. The main topic of the current work is the construction of such a notion. We shell introduce a general construction of a quotient of an irreducible Markov chain with respect to an arbitrary equivalence relation on the state space. The stationary distribution of the quotient chain is "coherent" with the stationary dis- tribution of the original chain. Although the transition probabilities of the quo- tient chain depend on the stationary distribution of the original chain, in some cases we can still exploit the quotient construction to deduce some properties of the stationary distribution of the original chain. As an example we shell estab- lish some inequalities telling us how fast the stationary distribution of Markov chains modelling EAs concentrates on the homogenous populations as mutation rate converges to 0. |
Year | Venue | Keywords |
|---|---|---|
2006 | Theory of Evolutionary Algorithms | equivalence relation,stationary distribution,evolutionary algorithm,state space,transition probability,mutation rate,markov chain |
Field | DocType | Citations |
Applied mathematics,Discrete mathematics,Markov chain mixing time,Continuous-time Markov chain,Coupling from the past,Markov chain Monte Carlo,Markov chain,Discrete phase-type distribution,Stationary distribution,Absorbing Markov chain,Mathematics | Conference | 0 |
PageRank | References | Authors |
0.34 | 6 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Boris Mitavskiy | 1 | 109 | 11.06 |
| Jonathan E. Rowe | 2 | 458 | 56.35 |