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

Simulated Annealing for Graph Bisection

Simulated Annealing for Graph Bisection

expectation is over random graphs G 2 G4n;p;r . Proof The distribution of X+ can be expressed as the sum and di erence of 8n? 4 Bernoulli random variables, corresponding to the 8n? 4 potential edges a ected by the speci ed move: X+= 2(n? k? 1) Bp+ 2(n+ k) Br? 2(n+ k) Bp? 2(n? k? 1) Br (2) where the equality sign is to be interpreted as\has the same

distribution as", and the notation t Bp stands for the sum of t Bernoulli r.v.s each with expectation p. Introduce a new r.v. X 0 with distribution X 0= 2n Bp+ 2(n? 1) Br? 2n Bp? 2(n? 1) Br: Observe that the distribution of X 0 is symmetric about the origin, while the function 1 A(x)? 2 is antisymmetric, and hence EA(X 0)= 1 . Our strategy is to estimate EA(X+) 2 by comparing the distributions of X+ and X 0, which are obviously close for small k. We construct a model for X+ and X 0, on a common sample space, that gives the correct distribution for each r.v., even though X+ and X 0 will (intentionally) be highly n? n? correlated. Express X+ as the sum X+= Pi4=1 2 Xi+? Pi8=4n4?1 Xi+ of independent 0,1 r.v.s fXi+ g, where the expectation of individual variables is suggested by expression (2). (Thus the rst 2(n?k?1) have expectation p, the next 2(n+k) have expectation r, and so n? n? on.) Let X 0= Pi4=1 2 Xi0? Pi8=4n4?1 Xi0 be a similar expression for X 0. For pairs (Xi+; Xi0) containing variables of the same type (i.e., both having expectation p, or both r), arrange for the variables to be perfectly correlated, i.e., Xi+= Xi0. For the remaining 4(k+ 1) pairs (e.g., where Xi+ has expectation p and Xi0 has expectation r) arrange for the pvariable to dominate the r-variable (e.g., Xi+ Xi0); this can be achieved by setting Pr(Xi+= Xi0= 0)= 1? p, Pr(Xi+= 1^ Xi0= 0)= p? r, and Pr(Xi+= Xi0= 1)= r. This construction yields the following sharply concentrated distribution for the di erence of X 0 and X+: X 0? X+= (4k+ 2) Bp?r 0: 1 It follows by symmetry that Pr (X 0? X+ 2k(p? r)) 2 . p From usual estimates for the binomial distribution, Pr(jX 0j 4 n ) 3, and hence, 4 p 1 with probability at least 4 the events X 0? X+ 2k(p? r) and jX 0j 4 n occur simultaneously. (This is so, irrespective of any probabilistic dependency between the pn, there is a probability of at least 1 that jX 0=T j 4 and events.) Thus, since T 4 X 0=T? X+=T 2k(p? r)=T hold simultaneously. Note that the conjunction of these two events implies A(X+ )? A(X 0)= (minfk(p? r)=T; 1g), since in any bounded range, the\sigmoid" (1+ex)?1 has negative gradient uniformly bounded away from 0. It follows that 1 EA(X+)? 2= EA(X+ )? EA(X 0)= E(A(X+ )? A(X 0)) (minfk(p? r)=T; 1g) (3)

Claim 3.2 Suppose T pn. Then EG A(X+)

1+ 2

(minfk(p? r)=T; 1g), where the

上一页第6页

你可能喜欢

热门文档

相关文档

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