实例2马氏链模型 问题1.迷宫问题 3(白) 试验者想分析不同颜色对老鼠 1(红)2(蓝) 的吸引作用。他设计了一个迷宫如 右图 他把一只老鼠放入迷宫的某一间,然后周期性 地定时观察老鼠的位置 问题分析老鼠的运动带有随机性,利用概率 论中的马氏链理论进行研究 假设 1.若观察时老鼠位于第j个分隔间,称老鼠 处于状态j 2.以P表示老鼠处于初始状态j的概率, 概率向量 P(0)=(P,P,PB) 称为初始概率分布。 (一般地,一个行向量的所有分量非负,分量之 和为1,称为概率向量)。 *3P表示老鼠从状态i运动到状态j的概率, 称P,i=1,2,3为转移概率,矩阵A=(P)为转 移矩阵,满足 1)0≤P≤1;
实例 2 马氏链模型 问题 1．迷宫问题 试验者想分析不同颜色对老鼠 的吸引作用。他设计了一个迷宫如 右图. 他把一只老鼠放入迷宫的某一间，然后周期性 地定时观察老鼠的位置. 问题分析 老鼠的运动带有随机性，利用概率 论中的马氏链理论进行研究. 假设 *1. 若观察时老鼠位于第 j 个分隔间，称老鼠 处于状态 j； *2. 以 0 j P 表示老鼠处于初始状态 j 的概率， 概率向量 P （0） =（ 0 P1 ， 0 P2 ， 0 P3 ） 称为初始概率分布。 （一般地，一个行向量的所有分量非负，分量之 和为 1，称为概率向量）。 *3 Pij 表示老鼠从状态 i 运动到状态 j 的概率， 称 Pij ，i,j=1，2，3 为转移概率，矩阵 A=（ Pij ）为转 移矩阵，满足 1） 0≤ Pij ≤1； 3（白） 1（红） 2（蓝）
2)∑P (一般,若方阵A的行向量是概率向量,称之为 转移矩阵)。 建模P表示第n次观察时,老鼠位于第j 个分隔间的概率由全概率公式可得: P=PP1+PB1+P"P,j=1,23.(1) 老鼠的运动具有马氏性(无后效性):在第n次 观察时,老鼠处于各状态的概率仅与第n-1次观察 时所处状态的概率以及转移概率有关,而与第n-1 之前的状态无关 老鼠的这一种随机转移过程是一类马氏链。 式(1)可改写为矩阵形式 Pt-A n=1,2 其中,P0=(P,P2,P0),A=(P)3×3,有递推 公式: A A A 由老鼠的初始分布可确定任何一次的分布情况。 定理1设A是一个马氏链的转移矩阵,P是 初始分布,则第n步的概率分布为
2） 1 3 1 = j= Pij . （一般，若方阵 A 的行向量是概率向量，称之为 转移矩阵）。 建模 (n) Pj 表示第 n 次观察时，老鼠位于第 j 个分隔间的概率.由全概率公式可得： , 1,2,3. (1) 3 ( 1) 2 3 ( 1) 1 2 ( 1) 1 ( ) = + + = − − − P P P P P P P j j n j n j n n j 老鼠的运动具有马氏性（无后效性）：在第 n 次 观察时，老鼠处于各状态的概率仅与第 n-1 次观察 时所处状态的概率以及转移概率有关，而与第 n-1 之前的状态无关. 老鼠的这一种随机转移过程是一类马氏链。 式（1）可改写为矩阵形式： P (n) = P (n−1) A, n = 1,2, 其中， ( , , ) 0 3 0 2 0 1 (0) P = P P P ，A=（ Pij ）3×3, 有递推 公式： (n) P = (n−1) P A= (n−2) P A2=…= (0) P An , (2) 由老鼠的初始分布可确定任何一次的分布情况。 定理 1 设 A 是一个马氏链的转移矩阵， (0) P 是 初始分布，则第 n 步的概率分布为
P=P0A",n=1,2,… 模型分析 例取P=(13,1/3,1/3),老鼠运动的转移 矩阵是 0.10.70.2 A=0.30.40.3 0.50.20.3 第三次观察时,老鼠在各个分隔间的概率分布为 0.10.70.2 3 P3)=P0A=(13,13,13)030403 0.50.20.3 (0.295,0.434,0.271) 要了解老鼠最终的活动情况,需要考察当n→∞时, P的变化趋势 0.5 0.5 例设转移矩阵R=0703,有 0.5 0.5 0.6 0.4 R2=0.7 0.3 0.56 0.44 0.5 0.5 0.58 0.42 R3=0.7 0.3 0.588 0.412 0.50.5 0.584 0.416 R4= 0.7 0.3 0.5842 0.4158
(n) P = (0) P An , n=1，2，… 模型分析 例 取 (0) P =（1/3，1/3，1/3），老鼠运动的转移 矩阵是 A= 0.5 0.2 0.3 0.3 0.4 0.3 0.1 0.7 0.2 ， 第三次观察时，老鼠在各个分隔间的概率分布为 (3) P = (0) P A3=（1/3，1/3，1/3） 3 0.5 0.2 0.3 0.3 0.4 0.3 0.1 0.7 0.2 =（0.295，0.434，0.271）, 要了解老鼠最终的活动情况，需要考察当 n → 时， (n) P 的变化趋势. 例 设转移矩阵 R= 0.7 0.3 0.5 0.5 ，有 R2= 2 0.7 0.3 0.5 0.5 = 0.56 0.44 0.6 0.4 , R3= 3 0.7 0.3 0.5 0.5 = 0.588 0.412 0.58 0.42 ’ R4= 4 0.7 0.3 0.5 0.5 = 0.5842 0.4158 0.584 0.416
0.5833 0.4167 当n→∞时,Rr 1212 0.5833 0.4167≈75 1212 令m=(m/12,5/12),有R=u,称u是矩阵R 的不动点向量 若老鼠的转移矩阵具有不动点向量,说明随着 转移次数的增大(时间的推移),老鼠的运动规律趋 于稳定 哪些转移矩阵具有不动点向量? 定义:一个马氏链的转移矩阵A是正则的,当且 仅当存在正整数K,使A的每一个元素都是正数 具有正则转移矩阵的马氏链称为正则链 定理2若A是一个马氏链的正则阵,则 (1)A有唯一的不动点向量W,W的每一个 分量为正; (2)A的n次幂A"(n为正整数)随n的增大而 趋于矩阵W,W的每一个行向量等于不动点向量 老鼠的转移矩阵是正则阵,由定理2可得 P(m)p(0)An→p(ow, 老鼠的运动随时间推移,逐渐趋于稳定。 问题2信息传播问题
当 n → 时， Rn → 0.5833 0.4167 0.5833 0.4167 ≈ 12 5 12 7 12 5 12 7 令 u=（7/12 ， 5/12），有 uR=u, 称 u 是矩阵 R 的不动点向量. 若老鼠的转移矩阵具有不动点向量，说明随着 转移次数的增大(时间的推移), 老鼠的运动规律趋 于稳定. 哪些转移矩阵具有不动点向量？ 定义：一个马氏链的转移矩阵 A 是正则的，当且 仅当存在正整数 K，使 AK 的每一个元素都是正数. 具有正则转移矩阵的马氏链称为正则链。 定理 2 若 A 是一个马氏链的正则阵，则 （1）A 有唯一的不动点向量 W，W 的每一个 分量为正； （2）A 的 n 次幂 An (n 为正整数)随 n 的增大而 趋于矩阵 W ， W 的每一个行向量等于不动点向量 W. 老鼠的转移矩阵是正则阵，由定理 2 可得 P (n) = P (0) A n → P (0)W ， 老鼠的运动随时间推移，逐渐趋于稳定。 问题 2 信息传播问题
条消息在人群中传播,每次由第i个人传给 第计1人,每次传播消息时的失真概率为p,0<p <1,经过长时间传播后,第n个人得知消息的真 实程度如何? 建模设整个传播过程是随机转移过程,转移矩 阵为 假 真 P P 假 R P 真 因0<p<1,R是正则阵。 设初始分布为v,则经过n次传播以后,消息 处于真、假状态的概率 分布为 f,n=1.2 模型求解需求出R的不动点向量W 一般的2阶正则阵有如下形式 A b 1-b 0<a<1,0<b<1 记A的不动点向量为W=(w1,w2),应满足 WA=W,即 WA=(1,w2 b b WI(
一条消息在人群中传播，每次由第 i 个人传给 第 i+1 人，每次传播消息时的失真概率为 p ，0＜p ＜1，经过长时间传播后，第 n 个人得知消息的真 实程度如何？ 建模 设整个传播过程是随机转移过程，转移矩 阵为 R = − − p p p p 1 1 因 0＜p＜1，R 是正则阵。 设初始分布为 v, 则经过 n 次传播以后，消息 处于真、假状态的概率 分布为 P (n) =VRn , n = 1,2, 模型求解 需求出 R 的不动点向量 W. 一般的 2 阶正则阵有如下形式 − − = b b a a A 1 1 ，0＜a＜1，0＜b＜1， 记 A 的不动点向量为 W=（w1, w2）,应满足 WA=W，即 − − = b b a a WA w w 1 1 ( , ) 1 2 = w1(1 － 假 真 假 真
a)+w2b,w1a+w2(1-b), WI=W1(1-a)+w2b 故 W2=w1a+w2(1-b), W1+1= 2 解得 W=( a+b a+b 信息传播转移矩阵R中,=b=p,得不动点向量 为W=(1/2,1/2),根据定理2知当n→∞时, R→ 2 2 若初始分布为v=(p,1-p),则经过n步传播后 处于真、假状态的概率分布是 2 p()=vR→(p,1-p) =(12,12 结论分析:说明消息的真实程度极低 问题3另一类迷宫问题 迷宫的四个分隔间都是相 通的在第四分隔间里放有食物 4(食物) 分析:老鼠受到食物的吸引 不会再运动到其它房间
a)+w2b, w1a+w2(1－b)）, 故 + = = + − = − + w 1. w (1 ), w w (1 ) , 1 2 2 1 2 1 1 2 w w a w b a w b 解得 W= ( , ) a b a a b b + + . 信息传播转移矩阵 R 中，a=b=p, 得不动点向量 为 W=（1/2，1/2），根据定理 2 知,当 n→∞时， → 2 1 2 1 2 1 2 1 R n , 若初始分布为 v =（p, 1－p）,则经过 n 步传播后 处于真、假状态的概率分布是 (n) P = vRn → (p,1－p) 2 1 2 1 2 1 2 1 =(1/2,1/2). 结论分析：说明消息的真实程度极低. 问题 3 另一类迷宫问题 迷宫的四个分隔间都是相 通的,在第四分隔间里放有食物. 分析：老鼠受到食物的吸引 不会再运动到其它房间. 3 4（食物） 2 1
建模老鼠运动过程的转移矩 阵为 234 10.30.300.4 2|0.20.30.20.3 T 300.30.30.4 (Pij ), 40001 模型分析: 1)老鼠一旦进入状态4,它将永远停留在状 态4,称状态4为吸收状态; 2)从任何一个状态出发,都可以进入状态4。 定义:若马氏链至少含有一个吸收状态,并且 从每一个非吸收状态出发,都可以到达某个吸收 状态,称此马氏链为吸收链 例随机游动问题 一个醉汉在一条大街上徘徊,若他位于第i个街 口,他会以各为1/3的概率向前 2 3 5 或向后移动,或以1/3的概率留在原处;当他走到 1和5时就会停下不动了 醉汉运动的转移矩阵为: 1234
建模 老鼠运动过程的转移矩 阵为 1 2 3 4 T = ( ), 0 0 0 1 0 0.3 0.3 0.4 0.2 0.3 0.2 0.3 0.3 0.3 0 0.4 4 3 2 1 = pij 模型分析： 1）老鼠一旦进入状态 4，它将永远停留在状 态 4，称状态 4 为吸收状态； 2）从任何一个状态出发，都可以进入状态 4。 定义：若马氏链至少含有一个吸收状态，并且 从每一个非吸收状态出发，都可以到达某个吸收 状态，称此马氏链为吸收链。 例 随机游动问题 一个醉汉在一条大街上徘徊，若他位于第 i 个街 口， 他会以各为 1/3 的概率向前 1 2 3 4 5 或向后移动，或以 1/3 的概率留在原处；当他走到 1 和 5 时就会停下不动了. 醉汉运动的转移矩阵为： 1 2 3 1 2 3 4 5
10 01-31-31-30 000 33 3 T 00 00 1—31-3 这是一个吸收链,吸收状态是“1”和“5”。 模型求解:对矩阵T进行行初等变换与列初等 变换,得到T的等价矩阵 10 0- 500131313 000 R S 0 0 3 般,有n个状态,r个吸收状态的吸收链的 转移矩阵的标准形式为: T R S 其中,S为s×s矩阵,s=n-r,S是非吸收状 态到非吸收状态的转移矩阵
T = 3 1 0 0 0 0 3 1 3 1 3 1 0 0 0 3 1 3 1 3 1 3 1 0 0 3 1 3 1 1 1 0 0 0 0 ， 这是一个吸收链，吸收状态是“1”和“5”。 模型求解： 对矩阵 T 进行行初等变换与列初等 变换，得到 T 的等价矩阵： T τ = 3 1 3 1 0 3 1 0 3 1 3 1 3 1 0 0 0 3 1 3 1 0 3 1 0 1 0 0 0 1 0 0 0 0 = R S E2 O . 一般，有 n 个状态，r 个吸收状态的吸收链的 转移矩阵的标准形式为： T= R S Er O ， 其中，S 为 s × s 矩阵，s=n－r , S 是非吸收状 态到非吸收状态的转移矩阵 1 5 2 3 4 1 5 2 3 4
定义:在吸收链的标准形式中,称F=(E S)-1为基矩阵。 定理3:设吸收链的基矩阵为F,有 1)F的元素f是从非吸收状态“i”到达非吸 收状态“”的平均转移次数; 2)F的第i行元素之和是从非吸收状态“i出 发,被某个吸收状态吸收之前的平均转移次数 定理4:令B=FR=(E-S)R=(b),则b 是从非吸收状态i出发,被吸收状态j吸收的概率 练习设醉汉问题中的状态“1”是表示“回到 酒吧”,状态“5”是表示“回家”,试计算他从各街 口回家或重回酒吧的平均徘徊次数 问题4智力竞赛问题 甲乙两队进行智力竞赛,赛前规定如下: 1)比赛前双方各记2分; 2)每比赛一次,胜方得1分,负方则扣去1分 有一队总分达4分时结束比赛 甲队赢1分的概率为p,0<p<1,讨论 1)甲队获得1,2,3分的平均次数? 2)决出胜负时,甲队分数的平均转移次数? 3)甲队最终获胜的概率? 分析:甲队的可能得分是0、1、2、3、4,分
定义：在吸收链的标准形式中，称 F=（Es －S）－1 为基矩阵。 定理 3：设吸收链的基矩阵为 F，有 1）F 的元素 fij 是从非吸收状态“i”到达非吸 收状态“j”的平均转移次数； 2）F 的第 i 行元素之和是从非吸收状态“i”出 发，被某个吸收状态吸收之前的平均转移次数. 定理 4：令 B=FR=（Es－S）－1R=（bij）, 则 bij 是从非吸收状态 i 出发，被吸收状态 j 吸收的概率. 练习 设醉汉问题中的状态“1”是表示“回到 酒吧”，状态“5”是表示“回家”，试计算他从各街 口回家或重回酒吧的平均徘徊次数. 问题 4 智力竞赛问题 甲乙两队进行智力竞赛，赛前规定如下： 1）比赛前双方各记 2 分； 2）每比赛一次，胜方得 1 分，负方则扣去 1 分， 有一队总分达 4 分时结束比赛. 甲队赢 1 分的概率为 p, 0＜p＜1，讨论： 1）甲队获得 1，2，3 分的平均次数？ 2）决出胜负时，甲队分数的平均转移次数？ 3）甲队最终获胜的概率？ 分析：甲队的可能得分是 0、1、2、3、4，分
别记为a、a1、a2、a3、a4,其中a0、a4是吸收状态, a1、a2、a3是非吸收状态。并且a2是初始状态。 建模:建立转移矩阵 2 3 a4 0 000 00 P 0 p 0 T 3 01-p0p 00 (4 T矩阵等价于 ao a1 10000 (4 01000 P 00 P 2 3 P E, O R S 分数的转移过程的基矩阵为 100 0 0 0 P 001 01 P
别记为 a0、a1、a2、a3、a4，其中 a0、a4是吸收状态， a1、a2、a3 是非吸收状态。并且 a2 是初始状态。 建模：建立转移矩阵 T = − − − 0 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 p p p p p p ， T 矩阵等价于 T τ = − − − 0 0 1 0 0 0 1 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 p p p p p p = R S E2 O 分数的转移过程的基矩阵为 F= 1 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 0 − − − − p p p p a0 a1 a2 a3 a4 a0 a4 a1 a2 a3 a0 a1 a2 a3 a4 a0 a4 a1 a2 a3