定理43.1: Mrakov链不可约所有状态之间是相通的 证明:←显然。→(反证法)若存在两状态,不是相通的,不妨设i办j。令 C={k→k},则首先jC;其次对vk∈C,MeC,P=0。因此C为一个闭集, 而这与 Mrakov链不可约矛盾。 例431:若 Markov链一步转移概率矩阵为 1(1/43/4 2|1/21/2 P 1/21/2 2},34,5}在相通意义下为两个等价类,此链是可约的 定义43:1记d()=gd21r0>0,这里gcd表示最大公因子( greatest common divisor),若d(i)>1,称i为周期的( periodic),且周期为d(i);否则称 为非周期的( aperiodic)。 由定义立即可知,若n不是d()的倍数,则P=0 定理43.2:若i)j,则d()=d()。 证明:由于j,故彐m,n使得Pm>0,P)>0。于是Pm>0。若有s使得 P”>0,则Pm”>0。由于dO+m,dOn+m+s,因此d(,进而 dOd()。同理有dO)l(),故d()=d() 定理43.3:存在正整数N使得对所有的n>N恒有Pm0)>0 证明依赖于一个数论知识:若k个正整数n1,n2…n4互素,则存在正整数N使得 对所有的n>N都存在非负整数a1,a2,…a使得n=∑an。对状态i,若定理 4.3.1：Mrakov 链不可约⇔ 所有状态之间是相通的。 证明：⇐显然。⇒（反证法）若存在两状态i, j 不是相通的，不妨设i →/ j 。令 C = {k i → k}，则首先 j ∉C ；其次对∀k ∈C,∀l ∉C, Pkl = 0。因此 为一个闭集， 而这与 Mrakov 链不可约矛盾。 C 例 4.3.1：若 Markov 链一步转移概率矩阵为 ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ ⎛ = 1 1/ 2 1/ 2 1 1/ 2 1/ 2 1/ 4 3 / 4 5 4 3 2 1 1 2 3 4 5 P { } 1,2 ,{3,4,5}在相通意义下为两个等价类，此链是可约的。 定义 4.3.3：记 ( ) gcd{ 1, 0} ( ) = ≥ > n n n Pii d i ，这里 表示最大公因子（greatest common divisor），若 ，称 为周期的（periodic），且周期为 ；否则称 为非周期的（aperiodic）。 gcd d(i) >1 i d(i) 由定义立即可知，若n 不是d(i) 的倍数，则 Pii (n) = 0 。 定理 4.3.2：若i ↔ j ，则d(i) = d( j) 。 证明：由于i ↔ j ，故 使得 。于是 。若有 s 使得 ，则 。由于 ∃m, n 0, 0 ( ) ( ) > > n ji m Pij P 0 ( ) > n+m Pjj 0 ( ) > s Pii 0 ( ) > n+m+s Pjj d( j) n + m ， d( j) n + m + s ，因此 d( j)s ，进而 d( j) d(i) 。同理有d(i) d( j) ，故d(i) = d( j) 。 定理 4.3.3：存在正整数 N 使得对所有的n > N 恒有 Pii (nd (i)) > 0。 证明依赖于一个数论知识：若 个正整数 互素，则存在正整数 使得 对所有的 都存在非负整数 使得 。对状态 i ，若 k n n Lnk , , 1 2 N n > N a a Lak , , 1 2 ∑= = k i n aini 1 4