Convergence rates in strong ergodicity for Markov processes

A coupling method is used to obtain the explicit upper and lower bounds for convergence rates in strong ergodicity for Markov processes. For one-dimensional diffusion processes and birth–death processes, these bounds are sharp in the sense that the upper one and the lower one only differ in a constant.     

Continuous-Time Markov Decision Processes with Unbounded Transition and Discounted-Reward Rates

Abstract

In this article, we study continuous-time Markov decision processes in Polish spaces. The optimality criterion to be maximized is the expected discounted criterion. The transition rates may be unbounded, and the reward rates may have neither upper nor lower bounds. We provide conditions on the controlled system's primitive data under which we prove that the transition functions of possibly non-homogeneous continuous-time Markov processes are regular by using Feller's construction approach to such transition functions. Then, under continuity and compactness conditions we prove the existence of optimal stationary policies by using the technique of extended infinitesimal operators associated with the transition functions of possibly non-homogeneous continuous-time Markov processes, and also provide a recursive way to compute (or at least to approximate) the optimal reward values. The conditions provided in this paper are different from those used in the previous literature, and they are illustrated with an example.     

Overflow and losses in a network queue with a self-similar input

This paper considers a discrete time queuing system that models a communication network multiplexer which is fed by a self-similar packet traffic. The model has a finite buffer of size h, a number of servers with unit service time, and an input traffic which is an aggregation of independent source-active periods having Pareto-distributed lengths and arriving as Poisson batches. The new asymptotic upper and lower bounds to the buffer-overflow and packet-loss probabilities P are obtained. The bounds give an exact asymptotic of log P/log h when h → to ∞. These bounds decay algebraically slow with buffer-size growth and exponentially fast with excess of channel capacity over traffic rate. Such behavior of the probabilities shows that one can better combat traffic losses in communication networks by increasing channel capacity rather than buffer size. A comparison of the obtained bounds and the known upper and lower bounds is done. This revised version was published online in June 2006 with corrections to the Cover Date.     

On exit time from balls of jump-type symmetric Markov processes

We obtain upper and lower bounds of the exit times from balls of a jump-type symmetric Markov process. The proofs are delivered separately. The upper bounds are obtained by using the Levy system corresponding to the process, while the precise expression of the （L^2-）generator of the Dirichlet form associated with the process is used to obtain the lower bounds.     

On the Stationary Distribution of the GI X /M Y /1 Queueing System

For the GI ^X /M/1 queue, it has been recently proved that there exist geometric distributions that are stochastic lower and upper bounds for the stationary distribution of the embedded Markov chain at arrival epochs. In this note we observe that this is also true for the GI ^X /M ^Y /1 queue. Moreover, we prove that the stationary distribution of its embedded Markov chain is asymptotically geometric. It is noteworthy that the asymptotic geometric parameter is the same as the geometric parameter of the upper bound. This fact justifies previous numerical findings about the quality of the bounds.     

First Hitting Time Analysis of the Independence Metropolis Sampler

In this paper, we study a special case of the Metropolis algorithm, the Independence Metropolis Sampler (IMS), in the finite state space case. The IMS is often used in designing components of more complex Markov Chain Monte Carlo algorithms. We present new results related to the first hitting time of individual states for the IMS. These results are expressed mostly in terms of the eigenvalues of the transition kernel. We derive a simple form formula for the mean first hitting time and we show tight lower and upper bounds on the mean first hitting time with the upper bound being the product of two factors: a “local” factor corresponding to the target state and a “global” factor, common to all the states, which is expressed in terms of the total variation distance between the target and the proposal probabilities. We also briefly discuss properties of the distribution of the first hitting time for the IMS and analyze its variance. We conclude by showing how some non-independence Metropolis–Hastings algorithms can perform better than the IMS and deriving general lower and upper bounds for the mean first hitting times of a Metropolis–Hastings algorithm.     

New sufficient conditions for average optimality in continuous-time Markov decision processes

This paper is devoted to studying continuous-time Markov decision processes with general state and action spaces, under the long-run expected average reward criterion. The transition rates of the underlying continuous-time Markov processes are allowed to be unbounded, and the reward rates may have neither upper nor lower bounds. We provide new sufficient conditions for the existence of average optimal policies. Moreover, such sufficient conditions are imposed on the controlled process’ primitive data and thus they are directly verifiable. Finally, we apply our results to two new examples.     

Average sample-path optimality for continuous-time Markov decision processes in Polish spaces

In this paper we study the average sample-path cost(ASPC) problem for continuous-time Markov decision processes in Polish spaces.To the best of our knowledge,this paper is a first attempt to study the ASPC criterion on continuous-time MDPs with Polish state and action spaces.The corresponding transition rates are allowed to be unbounded,and the cost rates may have neither upper nor lower bounds.Under some mild hypotheses,we prove the existence of ε(ε≥ 0)-ASPC optimal stationary policies based on two differe...     

Rate Functions for Symmetric Markov Processes via Heat Kernel

By making full use of heat kernel estimates, we establish the integral tests on the zero-one laws of upper and lower bounds for the sample path ranges of symmetric Markov processes. In particular, these results concerning on upper rate bounds are applicable for local and non-local Dirichlet forms, while lower rate bounds are investigated in both subcritical setting and critical setting.     

Some results on the nonstationary ideal II

This paper is a continuation of [Gi]. We show that the upper bound of [Gi] on the strength of NS _μ ⁺ precipitous for a regular μ is exact. The upper bounds on the strength of NS_κ precipitous for inaccessible κ are reduced quite close to the lower bounds.     

A Large Deviation Principle for Symmetric Markov Processes with Feynman–Kac Functional

We establish a large deviation principle for the occupation distribution of a symmetric Markov process with Feynman–Kac functional. As an application, we show the L ^p -independence of the spectral bounds of a Feynman–Kac semigroup. In particular, we consider one-dimensional diffusion processes and show that if no boundaries are natural in Feller’s boundary classification, the L ^p -independence holds, and if one of the boundaries is natural, the L ^p -independence holds if and only if the L ²-spectral bound is non-positive.     

On the optimal control of arrivals to a single queue with arbitrary feedback delay

We consider a problem of admission control to a single queue in discrete time. The controller has access to k step old queue lengths only, where k can be arbitrary. The problem is motivated, in particular, by recent advances in high-speed networking where information delays have become prominent. We formulate the problem in the framework of Completely Observable Controlled Markov Chains, in terms of a multi-dimensional state variable. Exploiting the structure of the problem, we show that under appropriate conditions, the multi-dimensional Dynamic Programming Equation (DPE) can be reduced to a unidimensional one. We then provide simple computable upper and lower bounds to the optimal value function corresponding to the reduced unidimensional DPE. These upper and lower bounds, along with a certain relationship among the parameters of the problem, enable us to deduce partially the structural features of the optimal policy. Our approach enables us to recover simply, in part, the recent results of Altman and Stidham, who have shown that a multiple-threshold-type policy is optimal for this problem. Further, under the same relationship among the parameters of the problem, we provide easily computable upper bounds to the multiple thresholds and show the existence of simple relationships among these upper bounds. These relationships allow us to gain very useful insights into the nature of the optimal policy. In particular, the insights obtained are of great importance for the problem of actually computing an optimal policy because they reduce the search space enormously. This revised version was published online in June 2006 with corrections to the Cover Date.     

New degree bounds for polynomial threshold functions

A real multivariate polynomial p(x ₁, …, x _n ) is said to sign-represent a Boolean function f: {0,1} ⁿ →{−1,1} if the sign of p(x) equals f(x) for all inputs x∈{0,1} ⁿ . We give new upper and lower bounds on the degree of polynomials which sign-represent Boolean functions. Our upper bounds for Boolean formulas yield the first known subexponential time learning algorithms for formulas of superconstant depth. Our lower bounds for constant-depth circuits and intersections of halfspaces are the first new degree lower bounds since 1968, improving results of Minsky and Papert. The lower bounds are proved constructively; we give explicit dual solutions to the necessary linear programs.     

On the sum of powers of Laplacian eigenvalues of bipartite graphs

For a bipartite graph G and a non-zero real α, we give bounds for the sum of the αth powers of the Laplacian eigenvalues of G using the sum of the squares of degrees, from which lower and upper bounds for the incidence energy, and lower bounds for the Kirchhoff index and the Laplacian Estrada index are deduced.     

Heat kernels of non-symmetric jump processes with exponentially decaying jumping kernel

In this paper we study the transition densities for a large class of non-symmetric Markov processes whose jumping kernels decay exponentially or subexponentially. We obtain their upper bounds which also decay at the same rate as their jumping kernels. When the lower bounds of jumping kernels satisfy the weak upper scaling condition at zero, we also establish lower bounds for the transition densities, which are sharp.     

Sub-stochastic matrix analysis for bounds computation—Theoretical results

Performance evaluation of complex systems is a critical issue and bounds computation provides confidence about service quality, reliability, etc. of such systems. The stochastic ordering theory has generated a lot of works on bounds computation. Maximal lower and minimal upper bounds of a Markov chain by a st-monotone one exist and can be efficiently computed. In the present work, we extend simultaneously this last result in two directions. On the one hand, we handle the case of a maximal monotone lower bound of a family of Markov chains where the coefficients are given by numerical intervals. On the other hand, these chains are sub-chains associated to sub-stochastic matrices. We prove the existence of this maximal bound and we provide polynomial time algorithms to compute it both for discrete and continuous Markov chains. Moreover, it appears that the bounding sub-chain of a family of strictly sub-stochastic ones is not necessarily strictly sub-stochastic. We establish a characterization of the families of sub-chains for which these bounds are strictly sub-stochastic. Finally, we show how to apply these results to a classical model of repairable system. A forthcoming paper will present detailed numerical results and comparison with other methods.     

Discounted Markov games; successive approximation and stopping times

This paper presents a number of successive approximation algorithms for the repeated two-person zero-sum game called Markov game using the criterion of total expected discounted rewards. AsWessels [1977] did for Markov decision processes stopping times are introduced in order to simplify the proofs. It is shown that each algorithm provides upper and lower bounds for the value of the game and nearly optimal stationary strategies for both players.     

Delay-range dependent stability criteria for neural networks with Markovian jumping parameters

The paper is concerned with a stability analysis problem for neural networks with Markovian jumping parameters. The jumping parameters considered here are generated from a continuous-time discrete-state homogenous Markov process, which are governed by a Markov process with discrete and finite state space. A new type of Markovian jumping matrix P_i is introduced in this paper. The discrete delays are assumed to be time-varying and belong to a given interval, which means that the lower and upper bounds of interval time-varying delays are available. Based on the new Lyapunov–Krasovskii functional, delay-interval dependent stability criteria are obtained in terms of linear matrix inequalities (LMIs). Finally, a numerical example is provided to demonstrate the lower conservatism and the effectiveness of the proposed LMI conditions.     

关于O-U型马氏过程维数和碰撞的一点结果

本文给出了维O－U型马氏过程像集的Housdorff维数上下界的一个估计，并研究了两个独立的一维O－U型马氏过程的碰撞问题。     

Sharp bounds for the first eigenvalue of symmetric Markov processes and their applications

By adopting a nice auxiliary transform of Markov operators, we derive new bounds for the first eigenvalue of the generator corresponding to symmetric Markov processes. Our results not only extend the related topic in the literature, but also are efficiently used to study the first eigenvalue of birth-death processes with killing and that of elliptic operators with killing on half line. In particular, we obtain two approximation procedures for the first eigenvalue of birth-death processes with killing, and present qualitatively sharp upper and lower bounds for the first eigenvalue of elliptic operators with killing on half line.