δ,= max a(x2=a I Hu(a)-Hu(B) 由此推出 C(Px)≤l-G| min aB Pirl(a,B)≤1 从而得到 (P)=C(Px1)…C(Px)≤(1 (9.10) 定理9.12(遍历收敛定理)以上定义的转移矩阵P的 Dobrushin收缩系数满 C(P)≤1-e(△为H的振幅) 记以P为转移矩阵的 Markov链为n,则它以Gibs分布兀为可逆分布,而且有 证明显见r(a)p(a,B)=r(B)P(B,a)·由P=(p(,B)a,Bes的定义立得 丌(a)p(a,B)=(B)p(B,a).因此兀为可逆分布.又由C(P)<1,用 Dobrushin定理可 知极限成立 [注]G-格点的排序{x,…,xa)并不是实质的我们可以用一个G上取值全正的预选概率分 布g(x),(即g(x)>0∑g(x)=1例如均匀分布)的随机数作随机选取来代替.这时转移矩阵P应 作相应的改动,代替P1x(a,B)的是,以g(x)的概率对只在x坐标不同的组态间进行转移,即令 =(P),P=(p(ax,B) 其中 ,B)=8(x)(x,B)(若o=Bm:) (其它情形) 这时我们仍有 1 1.5 Gibbs分布的模拟退火 本段讨论求得达到组态空间上能量函数最小值的组态的概率方法,就是用能量函数的 Gibs分布作模拟退火的方法.考虑依赖于温度Tn的Gibs分布,以它们作为不变分布构造 各步为非时齐Gibs转移矩阵,由此确定的一个非时齐 Markov链{n}.我们可以用它作模 拟退火,使得当n充分大以后,此非时齐的 Markov链n以大概率落在能量函数最小的组态 5235 max | ( ) ( )| \{ } \{ } d x a b HU a HU b G x G x = = - , x G x d Î D D =max . (9. 8) 由此推出 -D C P £ - G p £ - e ( {x} ) 1 | | min a ,b {x} (a,b) 1 . (9. 9) 从而得到 | | { } { } ( ) ( ) ( ) (1 ) 1 G x x C P C P C P e M -D = L £ - | | 1 G e -D £ - . (9. 10) 定理 9. １２ （遍历收敛定理） 以上定义的转移矩阵P 的 Dobrushin 收缩系数满 足 | | ( ) 1 G C P e -D £ - ( D 为 HU 的振幅). 记以 P 为转移矩阵的 Markov 链为 n x , 则它以 Gibbs 分布p 为可逆分布, 而且有 P p n n T ¾ ¾®1 ®¥ . 证明 显见 p (a) (a,b ) p (b ) (b,a) pJ = pJ . 由 P S p = a b a,bÎ ( ( , )) 的定义立得 p (a) p(a, b ) = p (b ) p(b ,a) . 因此p 为可逆分布. 又由 C(P) < 1, 用 Dobrushin 定理可 知极限成立. [注] G -格点的排序 { , , ) 1 |G| x L x 并不是实质的. 我们可以用一个 G 上取值全正的预选概率分 布 g (x) , (即 ( ) > 0,å ( ) = 1 xÎG g x g x 例如均匀分布) 的随机数作随机选取来代替. 这时转移矩阵 P 应 作相应的改动，代替 ( , ) { } a b xk p 的是, 以 g (x) 的概率对只在 x 坐标不同的组态间进行转移, 即令 P ( D = ~ P | | ) G , ~ P = p a b a,bÎS ~ ( ( , )) , 其中 î í ì = = 0 ( ) ( ) ( , ) ( ) ( , ) { } \{ } \{ } ~ 其它情形 p x 若 G x G x g x p a b a b a b . 这时我们仍有 P p n n T ¾ ¾®1 ®¥ . １. ５ Gibbs 分布的模拟退火 本段讨论求得达到组态空间上能量函数最小值的组态的概率方法, 就是用能量函数的 Gibbs 分布作模拟退火的方法. 考虑依赖于温度Tn的 Gibbs 分布, 以它们作为不变分布构造 各步为非时齐 Gibbs 转移矩阵，由此确定的一个非时齐 Markov 链{ }n x . 我们可以用它作模 拟退火, 使得当n 充分大以后，此非时齐的 Markov 链 n x 以大概率落在能量函数最小的组态