马尔可夫骨架过程及其应用
|
摘要
马尔可夫骨架过程是一类较为综合随机过程。它包含了许多已有的随机过程模型，如马尔可夫过程、半马尔可夫过程、逐段决定的马尔可夫过程等一系列经典的随机过程，具有重要的理论和应用价值。1997年，侯振挺教授等人首次提出马尔可夫骨架过程，并且将其应用于排队论、控制论等领域，成功地解决了排队论的瞬时分布、平稳分布、遍历性等一系列经典难题，并且提出了许多新问题和新思想。
在应用随机过程中，排队论无疑是其中极为重要的一类，其他的如随机流体模型、存储模型、易腐烂物品存储模型在实际应用中也具有重要地位。但过去由于数学工具的限制，只能处理一些特殊的情形。本文目的是利用马尔可夫骨架过程的理论来处理这些模型。本文的主要结果有：
第一，给出了马尔可夫骨架过程具有正规性的一个相当宽泛的充分条件：如果过程的轨道具有左极右连性质，则马尔可夫骨架过程一定具有正规性。
第二，给出马尔可夫骨架过程的有限维分布的递推公式。
第三，首先给出了带N-策略休假的GI／G／1排队系统的队长的瞬时分布以及所满足的方程以及有限维分布公式
第四，利用的马尔可夫骨架过程的理论讨论了研究了两类水
第五，
第
、_
/\，
库储水模型:进水和泻水速度受控于半马尔可夫过程
的水库储水模型以及泻水速度依赖于进水速度和储
水量的水库储水模型。
首次提出银行存贷差模型并利用的马尔可夫骨架过
程的理论讨论了它的一维分布。
利用的马尔可夫骨架过程的理论讨论了易腐烂物的
存储模型并且给出它的的一维分布。
Markov skeleton process is a new type of stochastic process and containing many classical processes as special cases. In 1997, Prof Hou Zhenting and and his colleagues raised this kind of processes and used it to solve queueing theory problem.
Queueing theory is a greatly important kind of application stochastic processes. The GI/G/1 queueing systems with N-vacation are new type of queueing modes among all the queueing systems. In this dissertation, we drew the following conclusions:
Firstly, we get a sufficient condition of normality for Markov skeleton process .
Secondly, we give finite dimension distribution formulae for Markov skeleton process.
Thirdly, we present the equation which satisfies the transient distribution and finite dimension distribution of the length GI/G/1 queueing systems with N-vacation.
Lastly, we study some modes with the theory of Markov skeleton process.
在应用随机过程中，排队论无疑是其中极为重要的一类，其他的如随机流体模型、存储模型、易腐烂物品存储模型在实际应用中也具有重要地位。但过去由于数学工具的限制，只能处理一些特殊的情形。本文目的是利用马尔可夫骨架过程的理论来处理这些模型。本文的主要结果有：
第一，给出了马尔可夫骨架过程具有正规性的一个相当宽泛的充分条件：如果过程的轨道具有左极右连性质，则马尔可夫骨架过程一定具有正规性。
第二，给出马尔可夫骨架过程的有限维分布的递推公式。
第三，首先给出了带N-策略休假的GI／G／1排队系统的队长的瞬时分布以及所满足的方程以及有限维分布公式
第四，利用的马尔可夫骨架过程的理论讨论了研究了两类水
第五，
第
、_
/\，
库储水模型:进水和泻水速度受控于半马尔可夫过程
的水库储水模型以及泻水速度依赖于进水速度和储
水量的水库储水模型。
首次提出银行存贷差模型并利用的马尔可夫骨架过
程的理论讨论了它的一维分布。
利用的马尔可夫骨架过程的理论讨论了易腐烂物的
存储模型并且给出它的的一维分布。
Markov skeleton process is a new type of stochastic process and containing many classical processes as special cases. In 1997, Prof Hou Zhenting and and his colleagues raised this kind of processes and used it to solve queueing theory problem.
Queueing theory is a greatly important kind of application stochastic processes. The GI/G/1 queueing systems with N-vacation are new type of queueing modes among all the queueing systems. In this dissertation, we drew the following conclusions:
Firstly, we get a sufficient condition of normality for Markov skeleton process .
Secondly, we give finite dimension distribution formulae for Markov skeleton process.
Thirdly, we present the equation which satisfies the transient distribution and finite dimension distribution of the length GI/G/1 queueing systems with N-vacation.
Lastly, we study some modes with the theory of Markov skeleton process.
引文
[1] Anderson,W.J., Continuous-time Markov chains. Springer Series in Statistics[M], New York: Springer-Verlag,1991.
[2] Bailey,N.T.J., A contiunous time treatment of a simple queue using generating functions, J.Roy. Soc.,B, 1954,16,288-291.
[3] Bhat, U.N.,Nance,R.E.,and Claybrook,B.G., Busy period analysis of a timesharing system:Transform inversion, J.ACM, 1972,19,453-463.
[4] Chen, M. F. and Wang, Y.Z., Algebraic Convergence of Markov Chains, Ann. Appl.Prob., To appear.
[5] Chen, M.F., Eigenvalues,inequalities and ergodic theory (Ⅱ), Advances in Math. (China), 1999,28(6),481-505.
[6] Chen, M.F., Ergodic donvergence rate of Markov processes- Eigenvalues, Inequalities and Ergodic Theory. Proceedings of ICM 2002, Vol.Ⅲ，25-40. Beijing: Higher Education Press, 2002.
[7] Chen, M.E, Estimate of exponential convergence rate in total variation by spectral gap, Acta Math.sin.New Ser.(A),1998 41(1), 9-16.
[8] Chen, M.F., From Markov Chains to Non-equilibrium Particle Systems, Singapore: World Scientific, 1992.
[9] Chung, K.L., Markov chains with stationary transition probabilities[J]. 2nd Springer-Verlag, Berlin, 1967.
[10] Chung, K.L. and Fuchs W.H.J., On the distribution of values of sums of random variables, Mem. Amer.Math.Soc., 1951,6,1-12.
[11] Davis, J. L., Renewal theory from the point of view of the theory of probability, Tran.Amer.Math. Soc., 1948,63,422-438.
[12] Davis, M. H.A, Piecewise-deterministic Markov processes: a general class of non-diffusion stochastic models, J.R. Statist. Soc.B. 1988, 46, 353-388.
[13] Doshi, B.,Queueing systems with vacation——a survey, Queueing Systems, 1(1986)29-66.
[14] Finch, P.D., On the distribution of gueue size in gueuing problem,Acta Math. Acad. Sci. Hungar., 1959,10,327-336.
[15] Finch, P.D., On the busy period in the gueuing system GI/G/1, J. Aust. Math. Soc.,1961,2,217-228.
[16] Foster, F.G., On the stochastic matrices associated with certain queuing processes, Ann. Math. Statist., 1953,24,355-360.
[17] 侯振挺等，生灭过程，长沙：湖南科学技术出版社，2000．
[18] 侯振挺等，马尔可夫骨架过程-混杂系统模型，长沙：湖南科学技术出版社，2000．
[19] 侯振挺，刘源远，排队过程的马氏化及各种遍历性，待发表．
[20] 侯振挺，Q-过程的唯一性准则[M]，长沙：湖南科学技术出版社，1982．
[21] 侯振挺，邹捷中，张汉君等，马尔可夫过程的Q-矩阵问题[M]，长沙：湖南科学技术出版社，1994．
[22] Hou Zhenting, Markov skeleton processes and applications to queueing systems, Acta Mathematicae Applicatae Sinica, English Series, 2002, 18(4), 537-552.
[23] Hou Zhenting, Yuan Chenggui, Zou Jiezhong et al, Transient distribution of the length of GI/G/n queueing systems, Stochastic Analysis and Applications, 21(3), 2003,567-592.
[24] Hou, Z.T. and Li, X.H., Ergodicity of Quasi-birth and death processes(Ⅰ) (Ⅱ), submitted.
[25] Hou Z. T. Lin X. Wang Y.M., Ergodicity of the queue length L(t) of M/G/1 queueing system, submitted.
[26] Hou, Z. T. and Liu, Y.Y., Explicit Criteria for Several Types of Ergodicity of Markov Chains in M/G/1 Queue with vacations, submitted.
[27] Hou, Z. T. and Liu, Y.Y., Explicit Criteria for Several Types of Ergodicity of Markov Chains in Classical GI/G/n Queue, submitted.
[28] Hou, Z.T. and Li, X.H., Ergodicity of queue length L(t) of M/M/c queue systems with server vacations, submitted.
[29] Hou, Zhenting and Li, Min, GI/G/1 Queueing System.su.b.mitted
[30] Hou Zhenting, Wang yimin. Explicit Expression for Laplice Transformation of Transient Queue Length Distribution of GI/G/1 Queuing System, Systems Science and Information,2003(4).
[31] 侯振挺，郭先平，马尔可夫决策过程，长沙：湖南科学技术出版社，1997
[32] Hou, Z.T., Guo,Q.F., Time-homogeneous Markov processes with countable state space[M]. New York: Springer-Verlag,1988
[33] Hou, Zhenting, Liu Zaiming, Zou Jiezhong., QNQL Processes:(H,Q)- processes and their Applications, Chinese Science Bulletin, 1977, 42(11): 881-886.
[34] Hou, Zhenting, Liu Zaiming, Zou Jiezhong., Markov Skeleton Processes. Chinese Science Bulletin, 1998, 43(11): 881-889.
[35] 胡迪鹤，可数状态的可尔可夫过程论[M]，武汉：武汉大学出版社，1983．
[36] 华兴[美]，排队论与随机服务系统，上海翻译出版公司，1987．
[37] Kendall, D.G., Some problems in the theory of queues, J. Roy. Statist. Soc., B,1951,13,151-185.
[38] Kendall, D.G., Stochastic processes occurring in the theory of queues and their analysis by the methods of the imbedded Markov chain, Ann. Math. Statist.,1953,24,338-354.
[39] Levy, P., Semi-Markovian Processes, Proc:Ⅲ Internat. Congr.Math. (Amster dam), 1954,416-426
[40] 李民，马尔可夫骨架过程与GI／G／1排队系统：[博士学位论文]．长沙：中南大学，2002．
[41] Li, X. H. and Hou, Z.T., Ergodicity of markov chains of the GI/M/1 type and the application in queue system, submitted.
[42] Li, X. H. and Hou, Z.T., Ergodicity ofPH/G/1 Queueing System, submitted.
[43] Li, X.H. and Hou, Z.T., Ergodicity of markov chains of the GI/M/1 type and the application in queue system, submitted.
[44] Li, X.H. and Hou, Z.T., Ergodicity of PH/G/1 Queueing System, submitted.
[45] Liu, Y.Y. and Hou, Z.T., Ergodicity of waiting time and queue length of M/G/1 queueing system with vacations, submitted.
[46] Liu, Y.Y. and Hou, Z.T., Ergodicity Of waiting time and queue length of M/G/1 queueing system with vacations, submitted.
[47] Lindley D. V., The theory of gueues with a simgle server, Proc. Camb. Phil. Soc.,1951,48,227-289.
[48] 陆传赉，排队论，北京：北京邮电学院出版社，1994．
[49] Mao,Y.H., Alebraic Convergence for Discrete-time Ergodic Markov Chains, Scientia Sinica, 2003, 33(2), 152-160.
[50] Mao, Y.H., Algebraic Convergence for Dicrete-time Markov Chains, Scientia Sinica, submitted, 2002.
[51] Meyn, S. P and Tweedie, R.L., Markov Chains and Stochastic Stability Springer-Verlag & Beijing World Publishing Corporation,1999.
[52] Neuts, M. F., Probability distributions of phase type, in Liber Amicorum Prof. Belgium Univ. Of Louvain, 1975,173-206.
[53] Neuts, M., Matrix-Geometric Solutions in Stochastic Models. Baltimore: The Johns Hopink University Press, 1981.
[54] Saaty, T. J., Time dependent solution of the many server Poisson queue, Operat. Res.,1951,13,151-185.
[55] Serfozo, R, Introduction to stochastic networks, Springer-Verlag, 1999.
[56] 盛友招，排队论及其在计算机通信中的应用，北京：北京邮电大学出版社，1998．
[57] 史定华，随机模型的密度演化方法北京：科学出版社，1999．
[58] Tian, N.,.Zhang, D. and Cao C.,X., M/G/1 queue with controllable vacations.and optimation of vacaction policy, Aeta Math. Appl. Sinica,3(1999)363-373
[59] Tak?cs, L., Delay distributions for simple trunk groups with recurrent input and exponential service times, Bell Syst.Tech.J., 1962,41,311-320.
[60] 田乃硕，拟生灭过程与矩阵几何解，北京：科学出版社，2002．
[61] 田乃硕，休假随机服务系统，北京：北京大学出版社，2001．
[62] 吴芳，GI／M／n队列，应用数学学报，1961，11，295-305．
[63] 徐光辉，随机服务系统，北京：科学出版社，1988．
[64] 徐光辉，GI／M／n的瞬时分布性质，应用数学学报，1965，15，91-120．
[65] 严加安，鞅与随机分析引论，上海：上海科技出版社，1981．
[66] 越明义，队列理论中的M／M／s问题，应用数学，1959，9，494-502．
[67] Zhang, H. J. et al, Strong ergodicity of monotone transition functions, Statistic & Probability Letters, 2001,55,63-69.
[68] 张汉君等，标准转移函数的多项式一致收敛，数学年刊，2000，21(3)．351-356．
[69] 张福德，排队论及其程序设计，长春：吉林大学出版社，1986．
[2] Bailey,N.T.J., A contiunous time treatment of a simple queue using generating functions, J.Roy. Soc.,B, 1954,16,288-291.
[3] Bhat, U.N.,Nance,R.E.,and Claybrook,B.G., Busy period analysis of a timesharing system:Transform inversion, J.ACM, 1972,19,453-463.
[4] Chen, M. F. and Wang, Y.Z., Algebraic Convergence of Markov Chains, Ann. Appl.Prob., To appear.
[5] Chen, M.F., Eigenvalues,inequalities and ergodic theory (Ⅱ), Advances in Math. (China), 1999,28(6),481-505.
[6] Chen, M.F., Ergodic donvergence rate of Markov processes- Eigenvalues, Inequalities and Ergodic Theory. Proceedings of ICM 2002, Vol.Ⅲ，25-40. Beijing: Higher Education Press, 2002.
[7] Chen, M.E, Estimate of exponential convergence rate in total variation by spectral gap, Acta Math.sin.New Ser.(A),1998 41(1), 9-16.
[8] Chen, M.F., From Markov Chains to Non-equilibrium Particle Systems, Singapore: World Scientific, 1992.
[9] Chung, K.L., Markov chains with stationary transition probabilities[J]. 2nd Springer-Verlag, Berlin, 1967.
[10] Chung, K.L. and Fuchs W.H.J., On the distribution of values of sums of random variables, Mem. Amer.Math.Soc., 1951,6,1-12.
[11] Davis, J. L., Renewal theory from the point of view of the theory of probability, Tran.Amer.Math. Soc., 1948,63,422-438.
[12] Davis, M. H.A, Piecewise-deterministic Markov processes: a general class of non-diffusion stochastic models, J.R. Statist. Soc.B. 1988, 46, 353-388.
[13] Doshi, B.,Queueing systems with vacation——a survey, Queueing Systems, 1(1986)29-66.
[14] Finch, P.D., On the distribution of gueue size in gueuing problem,Acta Math. Acad. Sci. Hungar., 1959,10,327-336.
[15] Finch, P.D., On the busy period in the gueuing system GI/G/1, J. Aust. Math. Soc.,1961,2,217-228.
[16] Foster, F.G., On the stochastic matrices associated with certain queuing processes, Ann. Math. Statist., 1953,24,355-360.
[17] 侯振挺等，生灭过程，长沙：湖南科学技术出版社，2000．
[18] 侯振挺等，马尔可夫骨架过程-混杂系统模型，长沙：湖南科学技术出版社，2000．
[19] 侯振挺，刘源远，排队过程的马氏化及各种遍历性，待发表．
[20] 侯振挺，Q-过程的唯一性准则[M]，长沙：湖南科学技术出版社，1982．
[21] 侯振挺，邹捷中，张汉君等，马尔可夫过程的Q-矩阵问题[M]，长沙：湖南科学技术出版社，1994．
[22] Hou Zhenting, Markov skeleton processes and applications to queueing systems, Acta Mathematicae Applicatae Sinica, English Series, 2002, 18(4), 537-552.
[23] Hou Zhenting, Yuan Chenggui, Zou Jiezhong et al, Transient distribution of the length of GI/G/n queueing systems, Stochastic Analysis and Applications, 21(3), 2003,567-592.
[24] Hou, Z.T. and Li, X.H., Ergodicity of Quasi-birth and death processes(Ⅰ) (Ⅱ), submitted.
[25] Hou Z. T. Lin X. Wang Y.M., Ergodicity of the queue length L(t) of M/G/1 queueing system, submitted.
[26] Hou, Z. T. and Liu, Y.Y., Explicit Criteria for Several Types of Ergodicity of Markov Chains in M/G/1 Queue with vacations, submitted.
[27] Hou, Z. T. and Liu, Y.Y., Explicit Criteria for Several Types of Ergodicity of Markov Chains in Classical GI/G/n Queue, submitted.
[28] Hou, Z.T. and Li, X.H., Ergodicity of queue length L(t) of M/M/c queue systems with server vacations, submitted.
[29] Hou, Zhenting and Li, Min, GI/G/1 Queueing System.su.b.mitted
[30] Hou Zhenting, Wang yimin. Explicit Expression for Laplice Transformation of Transient Queue Length Distribution of GI/G/1 Queuing System, Systems Science and Information,2003(4).
[31] 侯振挺，郭先平，马尔可夫决策过程，长沙：湖南科学技术出版社，1997
[32] Hou, Z.T., Guo,Q.F., Time-homogeneous Markov processes with countable state space[M]. New York: Springer-Verlag,1988
[33] Hou, Zhenting, Liu Zaiming, Zou Jiezhong., QNQL Processes:(H,Q)- processes and their Applications, Chinese Science Bulletin, 1977, 42(11): 881-886.
[34] Hou, Zhenting, Liu Zaiming, Zou Jiezhong., Markov Skeleton Processes. Chinese Science Bulletin, 1998, 43(11): 881-889.
[35] 胡迪鹤，可数状态的可尔可夫过程论[M]，武汉：武汉大学出版社，1983．
[36] 华兴[美]，排队论与随机服务系统，上海翻译出版公司，1987．
[37] Kendall, D.G., Some problems in the theory of queues, J. Roy. Statist. Soc., B,1951,13,151-185.
[38] Kendall, D.G., Stochastic processes occurring in the theory of queues and their analysis by the methods of the imbedded Markov chain, Ann. Math. Statist.,1953,24,338-354.
[39] Levy, P., Semi-Markovian Processes, Proc:Ⅲ Internat. Congr.Math. (Amster dam), 1954,416-426
[40] 李民，马尔可夫骨架过程与GI／G／1排队系统：[博士学位论文]．长沙：中南大学，2002．
[41] Li, X. H. and Hou, Z.T., Ergodicity of markov chains of the GI/M/1 type and the application in queue system, submitted.
[42] Li, X. H. and Hou, Z.T., Ergodicity ofPH/G/1 Queueing System, submitted.
[43] Li, X.H. and Hou, Z.T., Ergodicity of markov chains of the GI/M/1 type and the application in queue system, submitted.
[44] Li, X.H. and Hou, Z.T., Ergodicity of PH/G/1 Queueing System, submitted.
[45] Liu, Y.Y. and Hou, Z.T., Ergodicity of waiting time and queue length of M/G/1 queueing system with vacations, submitted.
[46] Liu, Y.Y. and Hou, Z.T., Ergodicity Of waiting time and queue length of M/G/1 queueing system with vacations, submitted.
[47] Lindley D. V., The theory of gueues with a simgle server, Proc. Camb. Phil. Soc.,1951,48,227-289.
[48] 陆传赉，排队论，北京：北京邮电学院出版社，1994．
[49] Mao,Y.H., Alebraic Convergence for Discrete-time Ergodic Markov Chains, Scientia Sinica, 2003, 33(2), 152-160.
[50] Mao, Y.H., Algebraic Convergence for Dicrete-time Markov Chains, Scientia Sinica, submitted, 2002.
[51] Meyn, S. P and Tweedie, R.L., Markov Chains and Stochastic Stability Springer-Verlag & Beijing World Publishing Corporation,1999.
[52] Neuts, M. F., Probability distributions of phase type, in Liber Amicorum Prof. Belgium Univ. Of Louvain, 1975,173-206.
[53] Neuts, M., Matrix-Geometric Solutions in Stochastic Models. Baltimore: The Johns Hopink University Press, 1981.
[54] Saaty, T. J., Time dependent solution of the many server Poisson queue, Operat. Res.,1951,13,151-185.
[55] Serfozo, R, Introduction to stochastic networks, Springer-Verlag, 1999.
[56] 盛友招，排队论及其在计算机通信中的应用，北京：北京邮电大学出版社，1998．
[57] 史定华，随机模型的密度演化方法北京：科学出版社，1999．
[58] Tian, N.,.Zhang, D. and Cao C.,X., M/G/1 queue with controllable vacations.and optimation of vacaction policy, Aeta Math. Appl. Sinica,3(1999)363-373
[59] Tak?cs, L., Delay distributions for simple trunk groups with recurrent input and exponential service times, Bell Syst.Tech.J., 1962,41,311-320.
[60] 田乃硕，拟生灭过程与矩阵几何解，北京：科学出版社，2002．
[61] 田乃硕，休假随机服务系统，北京：北京大学出版社，2001．
[62] 吴芳，GI／M／n队列，应用数学学报，1961，11，295-305．
[63] 徐光辉，随机服务系统，北京：科学出版社，1988．
[64] 徐光辉，GI／M／n的瞬时分布性质，应用数学学报，1965，15，91-120．
[65] 严加安，鞅与随机分析引论，上海：上海科技出版社，1981．
[66] 越明义，队列理论中的M／M／s问题，应用数学，1959，9，494-502．
[67] Zhang, H. J. et al, Strong ergodicity of monotone transition functions, Statistic & Probability Letters, 2001,55,63-69.
[68] 张汉君等，标准转移函数的多项式一致收敛，数学年刊，2000，21(3)．351-356．
[69] 张福德，排队论及其程序设计，长春：吉林大学出版社，1986．