第6章 连续参数马尔可夫链
在第3章中,曾详细地讨论了离散参数马尔可夫链的有关问题,本章将着重研究连续参数可列状态空间的马尔可夫过程.
6.1 定义与若干基本概念
仍记状态空间为S={0,1,2,…}.
定义6.1.1 设随机过程X={X(t), t≥0}对于任意0≤t0
0,就有
P{X(tn+1)=in+1|X(t0)=i0, X(t1)=i1, …, X(tn)=in}
=P{X(tn+1)=in+1|X(tn)=in},
(6.1.1)
则称{X(t), t≥0}为连续参数马尔可夫链(简称连续参数马氏链). 若对于任意s,t≥0, i,j∈S,有
P{X(s+t)=j|X(s)=i}=P{X(t)=j|X(0)=i}
Pij(t),
称X为齐次马尔可夫链. 本章仅讨论齐次马尔可夫链. 称P(t)=(Pij(t))(i,j∈S)为转移概率矩阵. 易知,它满足:
(P.1)
Pij(t)≥0, i,j∈S;
(P.2)
, i∈S;
(P.3)
Pij(s+t)=
Pkj(t), s.t≥0, i,j∈S;
((P.3)式通常称为Chapman-Kolmogorov方程,或C-K方程)
(P.4) Pij(0)=δij, δii=1, δij=0 (j≠i).
本章还附加所谓标准性条件
(P.5)
δij(即Pij(t)在原点连续).
将(P.3), (P.4), (P.5)式写成矩阵形式
P(s+t)= P(s) P(t),
P(0)=I,
P(t)=I (I为单位矩阵).
如果P(t)满足(P.1)~(P.4),并且还满足附加连续性条件(P.5),则P(t)有许多很好的分析性质.
命题6.1.1 若P(t)=(Pij(t))为标准性转移概率矩阵,则:
(1)对任意给定i∈S,Pij(t)在[0,∞
上一致连续,且此时一致性对j亦成立;
(2)
t≥0, i∈S, Pii(t)>0.
证明 (1)由C-K方程,对
t, h>0有
Pij(t+h)-Pij(t)=
Pkj(t)-Pij(t)[1-Pii(h)],
由此得
Pij(t+h)-Pij(t)≤
Pkj(t)≤
=1-Pii(h)
以及
Pij(t+h)-Pij(t)≥-Pij(t)(1-Pii(h))≥-(1-Pii(h)),
从而有|Pij(t+h)-Pij(t)|≤1-Pii(h). 类似地,当h<0时,有
|Pij(t)-Pij(t+h)|≤1-Pii(h).
(2)由Pii(0)>0及标准性条件(
)可知,对任意固定t>0,当n充分大时,有Pii(t/n)>0,再由C-K方程(Pii(s+t)=
Pik(s)Pki(t)≥Pii(s)Pii(t)),可得Pii(t)≥(Pii(t/n))n>0.
□
记πi(t)=P(X(t)=i),
i∈S, t≥0,称π(t)=(πi(t), i∈S)为马尔可夫链X={X(t), t≥0}在t时刻的分布,称π(0)=(πi(0), i∈S)为初始分布. 与第3章类似的证明方法可以证明,对于连续时间的马尔可夫链的任意n个时刻的联合分布律,可由其π(0)与P(t))唯一确定,且
t≥0,π(t)=π(0)P(t).
对于连续时间的马尔可夫链X={X(t), t≥0},任取h>0,定义
Xn(h)=X(nh),
n≥0.
由马尔可夫性知,{X(nh), n≥0}是一个离散时间的马尔可夫链,称为以h为步长的h-离散骨架,简称h骨架,它的n步转移概率矩阵为P(nh). 显然,h-离散骨架是研究连续时间马尔可夫链的一条有效途径(详见6.10节).
对于连续参数马尔可夫链与离散参数马尔可夫链,由于它们都具有“马尔可夫性”,且状态空间均为可数集或有限集,因而许多概念和性质有相同或相似之处. 例如状态相通,状态分类,不可约链,平稳分布与极限分布等,例如如下的定义.
定义6.1.2 若存在t>0,使Pij(t)>0,则称由状态i可达状态j,记为i→j.若对一切t>0,Pij(t)=0,则称由状态i不可达状态j,记为i→j. 若i→j且j→i,则称状态i与j相通,记为
.
由此定义及命题6.1.1知
i∈S, Pii(t)>0,即
,可知相通关系具有自反性、对称性、传递性,故相通关系是等价关系,从而可以按相通关系给状态分类. 相通的状态组成一个状态类. 若整个状态空间是一个状态类,则称该马尔可夫链是不可约的.
对于连续时间的马尔可夫链,由命题6.1.1知,对所有h>0及正整数n及所有的i∈S, Pii(nh)>0,这意味着对每一个离散的骨架Xn(h),每一个状态i都是非周期的,故由3.5节中关于n步转移概率的极限的讨论,可知对
i,j∈S,
h>0,
总存在,这样,对连续时间的马尔可夫链,就无需引入周期的概念. 而且利用Pij(t)在[0,∞
上的一致连续性及
总存在. 从而可以证明Pij(t)(在t→∞时)极限总存在.
命题6.1.2
i,j∈S, 下述极限总存在
.
证明参见文献[4].
定义6.1.3 (1)若
,则称状态i为常返状态;否则,称i为非常返状态.
(2)设i为常返状态,若
,则称i为正常返状态;若
=0,则称i为零常返状态.
(3)若概率分布
满足下式
称
为X={X(t), t≥0}的(或P(t)的)平稳分布.
(4)若对
存在,则称
为X={X(t), t≥0}的极限分布.
与定理3.5.8相类似的结果和证明,有如下定理.
定理6.1.1 不可约链是正常返链的充要条件是它存在平稳分布,且此时平稳分布就等于极限分布.
证明与定理3.5.8的证明类似,留给读者作为练习.
本章剩下的几节将着重讨论连续参数马尔可夫链中若干比较基本的特殊的问题(相对于离散的马尔可夫链而言). 如:转移率矩阵(Q矩阵)及概率意义,柯尔莫哥洛夫向前向后微分方程,Fokker-Planck方程,生灭过程及应用,强马尔可夫性与嵌入马尔可夫链,以及连续参数PH分布的若干性质、构造及反问题等.
6.2 转移率矩阵——Q矩阵及其概率意义
在离散参数马尔可夫链中,我们知道由一步转移概率矩阵P=(Pij)可以完全确定n步转移阵,即有P(n)=Pn=enlnP,那么对连续参数马尔可夫链,是否有类似的表达式,即P(t)=etQ呢?其中Q为与t无关的实数矩阵,假如上式存在,则应有
P'(0)=
这就提示我们先要研究P(t)在t=0的导数(即变化率)是否存在的问题,先看最简单的一个例子,再给出一般的结论.
例1 设{N(t), t≥0}为时齐泊松过程,参数为λ. 因它是独立增量过程,易知它是连续参数马尔可夫链,则
Pij(t)=P{N(s+t)=j|N(s)=i}
=P{N(s+t)-N(s)=j-i}
故P'ij(t)存在,且
若令Q=(qij),可以验证P(t)满足P(t)=etQ.
对于一般马尔可夫链,有以下定理.
定理6.2.1 对i∈S极限
(6.2.1)
存在,但可能是无限.
证明 首先,由Pii(t)>0, t≥0,故可以定义
. 它非负有限,且由于Pii(s+t)≥Pii(s)Pii(t),有
令
,下面要证
极限存在,且即为其上确界. 显然
0≤qi≤∞,
,
所以以下只需证
.
任给01-ε,Pjj(t)>1-ε, Pji(t)<ε.
下面要证:对任意0≤h0, X(t)≠X(0)}.
τ1表示逗留在初始状态的时间(或首次离开初始状态的时间)。τ1的概率特性与Q=(qij)有何关系呢?
定理6.2.3 设马尔可夫链X={X(t), t≥0}轨道右连续,则对i∈S,t≥0,有
(6.2.5)
证明 由轨道右连续,得
P(τ1>t|X(0)=i)=P[X(u)=i, 0≤u≤t|X(0)=i],
所以,首先要将不可列事件转化为可列事件运算. 令
将[0,t]区间2n等分,记
因为An+1
An,所以记
显然B
A,另一方面,由过程轨道右连续可以证明P(A-B)=0,故P(τ1>t|X(0)=i)=P(X(u)=i,0≤u≤t|X(0)=i)
=P(B|X(0)=i)
=P(A|X(0)=i)
=
P(An|X(0)=i)
=
P(X(kt/2n)=i,k=0,1,2,…,2n|X(0)=i)
=
(Pii(t/2n))
(马氏性)
=
exp{2nlnPii(t/2n)}
=
exp
=exp(-qit). (因为由qi的定义知Pii(t)=1-qit+o(t)
□
这说明系统逗留在X(0)=i状态的时间τ1是服从参数为qi的指数分布的,显然
E[τ1|X(0)=i]=q-1i.
可见,qi决定了过程{X(t), t≥0}停留在X(0)=i的平均逗留时间,它刻画了过程从i出发的转移速率,分3种情形:
(1)qi=0,称i为吸收状态,这是因为
即从i出发,过程以概率1永远停留在i状态.
(2)qi=∞,称i为瞬时状态,此时P[τ1=0|X(0)=i]=
,这说明X在i状态几乎不停留立即跳到别的状态.
(3)00时
. (6.3.4)
由Fatou引理,有
. (6.3.5)
另一方面,对N>i,有
令N
,由保守性得
. (6.3.6)
由(6.3.5)及(6.3.6)式得
.
再由(6.3.4)式得
.
仍由保守性知,上式右边的级数关于t一致收敛,因此是t的连续函数,故由引理6.3.1得定理.
考虑X(t)在t时刻的概率分布,记Pj (t) = P (X (t) = j),显然
.
于是有下面的结论.
定理6.3.3 当S为有限集时,成立下列Fokker-Planck方程
. (6.3.7)
证明 由(6.3.1a)式两边同乘以Pi(0)并对i求和即得(6.3.7)式.
□
为了解决具体问题,先回顾一下平稳分布和极限分布的概念.若一概率分布{
, j
S}满足
,则称{
, j
S }为平稳分布.与离散时间马尔可夫链有相类似的结果:当马尔可夫链X = {X(t), t≥0}为不可约遍历链时,则必存在唯一的平稳分布{
, j
S},且它就等于极限分布,即
=Pj (j
S).从而有以下定理.
定理6.3.4 当S为有限集且为不可约链时,其平稳分布
= (
, j
S)存在,且满足
.
证明 由于
, 在(6.3.1a)式两边对t取极限。
有了以上理论上的准备,可以进一步讨论由密度矩阵Q求解转移概率矩阵P(t)的几种方法.
(1)当S有限时,可以利用分析的方法求解向前向后微分方程.
例1 设某触发器状态只有两个,S = {0,1},“0”表示工作态,“1”表示失效态.X(t)表示t时触发器状态.已知其状态转移具有马尔可夫性,即X = {X (t), t≥0}为马尔可夫链,且P01(t) =
+o(t), P10(t) =
t+o(t),从而得
Q =
.
试求P(t) = (Pij(t)) (设P0(0) = 1).
解 由向后方程得
.
经适当简化后有
,
两边积分得
.
再由初始条件P00(0) = 1,P10(0) = 0,于是有
采用解常系数微分方程常用的常数变易法,解之得
.
从而
,
,
.
再由P0 (0) = P (X (0) = 0) = 1,得
,
.
再求平稳分布(也是极限分布),得
及
.
(2)当S为可列集时,若已知Q = (qij),欲求满足向前向后方程P (t)的解,可用概率构造法求之,这里仅以Q矩阵为保守(即qi<∞),且过程轨道右连续为例,求解向后方程.令
= 0,
= inf {t: t >
, X(t)≠X(
)}, n≥1,
nPij (t) = P[
≤t<
, X(t) = j | X(0) = i].
则首先易得
0Pij (t) =
,
再由全概率公式可求递推关系
n+1Pij (t) = P[
≤t<
, X(t) = j | X(0) = i]
=
×
P(
≤t<
, X(t) = j | X(0) = i,
=s, X(
) = k) ×
dP(
≤s, X(
) = k | X(0) = i) (对
及X(
)用全概率公式)
=
qik nPkj (t-s)ds
以上递推式也可有如下直观概率解释:
n+1Pij (t) =
(qik ds) ( nPkj (t-s)),
其中,
表示在[0, s]上停留在i状态的概率,qik ds表示在[s, s+ds]时间上恰有一次跳跃且跳到k状态的概率,nPkj (t-s)表示在余下时间内发生n次跳跃且X(t) = j的概率. 最后,对k求和,对时间s从0到t积分.
有了以上递推公式后,令
,则可验证F(t) = (fij (t))是向后方程的最小非负解. 这启示我们:可以借助于概率方法求某一类微分方程的解.
(3)用拉普拉斯变换求解向前向后微分方程. 它将这些方程转化成代数方程,以便于用代数方法作处理. 为此首先叙述一些必需的有关拉普拉斯变换的基本知识.
引理6.3.2 设[0, ∞]上的函数f (t)的拉普拉斯变换为
,则
,q>0
的拉普拉斯变换为
.
证明 直接计算即可.
在上述计算过程中以| f (s)|代f (s),由
可知,在计算中交换积分号是可行的,且
.
□
对于转移概率矩阵P (t),由于Pij (t)是
上的有界连续函数,它有拉普拉斯变换,记为
.
令
R
=
,
.
它们称作转移概率函数的预解式,有下面的性质.
定理6.3.5 对一切
及
有
(1)
>0;
(2)
;
(3)
;
(4)
.
或写成以下简洁的矩阵形式:
(
) R(
)≥0;
(
)
R(
)e = e ( e = (1, 1,…, 1)T);
(
) R(
)–R(
)+(
–
)R(
)R(
)=0;
(
)
称(
) ~ (
)为预解方程.
证明 称(1),(2)容易证,留给读者练习,这里只证(3)与(4).
(3) 可由C-K方程用如下方法推得.
(6.3.8)
现在不妨设
.注意到
有
(6.3.9)
易见,若
,可得到同样的结果. 由(6.3.8)和(6.3.9)式即得(3).
(4)可由连续性条件推得. 事实上
,
由控制收敛定理即得(4). □
下面引入向后方程的积分形式
. (6.3.10)
实际上,由向后方程
,可得
即得(6.3.10)式. 对其取拉普拉斯变换,利用引理6.3.2,得到预解式满足的向后方程(线性代数方程组)
.
类似地,也可得到向前方程的积分形式和向前线性代数方程组. 这样,解微分方程就转化成求解线性代数方程组了.
6.4 生灭过程
这一节转到讨论一类特殊的马尔可夫链——生灭过程,它在排队系统、可靠性理论、生物、医学、经济管理、物理、通讯、交通等方面有广泛的应用. 而且它的理论成果罗为系统,成熟和深入.
定义6.4.1 设马尔可夫链X = {X(t), t≥0},状态空间S = {0, 1, 2,…},若P (t) = (Pij (t))满足:当h充分小时,
(6.4.1)
称X为生灭过程.
(6.4.1)式表示,当h充分小时,状态转移有3种可能:i
i+1, i
i–1, i
i. 这个特性是许多生物群体,粒子裂变,信号计数等的共同特点,因而可作为这一类物理自然现象的数学模型.
由(6.4.1)式知:qi = (
), qi,i+1 =
, qi,i–1 =
,其他qij = 0,即Q = (qij)表示为
Q =
(6.4.2)
形如(6.4.2)式的矩阵,称作生灭过程Q矩阵. 显然,它是保守Q矩阵,且在
>0(i≥0),
>0(i≥1)时,有i–1
i
i+1(i≥1),可知对
,i
j,从而这样的生灭过程是不可约链,同时有以下定理.
定理6.4.1 若X为生灭过程,则P (t),Q满足向前向后方程
, (6.4.3)
. (6.4.4)
且{Pj (t),
}满足Fokker-Planck方程
(6.4.5)
证明 先证(6.4.3)式.
由C-K方程及(6.4.1)式,有
令h
0即得(6.4.3)式. 类似可证(6.4.4)式. 由(6.4.3)式两边乘以Pi (0)再对i求和,并注意到Pj (t) =
,即得(6.4.5)式.
□
如X的极限分布存在,即Pj =
Pij (t)存在,且与i无关(
),则有
.因此由(6.4.5)式令
,两边取极限得
(6.4.6)
解(6.4.6)式的代数方程组,得
再由
,得
可知,当
(6.4.7)
时,01). 因此,(6.4.7)式成立是(6.4.6)式的代数方程组存在唯一的极限分布解的充要条件. 进一步有以下结论.
定理6.4.2 设X = {X(t), t≥0}为生灭过程,
>0, i≥0,
>0, i≥1(
=0),则X存在唯一的平稳分布(它等于极限分布)的充要条件为(6.4.7)式成立,即
,
且P0 =
Pk =
证明 注意到当
>0, i≥0,
>0, i≥1时,此过程为不可约链. 再由定理6.1.1可知,它是正常返链的充要条件是存在平稳分布,且就等于极限分布,而(6.4.7)式成立是(6.4.6)式代数方程存在唯一极限分布的充要条件.
□
通常在排队论中,若存在极限分布,且等于平稳分布,称此时系统处于统计平衡,简称稳态.
例1 M/M/1排队系统,即顾客到达流是参数为
的泊松流,每个顾客的服务时间独立同分布,服从参数为
的指数分布且与顾客到达时间相互独立,另外只有一个服务员. 记X(t)表示系统t时刻顾客数,易知{X(t), t≥0}为生灭过程,
=
(i≥0),
=
(i≥1,
=0). 显然,当
<1时,00时,由全概公式
G(x) =
= P(Tg≤x, X(s) = 0) +
.
在X(s) = n条件下,Tg应等于n–1个顾客服务时间之和再加上正在服务的顾客的剩余服务时间,再由指数分布的无记忆性,知P(Tg≤x | X(s) = n)应等于参数为
的指数分布的n重卷积,即
故
平均等待时间
.
(4)费用最优的参数
考虑最优服务率
的问题,设每一顾客在系统一小时损失C1元,服务机构每小时费用正比于
,比例系数为C2,记R(
)为每小时费用,则系统平均每小时费用损失为
. 如何选取最优的
,使ER (
) = minER (
). 显然由
,可得
. □
例2 一台大型计算机系统,有m个终端,假定可能的用户有无限多. 在(t, t+h)内又有一用户要求使用终端的概率为
h+o(h) (
>0, h充分小),并与正在使用的用户无关. 此时若有空闲终端,则它占用一终端;否则,因终端占满,请示使用的用户被取消. 又假定每一个在t时刻正在占用一终端,在(t, t+h)内使用完毕而空出的概率为
h+o(h). 各用户正在占用与结束之间相互独立. 设X(t)表示t时刻正在占用的终端数,易验证{X(t), t≥0}为马尔可夫链,且是有限状态生灭过程,S={0, 1, 2,…, m}. 依题意有
Pi,i+1(h) =
h+o(h), 0≤i≤m–1;
Pi,i–1(h) =i
h+o(h), 1≤i≤m;
Pii (h) = 1–(
+i
)h+o(h), 0≤i≤m–1;
Pij (h) = o(h), | j-i |≥2;
Pmm(h) = 1–m
h+o(h).
则相应的极限分布{Pj, 0≤j≤m}满足方程(6.4.6) (0≤j≤m). 解之得
,再由
知
,
0≤k≤m. □
考虑几个特殊的生灭过程.
(1)有迁入的线性增长模型
生灭过程X = {X(t), t≥0},若
,
,
>0,
>0, a>0,称X为有迁入线性增长模型. 它用于描述生物再生和人口增长过程. 假定群体中的每个个体以指数率
出生,同时,群体由于从外界迁入的影响又以系数a增加,而群体中每个个体以指数率
死亡. 这时方程(6.4.3)化为
(6.4.8)
记Mi (t) = E [X (t)|X (0) = i] =
,则由(6.4.8)式两边乘以j,再对j求和,可知(Mi(t), t≥0)满足下列微分方程
解之得到
(6.4.9)
且
这在直观上的意义是很明显的.
(2)纯生过程(耶洛过程)
泊松过程是一个最简单的纯生过程,它是当
的生灭过程. 泊松过程的一个自然推广是在给定时刻一事件发生的可能性依赖于已发生的事件数,即对于充分小的h≥0,若Pi,i+1(h) =
+o(h),Pii(h) = 1–
+o(h),其他Pij(h) = o(h), j>i+1, Pij(h) = 0, ji+1时,Pij (h) = o(h);j
, Y (1) (t)≠Y (1) (
)}.
本章以下几节总假定时齐马尔可夫链X = {X(t), t≥0}轨道右连续,Q = (qij)为保守Q矩阵,且00,每个服务员的服务率为μ>0,若λ1, t1, t2, …, tn≥0,则
P(T1-T0≤t1, T2-T1≤t2, …, Tn-Tn-1≤tn|X0, X1, …, Xn)
=G(X0, X1, t1)G(X1, X2, t2)……G(Xn-1, Xn, tn),
(6.8.2)
即给定{Xn, n≥0}时,逗留时间序列{
n=Tn-Tn-1, n≥1}条件独立. 特别地,若S只有一个状态时,则{
n, n≥}独立同分布.
证明 用数学归纳法.
□
推论 若S只由一个状态组成,则T={Tn, n≥1}是一更新过程.
可见,马尔可夫更新过程是更新过程的推广.
有时,人们关心的是到达某状态的性态. 设j∈S固定,令
是第n次访问j的时刻,
-
是第n次与第n-1次访j的时间间隔.
命题6.8.3 令j∈S固定,则Sj={
, n≥0}是延时更新过程,即
,
…相互独立,且
同分布.
其证明由命题6.8.2的推论及下面命题6.8.4即得.
在马尔可夫更新过程中,允许Tn=+∞, X∞=∞. 为使状态空间S紧化,在S中增加一新的状态,记为∞. 设对状态子集
,记
命题6.8.4
是状态空间为
的马尔可夫更新过程.
证明从略.
给定马尔可夫更新过程{X, T}={(Xn, Tn), n≥0}.
t≥0,令
称Y={Y(t), t≥0}为由马尔可夫更新过程(X, T)产生的(最小)半马尔可夫过程.
显然,Y是连续参数随机过程,是否是马尔可夫过程呢?一般情况下回答是否定的. 但是在其更新点{Tn, n≥0}上{Y(Tn)=Xn, n≥0}是一马尔可夫链,故称Y={Y(t), t≥0}为半马尔可夫过程.
例1 M/G/1排队系统,即顾客到达流是参数为λ的泊松流,服务员对每位顾客的服务时间独立同分布,分布函数为G(x),且与到达流独立. 令T0=0,Tn表示第n个顾客离开时刻(n≥1), Xn为第n个顾客离开时刻
系统中的顾客数. 先证(X, T)={(Xn, Tn), n≥0}是状态空间S={0,1,2,…}的马尔可夫更新过程.
证明
P(Xn+1=j, Tn+1-Tn≤t|X0, T0,…, Xn, Tn)
=
(Xn+1=j|X0, T0, …, Xn, Tn, Tn+1-Tn=u)×
dP(Tn+1-Tn≤u|X0, T0, …, Xn, Tn)(对Tn+1-Tn使用全概率公式)
(Xn+1=j|Xn, Tn+1-Tn=u)dG(u)
(Xn+1只与Xn时数目和间隔u有关,服务时间相互独立,且与到达过程独立.)
=
(Xn+1=j, Tn+1-Tn≤t|Xn, Tn+1-Tn=u)dP(Tn+1-Tn≤u|Xn)
=P(Xn+1=j, Tn+1-Tn≤t|Xn).
□
(X, T)的半马尔可夫核Q(t)=(Q(i, j, t))如下:
Q(t)=
这里
推导如下:记θn=Tn-Tn-1,则Q(i, j, t)=P(Xn=j, θn≤t|Xn-1=i). 当i≥1, j≥i-1时,利用全概率公式
Q(i, j, t)=
{Xn=j, θn≤t|Xn-1=i, θn=x}dG(x)
=
{在[0,x]上恰好到达j-i+1个顾客|Xn-1=i, θn=x}dG(x)
=
当i=1时,Q(1, j, t)=qj(t). 显然,当i≥1, j0, 当r∈S0时,ri=0. 令
为第一次跳跃时间.
,规定:infФ=+∞. 若X(0)∈S0, τ=0. τ表示过程从S到S0的首达时间.
试举几种问题加以讨论.
(1)首达时间与首达目标积分型泛函
令
(其中
>0为折扣率因子)μk(i)=E(Wk|X(0)=i), k≥0, i∈
, M=
. 显然,当i∈S, qi=0时,
.下面仅讨论i∈S的情形,记
,易知,X(0)∈S时,有
(6.9.1)
记Pij
P(X(τ1)=j|X(0)=i)=δij+qij/qi, P=(Pij), i, j∈S;
P=(
k(i)Pij), i, j∈S; Rk(i)=(k
+qi)-1kr(i)μk-1(i), Rk=(Rk(i), i∈S)T, μk=(μk(i), i∈S)T. 易知,0<
1(i)<1, 0<
≤
1(i)<1. 有下面的定理.
定理6.9.1
μ1(i)=R1(i)+
1(i)
, i∈S,
(6.9.2)
即
μ1=R1+
1
P·μ1,
(6.9.3)
μ1=
P)n R1 .
(6.9.4)
证明 对
i∈S
(由强马氏性,
关于X(0)=i, X(
=j条件独立)
=R1(i)+
(由于
与X(
)关于X(0)=i条件独立及强马氏性)
=R1(i)+
(因为E(Wτ1|X(τ1)=j)=E(W|X(0)=j))
=R1(i)+qi(
+qi)-1
从而得μ1(i)=R1(i)+
1(i)
,写成向量形式,即有(6.9.3)式. 注意到,
的谱半径满足0<
,故由(6.9.3)式逐次迭代,有
μ1=R1+
(R1+
·μ1)
= R1+(
)R1+(
)2μ1
=…=
(
)kR1+(
)n+1μ1 .
因为n→+∞,
,即得(6.9.4)式.
□
为了讨论k≥2的情形,先给出两个引理.
引理6.9.1
,当qi>0时有
qi(k
+qi)-1
(6.9.5)
证明 注意到当X(0)=i∈S, X(
时,有
(二项式展开)
于是,类似于定理6.9.1中对k=1的证明,有
μk(i)=E(Wk|X(0)=i)
=(
-1ri)k
qi(m
+qi)-1+
即得(6.9.5)式.
□
引理6.9.2
k≥1,有
(6.9.6)
证明 用归纳法可证.
□
定理6.9.2
k≥1,qi>0,有
.
(6.9.6)
即
(6.9.8)
且
(6.9.9)
证明 利用归纳法及引理6.9.1,引理6.9.2.
当k=1时,公式(6.9.7)即为(6.9.2)式. 现设(6.9.7)式对1≤k≤n均成立,即对1≤l≤n,有
(6.9.10)
以(6.9.10)式及(6.9.6)式代入(6.9.5)式,对k=n+1的情形(并注意到
μ0(i)=1), 有
qi((n+1)
+qi)-1
=[(n+1)
+qi]-1(n+1)riμn(i)+qi[(n+1)
+qi]‑1
.
故(6.9.7)式对k≥1均成立. 由(6.9.7)式即得(6.9.8)式.
□
通过比较(6.9.8)式与(6.9.2)式知,μk与μ1有相同的代数结构.
(2)折扣积分型泛函
当S为闭集时,则当
X(0)=i∈S时,P(
|X(0)=i)=1. 此时,W=
化为折扣积分型泛函. 不难看出,μk(i)=E(Wk|X(0)=i), i∈S仍满足定理6.9.2.
(3)首达时间与首达目标积分型泛函
当取
=0,则W=
(X(t))dt是首达目标(非折扣)积分型泛函. 当取r(i)=1时,W=
就是从S到S0的首达时间. 这一类问题在理论与应用上更有意义. 在下面更详细地讨论它们.
连续时间积分型泛函k阶矩可以化为离散时间首达目标一阶矩问题. 以上几种连续时间积分型泛函求解k阶矩问题,均可转化为求解离散时间首达目标可加泛函的一阶矩问题. 确切叙述如下:
设马尔可夫链
,状态空间
S∪S0,其中S={1,2,…,m}, S0={δ}. 一步转移概率矩阵
R(i)表示系统在i状态的性能指标,称R:
R为性能函数,T=inf{n: n≥0, X(n)= δ}为从S到S0的首达时间. 令
,由3.6节的内容知,当S为瞬时态集时,
是方程y=R+
的唯一解(非负最小解). 一般地,对求解μk(k≥1)有以下定理:当取
(i)=Rk(i),
这说明求连续时间的积分型泛函的k阶矩可以转化为离散时间首达目标可加泛函的一阶矩问题. 类似的情形很多,这里不一一列举.
6.10 首达时间与首达目标积分型泛函的特性及其反问题
连续时间马尔可夫链的首达时间及首达目标积分型泛函有其广泛的应用背景,例如系统的使用寿命,人工神经网络训练达到要求的时间,排队系统中的队长与忙期,通讯中信号的堵塞时间,水坝水位超过警戒线的时刻等,无不与首达时间或首达目标相联系. 本节着重讨论首达时间的分布、生成函数及其矩的关系,及马尔可夫链的反问题.
考虑连续时间马尔可夫链X={X(t), t≥0},在状态空间
={1,2,…,m, m+1, m+2,…}=S∪S0(其中S={1,2,…,m}, S0=
-S={m+1, m+2,…}),其转移率矩阵
=(qij), i, j∈S(
亦称为无穷小生成算子),
,其中Q是m×m矩阵,qij≥0, j≠i, qi=-qii≥0,
,且q0+Qe=0, e=(1,1,…,1)T, 0=(0,0,…,0)T分别是S上的单位列向量,零列向量.
=inf{t: t>0, X(t)≠X(0)},
=inf{t: t>0, X(t)∈S0},易知
是从状态集S到S0的首达时间. 规定infФ=+∞,
=0(若X(0)∈S0). r:
R+, r(i)表示系统在i状态对应的性能指标,不失一般性,设r(i)>0, 若i∈S;r(i)=0, 若i∈S0. 取S0={0},此时
保守. 记W=
X(t))dt为首达目标积分泛函.
本节将研究
与W的矩与它们的分布函数,及其Laplace-Stieltjes变换(亦称生成函数)的关系. 为避免平凡情况,在本节设马尔可夫链X从S到S0以概率1可达,即设
(6.10.1)
成立. 为了便于检验(6.10.1)式是否成立,先给出以下几个引理.
引理6.10.1 从S出发以概率1可达S0的必要条件是S中没有吸收状态,即(6.10.1)式成立的必要条件是
, qi>0.
证明 记
=inf{t: t>1, X(t)≠X(0)},用反证法. 若
使qi=0,则P(
=+∞|X(0)=i)=1,因为{
=+∞, X(0)=i}
{
, X(0)=i},得1=P{
=+∞|X(0)=i}≤P(
|X(0)=I)≤1→P(
|X(0)=i)=1,这与假设
,
|X(0)=1)相矛盾.
□
引理6.10.2 (6.10.1)式成立的充要条件是限制在S上的Q矩阵Q=(qij)(i, j∈S)非奇异.
证明 记fi=
|X(0)=i), i∈S, f=(fi, i∈S)T,Pi0=
,
. 由全概率公式及强马尔可夫性,有fi=
+
, 写成向量形式,并注意到q0=-Qe, e=(1,1,…,1)T, 即有
Qf=Qe.
(6.10.2)
若Q非奇异,即Q-1存在,则f=e是方程(6.10.2)的唯一解,即fi=
|X(0)=i)=1,
.
下证当f=e时,Q非奇异. 用反证法,假设Q奇异,则存在一非负、非零的行向量,v, vQ=0. 故对所有t≥0,有veQte=ve>0,且向量
,从而vu=ve>0. 这表明至少存在一状态i∈S,使得fi=1-ui<1,矛盾. 故Q非奇异.
令Pij=δij+
, P=(Pij), i, j∈S,
(P)为P的谱半径. 进一步有下面的结论.
引理6.10.3 下面命题等价:
(1)f=e;
(2)Q-1存在;
(3)X在S中无任何闭子集;
(4)
<1;
(5)J1<+∞.
证明略. 有兴趣的读者可以作为练习自己证明.
记
Mk(i1, i2, …, ik)=
为由矩阵Q=(qij)的第i1,i2,…, ik行与第i1,i2,…, ik列的交叉元素构成的k阶子矩阵,1≤k≤m,1≤k≤m,1≤i10,
≤k≤m, 1≤i10. 本节以下均在(6.10.1)式成立下讨论. 令Qd=diag(qi, i∈S), M0=
.
令Jk(i)=E(
i∈S, Jk=(Jk(i), i∈S)T,
i∈S)T, Jk=
Jk,
则有下面的结论.
定理6.10.1
(1)
满足方程
Jk=kQ
Jk-1+ Q
(Q+Qd)Jk,
(6.10.3)
(2)
Jk=(-1)kk!Q-1e,
其中
EMBED Equation.3 .
(6.10.4)
(3)
|Jk|≤k!
(6.10.5)
证明 (1)注意定理6.9.2的(6.9.7)式,当
=0时,即得(6.10.3)式.
(2),(3)由96.10.3)式立得(6.10.4)式及(6.10.5)式.
令Fi(x)=P(τ≤x|X(0)=i),
=P(W≤x|X(0)=i), i∈S, x≥0. F(x)=
=
记Gi(x)= P(τ≤x|X(0)=i)=(1-
对Fi(x), Fi(x)有如下定理.
定理6.10.2
(6.10.6)
(6.10.7)
证明 令
=inf{t: t>0, X(
+t)∈S0}, X'(t)=X(
+t),则
. 注意到
与X(
)关于X(0)=i条件独立,
与X(
+t)关于X(0)=i条件独立. 再由全概率公式与强马尔可夫性,即可得(6.10.6)式及(6.10.7)式(可参考上节定理6.9.1的证明).
□
注意到,若令
仍为Q矩阵,且
存在,则(6.10.7)式化为
(6.10.8)
由(6.10.8)式说明,首达目标积分型泛函问题可化为首达时间问题(要求r(i)>0, i∈S). 故下面只需讨论首达时间的问题.
设S={1,2,…,p}有限,S0={0}, 且(6.10.1)式总成立,并设过程的初始分布为:
=(
1,…,
m, 0),
i≥0, i∈S,
记
x≥0, s≥0.
F(x)=(Fi(x), i∈S)T,
i∈S)T.
定义6.10.1 称从S到S0的首达时间
的分布F(x)=P(
≤x)为Phase-Type分布,简记为PH分布. 称
为PH分布的生成函数,即
是F(x)的Laplace-
Stieltjes变换.
定理6.10.3
(6.10.9)
(6.10.10)
证明 对(6.10.6)式两边取Laplace-Stieltjes变换,即得(6.10.9)式. 再注意到当s>0时,矩阵sI-Q是严格对角占优矩阵,故(sI-Q)-1存在. 从而方程(6.10.9)有唯一解,即(6.10.10)式成立.
□
由(6.10.10)式可知F(x),
完全由过程在S上的无穷小生成子Q唯一决定,而
及F(x)=
F(x)由初始分布
及Q唯一决定. 因此,可用(
,Q)表示F(x),记为F(x)~ (
,Q), 称(
,Q)是F(x)的一个表示.
对于首达时间的分布函数F(x)、生成函数
及矩{Jk, k≥0},有以下定理.
定理6.10.4
由其矩{Jk, k≥0}唯一确定,即存在s0>0,使当|s|
练习题
用券下载整式乘法计算练习题幼小衔接专项练习题下载拼音练习题下载凑十法练习题下载幼升小练习题下载免费
6.1 设{N(t), t≥0}是参数为λ的泊松过程,过程{X(t), t≥0}定义为{X(t)=1}=
(N(t)=2n), {X(t)=0}=
(N(t)=2n+1),试证{X(t), t≥0}为马尔可夫链,并求P(t)与Q=(qij).
6.2 设{X(t), t≥0}为马尔可夫链,S={0,1}, Q=
, P0(0)=1,
=inf{t: t>0, X(t)≠X(0)}. 求:
6.3 设{N(t), t≥0}是参数为λ的泊松过程,且设每次到达被登记上的概率为p,并与其他到达独立. 记{Np(t), t>0}为登记到达的过程. 证{Np(t), t≥0}是参数为pλ的泊松流.
6.4 设{Ni(t), t≥0}是参数为λi的泊松过程且相互独立(i=1,2). X(t)=N1(t)-N2(t), Pn(t)=P(X(t)=n), n∈N={0, ±1, ±2, …}, Ti=inf{t: t>0, Ni(t)=k}. 试证
,
并求E[X(t)], E(X(t)2)及P(T10, n≥0, μn=μ, n>1, μ0=0;
(2)λn=λ(n+1)-1, λ>0(n≥0), μn=μ, (n≥1), μ0=0;
(3)有迁入的线性增长模型:λn=nλ+a, μn=nμ, λ>0, μ>0, a>0 (不妨设
试求相应的平稳分布.
6.6 设{X(t), t≥0}是纯生耶洛过程{λn=nλ, μn=0, λ>0},证明
P(X(t)≥n|X(0)=N)=
q=1-p=e-λt,
及
E[X(t)]= eλt,
varX(t)= e2λt(1- e-λt).
6.7 设{X(t), t≥0}为纯灭过程(λn=0, μn=nμ, μ>0, n≥1), X(0)=i. 求
Pn(t)=P(X(t)=n), E[X(t)], var[X(t)].
{Pn(t)=
var[X(t)]=ie-μt(1-e-μt)}.
6.8 设{Xi(t), t≥0} (i=1,2)是两个互相独立、有相同参数λ的耶洛过程,Xi(0)=ni, N≥n1+n2,给定X1(t)+X2(t)=N,试求X1(t)的条件分布律.
6.9 考虑M/M/s排队系统,顾客按照参数为λ的泊松流到达一个有s个服务员的服务站. 每个顾客一到来,如果有服务员空闲,则直接进入服务,否则加入排队行列等待. 当一个服务员结束对一位顾客服务时,顾客即离开系统,排队中的下一顾客立即被服务(若有顾客等待). 假定相继的服务时间是相互独立,且参数为μ的指数分布的随机变量,如果以X(t)表时刻t系统的顾客数,则{X(t), t≥0}是生灭过程.
设
<1, Q(t)=max(X(t)-s, 0)是t时等待的顾客数.
(1)求系统的平稳分布;
(2)证明在稳态下
r=P(Q(t)=0)
E[Q(t)=(1-r)(1-
)-1.
6.10 一家由一个理发员营业的小理发点,至多能容纳两个顾客,顾客到达是速率为每小时3人的泊松流,相继服务时间是均值为1/4小时的指数随机变量. 求
(1)店中顾客的平均数是多少?
(2)进店的顾客比例;
(3)若理发员能加快一倍地工作,他会多做多少生意?
6.11 若{Xi(t), t≥0} (i=1,2)是两个相互独立的可逆马尔可夫链,证明{X1(t), X2(t), t≥0}也是可逆链.
6.12 考虑参数分别为
的两个M/M/1排队系统,其中
(i=1,2). 假设它们共同使用一个容纳n个人的候客室(即每当候客室占满时如再来客都自行离去消失),计算在第一个系统中有k人(当k>0时1人在接受服务而k-1在候客室等待)而l人在第二个系统的极限概率(提示:利用6.11习题的结果).
6.13 考虑一个M/M/∞排队系统,具有编号为1,2,…的通道(服务员)顾客一来就挑选编号为最小的通道接受服务. 于是可以认为一切来到全部发生在1号通道,当发现1号通道忙着的顾客就溢出而变成2号通道,当发现1号与2号通道都忙着的顾客就溢出变成3号通道,等等. 在稳态下
(1)1号通道忙时占多少比例?
(2)通过考虑相应的M/M/2消失系统,确定2号通道忙时的比例.
(3)对任意第C号通道忙时比例是多少?
(4)从C号通道到C+1号通道的溢出率是多少?相应的溢出过程是泊松流?并加以解释.
6.14 一排队系统在任一时刻的工作量定义为该时刻系统中全体顾客的剩余服务时间之和,试求稳态时的M/G/1排队系统工作量的期望值与方差.
6.15 设X={X(t), t≥0}为稳态下的遍历马尔可夫链,Q=(qij), (Pj, j≥0)为平稳分布,把状态空间S分为两个子集S=B∪Bc,Bc=G,
i∈B令
Ti=inf{t: t>0, X(0)=i, X(t)∈G}.
记
Tv=inf{s: s>0, X(t)∈G, X(t)∈B, X(t+s)
B},
Tv=inf{s: s>0, X(t)∈B, X(t+s)
B}.
(1)求P{X(t)=i|X(t)∈B}, i∈B.
(2)求P{X(t)= i|X(t)∈B, X(t-)∈G}.
(3)证明:
.
(4)证明:
(5)利用(3)及(4),证明:
(6)利用(2)试推导:
(7)利用(5)及(6),证明:
(8)利用(1),(5),(6)及(7),证明:
{sE[Tv|X(t)∈G, X(t)∈B]}-1.
(9)利用(8)与拉普拉斯变换的唯一性,证明:
{E[Tv|X(t-)∈G, X(t)∈B]}-1.
(10)利用(9)证明:
E{Tx|X(t)∈B}
6.16 设{X(t), t≥0}是纯生过程,
,求P(t)=(Pij(t)).
6.17 设{X(t), t≥0}是生灭过程,
, μ0=nμ, n≥1, μ>0,证明:
(1)当
或
时,链为非常返的;
(2)当
时,链为零常返的;
(3)当
时,链为正常返的,且这时平稳分布为
6.18 一个汽车加油站只能给一辆汽车加油,加油时间服从参数为
的指数分布,各辆汽车的加油时间相互独立,加油的汽车按参数为λ的泊松过程到达,当一辆汽车来到加油站发现站中已有n辆汽车时,以概率
立即离去,以概率
留下来排队. 记X(t)为时刻t加油站中汽车的数目,证{X(t), t≥0}为正常返不可约链并求其平稳分布.
6.19 一个系统由n个不同的部件串联构成,n个部件的寿命分别服从参数为λi的指数分布,失效后的修正时间分别服从参数为μi的指数分布. 若n个部件都正常工作,则系统处于工作状态;若有某个部件失效,则系统失效,这时修理工立即对失效部件进行处理,其余部件停止工作,若失效部件修复,所有部件立即进入工作状态,从而系统处于工作状态. 假设各部件的失效与否相互独立,求系统处于工作状态的概率.
6.20 设马尔可夫链{X(t), t≥0}, S={0, 1,2}, π(0)=(0,
1,
2),
i≥0,
,
Q=
,
T=inf{t: t≥0, X(t)=0}, 求:
(1)
的分布及E
;
(2)T的分布及ET.
6.21 设{X(t), t≥0}为马尔可夫链,S={0,1,2}, S12={1,2},π0=(0,2/3,1/3).
Q=
,
=T0=0,
n≥1, T1=inf{t: t>0, X(t)=0}, T2=inf{t: t>T1, X(t)∈S12}, …, T2k+1=inf{t: t>T2k, X(t)=0}, T2k+2=inf{t: t>T2k+1, X(t)∈S12}, k≥0,
t≥0, N1(t)=
,N2(t)=
(1)求
的一步转移矩阵,P(N(t)=1)=?;
(2)求ET1,
,1≤k≤4;
(3)求ET2及P(X(T2)=2);
(4)求EN1(t), EN2(T1);
(5)求P
(6)求EW(t).
6.22 设{T2k, k≥0}同上题定义,记
. 令Z0=1, Zn=
试问{Zn, n≥0}关于{T2n, n≥0}是否是鞅?并证明你的猜想.
6.23 证明:对
,存在极限
. (提示:由第3章离散时间的马尔可夫链的结果可知,对
,存在极限
.
6.24 设
,若存在t0>0使Pij(t0)>0. 证明对
t≥t0,有Pij(t)>0.
6.25 证明下列命题等价:(1)由i可j;(2)对任意的h骨架,由i可j;(3)对某个h骨架,由i可达j.
6.26 证明对
i∈S,若
,
(*)
则对所有h>0,
.
(**)
反之,若对某一个h>0, (**)式成立,则(*)式成立.
6.27 考虑一个G/M/1排队系统,即顾客到达服务台是一个更新过程,相邻到达顾客的时间间隔的分布为G(x),服务台对每一位顾客的服务时间是独立同指数分布,其参数为μ>0,且与到达流独立. 令T0=0,Tn表示第n个顾客到达的时刻,Xn表示第n个顾客到达服务台时刻(Tn)系统内的顾客数(包括该顾客). 证明{(Xn, Tn), n≥1}是马尔可夫更新过程,并求其半马尔可夫核.
PAGE
7
_1119257268.unknown
_1119331616.unknown
_1119341209.unknown
_1119359727.unknown
_1119360918.unknown
_1119364041.unknown
_1125605121.unknown
_1128796637.unknown
_1128796738.unknown
_1132253057.unknown
_1132339868.unknown
_1132407793.unknown
_1132566200.unknown
_1132407882.unknown
_1132342809.unknown
_1132328863.unknown
_1128796944.unknown
_1128797136.unknown
_1128797316.unknown
_1132219430.unknown
_1128797255.unknown
_1128797023.unknown
_1128796911.unknown
_1128796697.unknown
_1128796708.unknown
_1128796679.unknown
_1125686767.unknown
_1128796389.unknown
_1128796505.unknown
_1125689327.unknown
_1125924248.unknown
_1125688020.unknown
_1125671009.unknown
_1125671827.unknown
_1125640492.unknown
_1119364926.unknown
_1119417478.unknown
_1119418925.unknown
_1119419858.unknown
_1119421829.unknown
_1119427700.unknown
_1119440214.unknown
_1119440991.unknown
_1119441166.unknown
_1119441388.unknown
_1119441399.unknown
_1119441772.unknown
_1119441873.unknown
_1119441496.unknown
_1119441389.unknown
_1119441281.unknown
_1119441387.unknown
_1119441066.unknown
_1119441126.unknown
_1119441000.unknown
_1119440378.unknown
_1119440691.unknown
_1119440833.unknown
_1119440674.unknown
_1119440338.unknown
_1119440365.unknown
_1119440305.unknown
_1119428753.unknown
_1119428799.unknown
_1119440174.unknown
_1119440202.unknown
_1119439995.unknown
_1119428767.unknown
_1119428783.unknown
_1119428754.unknown
_1119428585.unknown
_1119428633.unknown
_1119428688.unknown
_1119428586.unknown
_1119428245.unknown
_1119428400.unknown
_1119428150.unknown
_1119428165.unknown
_1119428149.unknown
_1119423091.doc
X(t)
O
i0
i1
� EMBED Equation.3 ���
� EMBED Equation.3 ���
i2
� EMBED Equation.3 ���
� EMBED Equation.3 ���
� EMBED Equation.3 ���
t
_1119423544.unknown
_1119423631.unknown
_1119423648.unknown
_1119423616.unknown
_1119423500.unknown
_1119426298.unknown
_1119427202.unknown
_1119427495.unknown
_1119427638.unknown
_1119427388.unknown
_1119427107.unknown
_1119427144.unknown
_1119426880.unknown
_1119425692.unknown
_1119426027.unknown
_1119426267.unknown
_1119425926.unknown
_1119423863.unknown
_1119423901.unknown
_1119423471.unknown
_1119422274.unknown
_1119422447.unknown
_1119422589.unknown
_1119422640.unknown
_1119422504.unknown
_1119422441.unknown
_1119422043.unknown
_1119422156.unknown
_1119422114.unknown
_1119421943.unknown
_1119422030.unknown
_1119421839.unknown
_1119420590.unknown
_1119420938.unknown
_1119421056.unknown
_1119421327.unknown
_1119421412.unknown
_1119421738.unknown
_1119421068.unknown
_1119421150.unknown
_1119421023.unknown
_1119420690.unknown
_1119420769.unknown
_1119420409.unknown
_1119420477.unknown
_1119420492.unknown
_1119420296.unknown
_1119420379.unknown
_1119419933.unknown
_1119419932.unknown
_1119419526.unknown
_1119419626.unknown
_1119419844.unknown
_1119419855.unknown
_1119419789.unknown
_1119419585.unknown
_1119419201.unknown
_1119419384.unknown
_1119417955.unknown
_1119418345.unknown
_1119418604.unknown
_1119418622.unknown
_1119418687.unknown
_1119418495.unknown
_1119418496.unknown
_1119418460.unknown
_1119418494.unknown
_1119418152.unknown
_1119418188.unknown
_1119418218.unknown
_1119418249.unknown
_1119418038.unknown
_1119418003.unknown
_1119417610.unknown
_1119417672.unknown
_1119417740.unknown
_1119417539.unknown
_1119417576.unknown
_1119417595.unknown
_1119417495.unknown
_1119365021.unknown
_1119416800.unknown
_1119416956.unknown
_1119417252.unknown
_1119417458.unknown
_1119417146.unknown
_1119417159.unknown
_1119416973.unknown
_1119416819.unknown
_1119416871.unknown
_1119416807.unknown
_1119365185.unknown
_1119416629.unknown
_1119416673.unknown
_1119416572.unknown
_1119416533.unknown
_1119416560.unknown
_1119416419.unknown
_1119365090.unknown
_1119364929.unknown
_1119364928.unknown
_1119364421.unknown
_1119364442.unknown
_1119364316.unknown
_1119364199.unknown
_1119362335.unknown
_1119363560.unknown
_1119363690.unknown
_1119363758.unknown
_1119364027.unknown
_1119364011.unknown
_1119364013.unknown
_1119363925.unknown
_1119363888.unknown
_1119363723.unknown
_1119363597.unknown
_1119363645.unknown
_1119363594.unknown
_1119362526.unknown
_1119362798.unknown
_1119363011.unknown
_1119363456.unknown
_1119363472.unknown
_1119362972.unknown
_1119362662.unknown
_1119362743.unknown
_1119362539.unknown
_1119362600.unknown
_1119362476.unknown
_1119362513.unknown
_1119362457.unknown
_1119361828.unknown
_1119361864.unknown
_1119362151.unknown
_1119362169.unknown
_1119362108.unknown
_1119361981.unknown
_1119362086.unknown
_1119361888.unknown
_1119361838.unknown
_1119361863.unknown
_1119361055.unknown
_1119361264.unknown
_1119361451.unknown
_1119361762.unknown
_1119361804.unknown
_1119361542.unknown
_1119361407.unknown
_1119361230.unknown
_1119360966.unknown
_1119361011.unknown
_1119360938.unknown
_1119360228.unknown
_1119360583.unknown
_1119360807.unknown
_1119360809.unknown
_1119360675.unknown
_1119360368.unknown
_1119360528.unknown
_1119360255.unknown
_1119360308.unknown
_1119360248.unknown
_1119359966.unknown
_1119360191.unknown
_1119360207.unknown
_1119360047.unknown
_1119360152.unknown
_1119360042.unknown
_1119359978.unknown
_1119360034.unknown
_1119359763.unknown
_1119359942.unknown
_1119359746.unknown
_1119357645.unknown
_1119358787.unknown
_1119359210.unknown
_1119359518.unknown
_1119359663.unknown
_1119359717.unknown
_1119359669.unknown
_1119359614.unknown
_1119359659.unknown
_1119359580.unknown
_1119359604.unknown
_1119359237.unknown
_1119359296.unknown
_1119359316.unknown
_1119359439.unknown
_1119359257.unknown
_1119359236.unknown
_1119358991.unknown
_1119359095.unknown
_1119359182.unknown
_1119359151.unknown
_1119359070.unknown
_1119358856.unknown
_1119358865.unknown
_1119358835.unknown
_1119358199.unknown
_1119358412.unknown
_1119358708.unknown
_1119358499.unknown
_1119358234.unknown
_1119358246.unknown
_1119358218.unknown
_1119358023.unknown
_1119358169.unknown
_1119358176.unknown
_1119358083.unknown
_1119357986.unknown
_1119358009.unknown
_1119357891.unknown
_1119342145.unknown
_1119342849.unknown
_1119356719.unknown
_1119357536.unknown
_1119357558.unknown
_1119357280.unknown
_1119357459.unknown
_1119357511.unknown
_1119357196.unknown
_1119356537.unknown
_1119356646.unknown
_1119356374.unknown
_1119342336.unknown
_1119342760.unknown
_1119342522.unknown
_1119342643.unknown
_1119342298.unknown
_1119341404.unknown
_1119341835.unknown
_1119341987.unknown
_1119341527.unknown
_1119341726.unknown
_1119341830.unknown
_1119341415.unknown
_1119341238.unknown
_1119341290.unknown
_1119341384.unknown
_1119341229.unknown
_1119333044.unknown
_1119334069.unknown
_1119338696.unknown
_1119339737.unknown
_1119340397.unknown
_1119340462.unknown
_1119340529.unknown
_1119340573.unknown
_1119341173.unknown
_1119340561.unknown
_1119340472.unknown
_1119340423.unknown
_1119340202.unknown
_1119340270.unknown
_1119340362.unknown
_1119340260.unknown
_1119339889.unknown
_1119340166.unknown
_1119339936.unknown
_1119339832.unknown
_1119339625.unknown
_1119339676.unknown
_1119339702.unknown
_1119339665.unknown
_1119339306.unknown
_1119339346.unknown
_1119339559.unknown
_1119339571.unknown
_1119339332.unknown
_1119338801.unknown
_1119338903.unknown
_1119338780.unknown
_1119337808.unknown
_1119338081.unknown
_1119338478.unknown
_1119338618.unknown
_1119338668.unknown
_1119338625.unknown
_1119338575.unknown
_1119338591.unknown
_1119338532.unknown
_1119338254.unknown
_1119338378.unknown
_1119338171.unknown
_1119338193.unknown
_1119338082.unknown
_1119337881.unknown
_1119336666.unknown
_1119337043.unknown
_1119337154.unknown
_1119337219.unknown
_1119337359.unknown
_1119337067.unknown
_1119337020.unknown
_1119336303.unknown
_1119336470.unknown
_1119334318.unknown
_1119333385.unknown
_1119333646.unknown
_1119333696.unknown
_1119333446.unknown
_1119333573.unknown
_1119333391.unknown
_1119333192.unknown
_1119333269.unknown
_1119333313.unknown
_1119333243.unknown
_1119333045.unknown
_1119332600.unknown
_1119332675.unknown
_1119332810.unknown
_1119332942.unknown
_1119332985.unknown
_1119332925.unknown
_1119332690.unknown
_1119332760.unknown
_1119332670.unknown
_1119332631.unknown
_1119332263.unknown
_1119332446.unknown
_1119332465.unknown
_1119332290.unknown
_1119332058.unknown
_1119332206.unknown
_1119332218.unknown
_1119332168.unknown
_1119331807.unknown
_1119331854.unknown
_1119331960.unknown
_1119332014.unknown
_1119331902.unknown
_1119331824.unknown
_1119331732.unknown
_1119331766.unknown
_1119331657.unknown
_1119272583.unknown
_1119276265.unknown
_1119278286.unknown
_1119278577.unknown
_1119331020.unknown
_1119331503.unknown
_1119331543.unknown
_1119331593.unknown
_1119331522.unknown
_1119331328.unknown
_1119331373.unknown
_1119331240.unknown
_1119331300.unknown
_1119331180.unknown
_1119330903.unknown
_1119330941.unknown
_1119330812.unknown
_1119278549.unknown
_1119278560.unknown
_1119278430.unknown
_1119278337.unknown
_1119277369.unknown
_1119277831.unknown
_1119277972.unknown
_1119278077.unknown
_1119278159.unknown
_1119278220.unknown
_1119278144.unknown
_1119278039.unknown
_1119277938.unknown
_1119277947.unknown
_1119277590.unknown
_1119277698.unknown
_1119277372.unknown
_1119276921.unknown
_1119277187.unknown
_1119277322.unknown
_1119277227.unknown
_1119276990.unknown
_1119276947.unknown
_1119276540.unknown
_1119276767.unknown
_1119276891.unknown
_1119276289.unknown
_1119275350.unknown
_1119275727.unknown
_1119276208.unknown
_1119276249.unknown
_1119275839.unknown
_1119276183.unknown
_1119275954.unknown
_1119275763.unknown
_1119275443.unknown
_1119275545.unknown
_1119275572.unknown
_1119275467.unknown
_1119275400.unknown
_1119274224.unknown
_1119275022.unknown
_1119275284.unknown
_1119275307.unknown
_1119275327.unknown
_1119275263.unknown
_1119275100.unknown
_1119274547.unknown
_1119274912.unknown
_1119274512.unknown
_1119273298.unknown
_1119273775.unknown
_1119274096.unknown
_1119273785.unknown
_1119273706.unknown
_1119272865.unknown
_1119273200.unknown
_1119273265.unknown
_1119273134.unknown
_1119272716.unknown
_1119270189.unknown
_1119270832.unknown
_1119271068.unknown
_1119271498.unknown
_1119272370.unknown
_1119272433.unknown
_1119271660.unknown
_1119271807.unknown
_1119271520.unknown
_1119271189.unknown
_1119271293.unknown
_1119271152.unknown
_1119270888.unknown
_1119270919.unknown
_1119270950.unknown
_1119271020.unknown
_1119270901.unknown
_1119270864.unknown
_1119270874.unknown
_1119270841.unknown
_1119270363.unknown
_1119270582.unknown
_1119270740.unknown
_1119270805.unknown
_1119270670.unknown
_1119270610.unknown
_1119270534.unknown
_1119270549.unknown
_1119270559.unknown
_1119270507.unknown
_1119270425.unknown
_1119270450.unknown
_1119270398.unknown
_1119270231.unknown
_1119270280.unknown
_1119270353.unknown
_1119270214.unknown
_1119269567.unknown
_1119269978.unknown
_1119270114.unknown
_1119270170.unknown
_1119270064.unknown
_1119270094.unknown
_1119269872.unknown
_1119269973.unknown
_1119269698.unknown
_1119269826.unknown
_1119269669.unknown
_1119266644.unknown
_1119267057.unknown
_1119269343.unknown
_1119269454.unknown
_1119268080.doc
服务员2
服务员1
…
…
_1119268867.unknown
_1119269051.unknown
_1119268497.unknown
_1119267524.unknown
_1119267732.doc
t
_1119267271.unknown
_1119266705.unknown
_1119266757.unknown
_1119266952.unknown
_1119266686.unknown
_1119257811.unknown
_1119266401.unknown
_1119266443.unknown
_1119266392.unknown
_1119257461.unknown
_1119257528.unknown
_1119257298.unknown
_1119243234.unknown
_1119247049.unknown
_1119255885.unknown
_1119256344.unknown
_1119256597.unknown
_1119257220.unknown
_1119257239.unknown
_1119256667.unknown
_1119256809.unknown
_1119256884.unknown
_1119256625.unknown
_1119256598.unknown
_1119256414.unknown
_1119256469.unknown
_1119256507.unknown
_1119256405.unknown
_1119256131.unknown
_1119256248.unknown
_1119256249.unknown
_1119256235.unknown
_1119255936.unknown
_1119256000.unknown
_1119255903.unknown
_1119248430.unknown
_1119255524.unknown
_1119255692.unknown
_1119255793.unknown
_1119255829.unknown
_1119255663.unknown
_1119250345.unknown
_1119254739.doc
逆向
正向
t'n
t'n-1
tn-1
t1
t2
0
t'2
t'1
tn
t
_1119255453.unknown
_1119255463.unknown
_1119254461.unknown
_1119254631.unknown
_1119250569.unknown
_1119248715.unknown
_1119250309.unknown
_1119248599.unknown
_1119248049.unknown
_1119248418.unknown
_1119248419.unknown
_1119248128.unknown
_1119247520.unknown
_1119247832.unknown
_1119247966.unknown
_1119247783.unknown
_1119247807.unknown
_1119247610.unknown
_1119247659.unknown
_1119247594.unknown
_1119247327.unknown
_1119247490.unknown
_1119247100.unknown
_1119247280.unknown
_1119244724.unknown
_1119245959.unknown
_1119246073.unknown
_1119246630.unknown
_1119247026.unknown
_1119246881.unknown
_1119246123.unknown
_1119246010.unknown
_1119246012.unknown
_1119245987.unknown
_1119245347.unknown
_1119245769.unknown
_1119245957.unknown
_1119245902.unknown
_1119245384.unknown
_1119245062.unknown
_1119245247.unknown
_1119245327.unknown
_1119245168.unknown
_1119244898.unknown
_1119244917.unknown
_1119244761.unknown
_1119244119.unknown
_1119244403.unknown
_1119244565.unknown
_1119244666.unknown
_1119244687.unknown
_1119244445.unknown
_1119244221.unknown
_1119244331.unknown
_1119244138.unknown
_1119243876.unknown
_1119244024.unknown
_1119244060.unknown
_1119243970.unknown
_1119243849.unknown
_1119243857.unknown
_1119243844.unknown
_1119187807.unknown
_1119189188.unknown
_1119190428.unknown
_1119190935.unknown
_1119191232.unknown
_1119191250.unknown
_1119191183.unknown
_1119190749.unknown
_1119190894.unknown
_1119190516.unknown
_1119189972.unknown
_1119190181.unknown
_1119190291.unknown
_1119190141.unknown
_1119189323.unknown
_1119189377.unknown
_1119189850.unknown
_1119189294.unknown
_1119188530.unknown
_1119188897.unknown
_1119189087.unknown
_1119189119.unknown
_1119188989.unknown
_1119188780.unknown
_1119188797.unknown
_1119188708.unknown
_1119188335.unknown
_1119188457.unknown
_1119188497.unknown
_1119188416.unknown
_1119188273.unknown
_1119188303.unknown
_1119188090.unknown
_1119188212.unknown
_1119187941.unknown
_1119185929.unknown
_1119187134.unknown
_1119187563.unknown
_1119187674.unknown
_1119187791.unknown
_1119187597.unknown
_1119187496.unknown
_1119187536.unknown
_1119187229.unknown
_1119186182.unknown
_1119186322.unknown
_1119186394.unknown
_1119186241.unknown
_1119186090.unknown
_1119186141.unknown
_1119186037.unknown
_1119184661.unknown
_1119185583.unknown
_1119185800.unknown
_1119185892.unknown
_1119185729.unknown
_1119184765.unknown
_1119185495.unknown
_1119185533.unknown
_1119184688.unknown
_1119167472.unknown
_1119167614.unknown
_1119167714.unknown
_1119167586.unknown
_1099375244.unknown
_1119167155.unknown
_1119167197.unknown
_1119167055.unknown
_1114242102.unknown
_1099375226.unknown