Row Stochastic Matrices Similar to Doubly Stochastic Matrices

The problem of determining which row stochastic n-by-n matrices are similar to doubly stochastic matrices is considered. That not all are is indicated by example, and an abstract characterization as well as various explicit sufficient conditions are given. For example, if a row stochastic matrix has no entry smaller than (n+1)^-1 it is similar to a doubly stochastic matrix.

Relaxing the nonnegativity requirement, the real matrices which are similar to real matrices with row and column sums one are then characterized, and it is observed that all row stochastic matrices have this property. Some remarks are then made on the nonnegative eigenvalue problem with respect to i) a necessary trace inequality and ii) removing zeroes from the spectrum.     

Stationary,completely mixed and symmetric optimal and equilibrium strategies in stochastic games

In this paper, we address various types of two-person stochastic games—both zero-sum and nonzero-sum, discounted and undiscounted. In particular, we address different aspects of stochastic games, namely: (1) When is a two-person stochastic game completely mixed? (2) Can we identify classes of undiscounted zero-sum stochastic games that have stationary optimal strategies? (3) When does a two-person stochastic game possess symmetric optimal/equilibrium strategies? Firstly, we provide some necessary and some sufficient conditions under which certain classes of discounted and undiscounted stochastic games are completely mixed. In particular, we show that, if a discounted zero-sum switching control stochastic game with symmetric payoff matrices has a completely mixed stationary optimal strategy, then the stochastic game is completely mixed if and only if the matrix games restricted to states are all completely mixed. Secondly, we identify certain classes of undiscounted zero-sum stochastic games that have stationary optima under specific conditions for individual payoff matrices and transition probabilities. Thirdly, we provide sufficient conditions for discounted as well as certain classes of undiscounted stochastic games to have symmetric optimal/equilibrium strategies—namely, transitions are symmetric and the payoff matrices of one player are the transpose of those of the other. We also provide a sufficient condition for the stochastic game to have a symmetric pure strategy equilibrium. We also provide examples to show the sharpness of our results.     

The doubly stochastic matrix equations x:aty= A and X Aty=t

For a doubly stochastic matrix A, each of the equations x:a^ty= A and X A^ty=^t is shown to have doubly stochastic solutions X and Y if and only if A lies in a subgroup of the semigroup of all doubly stochastic matrices of a given order. All elements of this semigroup which are left regular, right regular, or intra-regular are identified.     

Doubly stochastic matrices of trees

In this paper, we obtain sharp upper and lower bounds for the smallest entries of doubly stochastic matrices of trees and characterize all extreme graphs which attain the bounds. We also present a counterexample to Merris’ conjecture on relations between the smallest entry of the doubly stochastic matrix and the algebraic connectivity of a graph in [R. Merris, Doubly stochastic graph matrices II, Linear Multilinear Algebr. 45 (1998) 275–285].     

On pth roots of stochastic matrices

In Markov chain models in finance and healthcare a transition matrix over a certain time interval is needed but only a transition matrix over a longer time interval may be available. The problem arises of determining a stochastic pth root of a stochastic matrix (the given transition matrix). By exploiting the theory of functions of matrices, we develop results on the existence and characterization of matrix pth roots, and in particular on the existence of stochastic pth roots of stochastic matrices. Our contributions include characterization of when a real matrix has a real pth root, a classification of pth roots of a possibly singular matrix, a sufficient condition for a pth root of a stochastic matrix to have unit row sums, and the identification of two classes of stochastic matrices that have stochastic pth roots for all p. We also delineate a wide variety of possible configurations as regards existence, nature (primary or nonprimary), and number of stochastic roots, and develop a necessary condition for existence of a stochastic root in terms of the spectrum of the given matrix.     

Picard Iterations for Diffusions on Symmetric Matrices

Matrix-valued stochastic processes have been of significant importance in areas such as physics, engineering and mathematical finance. One of the first models studied has been the so-called Wishart process, which is described as the solution of a stochastic differential equation in the space of matrices. In this paper, we analyze natural extensions of this model and prove the existence and uniqueness of the solution. We do this by carrying out a Picard iteration technique in the space of symmetric matrices. This approach takes into account the operator character of the matrices, which helps to corroborate how the Lipchitz conditions also arise naturally in this context.     

Distribution functions in stochastic programs with recourse: A parametric analysis

This paper studies the behavior of the optimum value of a two-stage stochastic program with recourse (random right-hand sides) as the mean and covariance matrices defining the random variables in the program are perturbed. Several results for convex programs are developed and are used to study the effect such perturbations have on the regularity properties of the stochastic programs. Cost associated with incorrectly specifying the mean and covariance matrices are discussed and estimated. A stochastic programming model in which the random variable is dependent on the first-stage decision is presented.     

Doubly stochastic matrices over arbitrary vector spaces and the Birkhoff theorem

Doubly stochastic matrices are defined which have entries from an arbitrary vector space V. The extreme points of this convex set of matrices are studied, and convex subsets of V are identified for which these extreme matrices are of a permutation matrix type, i.e. for which a Birkhoff theorem holds.     

Calculating the Lyapunov exponent for generalized linear systems with exponentially distributed elements of the transition matrix

A stochastic dynamic system of second order is considered. The system evolution is described by a dynamic equation with a stochastic transition matrix, which is linear in the idempotent algebra with operations of maximum and addition. It is assumed that some entries of the matrix are zero constants and all other entries are mutually independent and exponentially distributed. The problem considered is the computation of the Lyapunov exponent, which is defined as the average asymptotic rate of growth of the state vector of the system. The known results related to this problem are limited to systems whose matrices have zero off-diagonal entries. In the cases of matrices with a zero row, zero diagonal entries, or only one zero entry, the Lyapunov exponent is calculated using an approach which is based on constructing and analyzing a certain sequence of one-dimensional distribution functions. The value of the Lyapunov exponent is calculated as the average value of a random variable determined by the limiting distribution of this sequence.     

Matrices which commute with doubly stochastic matrices

The set doubly stochastic matrices which commute with the doubly stochastic matrices of any particular given rank is determined.     

Matrices which commute with doubly stochastic matrices

The set doubly stochastic matrices which commute with the doubly stochastic matrices of any particular given rank is determined.     

Separating inequalities for non-negative covariances

We demonstrate explicit inequalities which separate covariances generated by non-negative stochastic processes from the class consisting of all non-negative covariances. The first class of covariances corresponds to completely positive matrices whereas the second class corresponds to doubly non-negative matrices. A key ingredient in our analysis is a new result the "convexity" of quatratic functions defined on the surface of a sphere.     

Separating inequalities for non-negative covariances

We demonstrate explicit inequalities which separate covariances generated by non-negative stochastic processes from the class consisting of all non-negative covariances. The first class of covariances corresponds to completely positive matrices whereas the second class corresponds to doubly non-negative matrices. A key ingredient in our analysis is a new result the "convexity" of quatratic functions defined on the surface of a sphere.     

Permanents of special classes of doubly stochastic matrices

We identify the doubly stochastic matrices with at least one zero entry which are closest in the Euclidean norm to J_n, the matrix with each entry equal to 1/n, and we show that at these matrices the permanent function has a relative minimum when restricted to doubly stochastic matrices having zero entries.     

Exponential convergence of products of stochastic matrices

This paper considers a finite set of stochastic matrices of finite order. Conditions are given under which any product of matrices from this set converges to a constant stochastic matrix. Also, it is shown that the convergence is exponentially fast.     

An extension of the Dulmage-Mendelsohn theorem

We prove a local Dulmage-Mendelsohn theorem, a generalization of their Theorem 18[1] to matrices which are decomposable or have period greater than one. This can be used to estimate the index of a wide variety of matrices and has applications to finite automata theory, stochastic processes, graph theory, and other fields.     

Relationship between genetic algebras and semicommutative matrices

Three kinds of noncommutative Gonshor genetic algebras are defined and characterized in terms of matrices. A necessary condition for an algebra to have one of these properties is the semicommutativity of a set of matrices representing the left (and the right) transformations induced by basis elements. For Gonshor genetic algebras which are interpretable, bounds for the train roots of the algebraare given. In terms of matrices this result yields bounds for the eigenvalues of a set ofcertain stochastic semicommutative matrices.     

NCD系统的数学理论

无索赔折扣系统(No Claim Discount system,简记为NCD系统)是世界各国机动车辆险中广泛采用的一种经验费率厘定机制.本文尝试建立了NCD系统严谨的数学理论, 重点讨论了NCD系统的数学建模和稳态分析.此外,作为本文必要的数学前提,首先在第2节着重探讨了随机矩阵间的随机优序关系,并将所得结论运用至齐次不可约且遍历的马尔科夫链的研究中,这些内容也有其独立的数学上的兴趣.     

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.     

Continuity and stability of fully random two-stage stochastic programs with mixed-integer recourse

In order to derive continuity and stability of two-stage stochastic programs with mixed-integer recourse when all coefficients in the second-stage problem are random, we first investigate the quantitative continuity of the objective function of the corresponding continuous recourse problem with random recourse matrices. Then by extending derived results to the mixed-integer recourse case, the perturbation estimate and the piece-wise lower semi-continuity of the objective function are proved. Under the framework of weak convergence for probability measure, the epi-continuity and joint continuity of the objective function are established. All these results help us to prove a qualitative stability result. The obtained results extend current results to the mixed-integer recourse with random recourse matrices which have finitely many atoms.