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

Simulated Annealing for Graph Bisection

Simulated Annealing for Graph Bisection

Theorem 6.1 Let"> 0, p? r= n?1=6+2", and T= n5=6+", and select G 2 G4n;p;r. At constant temperature T, the Metropolis process on bisections of G reaches the unique minimum bisection in time O(n2+" ), with overwhelming probability.

established later in the section. It should be noted that the constant implicit in the de nition of\overwhelming probability" depends on", but on no other parameters. The analysis

leading to Theorem 6.1 tracks the Metropolis process through three regimes. These are now brie y described in order to map out the general shape of the proof. The rst two last for only n1+" time, and hence, by Corollary 5.3, pass without the process visiting atypical states. 1. The rstp regime is in force until the imbalance k of the partition rst reaches a value at least n. (For a fortuitous initial partition, this condition may already hold at the outset.) The evolution of the imbalance k as a function of time is su ciently close to that of an unbiased random walk on N, that we are able to argue (in p Subsection 6.1) that there is an appreciable probability that k reaches n in time O(n). Thus with overwhelming probability we pass to the second regime in time O(n1+" ). 2. The second regime lasts until k= (n). In Subsection 6.2 we show that the process experiences a de nite\drift" towards states (partitions) with higher values of k, with the result that k= (n) holds with overwhelming probability after only O(n1+" ) further steps. 3. When k= (n), convergence begins to slow, because the probability of proposing a k-increasing move diminishes (though the probability of accepting a given k-increasing move is obviously high). As a result, we are no longer covered by Corollary 5.3. Fortunately, the progress towards the optimal partition is now inexorable, as we are able to demonstrate by rather crude arguments in Subsection 6.3. As hinted above, we track the Metropolis process by observing the imbalance k as a function of time. The latter process is not Markovian, as the transition probabilities are a function of a\hidden" variable, namely the current partition . However, we shall be able to reason about the the process k(t) by comparing it with a simple random walk on N. The latter will be chosen so that it approximates the former, and is dominated by it in an appropriate sense. The technology for making this comparison is encapsulated in the following theorem.

Proof The result follows immediately from Lemmas 6.3, 6.4, and 6.5, which will be

Theorem 6.2 Let X (t), t= 1; 2;:::, be a random process on N, not necessarily Markov-

ian, having X (t+ 1) 2 fX (t)? 1; X (t); X (t)+ 1g as its only allowed transitions. (The transition probabilities may depend on some hidden state or even an external stimulus.) Let Y (t), t= 1; 2;:::, be a random walk on N that is totally independent of X, but is

上一页第13页

你可能喜欢

热门文档

相关文档

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