Name
Title | ||
|---|---|---|
Exploiting quotients of markov chains to derive properties of the stationary distribution of the markov chain associated to an evolutionary algorithm |
Abstract | ||
|---|---|---|
In this work, a method is presented for analysis of Markov chains modeling evolutionary algorithms through use of a suitable quotient construction. Such a notion of quotient of a Markov chain is frequently referred to as “coarse graining” in the evolutionary computation literature. We shall discuss the 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 distribution of the original chain. Although the transition probabilities of the quotient chain depend on the stationary distribution of the original chain, we can still exploit the quotient construction to deduce some relevant properties of the stationary distribution of the original chain. As one application, we shall establish inequalities that describe how fast the stationary distribution of Markov chains modelling evolutionary algorithms concentrates on the uniform populations as the mutation rate converges to 0. Further applications are discussed. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1007/11903697_91 | SEAL |
Keywords | Field | DocType |
quotient construction,stationary distribution,markov chain,quotient chain,arbitrary equivalence relation,suitable quotient construction,irreducible markov chain,exploiting quotient,evolutionary computation literature,evolutionary algorithm,original chain,equivalence relation,mutation rate,state space,evolutionary computing,transition probability,markov chain model | Applied mathematics,Mathematical optimization,Markov chain mixing time,Combinatorics,Continuous-time Markov chain,Coupling from the past,Markov property,Markov chain Monte Carlo,Markov chain,Balance equation,Stationary distribution,Mathematics | Conference |
Volume | ISSN | ISBN |
4247 | 0302-9743 | 3-540-47331-9 |
Citations | PageRank | References |
6 | 0.89 | 8 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Boris Mitavskiy | 1 | 109 | 11.06 |
| Jonathan E. Rowe | 2 | 458 | 56.35 |
| Alden Wright | 3 | 24 | 2.69 |
| Lothar M. Schmitt | 4 | 116 | 12.00 |