Research in Large Deviations and Applications to Queueing Networks

本研究将集中在两个广泛的领域：(1)大偏差理论的弱收敛方法；(2)跳转马尔可夫过程的大偏差及其在排队网络中的应用。在区域(1)中，研究部分基于与Paul Dupuis合著的一本新书。它包括以下内容：(a)推导新类型过程的表示公式，包括跳跃马尔可夫过程；(b)证明了具有各种几何形状的不连续统计的扩散和其他过程的拉普拉斯原理；(c)证明了具有状态相关噪声的随机行走模型的拉普拉斯原理；(d)证明了马尔可夫链和相关过程的经验测度的拉普拉斯原理，包括具有状态依赖的测度值过程；(e)推广了凸函数复合的legende - fenchel变换的一个新公式。在(2)领域的研究包括：(a)利用一种新的大偏差概率表示公式，结合弱收敛方法，得到了一系列感兴趣的排队模型的率函数的显式表达式；(b)将最近一篇关于一般排队系统的大偏差分析的论文推广到其他排队模型，包括状态相关队列；(c)在多个排队网络中，评估准确的大偏差率并确定与某些溢出事件相对应的溢出路径。由于排队网络在通信和高性能计算领域具有重要的应用价值，本研究计划在大偏差情况下进行研究。在过去的几年里，首席研究员的工作在一些重要的论文和一本研究水平的书中达到高潮，开发了一套新的和强大的技术来研究这种网络的行为。例如，高速网络技术设计中的一个关键问题是确定这些网络中通信交换机的缓冲大小，以使某些溢出概率适当地小。大型多处理器系统设计中的另一个关键问题是估计系统在一定时间间隔内发生故障的概率。本研究将适用于这些及相关问题的研究。

9700852 Ellis This research will focus on two broad areas: (1) a weak convergence approach to the theory of large deviations and (2) large deviations for jump Markov processes and applications to queueing networks. In area (1) the research is based in part on a new book written jointly with Paul Dupuis. It consists of the following: (a) deriving representation formulas for new classes of processes, including jump Markov processes; (b) proving the Laplace principle for diffusions and other processes having discontinuous statistics with various geometries; (c) proving the Laplace principle for a random walk model with state- dependent noise; (d) proving the Laplace principle for empirical measures of Markov chains and related processes, including measure-valued processes with state dependencies; (e) generalizing a new formula on the Legendre-Fenchel transform of compositions of convex functions. Research in area (2) consists of the following: (a) using a new representation formula for large deviation probabilities together with weak convergence methods to obtain an explicit formula for the rate function for a number of queueing models of interest; (b) extending a recent paper on the large deviation analysis of general queueing systems to other queueing models, including state-dependent queues; (c) evaluating the exact large deviation rates and determining the overflow paths corresponding to certain overflow events in a number of queueing networks. This research program in large deviations is motivated by applications to queueing networks, which are of fundamental importance in communication and high performance computing. The work of the Principal Investigator over the past few years, which culminated in a number of important papers and a research-level book, develops a set of new and powerful techniques for studying the behavior of such networks. For example, a critical problem in the design of high speed networking technologies is to size the buffe rs at communications switches within these networks so that certain overflow probabilities are suitably small. Another critical problem in the design of very large multiprocessor systems is to estimate the probability that the system will fail in some time interval. This research will be adapted to studying these and related problems.