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

Simulated Annealing for Graph Bisection

Simulated Annealing for Graph Bisection

dominated by X in the following sense: if X (t)= Y (t)= k, then and

Pr X (t+ 1)= k+ 1] Pr X (t+ 1)= k? 1]

Pr Y (t+ 1)= k+ 1] Pr Y (t+ 1)= k? 1]:

Furthermore, assume that the loop probabilities Pr Y (t+ 1)= k j Y (t)= k] for the 1 random walk are at least 2, for all k. Then the process X (t) dominates Y (t): for every nal state j, every choice of initial states satisfying Y (0) X (0) j, and every time bound t, it is the case that

Pr X (t0)= j; for some t0 t] Pr Y (t0)= j; for some t0 t]: so that X (0) Y (0) implies X

(t) Y (t) for all t. The result follows immediately. The sample space consists of a sequence (0); (1);::: of independent\coin tosses", the result of the t'th toss being a real number (t) uniformly distributed in 0; 1). Focus attention on time step t, and let p+= Pr X (t+ 1)= X (t)+ 1] and p?= Pr X (t+ 1)= X X X (t)? 1], with analogous de nitions for p+ and p? . (The probabilities p+ and p? may Y Y X X depend on a hidden state or external stimulus: the argument is not a ected.) Then the next state of the process X is given by

Proof We shall base the processes X (t) and Y (t) on a common underlying sample space,

X (t)? 1 if (t)< p?; X X (t+ 1)= X (t)+ 1 if (t) 1? p+; X X (t) otherwise; 8><>:

and similarly for the process Y . Observe that the high loop probabilities of process Y, combined with dominance of 1 1 the transition probabilities of Y by those of X, ensure that p+ 2 and p? 2 . Thus it X Y cannot happen that X (t+ 1)= X (t)? 1 and Y (t+ 1)= Y (t)+ 1, for the former implies 1 (t)< p? 1 and the latter (t) 1? p+ 2 . X 2 Y The proof of X (t) Y (t) for all t is by induction on t, the case t= 0 being satis ed by hypothesis. If X (t)> Y (t) then it is immediate that X (t+ 1) Y (t+ 1) by the previous observation. If X (t)= Y (t) then there are two possible bad cases: either Y increases and X does not; or Y is unchanged and X decreases. But Y increases only if (t) 1? p+ 1? p+, in which case X also increases; similarly a decrease in X requires Y X (t)< p? p?, which in turn requires Y to decrease. X Y The machinery required for analyzing the three regimes described earlier is now in place. Here we consider the Metropolis process on partitions with imbalance at most pn. We show that the process exhibits the following favorable behavior. 14

6.1 Small imbalance

上一页第14页

你可能喜欢

热门文档

相关文档

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