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

Simulated Annealing for Graph Bisection

Simulated Annealing for Graph Bisection

4 Progress of Annealing: Sketch In this section we begin by proving that for any"> 0, p? r= n?1=6+2", T= n1=2+",= n?1=6, and any t= O(n2=3+" ), in the course of t moves it is almost certain that a -atypical state is never encountered. Presuming that this is so, the probabilities for k increasing (or decreasing or remaining the same) are closely bounded by Corollary 3.3. We go on to present an intuitive justi cation that with these parameter values, and p assuming an initial imbalance of k= ( n ), the pessimistic values for these bounds on the transition probabilities su ce to drive k from (n1=2) to (n2=3) within t moves. For now we simply note that this is a comparatively huge imbalance, and do not consider completion to k= n. In later sections we will tighten up what is essentially the same reasoning. First, if p we do not presume that k= ( n ) initially, getting to such a k calls for both a greater number of moves and a larger T (and consequently a smaller ), requiring a more sophisticated argument to show that no atypical state is likely to be encountered (Claim 5.2). Then, it is proved

that the pessimistic values for the probabilities of k increasing, decreasing, or unchanging, when interpreted as the transition probabilities for a Markov chain (which k is not), do indeed yield pessimistic bounds for k (Theorem 6.2). Finally, from the point k= (n) at which these arguments leave o, di erent arguments show that after about n2 additional moves, with high probability k is exactly n (Subsection 6.3). a random G 2 G4n;p;r and any initial partition (0): with overwhelming probability, the Metropolis process run at temperature T for t moves encounters no -atypical partition of G.

Claim 4.1 Let= n?1=6 and T= n1=2+", and let t be any time bound t= O(n2=3+" ). For Proof In addition to (0), let the sequence of t= O(n2=3+") proposed moves be given.

For any such sequence, over all possible choices of accepting or rejecting each move, there are 2 states possible at time, for a set of 2t+1? 1 states possible over all t moves. By Claim 3.6, for a random graph G the expected number of -atypical states in this set is at most 2t+1 4 exp(?4 2 T 2), which for the given parameter values is exp(O(n2=3+")? 4n2=3+2")= exp(? (n2=3+2")). It follows that it is exponentially unlikely that any -atypical state exists among these t+1? 1 states, and in particular that there is unlikely to be one among the t+ 1 states 2 in the actual\trajectory" where the Metropolis rule determines the acceptances and rejections. Presuming now that no -atypical states are encountered, by Corollary 3.3 and the de nition of -atypicality, at every step, 1 f+ 8+ (minfk (p? r)=T; 1g)? O(k=n)? 1= 8+ (minfkn?2=3+"; 1g)? O(k=n)? O(n?1=6) 1 which for (n1=2) k O(n2=3) is f+= 8+ (minfkn?2=3+"; 1g): Symmetrically, f?=?2=3+"; 1g): 1 8? (minfkn

上一页第8页

你可能喜欢

热门文档

相关文档

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