Search

We revisit the problem of the computation of the limiting characteristics of (in)homogeneous continuous-time Markov chains with the finite state space. In general, it can be performed only numerically. The common rule of thumb is to interrupt calculations after quite some time, hoping that the values at some distant time interval will represent the sought-after solution. Convergence or ergodicity bounds, when available, can be used to answer such questions more accurately; i.e., they can indicate how to choose the position and the length of that distant time interval. The logarithmic norm method is a general technique that may allow one to obtain such bounds. Although it can handle continuous-time Markov chains with both finite and countable state spaces, its downside is the need to guess the proper similarity transformations, which may not exist. In this paper, we introduce a new technique, which broadens the scope of the logarithmic norm method. This is achieved by firstly splitting the generator of a Markov chain and then merging the convergence bounds of each block into a single bound. The proof of concept is illustrated by simple examples of the queueing theory. [ABSTRACT FROM AUTHOR]

Nonstationary countable Markov chains with continuous time and absorption at zero are considered. We study the convergence rate to the limit mode. As examples, we consider simple nonstationary random walks., 1. Introduction The problem of studying the convergence rate to the limit mode for birth and death processes was considered during the last two decades in many papers, e.g., [1, [...]

In this paper it is shown, that if a possibly inhomogeneous Markov chain with continuous time and finite state space is weakly ergodic and all the entries of its intensity matrix are locally integrable, then, using available results from the perturbation theory, its time-dependent probability characteristics can be approximately obtained from another Markov chain, having piecewise constant intensities and the same state space. The approximation error (the taxicab distance between the state probability distributions) is provided. It is shown how the Cauchy operator and the state probability distribution for an arbitrary initial condition can be calculated. The findings are illustrated with the numerical examples. [ABSTRACT FROM AUTHOR]

We consider a nonhomogeneous continuous-time Markov chain with finite phase space and 1-periodic intensities. The behavior of two important characteristics of the process is studied, namely, we obtain the bounds on the rate of convergence to the limiting mean and to double mean. Some examples of introduced values analysis are considered., Introduction The problem of analyzing convergence rate to the limit mode for different classes of Markov chains has been actively studied for the past few decades. In the present paper [...]

Conditions of the ergodicity of some continuous-time Markov processes close to birth-and-death processes with proportional intensities are studied., Nonstationary (time-nonhomogeneous) Markov chains and their stability have been intensively investigated over the past two decades (8), (11). Early research in this area appears to have been initiated by B. [...]

We consider inhomogeneous continuous-time Markov chains with vanishing perturbations. It is proved that, under some natural conditions, the limiting regimes of the initial and perturbed chains coincide. We obtain explicit estimates, which allow construction of the limiting regime of the perturbed chain, and show how these results can be used in the analysis of several known classes of queuing systems. [ABSTRACT FROM AUTHOR]

Consideration is given to three different analytical methods for the computation of upper bounds for the rate of convergence to the limiting regime of one specific class of (in)homogeneous continuous-time Markov chains. This class is particularly well suited to describe evolutions of the total number of customers in (in)homogeneous M/M/S queueing systems with possibly state-dependent arrival and service intensities, batch arrivals and services. One of the methods is based on the logarithmic norm of a linear operator function; the other two rely on Lyapunov functions and differential inequalities, respectively. Less restrictive conditions (compared with those known from the literature) under which the methods are applicable are being formulated. Two numerical examples are given. It is also shown that, for homogeneous birth-death Markov processes defined on a finite state space with all transition rates being positive, all methods yield the same sharp upper bound. [ABSTRACT FROM AUTHOR]

Abstract We study a non-stationary Markovian queueing model of a two-processor heterogeneous system and obtain basic limiting characteristics for this model. Some specific examples are considered illustrated by the corresponding plots. [ABSTRACT FROM AUTHOR]

The paper deals with a Markovian retrial queueing system with a constant retrial rate and two servers. We present the detailed description of the model as well as establish the sufficient conditions for null ergodicity and strong ergodicity of the corresponding process and obtain the upper bounds on the rate of convergence for both situations. [ABSTRACT FROM AUTHOR]

In this paper we present a method for the computation of convergence bounds for four classes of multiserver queueing systems, described by inhomogeneous Markov chains. Specifically, we consider an inhomogeneous M/M/S queueing system with possible state-dependent arrival and service intensities, and additionally possible batch arrivals and batch service. A unified approach based on a logarithmic norm of linear operators for obtaining sharp upper and lower bounds on the rate of convergence and corresponding sharp perturbation bounds is described. As a side effect, we show, by virtue of numerical examples, that the approach based on a logarithmic norm can also be used to approximate limiting characteristics (the idle probability and the mean number of customers in the system) of the systems considered with a given approximation error. [ABSTRACT FROM AUTHOR]

Weakly ergodic continuous-time countable Markov chains are studied. We obtain uniform in time bounds for approximations via truncations by analogous smaller chains under some natural assumptions. [ABSTRACT FROM AUTHOR]

A class of inhomogeneous Markovian queuing systems with possible catastrophic failures and group arrival of customers in the case of empty queue is considered; basic estimates of the rate of convergence and stability for this class are obtained. [ABSTRACT FROM AUTHOR]

Service life of many real-life systems cannot be considered infinite, and thus the systems will be eventually stopped or will break down. Some of them may be re-launched after possible maintenance under likely new initial conditions. In such systems, which are often modelled by birth and death processes, the assumption of stationarity may be too strong and performance characteristics obtained under this assumption may not make much sense. In such circumstances, timedependent analysis is more meaningful. In this paper, transient analysis of one class of Markov processes defined on non-negative integers, specifically, inhomogeneous birth and death processes allowing special transitions from and to the origin, is carried out. Whenever the process is at the origin, transition can occur to any state, not necessarily a neighbouring one. Being in any other state, besides ordinary transitions to neighbouring states, a transition to the origin can occur. All possible transition intensities are assumed to be non-random functions of time and may depend (except for transition to the origin) on the process state. To the best of our knowledge, first ergodicity and perturbation bounds for this class of processes are obtained. Extensive numerical results are also provided. [ABSTRACT FROM AUTHOR]

We consider a class of birth and death processes with finally constant birth and death intensities and obtain the exact formula for spectral gap of the process in some situations. Moreover, we study spectral gap values for a number of famous queueing models. [ABSTRACT FROM AUTHOR]

We deal with nonstationary continuous-time Markov chains for Markovian queues with bulk arrivals and group services. Under the assumption that arrival and service rates do not depend on the length of the queue, we suggest the approach of obtaining the sharp bounds on the rate of convergence to the limiting regime. We also study the approximations of the limiting characteristics of the queue-length process. [ABSTRACT FROM AUTHOR]

This articles focuses on M t /M t /N queue with catastrophes and obtains stability bounds for the main characteristics of the respective queue-length process. [ABSTRACT FROM AUTHOR]

Nonstationary loss queueing system (Erlang model) is considered. We study weak ergodicity, bounds on the rate of convergence, approximations, bounds for limit characteristics. [ABSTRACT FROM AUTHOR]

Consideration is given to queueing systems described by nonstationary birth-death processes with rates close to periodic. Questions connected with the existence and design of limiting mean characteristics are studied. Some examples of designing the means for concrete queueing systems are considered. [ABSTRACT FROM AUTHOR]

Optimal statistical process control (SPC) requires models of both in-control and out-of-control process states. Whereas a normal distribution is the generally accepted model for the in-control state, there is a doubt as to the existence of reliable models for out-of-control cases. Various process models, available in the literature, for discrete manufacturing systems (parts industry) can be treated as bounded discrete-space Markov chains, completely characterized by the original in-control state and a transition matrix for shifts to an out-of-control state. The present work extends these models by using a continuous-state Markov chain, incorporating non-random corrective actions. These actions are to be realized according to the SPC technique and should substantially affect the model. The developed stochastic model yields a Laplace distribution of a process mean. An alternative approach, based on the Information theory, also results in a Laplace distribution. Real-data tests confirm the applicability of a Laplace distribution for the parts industry and show that the distribution parameter is mainly controlled by the SPC sample size. [ABSTRACT FROM AUTHOR]

Focuses on nonergodicity of some continuous time Markov chains. Properties of an intensity matrix that guarantee the ergodicity or nonergodicity of a chain; Approaches for studying nonergodicity based on the upper and lower bounds.

Focuses on the rate of convergence for some birth and death processes (BDP). BDP with finally constant intensities;Queueing examples; Discussion of related theorems, corollaries and equations.

Various process models for discrete manufacturing systems (parts industry) can be treated as bounded discrete-space Markov chains, completely characterized by the original in-control state and a transition matrix for shifts to an out-of-control state. The present work extends these models by using a continuous-state Markov chain, incorporating non-random corrective actions. These actions are to be realized according to the statistical process control (SPC) technique and should substantially affect the model. The developed stochastic model yields Laplace distribution of a process mean. Real-data tests confirm its applicability for the parts industry and show that the distribution parameter is mainly controlled by the SPC sample size. [ABSTRACT FROM AUTHOR]

We extend Zeifman's method for bounding the spectral gap and obtain the asymptotical behaviour, as N→∞, of the spectral gap of a class of birth–death Markov chains known as random walks on a complete graph of size N. Copyright © 2000 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

An approach making it possible to obtain estimates of certain probabilities related to inhomogeneous multidimensional birth-and-death processes is proposed. [ABSTRACT FROM AUTHOR]

We apply the method of differential inequalities for the computation of upper bounds for the rate of convergence to the limiting regime for one specific class of (in)homogeneous continuous-time Markov chains. Such an approach seems very general; the corresponding description and bounds were considered earlier for finite Markov chains with analytical in time intensity functions. Now we generalize this method to locally integrable intensity functions. Special attention is paid to the situation of a countable Markov chain. To obtain these estimates, we investigate the corresponding forward system of Kolmogorov differential equations as a differential equation in the space of sequences l 1 . [ABSTRACT FROM AUTHOR]

The problem considered is the computation of the (limiting) time-dependent performance characteristics of one-dimensional continuous-time Markov chains with discrete state space and time varying intensities. Numerical solution techniques can benefit from methods providing ergodicity bounds because the latter can indicate how to choose the position and the length of the "distant time interval" (in the periodic case) on which the solution has to be computed. They can also be helpful whenever the state space truncation is required. In this paper one such analytic method—the logarithmic norm method—is being reviewed. Its applicability is shown within the queueing theory context with three examples: the classical time-varying M / M / 2 queue; the time-varying single-server Markovian system with bulk arrivals, queue skipping policy and catastrophes; and the time-varying Markovian bulk-arrival and bulk-service system with state-dependent control. In each case it is shown whether and how the bounds on the rate of convergence can be obtained. Numerical examples are provided. [ABSTRACT FROM AUTHOR]

This paper is largely a review. It considers two main methods used to study stability and to obtain appropriate quantitative estimates of perturbations of (inhomogeneous) Markov chains with continuous time and a finite or countable state space. An approach is described to the construction of perturbation estimates for the main five classes of such chains associated with queuing models. Several specific models are considered for which the limit characteristics and perturbation bounds for admissible "perturbed" processes are calculated. [ABSTRACT FROM AUTHOR]

We consider a multidimensional inhomogeneous birth-death process. In this paper, a general situation is studied in which the intensity of birth and death for each coordinate ("each type of particle") depends on the state vector of the whole process. A one-dimensional projection of this process on one of the coordinate axes is considered. In this case, a non-Markov process is obtained, in which the transitions to neighboring states are possible in small periods of time. For this one-dimensional process, by modifying the method previously developed by the authors of the note, estimates of the rate of convergence in weakly ergodic and null-ergodic cases are obtained. The simplest example of a two-dimensional process of this type is considered. [ABSTRACT FROM AUTHOR]

The model of a two-dimensional birth-death process with possible catastrophes is studied. The upper bounds on the rate of convergence in some weighted norms and the corresponding perturbation bounds are obtained. In addition, we consider the detailed description of two examples with 1-periodic intensities and various types of death (service) rates. The bounds on the rate of convergence and the behavior of the corresponding mathematical expectations are obtained for each example. [ABSTRACT FROM AUTHOR]

Home energy displays are emerging home energy management devices. Their energy saving potential is limited, because most display whole-home electricity consumption data. We propose a new approach to disaggregation electricity consumption by individual appliances and/or end uses that would enhance the effectiveness of home energy displays. The proposed method decomposes a system of appliance models into tuplets of appliances overlapping in power draw. Each tuplet is disaggregated using a modified Viterbi algorithm. In this way, the complexity of the disaggregation algorithm is linearly proportional to the number of appliances. The superior accuracy of the method is illustrated by a simulation example and by actual household data. [ABSTRACT FROM AUTHOR]