Trouve (1121214), страница 5
Текст из файла (страница 5)
This ends the proof of the rst inequality of Hn1 .From now, we left to the reader, the easy verications which prove that the parameters can always be chosen independently of V .We are here concerned by the study of the exit time from . Since we can taked 1, we will assume that Tn > 0 and He () > 0 (otherwise the result is trivial).
Letf 2 F (), considering the last visit of f by the Markov chain, we have the inequalityP ( (; m) n j Xm = i ) +nX?1nXk=m+1 l=k+1nXl=m+1M ( n ff g; c)E;li;mP ( Xk = f; (; m) > k j Xm = i)M ( n ff g; c)E;lf;k :ALAIN TROUVE26For a xed n, consider the new cooling schedule (T^l)l2N dened by T^l = Tl for l < nand T^l = Tn for l n. For this new cooling schedule, we get from Hn2 ?1 (since wehave assume Tn > 0 and He() > 0)1Xl=m+1so that(29)1Xl=m+1M ( n ff g; ff g)f;li;m K1 ;M ( n ff g; c)E;li;m 1 ? K1 :Then, we deduce from the proof of the rst inequality of Hn1 thatP ( (; m) n j Xm = 1 ) 1 ? K1 + K2so that(30)P ( (; m) > n j Xm = 1 ) K1 ? K2nXk=m+1nXk=m+1e?He()=Tk ;e?He()=Tk :The lemma 4.6 given below shows that the result follows from inequality (30). Hencethe proof of Hn1 is completed.Lemma 4.6.
Let 2]0; 1] and A E . Assume that for all n > m, all i 2 E wehaveP ( (A; m) > n j Xm = i) ? KnXk=m+1e?V (A)=Tk ;then, there exists c and d which depend only on and K such thatP ( (A; m) > n j Xm = i) cnYk=m+1(1 ? de?V (A)=Tk ):Proof. This lemma has been established by O. Catoni in [2]. For completeness, wereport here the proof.Assume rst that e?V (A)=Tm+1 =(4K ), then consider the family (uk ) dened by u0 = m, uk+1 = inf fl > uk j Plh=uk +1 e?V (A)=Th =(4K ) g:OPTIMAL CONVERGENCE SPEED EXPONENT FOR G.S.AIf uk < 1, we haveHowever,27inf P ( (A; uk?1) > uk j Xuk?1 = i ) =2:i2ukYh=uk?1 +1(1 ? ce?V (A)=Th ) exp(?cukXh=uk?1 +1e?V (A)=Th ):Hence, if c = supf? ln(=2)4K=; 4K= g, we haveukY(1 ? ce?V (A)=Th ) =2:h=uk?1 +1Now, for each n 2 N , consider the integer k(n) such that uk(n) < n uk(n)+1.
Wehave0P ( (A; m) > n j Xm = i) (=2)k(n)?1 iinf0 2 P ( (A; uk(n)) > n j Xuk(n) = i )uYk(n)h=m+1(1 ? ce?V (A)=Th )( ? KnXl=uk(n) +1e?V (A)=Tl ) (=2)nYh=m+1(1 ? ce?V (A)=Th ):Assume now that e?V (A)=Tm+1 > =(4K ). since we have c (4K ) , we deduce(1 ? ce?V (A)=Tm+1 ) < 0 so that we have the result with the convention that theproduct is zero if one of its term has a negative value.The proof of the lemma is complete.Hn(2): Let g 2 PthE (i; j ) such that CA(g) = CA (i; j ). As in the proof of Hn1 , we decompose the graph g into its exit points out of the elements of M(A).
More preciselywe consider the unique family (ik ; nk ; k )0kr dene by the following procedure : i0 = g0 = i, n0 = 0, and 0 is the unique element of M(A) such that i0 2 0. Let nk+1 = inf f l > nk j gl 2= k g and ik+1 = gnk+1 .{ If ik+1 = j then the construction is completed.{ Otherwise, dene k+1 in M(A) such that ik+1 2 k+1.Let r be the integer such that ir = j .rst case: Assume that A 2= C (E ), then for all 2 M(A), all i0 2 and all j 0 2 Ewe have(31)C (i0; j 0) = CA(i0; j 0);ALAIN TROUVE28so that we deduce from the previous construction that(32)CA (i; j ) = CA (g) =rX?1Xk=0 nk l<nk+1Ck (gl; gl+1) rX?1k=0C k (ik ; ik+1):Furthermore, we haveM (A; Ac)j;ni;m frY?1k=0M (k ; ck )iikk+1 gnm:Since the cycles k verify jkj < n, we deduce from Hn2 ?1 and from the stabilitylemmas that the right hand term is bounded from below byK1e?Pr?1 C (i ;i )=Tk=0 k k k+1 n Qn ;mwith Q 2 Dr (He (A); a1; b1).
The result follows from inequality (32).Second case: We assume now that A is a cycle . The main dierence with theprevious case is that the equality (31) is true only for j 0 2 . Hence the equation(32) must be changed in(33)C (i; j ) = C(g) rX?1k=0C k (ik ; ik+1) + C(gnr ?1; j ) ? Cr?1 (gnr ?1; j ):Since one easily veries that C(gnr ?1; j ) ? Cr?1 (gnr ?1; j ) = Hm () ? He (), wededuce in the same way that above :(34)?C (i;j )=Tn e?(He ()?Hm ())=Tn Qn ;M (; c)j;ni;m K1 e mwith Q 2 Dr (Hm(); a2; b2).Dene now for all H 0, c > 0 and m 2 NR(H; c; m) = inf f l > m jlXk=m+1e?H=Tk c g:We dene the sequence (uk )k2N by: u0 = m, uk+1 = R(Hm (); ln(2(1 + b))=a; uk) for k 0.OPTIMAL CONVERGENCE SPEED EXPONENT FOR G.S.A29For all n > m, we dene k(n) 2 N by uk(n) < n uk(n)+1.
We deduce then from theconstruction of uk thatM (; c)j;ni;m P ( (; m) > uk(n) j Xm = i )X P (Xuk(n) = i1 j (; m) > uk(n) ; Xm = i )M (; c)j;ni1 ;uk(n) :i1 2From lemma 3.4, we deduce that C (i1; j ) is independent of i1 2 so that we candened C (; j ) by:C (; j ) = C (i1; j ); i1 2 :Hence, we deduce from the previous inequality and from (34) that:(35)?(C (;j )+He ()?Hm ())=Tn Qn ;M (; c)j;ni;m K1 P ( (; m) > uk(n) j Xm = i )euk(n)with Q 2 Dr (Hm (); a; b). Since we have here jj 2, we get easily that P ( (; m) >m + 1 j Xm = i ) 1 ? ou = 1 ? =.
Hence we deduce from Hn1 thatP ( (; m) > uk(n) j Xm = i ) cand we get from (35)M (; c)j;ni;mDene nowAnm K1 cby:Anm =For provingHn2 ,uYk(n)l=m+1uYk(n)l=m+1l=m+1(1 ? ^ (de?He ()=Tl ));(1 ? ^ (de?He()=Tl ))e?(C(;j)+He()?Hm ())=Tn Qnuk(n) :(1 ? ^ (de?He ()=Tl ))e?(He()?Hm ())=Tn Qnuk(n) :we have to prove that there exists a0; b0; K10 such thatK10 (1 ? (1 + b0)(36)uYk(n)nYl=m+1(1 ? a0e?He()=Tl )) We consider rst the lower bound. We havenXAll=m0m K1uXk(n)nXlAm Alm(37)l=ml=mk(Xn)?1 YukuXk+1?H()=Tel(1 ? ^ (de))e?(He()?Hm())=Th Qhuk :k=0 l=m+1h=uk +1ALAIN TROUVE30Furthermore,uXk+1h=uk +1Sincee?(He()?Hm ())=Th Qhuk e?(He()?Hm())=Tuk+1uXk+1h=uk +1QhukanduYk+1 (1 ? (1 + b)uYk+1uXk+1h=uk +1Qhuk :(1 ? ae?Hm()=Th ));uk +1(1 ? ae?Hm()=Th ) e?ah=uk +1Puk+1 e?Hm ()=Thh=uk +1;we deduce from the denition of un thatuXk+1h=uk +1However,e?He()=Tuk+1 e?Hm()=Tuk+1so that we deduce fromuXk+2h=uk+1 +1uXk+2h=uk+1 +1thatuXk+1h=uk +1Qhuk 1=2:e?He()=Th!=uXk+2h=uk+1 +1e?Hm()=Th!;e?Hm()=Th ln(2(1 + b))=a + 1;e?(He()?Hm ())=Th Qhuk KuXk+2h=uk+1 +1e?He()=Th ;with K = (ln(2(1 + b))=a + 1)=2.
Coming back to inequality (37),we getnXAll=mmKk(Xn)?1 Yukk=0 l=m+1(1 ? ^ (de?He()=Tl ))Consider now uk+1 + 1 h uk+2, we have:ukYl=m+1uXk+2h=uk+1 +1e?He()=Th :(1 ? ^ (de?He()=Tl ))e?He()=ThfhY?1l=u1 +1(1 ? ^ (de?He()=Tl ))e?He()=Th g f Kd?10 hYu1Yl=m+1(1 ? ^ (de?He()=Tl ))g(1 ? ^ (de?He()=Tl )) ^ (de?He()=Th );l=u1 +1OPTIMAL CONVERGENCE SPEED EXPONENT FOR G.S.A31Indeed, for all 0 x , we have (1 ? x) eln(1? )x= so thatu1Yl=m+1(1 ? ^ (de?He()=Tl )) exp( ln(1 ? ) exp(u1Xl=m+1u1ln(1 ? ) X l=m+1de?He()=Tl )de?Hm ()=Tl ) K 0;where K 0 = exp( ln(1 ? ) d(ln(2(1 + b))=a + 1):Therefore,nXAll=mmukY(n)+10K(1 ? ^ (de?He()=Tl )) d (1 ?l=u1 +10 Kd (1 ? fnYl=m+1(1 ? ^ (de?He()=Tl ))g=fu1Yl=m+1(1 ? ^ (de?He()=Tl ))g:Hence, dening b0 = (1=K 0 ) ? 1 and K10 = K 0=d, we havenXAll=mm Kd (1 ? (1 + b0) K10 (1 ? (1 + b0)nYl=m+1nY(1 ? ^ (de?He()=Tl )))l=m+1(1 ? ( ^ d)e?He()=Tl ))):To establish the upper bound in (36), it is sucient to consider for all m 2 Z,the integer n(m) dened by n(m) = inf f k 2 Z j Pkl=m Alm > K10 g.
Then, weconsider A^nm dened by A^nm = Anm for n < n(m), and if n(m) < +1, we deneA^nm = K10 ? Pnl=(mm)?1 Anm and A^km = 0 if k > n(m). We can verify thatnM (; c)i;ni;m A^mand A^nm satises the inequalities (36). This ends the proof of the rst inequality ofHn2 .We prove now the last assertion of Hn2 .
We do not any longer assume that A is acycle. Let i be in A, from lemma 3.4 we deduce that there exists j 2 Ac so thatALAIN TROUVE32CA (i; j ) = 0. Hence(38) P ( (A; m) > n j Xm = i) = 1 ? P ( (A; m) n j Xm = i )1?nXk=m+1Qkm 1 ? K1(1 ? (1 + b)nYl=m+1(1 ? ae?He(A)=Tl ):The proof is completed as in [2] but we recall it for sake of completeness. Considerthe family (uk ) dened by u0 = m.
uk = inf f l > uk?1 j Plh=uk?1 +1 e?He(A)=Th ln(2(1 + b))=a g:From (38) we deduce that for uk+1 < 1sup P ( (A; uk) > uk+1 j Xuk = i) 1 ? K1 =2:i2However, assuming that a0 1=2, we haveuYk+1(1 ? a0e?He(A)=Tl ) exp(2 ln(1=2)a0l=uk +1Now, assuming a0 = inf f1=2; ln(1 ? KuYk+1l=uk +1uXk+1l=uk +1e?He(A)=Tl ):g we deduce1=2)=[(ln(2(1+ b))=a +1)(2 ln(1=2))](1 ? a0e?He(A)=Tl ) 1 ? K1=2:Hence, using the Markov property at time uk , we deducenY1(1 ? a0e?He(A)=Tl );P ( (A; m) > n j Xm = i) 1 ? K=21 l=m+1from which the proof of Hn2 is completed.Hn3 : Let f 2 F () and consider the last visit of f by the Markov chain. We canwrite+nX?1k=mc j;nM (; c)j;ni;m M ( n ff g; )i;mP ( (; m) > k ; Xk = f j Xm = i )M ( n ff g; c)j;nf;k :From Hn1 ?1 we deduce that the rst term of the inequality has the upper bound?C (i;j )=Tm+1 Qn with Q 2 D r (He (); a; b):(39) M ( n ff g; c)j;ni;m K2 e mOPTIMAL CONVERGENCE SPEED EXPONENT FOR G.S.A33Now, considering the second term, we get from Hn2 and Hn1 ?1nX?1k=mP ( (; m) > k ; Xk = f j Xm = i )M ( n ff g; c)j;nf;k(40) Ke?(Cnff g(f;j)?He())=Tm+1 Qnm with Q 2 Dr (He (); a0; b0):In the same way than in the proof of lemma 3.5 we easily show that C nff g(f; j ) ?He () = C (f; j ) and from lemma 3.4 we get C (f; j ) = C (i; j ) for any i 2 sothat the proof of Hn3 follows from (39) and (40).The proof of Hn3 is completed.Hn4 : We can assume that A is not a cycle, otherwise the result is trivial.
We willshow at rst that there exists Q 2 Dr (He(A); a; b) and K > 0 such thatnM (A; [ Ac)j;ni;m KQm :Let g 2 A and g 2 M(A) such that g 2 F (g) and He (g) = He(A). Consideringthe last visit to g by the Markov chain, we getc j;nM (A; [ Ac)j;ni;m M (A n fg g; [ A )i;m+nX?1k=m+1P ( (A; m) > k; Xk = g j Xm = i )M (A n fgg; [ Ac)j;ng;k :Furthermore, concerning the last term, we have the decomposition for j 2 [ Acc j;nM (A n fgg; [ A)j;ng;k M (g n fg g; g )g;k(41)+ fM (g n fgg; cg)M (A n fgg; [ Ac)gj;ng;k :Now, consider the family (p)0pr of elements in M(A n fgg) such that [ Ac =0[pr (p [ Bg )where Bg = Ac if g 2= and Bg = Ac [ fgg otherwise.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
