排队论2-历史历史幽默小故事44

《排队论2-历史历史幽默小故事44》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、排队论计算机科学与技术学院刘咏彬aliuyb@163.com2006年9月1第二章马尔可夫链（MarkovChain）一离散时间的马尔可夫链二连续时间的马尔可夫链三生灭过程四泊松过程2随机过程设R表示全体实数，对任一实数t，X(t)是一个随机变量，则随机变量族{X(t),tR}称为一个随机过程随机过程分类的三个主要因素状态空间离散状态空间（称之为链Chain）连续状态空间时间t离散时间（常把随机变量记做Xn，称之为随机序列stochasticsequence）连续时间（X(t),称为随机过程stochasticprocess)不同时间

2、上随机变量之间的依赖关系3马尔可夫链的产生1907年马尔可夫发表论文，定义并研究了一种随机过程的性质，就是我们现在所称的马尔可夫过程离散状态空间的马尔可夫过程就是马尔可夫链（Kleinrock）Whathecreatedwasasimpleandhighlyusefulformofdependencyamongtherandomvariablesformingastochasticprocess,whichwenowdescribe4第二章马尔可夫链第一节离散时间的马尔可夫链51离散时间的马尔可夫链定义设X={Xn，n=0,1,2,3

3、….}是一个随机过程，Xn取值为0,1,2,3…，即状态空间E={0,1,2,3…}，用“Xn=i”表示时刻n系统X处于状态i这一事件。称pij(n)=P(Xn+1=j

4、Xn=i)为在事件“Xn=i”出现的条件下，事件“Xn+1=j”出现的条件概率。61离散时间的马尔可夫链定义如果对任意的非负整数i1,i2,….,in-1,i,j及一切n0有P(Xn+1=j

5、Xn=i,Xk=ik,k=0,1,2,…,n-1)=P(Xn+1=j

6、Xn=i)=pij(n)则称X是一离散时间的马尔可夫链(MarkovChain)。7(Kleinrock)Th

7、eMarkovpropertyinsiststhatthepasthistorybecompletelysummarizedinthespecificationofthecurrentstate.Markov8马尔可夫性举例例1统计通过路口的车辆。设Xn表示时刻n时已通过的车辆数，已知n=10的车辆数，要想知道n=15时的车辆数，只要统计10-15时之间通过的车辆数情况就可以了。因此，车流具有马尔可夫性。Xnn01015500?9马尔可夫性举例例2假定每个细菌经过一个时间单位分裂一次或走向死亡，如果已知时刻i时刻的细菌数Xi，求时刻j（j

8、>i）时的细菌数Xj，只要知道从时刻i时的情况推算就可以了，因而｛Xn｝也是一个马尔可夫链0mnXn时刻XiXj102齐次马尔可夫链当pij(n)与起始时刻无关时，则称为齐次的马尔可夫链。此时可将pij(n)记为pij称pij为系统的一步转移概率。把一布转移概率写成矩阵形式：称为一步转移矩阵矩阵元素性质：113　n步转移概率齐次马尔可夫链中，称pij(n)=P(Xn=j

9、X0=i)=P(Xm+n=j

10、Xm=i)为马尔可夫链X的n步转移概率也可写成矩阵的形式称为n步转移矩阵124K-C方程ij****….nm时间XnKolmogorovCh

11、apman135初始分布绝对概率若记pi＝P(X0=i)，则有称{pi，iE}为齐次马氏链X的初始分布。P(Xn=i)记做,为齐次马尔可夫链的绝对概率145初始分布绝对概率第n步绝对概率＝初始分布×n步转移概率156平稳分布若极限存在，且则称为{i}系统的平稳分布X0初始分布pi0kXk瞬时分布平稳分布i166平稳分布（书第27页）176平稳分布这就是离散时间的马尔可夫链求平稳分布的公式18平稳分布举例齐次马氏链一步转移概率矩阵为0213/41/41/43/41/41/41/219平稳分布举例根据求平稳分布公式得20平稳分布举例解之

12、得：为平稳分布的值0213/41/41/43/41/41/41/221平稳分布举例三种初始分布对瞬时概率和平稳分布的影响A.初始分布[1,0,0]:B.初始分布[0,1,0]:n01234…100.2500.1870.2030.2000.750.0620.3590.2540.2800.250.6880.4540.5430.52n01234…00.250.1870.2030.1990.20100.3750.2500.2890.2800.750.4380.5470.5120.5222平稳分布举例C.初始分布[0,0,1]:可以看出不论初始

13、分布如何，系统的瞬时概率总是很快的趋近于平稳分布的取值瞬时分布趋近平稳分布的速度与转移矩阵P有关n01234…00.250.1870.2030.1990.2000.250.3130.2660