Stationary Analysis of a Fluid Queue Driven by Some Countable State Space Markov Chain

Motivated by queueing systems playing a key role in the performance evaluation of telecommunication networks, we analyze in this paper the stationary behavior of a fluid queue, when the instantaneous input rate is driven by a continuous-time Markov chain with finite or infinite state space. In the case of an infinite state space and for particular classes of Markov chains with a countable state space, such as quasi birth and death processes or Markov chains of the G/M/1 type, we develop an algorithm to compute the stationary probability distribution function of the buffer level in the fluid queue. This algorithm relies on simple recurrence relations satisfied by key characteristics of an auxiliary queueing system with normalized input rates.      

渐近循环马氏链的收敛速度

引入了渐近循环马氏链的概念,它是循环马氏链概念的推广.首先研究了在强遍历的条件下,可列循环马氏链的收敛速度,作为主要结论给出了当满足不同条件时可列渐近循环马氏链的C-强遍历性,一致C-强遍历性和一致C-强遍历的收敛速度     

Steady State Analysis of Finite Fluid Flow Models Using Finite QBDs

The Markov modulated fluid model with finite buffer of size β is analyzed using a stochastic discretization yielding a sequence of finite waiting room queueing models with iid amounts of work distributed as exp (nλ). The n-th approximating queue’s system size is bounded at a value q_n such that the corresponding expected amount of work q_n/(nλ) → β as n → ∞. We demonstrate that as n → ∞, we obtain the exact performance results for the finite buffer fluid model from the processes of work in the system for these queues. The necessary (strong) limit theorems are proven for both transient and steady state results. Algorithms for steady state results are developed fully and illustrated with numerical examples.AMS subject classification: 60J25, 60K25, 60K15, 60K37This revised version was published online in June 2005 with corrected coverdate     

Transient solutions for multidimensional denumerable state Markov processes

The computational problem of transient solutions for denumerable state Markov Processes (MP's) has been solved by Hsu and Yuan [12], who derived an efficient algorithm with uniform error. However, when the state space of an MP is of two or more dimensions, even for computational methods dealing with stationary solutions, only the case where one of the dimensions is infinite and all the others are finite has been studied. In this paper, we study transient solutions for multidimensional denumerable state MP's and give an algorithm with uniform error. Some numerical results are presented.Supported by the National Natural Science Foundation of China.     

随机过程Wn的渐近特性

本文讨论了随机过程Wn的渐近性质,得出对于固定的y,Wn(t,x,y)弱收敛于某一高斯过程.     

A Note on Transient Gaussian Fluid Models

In this paper we study the distribution of the supremum over interval [0,T] of a centered Gaussian process with stationary increments with a general negative drift function. This problem is related to the distribution of the buffer content in a transient Gaussian fluid queue Q(T) at time T, provided that at time 0 the buffer is empty. The general theory is illustrated by detailed considerations of different cases for the integrated Gaussian process and the fractional Brownian motion. We give asymptotic results for P(Q(T)>x) and P(sup _0tT Q(t)>x) as x.     

Averaging in Markov Models with Fast Markov Switches and Applications to Queueing Models

An approximation of Markov type queueing models with fast Markov switches by Markov models with averaged transition rates is studied. First, an averaging principle for two-component Markov process (x _n (t), _n (t)) is proved in the following form: if a component x _n () has fast switches, then under some asymptotic mixing conditions the component _n () weakly converges in Skorokhod space to a Markov process with transition rates averaged by some stationary measures constructed by x _n (). The convergence of a stationary distribution of (x _n (), _n ()) is studied as well. The approximation of state-dependent queueing systems of the type M _M,Q /M _M,Q /m/N with fast Markov switches is considered.     

Markov Decision Processes with a Constraint on the Asymptotic Failure Rate

In this paper, we introduce a Markov decision model with absorbing states and a constraint on the asymptotic failure rate. The objective is to find a stationary policy which minimizes the infinite horizon expected average cost, given that the system never fails. Using Perron-Frobenius theory of non-negative matrices and spectral analysis, we show that the problem can be reduced to a linear programming problem. Finally, we apply this method to a real problem for an aeronautical system.     

Uniform Asymptotic Expansion of Likelihood Ratio for Markov Dependent Observations

An asymptotic expansion of the logarithm of the likelihood ratio for Markov dependent observation is obtained. A functional limit theorem for the likelihood ratio is proved, which gives a way to study limiting distributions of the likelihood ratio based on stopping times, in particular, that of sequential probability ratio test.     

Binary Markov Mesh Models and Symmetric Markov Random Fields: Some Results on their Equivalence

In this article, we focus on statistical models for binary data on a regular two-dimensional lattice. We study two classes of models, the Markov mesh models (MMMs) based on causal-like, asymmetric spatial dependence, and symmetric Markov random fields (SMFs) based on noncausal-like, symmetric spatial dependence. Building on results of Enting (1977), we give sufficient conditions for the asymmetrically defined binary MMMs (of third order) to be equivalent to a symmetrically defined binary SMF. Although not every binary SMF can be written as a binary MMM, our results show that many can. For such SMFs, their joint distribution can be written in closed form and their realizations can be simulated with just one pass through the lattice. An important consequence of the latter observation is that there are nontrivial spatial processes for which exact probabilities can be used to benchmark the performance of Markov-chain-Monte-Carlo and other algorithms.     

Factorization of Markov Chains

Existence of following factorization is proved:

Dynamic Routing and Admission Control in High-Volume Service Systems: Asymptotic Analysis via Multi-Scale Fluid Limits

Motivated by applications in telephone call centers, we consider a service system model with m customer classes and r server pools. The model is one with doubly stochastic arrivals, which means that the m-vector λ of instantaneous arrival rates is allowed to vary both temporally and stochastically. Two levels of dynamic control are considered: customers may be either blocked or accepted at the time of their arrival, and then accepted customers of each class must be routed, either immediately upon acceptance or after some period of waiting, to a server pool that is qualified to handle that class. Customers who are made to wait before commencement of their service are liable to defect. The objective is to minimize the expected sum of blocking costs, waiting costs and defection costs over a fixed and finite planning horizon. We consider an asymptotic parameter regime in which (i) the arrival rates, service rates and defection rates are uniformly accelerated by a large factor κ, then (ii) arrival rates are increased by an additional factor g(κ), and the number of servers in each pool is increased by g(κ) as well. This produces a separation of time scales, justifying a pointwise stationary stochastic fluid approximation for our original system model. In the stochastic fluid approximation, optimal admission control and routing decisions are determined by a simple linear program that uses the current arrival rate vector λ as data. We explain how to implement the fluid model's optimal control policy in our original service system context, and prove that the proposed implementation is asymptotically optimal in the first-order sense. AMS subject classification: 60K30, 90B15, 90B36     

Transient solutions of Markov processes and generalized continued fractions

In 1974 J. A. Murphy and M. R. O'Donohoe numerically approximatedthe minimal solution of the Kolmogorov forward equation forthe generalized birth and death process by use of continuedfractions. This paper generalizes this approach by suggestingan algorithm for q-matrices of lower band structure (n, 1).This is achieved by analogy with generalized continued fractions.Applications involving q-matrices of this type include, forexample, many types of queueing systems with batch processingor birth–death–catastrophe population processesin biology.     

Asymptotic Expansions of Transition Densities for Hybrid Jump-diffusions

A class of hybrid jump diffusions modulated by a Markov chain is considered in this work.Themotivation stems from insurance risk models,and emerging applications in production planning and wirelesscommunications.The models are hybrid in that they involve both continuous dynamics and discrete events.Under suitable conditions,asymptotic expansions of the transition densities for the underlying processes aredeveloped.The formal expansions are validated and the error bounds obtained.     

Asymptotic expansions of backward equations for two-time-scale Markov chains in continuous time

This work develops asymptotic expansions for solutions of systems of backward equations of time- inhomogeneous Maxkov chains in continuous time. Owing to the rapid progress in technology and the increasing complexity in modeling, the underlying Maxkov chains often have large state spaces, which make the computa- tional tasks ihfeasible. To reduce the complexity, two-time-scale formulations are used. By introducing a small parameter ε〉 0 and using suitable decomposition and aggregation procedures, it is formulated as a singular perturbation problem. Both Markov chains having recurrent states only and Maxkov chains including also tran- sient states are treated. Under certain weak irreducibility and smoothness conditions of the generators, the desired asymptotic expansions axe constructed. Then error bounds are obtained.     

关于渐近循环马氏链泛函的强大数定律

研究了一类非齐次马氏链———渐近循环马氏链泛函的强大数定律,首先引出了渐近循环马氏链的概念,然后给出了若干引理.利用了渐近循环马氏链关于状态序偶出现频率的强大数定理给出并证明了关于渐近循环马氏链泛函的强大数定律,所得定理作为推论可得到已有的结果.     

Asymptotic behavior of Bayes estimators for hidden Markov models with application to ion channels

In this paper we study the asymptotic behavior of Bayes estimators for hidden Markov models as the number of observations goes to infinity. The theorem that we prove is similar to the Bernstein—von Mises theorem on the asymptotic behavior of the posterior distribution for the case of independent observations. We show that our theorem is applicable to a wide class of hidden Markov models. We also discuss the implication of the theorem’s assumptions for several models that are used in practical applications such as ion channel kinetics.      

Directed Markov Point Processes as Limits of Partially Ordered Markov Models

In this paper, we consider spatial point processes and investigate members of a subclass of the Markov point processes, termed the directed Markov point processes (DMPPs), whose joint distribution can be written in closed form and, as a consequence, its parameters can be estimated directly. Furthermore, we show how the DMPPs can be simulated rapidly using a one-pass algorithm. A subclass of Markov random fields on a finite lattice, called partially ordered Markov models (POMMs), has analogous structure to that of DMPPs. In this paper, we show that DMPPs are the limits of auto-Poisson and auto-logistic POMMs. These and other results reveal a close link between inference and simulation for DMPPs and POMMs.     

Asymptotic properties of constrained Markov Decision Processes

We present in this paper several asymptotic properties of constrained Markov Decision Processes (MDPs) with a countable state space. We treat both the discounted and the expected average cost, with unbounded cost. We are interested in (1) the convergence of finite horizon MDPs to the infinite horizon MDP, (2) convergence of MDPs with a truncated state space to the problem with infinite state space, (3) convergence of MDPs as the discount factor goes to a limit. In all these cases we establish the convergence of optimal values and policies. Moreover, based on the optimal policy for the limiting problem, we construct policies which are almost optimal for the other (approximating) problems. Based on the convergence of MDPs with a truncated state space to the problem with infinite state space, we show that an optimal stationary policy exists such that the number of randomisations it uses is less or equal to the number of constraints plus one. We finally apply the results to a dynamic scheduling problem.This work was partially supported by the Chateaubriand fellowship from the French embassy in Israel and by the European Grant BRA-QMIPS of CEC DG XIII     

Computational Bayesian Analysis of Hidden Markov Models

Abstract

Versions of the Gibbs Sampler are derived for the analysis of data from hidden Markov chains and hidden Markov random fields. The principal new development is to use the pseudolikelihood function associated with the underlying Markov process in place of the likelihood, which is intractable in the case of a Markov random field, in the simulation step for the parameters in the Markov process. Theoretical aspects are discussed and a numerical study is reported.