New Methods for Studying the Time-Dependent and Steady-State Behavior of Markov Chains

研究马尔可夫链瞬态和稳态行为的新方法

• 批准号: 1435261
• 负责人: Brian Fralix
• 金额: $ 24.26万
• 依托单位: Clemson University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-08-01 至 2017-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1435261&HistoricalAwards=false
• 关键词: New; Methods; Studying; Time; Dependent

Markov chains are mathematical objects used to model random phenomena, such as customer flow within a call center, traffic flow on a highway, as well as protein production within a cell. This project focuses on the development of new methods towards studying, for such a phenomenon, both its long-run behavior, as well as its behavior over moderate time frames. If successful, these methods will provide new insight into the behavior of systems that can be modeled with Markov chains, and could lead to improved methods toward managing such systems. For example, such information could be used to set staffing levels in a call center: a study of its long-run behavior may suffice when customer arrivals are relatively stable over time, but a study over shorter time scales is needed if the arrival rate fluctuates too often. This research plan will provide training for graduate students to prepare them for research-based careers in academia, government or industry, and the results of this study will be published in the appropriate scholarly journals, and incorporated into graduate courses taught by the PI. The methods developed within this project will build on new "random-product representations" recently discovered by the PI, and will be used to analyze both the stationary distribution, as well as the time-dependent distributions of a Markov chain. Examples of the types of chains that will be studied include hysteretic reflected Brownian motion, various types of two-dimensional random walks on the nonnegative quarter-plane, Markovian queueing systems under the influence of an external Markovian environment and other `matrix-geometric' models, as well as other types of Markovian queueing networks not included within the above-mentioned types of chains. The results of this study should lead towards understanding what characteristics of a Markov chain lead to stationary distributions having a "product-form-like" structure. Having such insight should prove useful, as such a distribution often yields analytically tractable performance measures that aid in further understanding the behavior of the underlying Markov chain. The techniques used in this study should draw from many concepts found within the theory of random walks, and the theory of Laplace transforms should play a large role in the study of the time-dependent behavior of the above-mentioned types of Markov chains.

马尔可夫链是用于模拟随机现象的数学对象，例如呼叫中心内的客流、高速公路上的交通流量以及细胞内的蛋白质生产。这个项目的重点是开发新的方法来研究这种现象，既包括它的长期行为，也包括它在中等时间框架内的行为。如果成功的话，这些方法将为用马尔可夫链建模的系统的行为提供新的见解，并可能导致管理此类系统的改进方法。例如，此类信息可用于设置呼叫中心的人员配备水平：当客户到达率随着时间的推移相对稳定时，对其长期行为进行研究可能就足够了，但如果到达率波动太频繁，则需要对较短时间尺度进行研究。这项研究计划将为研究生提供培训，为他们在学术界、政府或工业界从事以研究为基础的职业做好准备，这项研究的结果将发表在适当的学术期刊上，并纳入PI教授的研究生课程。该项目中开发的方法将建立在PI最近发现的新的“随机乘积表示”基础上，并将用于分析平稳分布以及马尔可夫链的时间相关分布。将研究的链类型的例子包括滞后反射布朗运动，非负四分之一平面上的各种类型的二维随机行走，外部马尔可夫环境影响下的马尔可夫排队系统和其他“矩阵几何”模型，以及不包括在上述类型链中的其他类型的马尔可夫排队网络。这项研究的结果应该有助于理解马尔可夫链的哪些特征导致具有“产品形式”结构的平稳分布。拥有这样的洞察力应该被证明是有用的，因为这样的分布通常产生分析上可处理的性能度量，有助于进一步理解底层马尔可夫链的行为。本研究中使用的技术应该借鉴随机行走理论中的许多概念，拉普拉斯变换理论应该在上述类型的马尔可夫链的时间依赖行为的研究中发挥重要作用。