1 INTRODUCTION

Genetic algorithms (GAs) are stochastic optimization algorithms designed to solve hard, typically NP-complete, problems (Goldberg, 1989), (Bäck, 1996), (Vose, 1999). Introduced by Holland (Holland, 1975), these algorithms mimick the genetic mechanisms of natural evolution. An initial random population of potential solutions is evolved by applying genetically inspired operators: mutation, crossover and selection. With time, “better” solutions emerge in the population. The quality of a solution is evaluated in terms of a fitness function. The original optimization problem now translates into finding a global optimum of this function. Note that in general, the convergence of a GA to an optimal solution is not guaranteed. Only few rigorous mathematical results ensuring convergence of GAs are available.

For the past ten years, increasing efforts have been put into providing rigorous mathematical analyses of GAs (Rawlins, 1991), (Whitley, 1993), (Whitley, 1995), (Belew, 1997), (Banzhaf and Reeves, 1999). Towards this end, GAs have been modeled with Markov chains (Nix and Vose, 1992), (Rudolph, 1994). Application of Markov chain techniques has proved very successful in the study of simulated annealing (SA). This approach has produced an extensive mathematical literature describing the dynamics and investigating convergence properties of SA (Aarts and Laarhoven, 1987), (Aarts and Korst, 1988), (Hajek, 1988), (Catoni, 1992), (Deuschel and Mazza, 1994). It was therefore natural to try to carry over SA formalism to GAs. This was to our knowledge initiated by Goldberg (Goldberg, 1990), who borrowed the notions of thermal equilibrium and Boltzmann distribution from SA and adapted them to GA practice. A theoretical basis was later elaborated by Davis for simple GAs (Davis and Principe, 1991). His approach was further developed by Suzuki and led to a convergence result (Suzuki, 1997).

We believe the first mathematically well-founded convergence results for GAs were obtained by Cerf (Cerf, 1996a), (Cerf, 1996b), (Cerf, 1998), who constructed an asymptotic theory for the simple GA comparable in scope to that of SA. The asymptotic dynamics was investigated using the powerful tools developed by Freidlin and Wentzell (Freidlin and Wentzell, 1984) for the study of random perturbations of dynamical systems. Cerf’s pioneering work takes place in the wider context of generalized simulated annealing, which was defined by Trouvé (Trouvé, 1992a), (Trouvé, 1992b), extending results of Catoni for SA (Catoni, 1992). The dynamics for simulations in various contexts, like statistical mechanics, image processing, neural computing and optimization, can be described in this setting.

Complementary to the asymptotic approach, novel work has been achieved by Rabinovich and Wigderson in providing an original mathematical analysis of a crossover–selection algorithm (Rabinovich and Wigderson, 1999). Both analyses shed some light on the behavior of GAs. Let us still quote a paper by François in which he proves convergence of an alternate mutation-selection algorithm (François, 1998), also within the framework of generalized simulated annealing.

In this contribution, we address the problem of optimizing a fitness function $F:\mathrm{\Omega }\to {ℛ}_{>0}$ on the space Ω of binary strings of length l (Ω is the l–dimensional hypercube). We apply to this problem a mutation-selection algorithm, which was introduced in a slightly different form by Davis (Davis and Principe, 1991) and extensively studied in greater generality by Cerf (Cerf, 1996a), (Cerf, 1996b) (the difference resides in the Boltzmann selection to which we add a noise component). We will show that this mutation–selection algorithm is asymptotically equivalent to SA. This emphasizes the importance of the crossover operator for GAs. Our treatment also takes place within the framework defined by the theory of Freidlin–Wentzell for random perturbation of dynamical systems. The main mathematical object consists of irreducible Markov kernels with exponentially vanishing coefficients.

The paper is organized as follows. In section 2 we describe the mutation–selection algorithm and state some convergence results. The proofs of these results are sketched in section 3 where we perform a large deviation analysis of the algorithm. The algorithm is run in three different ways depending on how we let the temperature for the Boltzmann selection and the mutation probability go to zero. We finally draw some conclusions in section 4.

2 MUTATION–SELECTION ALGORITHM

We now describe a two–operator mutation-selection algorithm on the search space Ω^p of populations consisting of p individuals (Ω = {0,1}^l).

Mutation acts as in classical GAs. Each bit of an individual in Ω independently flips with probability 0 < τ < 1. At the population level, all individuals mutate independently of each other. Mutation is fitness–independent and operates as a blind search over Ω.^p.

We consider a modified version of the selection procedure of classical GAs. We begin by adding some noise g(ξ,.) to log(F(ξ)) for technical reasons. It helps lift the degeneracy over the global maxima set of F. The real-valued random variables g(ξ,.), indexed by ξ Ω, are defined on a sample space I (e.g. a subinterval of ). They are independent identically distributed (i.i.d.) with mean zero and satisfy

$\left|g\left(\xi ,\mathrm{\omega }\right)\right|<\frac{1}{2}min\left\{\left|\mathit{log}\left(\frac{F\left({\xi }_1\right)}{F\left({\xi }_2\right)}\right)\right|:F\left({\xi }_1\right)\ne F\left({\xi }_2\right),{\xi }_1,{\xi }_2\in \mathrm{\Omega }\right\},\forall \omega \in I\text{.}$

Hence the random variables f(ξ,.) = log(F(ξ)) + g(ξ,.) have mean log(F(ξ)) and the function f(.,ω) has the same optima set as F by assumption (1), but a unique global maximum for almost every sample point ω I.

Fix a point ω in the sample space I. Given a population x = (x₁, …, x_p) Ω^P of size p, individual x_i is selected under a Gibbs distribution (Boltzmann selection) with probability

$\frac{exp\left(\beta f\left(x_i,\mathrm{\omega }\right)\right)}{{\displaystyle {\sum }_{j=1}^{p}exp\left(\beta f\left(x_j,\mathrm{\omega }\right)\right)}}\text{,}$

from population x. The parameter β ≥ 0 corresponds to an inverse temperature as in simulated annealing and controls the selective pressure. Note that if we remove the noise and set β = 1, the above selection procedure reduces to classical GA fitness-proportional selection.

The algorithm is run only after the fitness function has been perturbed by the noise component. For any given sample point ω and τ, β fixed, we get an irreducible Markov chain on the search space Ω^p by successively applying mutation and selection. Denote by μ_{τ, β}^ω its stationary probability distribution and by μ_{τ, β} the probability distribution obtained after averaging the μ_{τ, β}^ω ' s over the sample space.

Before stating results, we introduce some notations and terminology. We define the set of uniform populations

${\mathrm{\Omega }}_{=}=\left\{\left(x_1,\dots ,x_p\right)\in {\mathrm{\Omega }}^p:x_1=\cdot \cdot \cdot =x_p\right\}$

and the set of populations consisting only of maximal fitness individuals

$F_{\mathit{max}}=\left\{\left(x_1,\dots ,x_p\right)\in {\mathrm{\Omega }}^p:F\left(x_i\right)=\underset{\xi \in \mathrm{\Omega }}{max}F\left(\xi \right)\right\}\text{.}$

We also recall that the support of a probability distribution on Ω^p consists of all populations having positive probability.

Each theorem stated below corresponds to a specific way of running the mutation-selection algorithm.

Theorem 1 Let β > 0 be fixed. Then, as τ → 0, the probability distribution μ_{τ, β} converges to a probability distribution μ_{0, β} with support(μ_0,β) = Ω₌. Moreover, the limit probability distribution lim_β→∞ μ_{0, β} concentrates on Ω₌ ∩ F_max.

The first assertion in theorem 1 was already obtained by Davis (Davis and Principe, 1991) and the second by Suzuki (Suzuki, 1997) by directly analyzing the transition probabilities of the Markov chain. However their algorithm did not include the added noise component. We give a different proof in the next section.

Theorem 1 implies that, for β, τ both fixed and τ ≈ 0, the mutation-selection algorithm concentrates on a neighboorhood of Ω₌ in Ω^p. Hence a run has a positive probability of ending on any population in Ω₌. The hope remains that the stationary probability distribution has a peak on Ω₌ ∩ F_max. This is actually the case, since the probability distribution lim_β→∞ concentrates on Ω₌ ∩ F_max. The latter statement can be obtained as a consequence of theorem 3.

Notice that GAs are usually run with τ ≈ 0. We believe that the crossover operator improves the convergence speed, but probably not the shape of the stationary probability distribution.

Theorem 2 Let 0 < τ < 1 be fixed. Then, as β → ∞, the probability distribution μ_{τ, β} converges to a probability distribution μ_τ,∞ with support(μ_τ,∞).= Ω₌. Moreover, the limit probability distribution lim_τ→0 μ_τ,∞ concentrates on Ω=.

Theorem 2 shows that, in terms of probability distribution support, increasing the selective pressure is equivalent to diminishing the mutation probability. However, lim_τ→0 μ_τ,∞ remains concentrated on Ω₌.

Consequently, it is a natural idea to link the mutation probability τ to the inverse temperature β. The algorithm becomes a simulated annealing process: the intensity of mutation is decreased, while selection becomes stronger. This actually ensures convergence of the algorithm to an optimal solution.

Theorem 3 Let τ = τ (, κ, β) = exp(–κβ) with 0 < < 1 and κ > 0. Then, for κ large enough, the probability distribution μ_{τ, β} converges, as β → ∞, to the uniform probability distribution over Ω₌ ∩ F_max. Asymptotically, the algorithm behaves like simulated annealing on Ω₌ with energy function –p log F.

Notice that the initial mutation probability does not influence the convergence.

The first assertion in theorem 3 was obtained by Cerf (Cerf, 1996a), (Cerf, 1996b), in a much more general setting, but again with a mutation-selection algorithm not including the added noise component. However, we hope that our proof, presented below in the simple case of binary strings, is more intuitive and easier to grasp. Maybe will it illustrate the importance of Cerf’s work and the richness of the Freidlin–Wentzell theory.

3 LARGE DEVIATION ANALYSIS

In analogy with the original treatment of simulated annealing, we prefer to deal with U^ω = –f(.,ω) the energy function. The optimization problem now amounts to finding the global minima set of Uω which can be thought as the set of fundamental states of the energy function Uω. For almost every ω, Uω has a unique fundamental state.

Denote by ρ(.,.) the Hamming distance on Ω and set

$d\left(x,y\right)={\displaystyle \sum _{i=1}^p\rho \left(x_i,y_i\right)}\text{,}$

with x = (x₁,…, x_p) and y = (y₁,…, y_p) populations in Ω^p; d(.,.) is a metric on Ω^p.

Let Mτ be the transition matrix for the mutation process on Ω^p. The probability that a population x Ω^p is transformed into y Ω^p by mutation is

$M_{\tau }\left(x,y\right)={\tau }^{d\left(x,y\right)}{\left(1-\tau \right)}^{ip-d\left(x,y\right)}\text{.}$

We define the partial order relation on Ω^p by:

$x\prec y\iff x_i\in \left\{y_1,\dots ,y_p\right\},\forall i\in \left\{1,\dots ,p\right\}\text{.}$

In words, x y if and only if all individuals in population x belong to population y.

Let S_β^ω be the transition matrix for the selection process on Ω^p. The probability that a population x ∈ Ω^p is transformed into y ∈ Ω^p by selection (see (2)) is given by

$S_{\beta }^{\omega }\left(x,y\right)=\left\{\begin{array}{cc}\hfill \frac{exp\left(-\beta {\displaystyle {\sum }_{i=1}^p{U}^{\omega }}\left(y_i\right)\right)}{\left({\displaystyle {\sum }_{i=1}^{p}exp(-\beta U^{\omega }\left(x_i\right)}\right)){}^p}\hfill & \hfill \mathrm{if}x\succ y,\hfill \\ 0\hfill & \hfill \mathrm{if}x\nsucc y\text{.}\hfill \end{array}\right.$

The transition matrix of the Markov chain corresponding to our mutation-selection algorithm is $S_{\beta }^{\omega }\circ M_{\tau }$. From eqs. (5) and (6), we compute the transition probabilities

$\begin{array}{l}{S}_{\beta }^{\omega }\circ M_{\tau }\left(x,y\right)={\displaystyle \sum _{z\succ y}{M}_{\tau }}\left(x,z\right)S_{\beta }^{\omega }\left(z,y\right)\\ ={{\displaystyle \sum _{z\succ y}{\tau }^{d\left(x,z\right)}\left(1-\tau \right)}}^{lp-d\left(x,z\right)}\frac{exp\left(-\beta {\displaystyle {\sum }_{i=1}^p{U}^{\omega }\left(y_i\right)}\right)}{{\left({\displaystyle {\sum }_{i=1}^{p}exp\left(-\beta U^{\omega }\left(z_i\right)\right)}\right)}^p}\text{.}\end{array}$

The mutation and selection processes are simple to treat on their own. However, their combined effect proves to be more complicated. A way of dealing with this increase in complexity is to consider these processes as asymptotically vanishing perturbations of a simple random process. We study three cases. In the first, mutation acts as the perturbation, while selection plays this role in the second. In the third case, the combination of mutation and selection acts as a perturbation of a simple selection scheme, namely equiprobable selection among the best individuals in the current population.

We will now compute three different communication cost functions corresponding to various ways of running the mutation-selection algorithm. The communication cost reflects the asymptotic difficulty for passing from one population to another under the considered random process.

Write τ = τ(α) = e^−α with α > 0. Asymptotically, for β fixed and α → ∞, eq. (7) yields

$\underset{\alpha \to \infty }{lim}-\frac{1}{\alpha }log\left(S_{\beta }^{\omega }\circ M_{\tau \left(\alpha \right)}\left(x,y\right)\right)={\displaystyle \underset{z\succ y}{\min }}d\left(x,z\right)\text{.}$

Henceforth, we will use the asymptotic notation

$S_{\beta }^{\omega }\circ M_{\tau \left(\alpha \right)}\left(x,y\right)\asymp \mathit{exp}\left(-\alpha \underset{z\succ y}{min}d\left(x,z\right)\right)\text{.}$

The communication cost for asymptotically vanishing mutation is given by

$V^M\left(x\to y\right)={\displaystyle \underset{z\succ y}{\min }}d\left(x,y\right)\text{.}$

Define the total energy function u^ω: Ω^p → R by

$u^{\omega }\left(y\right)={\displaystyle \sum _{i=1}^p{U}^{\omega }}\left(y_i\right)\text{,}$

and notice that min_u z u^ω(u) = p min_1 ≤i≤p U^ω (z_i). Asymptotically, for τ fixed and β → ∞, eq. (7) yields

$S_{\beta }^{\omega }\circ M_{\tau }\left(x,y\right)\asymp exp\left(-\beta {\displaystyle \underset{z\succ y}{min}}\left(u^{\mathrm{\omega }}\left(y\right)-{\displaystyle \underset{u\prec z}{min}}{u}^{\mathrm{\omega }}\left(v\right)\right)\right)\text{.}$

The associated communication cost is given by

$V^{S,\omega }\left(x\to y\right)={\displaystyle \underset{z\succ y}{min}}\left(u^{\omega }\left(y\right)-{\displaystyle \underset{v\prec z}{min}}{u}^{\omega }\left(v\right)\right)\text{.}$

Next, let τ = τ(∈, κ, β) = ∈ exp(-κβ) with 0 < ∈ < 1 and κ > 0. Asymptotically, for , κ fixed and β → ∞, eq. (7) yields

$S_{\beta }^{\omega }\circ M_{\tau \left(\in ,k,\beta \right)}\left(x,y\right)\asymp exp\left(-\beta {\displaystyle \underset{z\succ y}{min}}\left(kd\left(x,y\right)+u^{\mathrm{\omega }}\left(y\right)-{\displaystyle \underset{u\prec z}{min}}{u}^{\mathrm{\omega }}\left(v\right)\right)\right)\text{.}$

The associated communication cost is given by

$V_k^{MS,\mathrm{\omega }}\left(x\to y\right)={\displaystyle \underset{z\succ y}{min}}\left(kd\left(x,z\right)+u^{\mathrm{\omega }}\left(y\right)-{\displaystyle \underset{u\succ z}{min}}{u}^{\mathrm{\omega }}\left(v\right)\right)\text{.}$

3.4 AN ANNEALING PROCESS

We go on to sketch the proof of theorem 3.

We begin by defining

$\mathrm{\Delta }=\underset{\mathrm{\xi }\in \mathrm{\Omega }}{max}{U}^{\omega }\left(\xi \right)-\underset{\mathrm{\xi }\in \mathrm{\Omega }}{min}{U}^{\omega }\left(\xi \right)$

the energy barrier. Until the end of this subsection, we assume that the exponential decrease rate κ of the mutation probability, is greater than p∆.

Let x y. Taking z = x, we get

$\kappa d\left(x,z\right)+{\mathcal{U}}^{\mathrm{\omega }}\left(y\right)-\underset{v\prec z}{min}{\mathcal{U}}^{\mathrm{\omega }}\left(v\right)={\mathcal{U}}^{\mathrm{\omega }}\left(y\right)-\underset{v\prec x}{\min }{\mathcal{U}}^{\mathrm{\omega }}\left(v\right)$

For z ≠ x, d(x, z)≥1 and therefore,

$\kappa d\left(x,z\right)+{\mathcal{U}}^{\mathrm{\omega }}\left(y\right)-\underset{v\prec z}{min}{\mathcal{U}}^{\mathrm{\omega }}\left(v\right)={\mathcal{U}}^{\mathrm{\omega }}\left(y\right)-\underset{v\prec x}{\min }{\mathcal{U}}^{\mathrm{\omega }}\left(v\right)$

Consequently, eqs. (15) and (16) above imply that, in (10), the minimum over all z y is realized by z = x. Comparing with (9), we get

$V_{\kappa }^{MS,\omega }\left(x\to y\right)=V^{S,\omega }\left(x\to y\right)$

for y x.

Let x ∈ Ω^P ΩUω. There exists y ∈ Ω_Uω, y x, such that $V_{\kappa }^{MS,\omega }\left(x\to y\right)=0$ Just recall that $V^{S,\omega }\left(x\to y\right)=0$ for any y ∈ Ω_U^ω (see eq. (12)).

However, for x ∈ Ω_U^ω, we have $V_{\kappa }^{MS,\omega }\left(x\to y\right)=0$ for all y ∈ Ω^P ΩUω This follows from eqs. (13) and (17).

Applying lemma 5 to S = Ω^P and S_– = ΩUω for the communication cost function $V_{\kappa }^{MS,\omega }\left(x\to y\right)=0$ we can restrict the dynamics from Ω^P onto ΩUω Since the probability that Ω_Uω Ω₌ ≠ ∅ is zero, we will assume that Ω₌ = Ω_Uω

Let (ξ),(η) ∈ Ω₌ with ξ ≠ η. Naturally (ξ) (η) and (η) (ξ) Now let $\stackrel{⌢}{z}$ = (ξ,…, ξ, η, ξ,…, ξ) Then, if z (η) is not of the form $\stackrel{⌢}{z}$,

$\begin{array}{l}\kappa d\left(\left(\mathrm{\xi }\right),z\right)\ge \kappa \left(\rho \left(\mathrm{\xi },\eta \right)+1\right)\\ >\kappa d\left(\left(\xi \right),\widehat{z}\right)+{\mathcal{U}}^{\omega }\left(\left(\eta \right)\right)-\underset{v\prec \widehat{z}}{min}{\mathcal{U}}^{\omega }\left(v\right)\text{,}\end{array}$

where we used the assumption κ > p∆ and eq. (14). Hence,

$\begin{array}{l}{V}_{\kappa }^{MS,\omega }\left(\left(\mathrm{\xi }\right)\to \left(\eta \right)\right)=\kappa d\left(\left(\mathrm{\xi }\right),\widehat{\mathrm{z}}\right)+{\mathcal{U}}^{\omega }\left(\left(\eta \right)\right)-\underset{v\prec \widehat{z}}{min}{\mathcal{U}}^{\omega }\left(v\right)\\ =\kappa \rho \left(\mathrm{\xi },\eta \right)+p{U}^{\omega }\left(\eta \right)-p\underset{1\le i\le p}{min}{U}^{\omega }\left({\widehat{z}}_i\right)\\ =\kappa \rho \left(\xi ,\eta \right)+p{U}^{\omega }\left(\eta \right)-pmin\left(U^{\omega }\left(\xi \right),U^{\omega }\left(\eta \right)\right)\end{array}$

and thus

$V_{\kappa }^{MS,\omega }\left(\left(\xi \right)\to \left(\eta \right)\right)=\kappa \rho \left(\xi ,\eta \right)+p\left(U^{\omega }\left(\eta \right)-U^{\omega }\left(\xi \right)\right)+$

Therefore,

$\begin{array}{l}{\mathcal{U}}^{\omega }\left(\left(\xi \right)\right)-{\mathcal{U}}^{\omega }\left(\left(\eta \right)\right)=p\left(U^{\omega }\left(\xi \right)-U^{\omega }\left(\eta \right)\right)\\ =V_{\kappa }^{MS,\omega }\left(\left(\eta \right)\to \left(\xi \right)\right)-V_{\kappa }^{MS,\omega }\left(\left(\xi \right)\to \left(\eta \right)\right)\end{array}$

implying that the energy function pUω is a potential on Ω₌

For almost every ω, Ω₌ = Ω_Uω and thus Uωhas a unique minimum. As a consequence of lemma 4, the probability distribution μ_{τ(ε,κ, β),β}^ω converges for almost every ω, as β→∞, to a point mass on the unique minimum of Uω. The latter is a maximum of the fitness function. Finally, since the random variables $\mathsf{g}\left(\mathrm{\xi },\text{.}\right)$’s are i.i.d., the minimum of Uω can be equiprobably any maximum of the fitness function. Therefore, averaging over w yields a uniform probability distribution over the set of global maxima of the fitness function (seen as a subset of Ω_=.

4 CONCLUSION

The mutation-selection algorithm considered in this work helps us improve our understanding of GAs. It differs slightly from the algorithm considered by Davis (Davis and Principe, 1991) and Cerf (Cerf, 1996a), (Cerf, 1996b), because we added a noise component in the Boltzmann selection. This difference is however only technical. We studied this two-operator algorithm by resorting to the theory of Freidlin–Wentzell and by making use of the approach developed in (Deuschel and Mazza, 1994).

The first result (theorem 1) explains the behavior of the algorithm for small mutation probability τ ≈ 0. Under this condition, the algorithm is forced to narrow its search to a neighborhood in Ω^P of the set of uniform population Ω₌ (defined in (3)). The latter set is 1–dimensional and corresponds to the diagonal of the search space Ω^P. GAs are usually run with τ ≈ 0. Setting β = 1 and removing the noise component, our selection procedure (see (2)) reduces to classical GA fitness-proportional selection. Hence, we can infer how the combined effect of a low mutation probability and a comparatively strong selection, as in classical GAs, removes diversity from the populations in the long–run. The second result (theorem 2) shows that the effect of increasing the selective pressure is similar, in terms of restricting the search, to lowering the mutation probability.

Since gradually decreasing τ to zero and then letting β tend to infinity, actually constrains the search to the set of maximal fitness solutions in Ω₌, it was natural to link mutation probability τ and selective pressure β. Theorem 3 shows that, by exponentially decreasing τ with β, the algorithm behaves like simulated annealing on Ω₌ with energy function pU. This procedure ensures convergence to an optimal solution in the limit β→∞. Therefore, if we fix β large enough and choose τ accordingly (see theorem 3), the algorithm will end up, in the long–run, in a neighborhood of the set of maximal fitness solutions in i2 =. Of course, the convergence performances of the algorithm will be no better than those of simulated annealing. In practical situations, the annealed version of the mutation-selection algorithm should be implemented using a cooling schedule of the form β ~ log n, where n is the generation number, as it is the case for simulated annealing. Of course, parameters like the initial temperature and initial mutation probability as well as the exponential rate κ for τ must be set empirically. Prior knowledge about the energy barrier ∆ (see (14)) would yield the estimate κ ≈ p∆, where p is the population size.

The most interesting question arises in the comparison of the mutation–selection algorithm with classical GAs. Crossover is the distinctive feature between this algorithm and GAs. A generation in a GA is the succession of mutation, crossover and selection. From the considerations of the previous paragraph, we understand more clearly the role of crossover. The latter operator is expected to speed up the search, provided it is not fitness–decreasing on average.

More precisely, the search proceeds in successive stages. First it progresses towards the set Ω₌. On Ω₌, it converges towards the optimal set Ω₌ ∩ F_max (see (4)). For GAs, crossover is expected to speed up the preliminary convergence stage towards Ω₌, if on average the mean fitness of the offsprings is not smaller than for the parents. However, populations in Ω₌ are invariant under its action. Therefore, on Ω₌, the GA performances are similar to those of simulated annealing.

Finally, we did not study the inhomogeneous Markov chain. It would be interesting to investigate finite time convergence and convergence rates.

APPENDIX

In this appendix, we introduce some notions from the theory of Freidlin–Wentzell (Freidlin and Wentzell, 1984).

As in subsection 3.1, consider a family of Markov chains on a finite set S, indexed by a real parameter α > 0, with irreducible transition matrix {qα (x,y)}_{x,y s} satisfying

$q_{\alpha }\left(x,y\right)\asymp exp\left(-\alpha V\left(x\to y\right)\right),\begin{array}{cc}\hfill \hfill & \hfill x,y\in S\text{,}\hfill \end{array}$

where 0 ≤ V (x → y) ≤ ∞ is the communication cost function. Let μα denote the stationary probability distribution on S associated to {q_α(x, y)}x, y S and μ_∞= lim_α→∞ μ_α

Let us consider the elements of S as the vertices of the complete oriented graph G on |S| vertices. A spanning tree of G pointing at x S is a subtree T of G such that

1. S is the vertex set of T,

2. for every y S, there is a directed path from y to x.

Denote by G(x) the set of all spanning trees of G pointing at x ∈ S and define

$\begin{array}{l}V\left(\mathrm{\gamma }\right)={\displaystyle \sum _{\left(y\to z\right)\in \mathrm{\gamma }}V(y\to z}),\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{\gamma }\in G\left(x\right),\\ V\left(x\right)=\underset{\mathrm{\gamma }\in G\left(x\right)}{min}V\left(\mathrm{\gamma }\right),\\ V_{\min }=\underset{x\in S}{min}V\left(x\right)\end{array}$

The stationary probability distribution μ_α can be estimated in terms of the spanning trees defined above. This is formulated in the result of Freidlin and Wentzell (Freidlin and Wentzell, 1984, lemma 3.1, p.177) stated below.

Lemma 6 We have the following representation formula for μ_α:

${\mu }_{\mathrm{\alpha }}\left(x\right)\equiv \frac{Q_{\mathrm{\alpha }}\left(x\right)}{{\displaystyle \sum _{x^{\prime }\in S}{Q}_{\mathrm{\alpha }}\left(x^{\prime }\right)}},\forall x\in S\text{,}$

$\mathit{where}{Q}_{\mathrm{\alpha }}\left(x\right)={\displaystyle \sum _{\mathrm{\gamma }\in G\left(x\right)}{\displaystyle \prod _{\left(y\to z\right)\in \mathrm{\gamma }}{\mathrm{q}}_{\mathrm{\alpha }}}}\left(y,z\right)\text{.}$

Moreover,

${\mu }_{\mathrm{\alpha }}\left(x\right)\asymp exp\left(-\mathrm{\alpha }\left(V\left(x\right)-V_{\min }\right)\right)\text{.}$

As a corollary to this lemma, we get

$\mathit{support}\left({\mu }_{\infty }\right)=\{x\in S:V\left(x\right)=V_{\min }$

from (18).

The next lemma is lemma 4 of subsection 3.1 and can be found in (Deuschel and Mazza, 1994). We reproduce the proof here for the sake of clarity.

Lemma 7 Assume there is a potential ψ: S→  for the communication cost function V(x —> y). Then

$\mathit{support}\left({\mu }_{\infty }\right)=\left\{x\in S:\mathrm{\psi }\left(x\right)=\underset{y\in S}{min}\mathrm{\psi }\left(y\right)\right\}$

Proof: Let x,y ∈ S.For an arbitrary spanning tree γ ∈ G(x), let ${\mathsf{g}}_{yx}$ be the unique geodesic of γ starting at y and ending at x. Define a mapping R: G(x) → G(y) by R(γ) = (γ ${\mathsf{g}}_{yx}$) ∪ ${\mathsf{g}}_{xy}$, where ${\mathsf{g}}_{xy}$ is just the reversed geodesic from x to y. This mapping R is well–defined and onto. Moreover,

$\begin{array}{ll}V\left(R\left(t\right)\right)\hfill & =V\left(\mathrm{\gamma }\right)-V\left({\mathsf{g}}_{yx}\right)+V\left({\mathsf{g}}_{xy}\right)\hfill \\ \hfill & =V\left(\mathrm{\gamma }\right)+{\displaystyle \sum _{\left(e^{-}\to e^{+}\right)\in {\mathsf{g}}_{xy}}(V\left(e^{-}\to e^{+}\right)-V(e^{+}\to e^{-}}\left)\right)\hfill \\ \hfill & =V\left(\mathrm{\gamma }\right)+{\displaystyle \sum _{\left(e^{-}\to e^{+}\right)\in {\mathsf{g}}_{xy}}(\mathrm{\psi }}\left(e^{+}\right)-\mathrm{\psi }\left({\mathrm{e}}^{‐}\right))\hfill \end{array}$

which implies V(R(γ)) = V(γ) + ψ(y) – ψ (x) for any γ ∈ G(x) It follows that

$\begin{array}{ll}V\left(y\right)\hfill & =\underset{\overline{\mathrm{\gamma }}\in G\left(y\right)}{min}V\left(\overline{\mathrm{\gamma }}\right)=\underset{\mathrm{\gamma }\in G\left(x\right)}{min}V\left(R\left(\mathrm{\gamma }\right)\right)\hfill \\ \hfill & =\underset{\mathrm{\gamma }\in G\left(x\right)}{min}\left(V\left(\mathrm{\gamma }\right)+\mathrm{\psi }\left(y\right)-\mathrm{\psi }\left(x\right)\right)=V\left(x\right)+\mathrm{\psi }\left(y\right)-\mathrm{\psi }\left(x\right)\hfill \end{array}$

Thus V(y) − V(x) = ψ (y) − ψ (x)for any x, y S so there is a constant C such that V(x) = ψ(x) + C for any x ∈ S.

Notice from (20) that, if the cost function V(x → y) admits a potential, then the function V(x) is also a potential for V(x → y). Two potentials differ by a constant.

The lemma below is lemma 5 of section 3.1.

Lemma 8 Let S_– be a subset of S with the properties:

1. for any x ∈ S₊ = S S_–, there exists y ∈ S_– such that V(x → y) = 0.

2. for any y ∈ S₋, we have V(x → y) > 0 for all x ∈ S₊.

Then the dynamics can be restricted from S onto S₋.

Proof: It follows from (Freidlin and Wentzell, 1984, lemmata 4.1–3, pp.185–189) that

1. ∀x ∈ S_–, V(x) is computable from graphs over S_–,

2. $\forall y\in S_{+},V\left(y\right)=\underset{x\in S_{-}}{min}\left(V\left(x\right)+\overline{V}\left(x\to y\right)\right)\text{,}$

where the path communication cost $\overline{V}\left(x\to y\right)$ is defined as

$\overline{V}\left(x\to y\right)=\underset{k=2}{\overset{|\mathrm{\Omega }|{}^P}{\wedge }}\underset{z_2,\dots ,z_{k-1}}{min}\left({\displaystyle \sum _{i=2}^{k}V(z_{i-1}}\to z_i\right))\text{,}$

with x = z₁ and y = z_k.

Since by assumption V(x → y) > 0 for any x S_– and y S₊, assertions 1 and 2 above justify the restriction of the dynamics to S_–.

Acknowledgements

This work is supported by the Swiss National Science Foundation and the Région Rhône–Alpes.