Trouve (1121214), страница 3
Текст из файла (страница 3)
However, for any starting point in A, a G.S.Awith parameter (q; ; PT ) (see remark 5) can exit from A at least within a time oforder eHe(A)=T .We show in the next proposition proved in [16] the strong link that exists betweenthe virtual energy W and the cycle decomposition.OPTIMAL CONVERGENCE SPEED EXPONENT FOR G.S.AProposition 2.6. Let i 2 E . ThenW (i) = AE ?where AE =X0knEnE XX13(Hek (ik ) ? Hmk (ik ))k=0 2E kHek () ? Hmk ():3. Renormalization of the communication costIn this section, we dene from the communication cost V and action functional forthe exit paths from a subset A of E . More precisely, starting from a point i 2 A, wewant to evaluate the probability that before the exit time from A, the process (runningat constant temperature T ) visits the edge (i; j ). It appears that this probability isof order e?CA(i;j)=T . Hence CA(i; j ) can be interpreted as a new cost which weightsthe cost of a large deviation event (the visit of the edge (i; j )) from the standardbehavior of the process running in A.
This cost will be called the renormalized costin A. This section is devoted to its combinatorial denition in function of V and topreparatory lemmas for the large deviation estimates established in Section 4.Denition 3.1. (1) Let i; j 2 E , i 6= j . We denote by nij the integer uniquelydened by :inij 6= j nij and inij +1 = j nij +1:(2) Let A E , A 6= E . For all i 2 E we dene ni;A byni;A = inf f 0 k nE j ik+1 \ Ac 6= ; g:Proposition 3.2. Let A E , A 6= E . We dene on E the function CA by :8>0if i = j;>>< V (i; j )if i 2= A and j 6= i;nijX^ni;ACA(i; j ) = >>V(i;j)?(Hek (ik ) ? Hmk (ik )) otherwise.:k=0Then CA is a communication cost called the renormalized communication cost in A.Proof.
It is sucient to prove that CA(i; j ) 0. Moreover, it is sucient to provethat for i 6= j we have :(14)V (i; j ) ?nijXk=0(Hek (ik ) ? Hmk (ik )) 0:ALAIN TROUVE14This will be proved by induction on the value of nij .Assume that nij = 0. Then (14) is equivalent toV (i; j ) ? He (i) 0:which is obvious.Now assume that the result has been proved for nij k ? 1. Then from the recursiveconstruction of the cycles and from the induction hypothesis we have(15)V 1(i1; j 1)nijX? (Hek (ik ) ? Hmk (ik )) 0:k=1denition of V 1Furthermore, from thewe have(16)(V (i; j ) ? He (i)) ? (V 1(i1; j 1) ? Hm1 (i1)) 0:Adding (15) and (16) we deduce (14) so that the proposition is proved.Denition 3.3.
Let A E , and let i; j 2 E be two distinct congurations. Wedenote by CA (i; j ) the numberCA (i; j ) = inf fCA (g) j (gk )0kng 2 PthE (i; j ); gk 2 A for 0 < k < ng g:Here the inmum is taken on the paths from i to j that stay within A except eventually at their extremities.Remark 7. Starting from the probabilistic interpretation of CA given in the introduction of this section, we can easily deduce the interpretation of CA (i; j ). For all i 2 Aand j 2 E , if g 2 PthA(i; j ) is a path staying in A (excepted eventually for its righthand extremity), the probability that the process starting from i visits all the edgesof g before exiting from A is of order e?CA(g)=T .
Hence, if j 2 Ac, the probability thatthe process exit from A at point j is of order e?CA (i;j)=T .We establish now four lemmas which will be useful for the next section.Lemma 3.4. Let 2 C (E ) and A E; A 6= E .(1) For all i, j 2 , we have:C (i; j ) = 0:(2) For all i 2 A, let CA (i; Ac) = inf f CA (i; j ) j j 2 Ac g: We haveCA (i; Ac) = 0:OPTIMAL CONVERGENCE SPEED EXPONENT FOR G.S.A15Remark 8. According to the probabilistic interpretation given in the remark 7, (1)says that starting from i 2 , the process visits all the congurations j 2 beforeexiting with a probability non vanishing with the temperature. The interpretationof (2) is straightforward.Proof.
We prove the part 1) of the lemma by induction on k = supi;j2 nij . Assumethat k = 0, then nij = 0 and j 2 i1. Furthermore, for all a; b 2 , a 6= b, nab = 0 wehaveC (a; b) = V (a; b) ? He(a) = V0(fag; fbg);so that the result follows easily.Assume now that the result is true for k ? 1. If ik = j k then the induction hypothesisgives Cik (i; j ) = 0. Since we have Cik (i; j ) C (i; j ), the result is proved.
Otherwise,it is sucient to prove that if V k (ik ; j k ) = Hek (ik ) then C(i; j ) = 0. For that, wedene i1 and j1 in by the following recursive denition :(17)ik1 = ik , j1k = j k ;and V r (ir1; j1r ) ? Her (ir1) = V r+1(ir1+1; j1r+1) ? Hmr+1(ir1+1) for r < k:One easily veries thatC(i1; j1) = V k (ik1 ; j1k ) ? Hek (ik1 ) = V k (ik ; j k ) ? Hek (ik ) = 0:The proof is completed if we notice that (17) implies thatC (i; i1) = C (j1; j ) = 0:We are now concerned by the proof of 2).
We start by proving the result for a cycle 2 C (E ) distinct of E . Since the point 1) is proved, it is sucient to prove thatthere exists e 2 and f 2 c such that C(e; f ) = 0. Let n be an integer suchthat 2 E n and let 0 2 E n be a cycle such that(18)V n (; 0) = Hen ():Let e 2 and f 2 0 be two points satisfying:(19) V r (er; f r ) ? Her (er) = V r+1(er+1; f r+1) ? Hmr+1(er+1) ; 0 r < n ? 1:ALAIN TROUVE16As previously, we verify thatC(e; f ) = V n (en ; f n ) ? Hen (en )+nX ?1l=0f(V l(elh; fhl ) ? Hel (elh)) ? (V l+1(elh+1; fhl+1) ? Hml+1(elh+1))g:so that we get with (18) and (19) that C(e; f ) = 0.We consider now the general case of a strict subset of E .
Let i be an element ofA, we prove the result by induction on the value ni;A.We assume here that ni;A = 0. From the denition of ni;A , we deduce that i1 \ Ac 6= ;.Let j be in i1 \ Ac. From the construction of the cycle i1, there exists a pathg 2 Pthi1 (i; j ) such that:V (gk ; gk+1) ? He (gk ) = 0; 0 k < ng :Hence, if rg = inf f 0 k ng j gk 2 Ac g, the path g stopped at rg dened byg^ = (gk )0krg veries:CA (^gk ; g^k+1 ) = 0; 0 k < rg = ng^;so that CA (^g) = 0 and the result is proved.Assume now that the result is proved for all i in A such that ni;A < k. Assume thatni;A = k. We note then + = ini;A +1. From the denition of ni;A, we have + \Ac 6= ;.Let j be in + \ Ac, we have from the point 1) that C + (i; j ) = 0.
Hence, we considera path g 2 Pth+ (i; j ) such that C+ (i; j ) = 0. As previously, we stop the path atits rst exit from A, i.e. we dene g^ = (gk )0krg where rg = inf f k ng j gk 2= Ag.Since for all k rg , g^k 2 +, we have8>< ng^k ;A ni;A(20)> et:ng^k ;g^k+1 ni;A ; 0 k < rgDene sg = supf0 k < rg j ng^k ;A = ni;A g. For all k sg , we have from (20) thatng^k ;g^k+1 ni;A = ng^k ;A ng^k ;+ so thatCA (^gk ; g^k+1 ) = C+ (^gk ; g^k+1 ) = 0; 0 k sg ;and CA (i; g^sg +1) = 0. Now consider the two following cases. If sg + 1 = rg ,then the result is proved. Otherwise, applying the induction hypothesis, we haveCA (^gsg +1; Ac) = 0 so thatCA (i; Ac) CA (i; g^sg +1) + CA (^gsg +1; Ac) = 0:OPTIMAL CONVERGENCE SPEED EXPONENT FOR G.S.A17The proof of the lemma is complete.Lemma 3.5.
Let 2 C (E ) n fE g and i 2 .Let C nfig (i; c) = inf f C nfig(i; j ) j j 2 c g. We haveC nfig(i; c) = He () + W () ? W (i):Remark 9. We can give an heuristic proof of the above equality with the probabilisticinterpretation of the renormalized costs. Consider the process at equilibrium for aconstant cooling schedule at temperature T . Now, compute the order of the massexiting from at each time step.
This mass is given by the probability to be in which is of order of e?W ()=T (see proposition 1.6) multiplied by the probability byunit of time to escape from starting from which is of order e?He()=T . However,choosing a point i 2 , we can say that this mass is given by the probability to be ati which is of order e?W (i)=T multipliedby thec probability to escape from withoutany return to i which is of order e?Cnfig (i; )=T . Hence we get W () + He () =C nfig + W (i).Proof. From the proposition 2.6 we know that there exists a constant AE such that:W (j ) = AE ?Assume that j 2 , thennEX(Hek (j k ) ? Hmk (j k )):k=0nXj;kkkkW (j ) = AE ?(He (j ) ? Hm (j )) ? (Hek (j k ) ? Hmk (j k )):k=nj; +1k=0nEXIt is true that nj; does not depend on j for j 2 so that we will omit the index j .Furthermore, since j n = , only the last term depends really on j for j 2 .
Hencefor f 2 F (), we havenXnXkkkk(He (f ) ? Hm (f )) = sup (Hek (j k ) ? Hmk (j k )) = He ():j 2 k=0k=0Hence to prove the lemma it is sucient to prove thatnXc(Hek (ik ) ? Hmk (ik )):nfig(i; ) =k=0Since nj;nfig = nij we havenX^njlC(j; l) ? Cnfig(j; l) = ?(Hek (j k ) ? Hmk (j k )):k=nij ^njl +1CLet j 2 .ALAIN TROUVE18However, for k > nij , we have j k = ik so thatC(j; l) ? Cnfig(j; l) = ?nX^njl(Hek (ik ) ? Hmk (ik)):k=nij ^njl +1Otherwise, if njl > nij , then nil = njl. We deduce then thatC(j; l) ? Cnfig(j; l) = ?Hence for all paths g from i to(21)(Hek (ik ) ? Hmk (ik ))1Inil >nij :k=nij +1through we haveCnfig(g) C(g) +Moreover, there exists a path gis increasing in k.
Hence(22)cnilXnX(Hek (ik ) ? Hmk (ik )):k=0from i to c throughCnfig(g) =We deduce from (21) and (22) thatnXk=0 such that C (g) = 0 and nigk(Hek (ik) ? Hmk (ik )):nXcCnfig(i; ) = (Hek (ik ) ? Hmk (ik )):k=0so that the lemma is proved.Lemma 3.6. Let 2 C (E ), there exists a real valued constant A such that for each0 2 M(), we haveW (0) + He (0) = A:Remark 10. The probabilistic interpretation of the above equality is that at equilibrium at constant temperature T , the mass exiting from each maximal proper sub-cycle0 of is of the same order.Proof. Let f 2 F (0). We haveW (0) + He (0) = W (f ) += AE ?nXf;0k=0nEX(Hek (f k ) ? Hm (f k ))k=n0 +1(Hek (f k ) ? Hm (f k )):The result is proved if we notice that the last summation term does not depend on0 but on .OPTIMAL CONVERGENCE SPEED EXPONENT FOR G.S.A19Lemma 3.7.
Let (i; j ) 2 E E , i 6= j and consider a cycle E n fj g; i 2 .Then we haveW (i) + V (i; j ) = W () + He () + C (i; j ):Remark 11. Here again we can give a heuristic probabilistic proof of the above equality if we consider the process at equilibrium at constant temperature T . The probability to visit the edge (i; j ) is given by the probability to be at i which is of ordere?W (i)=T multiplied by the probability of the transition from i to j which is of ordere?V (i;j)=T . However, considering the cycle this probability can be compute in another way. The probability is given by the probability to exit from which is of ordere?(W ()+He())=T multiplied by the probability to visit the edge (i; j ) at the exit timewhich is of order e?C(i;j)=T .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
