文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > Simulated Annealing for Graph Bisection
侵权投诉

Simulated Annealing for Graph Bisection

Simulated Annealing for Graph Bisection

Lemma 6.3 Let p? r and T be as in Theorem 6.1, and select G 2 G4n;p;r. At con-

stant temperature T and starting at any initial state, the Metropolis process on bisections p of G reaches a bisection with imbalance at least n in time O(n1+" ), with overwhelming probability. Proof Let= n?1=2. By Corollary 5.3," with overwhelming probability no -atypical states are encountered in the rst O(n1+ ) steps of the Metropolis process. It is therefore enough to prove the result under the assumption that no -atypical states are encountered. p Set b= d n e, and consider the random walk Y (t) on N de ned by transition probabilities ( u if 0 k< Pr Y (t+ 1)= k+ 1 j Y (t)= k]= 0 otherwise; b;

d Pr Y (t+ 1)= k? 1 j Y (t)= k]= 1 if 0< k b; if k> b; 1 where u= 1?, d= 8+, and> 0 is a constant to be chosen shortly. (Loop 8 probabilities are implicitly de ned by complementation.) Let k(t), t= 0; 1;:::, be the sequence of imbalances recorded as the Metropolis process evolves from a random initial state. Under the assumption that the current state is not -atypical, Corollary 3.3 assures us that k-increasing and k-decreasing transitions both occu

r with probability 1 O(n?1=2) 8 p when k b= d n e. Thus, for some choice of= O(n?1=2) the random walk Y (t) stands in relation to k(t) as its namesake does to the process X (t) in Theorem 6.2.1 We are thus reduced to showing that the random walk Y reaches b in time O(n1+" ) with overwhelming probability when started in state 0. For 0 k b, let i be the expected time for the random walk Y to hit state b, given that the initial state is i. According to Feller 7, eq. XIV.3.3], the general solution for i is2 d i i (10)= d?u+A+B u; i where A and B are constants that must be tted to the boundary conditions; in our case, these are b= 0 and 0= 1+ u 1+ (1? u) 0, the latter simplifying to 0? 1= u?1. Substituting the general solution from equation (10) into each of these in turn yields d b b A+B u+ d?u=0 and d d B 1? u? u(d? u)= 0: correspondence with the condition of Theorem 6.2; in fact we are only interested in the evolution of k(t) until k(t) b. 2 Feller has the convention u+ d= 1, but his derivation is valid for the general case. 1 The transition probabilities for Y when Y (t) exceeds b are arti cially de ned to ensure a formal

and

(

上一页第15页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email