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

Simulated Annealing for Graph Bisection

Simulated Annealing for Graph Bisection

over random sequences ( ), some correction tape makes^ ( )= ( ) for all 0 t. To see this, we will\reverse-engineer" the correction tape: the\bad" times i are those at which the blu er's choice for the state following^ ( i? 1)

| given^ ( i? 1)= ( i? 1)| fails to agree with the true Metropolis state ( i); the suggested moves m( i) are those required to take state^ ( i? 1) to state ( i). It should be clear that this construction makes the corrected blu er's sequence identical to the Metropolis trajectory. It remains to verify that the number of bad times is small, so that the correction tape is of acceptable brevity. A given time is bad only if falls intopone of the\excess" intervals, which occurs 1 with probability at most 2 kP?p k O( n=T ). Thus the number of bad times is P distributed binomially as B (t; O( n=T )).pOver the space of coin tosses, the probability p that the total number of bad moves is O(t n=T ) is 1? exp(? (t n=T )), which by choice of t is 1? exp(? ( 2T 2= log2 n)). We now close the argument. For any initial state and with overwhelming probability over graphs and random coin tosses, for some correction tape, the sequence (^( ))t=1 produced by a blu er (without access to G) is identical to the Metropolis trajectory ( ( ))t=1. Since there are only ptn=T )= exp(O(pn t log t=T )) O(t possibilities for the set of times at which the corrector can act, and p p (4n2)O(t n=T )= exp(O( n t log n=T )) p possibilities for how it can act at those times, there are only exp(O(t n log n=T )) possible correction tapes. (Note that, by assumption, T is polynomial in n, and hence log t= O(log n).) Given an initial state (0) and the sequence of coin tosses ( ), run the blu er in p turn with all possible correction tapes, producing a set of exp(O(t n log n=T )) states. Only now choose a random G 2 G4n;p;r. Applying Claimp the probability that any 3.6, state in the set is -atypical for G is at most t exp(O(t n log n=T )) 4 exp(?4 2 T 2), which is exp(? ( 2T 2)), by choice of t. Since, with overwhelming probability, the set includes the Metropolis trajectory ( ), it is overwhelmingly likely that no -atypical state is encountered by the Metropolis algorithm. Specializing the parameters T,, and t appearing in Claim 5.2 we obtain the following. Corollary 5.3 Let"> 0, T= n5=6+",= n?1=2, t= (n1+2"), and select G 2 G4n;p;r. With overwhelming probability, the Metropolis process run at temperature T for t steps starting at an arbitrary initial state encounters no -atypical state. b !

6 Progress of Annealing: Detailed Analysis We now re ne the argument sketched in Section 4 to demonstrate that the Metropolis process on bisections, when run at an appropriate temperature, converges rapidly to the optimal bisection with overwhelming probability. 12

上一页第12页

你可能喜欢

热门文档

相关文档

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