Nonnegative tensors revisited: plane stochastic tensors

In this paper, we develop and enrich the theory of nonnegative tensors. We define the sign nonsingular tensors and establish the relationship between the combinatorial determinant and the permanent of nonnegative tensors. We generalize the results from doubly stochastic matrices to totally plane stochastic tensors and obtain a probabilistic algorithm for locating a positive diagonal in a nonnegative tensor under certain conditions. We form a normalization algorithm to convert some nonnegative tensors to plane stochastic tensors. We obtain a lower bound for the minimum of the axial N-index assignment problem by means of the set of plane stochastic tensors.     

Average stochastic games for continuous-time jump processes

We consider nonzero-sum games for continuous-time jump processes with unbounded transition rates under expected average payoff criterion. The state and action spaces are Borel spaces and reward rates are unbounded. We introduce an approximating sequence of stochastic game models with extended state space, for which the uniform exponential ergodicity is obtained. Moreover, we prove the existence of a stationary almost Markov Nash equilibrium by introducing auxiliary static game models. Finally, a cash flow model is employed to illustrate the results.     

Local convergence of the (exact and inexact) iterative aggregation method for linear systems and Markov operators

Summary. The iterative aggregation method for the solution of linear systems is extended in several directions: to operators on Banach spaces; to the method with inexact correction, i.e., to methods where the (inner) linear system is in turn solved iteratively; and to the problem of finding stationary distributions of Markov operators. Local convergence is shown in all cases. Convergence results apply to the particular case of stochastic matrices. Moreover, an argument is given which suggests why the iterative aggregation method works so well for nearly uncoupled Markov chains, as well as for Markov chains with other zero-nonzero structures. Received May 25, 1991/Revised version received February 23, 1994     

Zero-sum stochastic games with unbounded costs: Discounted and average cost cases

Zero-sum stochastic games with countable state space and with finitely many moves available to each player in a given state are treated. As a function of the current state and the moves chosen, player I incurs a nonnegative cost and player II receives this as a reward. For both the discounted and average cost cases, assumptions are given for the game to have a finite value and for the existence of an optimal randomized stationary strategy pair. In the average cost case, the assumptions generalize those given in Sennott (1993) for the case of a Markov decision chain. Theorems of Hoffman and Karp (1966) and Nowak (1992) are obtained as corollaries. Sufficient conditions are given for the assumptions to hold. A flow control example illustrates the results.     

On truncations and perturbations of Markov decision problems with an application to queueing network overflow control

Conditions are provided to derive error bounds on the effect of truncations and perturbations in Markov decision problems. Both the average and finite horizon case are studied. As an application, an explicit error bound is obtained for a truncation of a Jacksonian queueing network with overflow control.     

Rainflow analysis in Coastal Engineering using switching second order Markov models

The paper deals with the use of Markov and switching Markov chain models of turning points to reproduce random sets of sea states. The advantages of these models are emphasized and compared with existing models based on wave height records, indicating that long and short range and period cycles are included, while the wave height records ignore this important information from the point of view of damage accumulation. Existing models for first order Markov processes are extended to the case of second order processes and closed formulas are given to derive the rainflow matrices of these processes. Finally, one illustrative example of application is given.     

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.     

Stochastic matrices over cones

The notion of a stochastic operator in an ordered Banach space is specialized to a finite dimensional ordered real vector space. The classical limit theorems are obtained, and an application is made to non-homogeneous Markov chains. Finally, groups of nonnegative matrices are discussed.     

Stochastic matrices over cones

The notion of a stochastic operator in an ordered Banach space is specialized to a finite dimensional ordered real vector space. The classical limit theorems are obtained, and an application is made to non-homogeneous Markov chains. Finally, groups of nonnegative matrices are discussed.     

Nonnegative matrices having nonnegative Drazin pseudoinverses

Necessary and sufficient conditions for nonnegative matrices having nonnegative Drazin pseudoinverses are obtained. A decomposition theorem which characterizes the class of all nonnegative matrices with nonnegative Drazin pseudoinverses is proved, thus answering a question raised by several people. It is also shown that if a row (or column) stochastic matrix has a nonnegative Drazin pseudoinverse A(^d), then A(^d) is some power of A. These results extend known results for nonnegative group-monotone matrices.     

Robustness and applicability of Markov chain Monte Carlo algorithms for eigenvalue problems

In this paper we analyse applicability and robustness of Markov chain Monte Carlo algorithms for eigenvalue problems. We restrict our consideration to real symmetric matrices.

Almost Optimal Monte Carlo (MAO) algorithms for solving eigenvalue problems are formulated. Results for the structure of both – systematic and probability error are presented. It is shown that the values of both errors can be controlled independently by different algorithmic parameters. The results present how the systematic error depends on the matrix spectrum. The analysis of the probability error is presented. It shows that the close (in some sense) the matrix under consideration is to the stochastic matrix the smaller is this error. Sufficient conditions for constructing robust and interpolation Monte Carlo algorithms are obtained. For stochastic matrices an interpolation Monte Carlo algorithm is constructed.

A number of numerical tests for large symmetric dense matrices are performed in order to study experimentally the dependence of the systematic error from the structure of matrix spectrum. We also study how the probability error depends on the balancing of the matrix.     

Hierarchical Production Control in Dynamic Stochastic Jobshops with Long-Run Average Cost

We consider a production planning problem for a dynamic jobshop producing a number of products and subject to breakdown and repair of machines. The machine capacities are assumed to be finite-state Markov chains. As the rates of change of the machine states approach infinity, an asymptotic analysis of this stochastic manufacturing systems is given. The analysis results in a limiting problem in which the stochastic machine availability is replaced by its equilibrium mean availability. The long-run average cost for the original problem is shown to converge to the long-run average cost of the limiting problem. The convergence rate of the long-run average cost for the original problem to that of the limiting problem together with an error estimate for the constructed asymptotic optimal control is established.     

Block-successive approximation for a discounted Markov decision model

In this paper we suggest a new successive approximation method to compute the optimal discounted reward for finite state and action, discrete time, discounted Markov decision chains. The method is based on a block partitioning of the (stochastic) matrices corresponding to the stationary policies. The method is particularly attractive when the transition matrices are jointly nearly decomposable or nearly completely decomposable.     

Explicit forms for ergodicity coefficients and spectrum localization

Explicit forms for orgodicity coefficients which bound the non-unit eigenvalues of finite stochastic matrices are known in the cases p = 1, ∞ when the l_p norm is used [3,6,7]. The purpose of this report is to generalize these results to arbitrary real matrices (in particular square matrices with a real-valued eigenvalue), by giving a generalized (and to some extent simplified) synthesis of methods used hitherto. Alternative procedures are mentioned in the light of the framework established. The results are of particular relevance for a primitive nonnegative matrix, for which a bound results for the non-Perron-Frobenius eigenvalues.     

A geometric treatment of generalized inverses and semigroups of nonnegative matrices

The purpose of this paper is to provide a unified treatment from the geometric viewpoint of the following closely related aspects of nonnegative matrices: nonnegative matrices with nonnegative generalized inverses of various kinds; nonnegative rank factorization; regular elements, Green's relations, and maximal subgroups of the semigroups of nonnegative matrices, stochastic matrices, column stochastic matrices, and doubly stochastic matrices.     

Stability analysis and stabilization of linear symmetric matrix-valued continuous,discrete, and impulsive dynamical systems — A unified approach for the stability analysis and the stabilization of linear systems

Matrix-valued dynamical systems are an important class of systems that can describe important processes such as covariance/second-order moment processes, or processes on manifolds and Lie Groups. We address here the case of processes that leave the cone of positive semidefinite matrices invariant, thereby including covariance and second-order moment processes. Both the continuous-time and the discrete-time cases are first considered. In the LTV case, the obtained stability and stabilization conditions are expressed as differential and difference Lyapunov conditions which are equivalent, in the LTI case, to some spectral conditions for the generators of the processes. Convex stabilization conditions are also obtained in both the continuous-time and the discrete-time setting. It is proven that systems with constant delays are stable provided that the systems with zero-delays are stable—which mirrors existing results for linear positive systems. The results are then extended and unified into an impulsive formulation for which similar results are obtained. The proposed framework is very general and can recover and/or extend many of the existing results in the literature on linear systems related to (mean-square) exponential (uniform) stability. Several examples are discussed to illustrate this claim by deriving stability conditions for stochastic systems driven by Brownian motion and Poissonian jumps, Markov jump systems, (stochastic) switched systems, (stochastic) impulsive systems, (stochastic) sampled-data systems, and all their possible combinations.     

A new strong optimality criterion for nonstationary Markov decision processes

This paper deals with a new optimality criterion consisting of the usual three average criteria and the canonical triplet (totally so-called strong average-canonical optimality criterion) and introduces the concept of a strong average-canonical policy for nonstationary Markov decision processes, which is an extension of the canonical policies of Herna′ndez-Lerma and Lasserre [16] (pages: 77) for the stationary Markov controlled processes. For the case of possibly non-uniformly bounded rewards and denumerable state space, we first construct, under some conditions, a solution to the optimality equations (OEs), and then prove that the Markov policies obtained from the OEs are not only optimal for the three average criteria but also optimal for all finite horizon criteria with a sequence of additional functions as their terminal rewards (i.e. strong average-canonical optimal). Also, some properties of optimal policies and optimal average value convergence are discussed. Moreover, the error bound in average reward between a rolling horizon policy and a strong average-canonical optimal policy is provided, and then a rolling horizon algorithm for computing strong average ε(>0)-optimal Markov policies is given.     

Active parametric identification of stochastic linear discrete systems in the frequency domain

Under consideration are some theoretical and applied aspects of the active identification of the multidimensional stochastic linear discrete systems in the frequency domain which are described by models in the state space. Original results are obtained in the case that the parameters of mathematical models to be estimated appear in various combinations in the state and control matrices, as well as in the perturbation matrix and the covariation matrices of the dynamic noise and measurement errors. By an example of a system controlling a boring machine, the efficiency and sensibility is shown of applying the active identification procedure.     

Special operator equations

The study addresses the matrix operator equations of a special form which are used in the theory of Markov chains. Solving the operator equations with stochastic transition probability matrices of large finite or even countably infinite size reduces to the case of stochastic matrices of small size. In particular, the case of ternary chains is considered in detail. A Markov model for crack growth in a composite serves as an example of application.