跳过程的主特征值

本文给出了一般跳过程主特征值下界的一个变分公式．对于马氏链,所设条件常满足;所得估计在轻微条件下可达到精确．从这个意义上讲,所得到的公式是彻底的．     

A finiteness theorem for Markov bases of hierarchical models

We show that the complexity of the Markov bases of multidimensional tables stabilizes eventually if a single table dimension is allowed to vary. In particular, if this table dimension is greater than a computable bound, the Markov bases consist of elements from Markov bases of smaller tables. We give an explicit formula for this bound in terms of Graver bases. We also compute these Markov and Graver complexities for all K×2×2×2 tables.     

Continuity of the Value of Competitive Markov Decision Processes

We provide a bound for the variation of the function that assigns to every competitive Markov decision process and every discount factor its discounted value. This bound implies that the undiscounted value of a competitive Markov decision process is continuous in the relative interior of the space of transition rules.     

Spectral gap for open Jackson networks

We generalize the decomposition method of the finite Markov chains for Poincaré inequality in Jerrum et al. (Ann. Appl. Probab., 14, 1741-1765 (2004)) to the reversible continuous-time Markov chains. And inductively, we give the lower bound of spectral gap for the ergodic open Jackson network by the decomposition method and the symmetrization procedure. The upper bound of the spectral gap is also presented.     

Ultracontractivity for Brownian motion with Markov switching

Consider the transition density functions for Brownian motion with two-state Markov switching. The characteristic functions for transition density functions are presented. Then, we show that the semigroup-associated Brownian motion with Markov switching is ultracontractive. And an explicit time-dependent upper bound for heat kernels are presented. Moreover, we prove that the Dirichlet form associated Brownian motion with Markov switching satisfies the Nash inequality.     

Relaxation of Product Markov Chains on Product Spaces

We study the relaxation time of product-type Markov chains approaching a product distribution. We bound the approach to stationarity for such Markov chains in terms of the mixing times of the component Markov chains. In cases where the component mixing times differ considerably we propose an optimized visiting scheme which makes such product-type Markov chains comparable to Gibbs-type samplers. We conclude the paper by discussing the relaxation of Metropolis-type samplers for separable energy functions.     

Truncated taylor series approximation to the state transition matrix of a continuous parameter finite Markov chain

A readily computable bound is established for the error in approximating the transition matrix for a continuous parameter Markov chain.     

Exponential Convergence Rates of Markov Chains under a Weaken Minorization Condition

In this paper, we obtain the quantitative bound of the exponential convergence rates of Markov chains under a weaken minorization condition, using the coupling method and the analytic approach. And also, we obtain the convergence rates for continuous time Markov processes.     

Upper bound for the non-maximal eigenvalues of irreducible nonnegative matrices

We present a lower and an upper bound for the second smallest eigenvalue of Laplacian matrices in terms of the averaged minimal cut of weighted graphs. This is used to obtain an upper bound for the real parts of the non-maximal eigenvalues of irreducible nonnegative matrices. The result can be applied to Markov chains.     

Numerical Bounds for Semi-Markovian Quantities and Application to Reliability

We propose new easily computable bounds for different quantities which are solutions of Markov renewal equations linked to some continuous-time semi-Markov process (SMP). The idea is to construct two new discrete-time SMP which bound the initial SMP in some sense. The solution of a Markov renewal equation linked to the initial SMP is then shown to be bounded by solutions of Markov renewal equations linked to the two discrete time SMP. Also, the bounds are proved to converge. To illustrate the results, numerical bounds are provided for two quantities from the reliability field: mean sojourn times and probability transitions.      

Linear variance bounds for particle approximations of time-homogeneous Feynman–Kac formulae

This article establishes sufficient conditions for a linear-in-time bound on the non-asymptotic variance for particle approximations of time-homogeneous Feynman–Kac formulae. These formulae appear in a wide variety of applications including option pricing in finance and risk sensitive control in engineering. In direct Monte Carlo approximation of these formulae, the non-asymptotic variance typically increases at an exponential rate in the time parameter. It is shown that a linear bound holds when a non-negative kernel, defined by the logarithmic potential function and Markov kernel which specify the Feynman–Kac model, satisfies a type of multiplicative drift condition and other regularity assumptions. Examples illustrate that these conditions are general and flexible enough to accommodate two rather extreme cases, which can occur in the context of a non-compact state space: (1) when the potential function is bounded above, not bounded below and the Markov kernel is not ergodic; and (2) when the potential function is not bounded above, but the Markov kernel itself satisfies a multiplicative drift condition.     

A note on Markov type constants

We prove that, if a geodesic metric space has Markov type 2 with constant 1, then it is an Alexandrov space of nonnegative curvature. The same technique provides a lower bound of the Markov type 2 constant of a space containing a tripod or a branching point. Received: 28 November 2007     

On the minimal penalty for Markov order estimation

We show that large-scale typicality of Markov sample paths implies that the likelihood ratio statistic satisfies a law of iterated logarithm uniformly to the same scale. As a consequence, the penalized likelihood Markov order estimator is strongly consistent for penalties growing as slowly as log log n when an upper bound is imposed on the order which may grow as rapidly as log n. Our method of proof, using techniques from empirical process theory, does not rely on the explicit expression for the maximum likelihood estimator in the Markov case and could therefore be applicable in other settings.     

Generalization bounds of ERM algorithm with V-geometrically Ergodic Markov chains

The previous results describing the generalization ability of Empirical Risk Minimization (ERM) algorithm are usually based on the assumption of independent and identically distributed (i.i.d.) samples. In this paper we go far beyond this classical framework by establishing the first exponential bound on the rate of uniform convergence of the ERM algorithm with V-geometrically ergodic Markov chain samples, as the application of the bound on the rate of uniform convergence, we also obtain the generalization bounds of the ERM algorithm with V-geometrically ergodic Markov chain samples and prove that the ERM algorithm with V-geometrically ergodic Markov chain samples is consistent. The main results obtained in this paper extend the previously known results of i.i.d. observations to the case of V-geometrically ergodic Markov chain samples.     

Error Bounds for Nonnegative Dynamic Models

The extension of Markov reward models to dynamic models with nonnegative matrices is motivated by practical applications, such as economic input–output, employment, or population models. This paper studies the generalization of error bound theorems for Markov reward structures to dynamic reward structures with arbitrary nonnegative matrices. Both irreducible and reducible matrices are covered. In addition, results for the stochastic case are unified and extended. First, generalized expressions are derived for average reward functions. The special normalization case is distinguished and is shown to be transformable into the stochastic case. Its interpretation is of interest in itself. Next, error bound results are studied. Under a general normalization condition, it is shown that the results for the stochastic case can be extended. Both the average case and the transient case are included. A random walk-type example is included to illustrate the results.     

Markov shifts and topological entropy of families of homoclinic tangles

The existence of a homoclinic orbit in dynamical systems implies chaotic behaviour with positive entropy. In this work, we determine explicitly the Markov shifts associated to certain Smale horseshoe homoclinic orbits which allow us to compute a lower bound for the topological entropy that such a system can have. It is done associating a heteroclinic orbit which belongs to the same isotopy class and then determining the Markov partition of the dynamical core of an end periodic mapping.     

Markov decision processes and strongly excessive functions

Strongly excessive functions play an important role in the theory of Markov decision processes and Markov games. In this paper the following question is investigated: What are the properties of Markov decision processes which possess a strongly excessive function? A probabilistic characterization is presented in the form of a random drift through a partitioned state space. For strongly excessive functions which have a positive lower bound a characterization is given in terms of the lifetime distribution of the process.Finally we give a characterization in terms of the spectral radius.     

随机单调的离散时间马氏链强遍历速度的估计I

研究了离散时间马氏链的强遍历性,对随机单调的离散时间马氏链,给出了最大强遍历收敛速度的下界估计。     

Stability of the nonlinear filter for slowly switching Markov chains

Exponential stability of the nonlinear filtering equation is revisited, when the signal is a finite state Markov chain. An asymptotic upper bound for the filtering error due to an incorrect initial condition is derived in the case of a slowly switching signal.