Perturbations and expressions for generalized inverses in Banach spaces and Moore-Penrose inverses in Hilbert spaces of closed linear operators

The problems of perturbation and expression for the generalized inverses of closed linear operators in Banach spaces and for the Moore-Penrose inverses of closed linear operators in Hilbert spaces are studied. We first provide some stability characterizations of generalized inverses of closed linear operators under T-bounded perturbation in Banach spaces, which are exactly equivalent to that the generalized inverse of the perturbed operator has the simplest expression T⁺(I+δTT⁺)^-1. Utilizing these results, we investigate the expression for the Moore-Penrose inverse of the perturbed operator in Hilbert spaces and provide a unified approach to deal with the range preserving or null space preserving perturbation. An explicit representation for the Moore-Penrose inverse of the perturbation is also given. Moreover, we give an equivalent condition for the Moore-Penrose inverse to have the simplest expression T^†(I+δTT^†)^-1. The results obtained in this paper extend and improve many recent results in this area.     

Generalized inverses of circulant and generalized circulant matrices

An expression for the Moore-Penrose inverse of certain singular circulants by S.R. Searle is generalized to include all circulants. Similar expressions are given for the Moore-Penrose inverse of block circulants with circulant blocks, level-q circulants, k-circulants where |k|=1, and certain other matrices which are the product of a permutation matrix and a circulant. Expressions for other generalized inverses are given.     

Generalized inverses and the total stopping times of collatz sequences

Let f(n) be defined on the set N is even, and f(n)=3n+1 if nie: is odd. A well-known conjecture in number theory asserts that for every n the sequence of iterates eventually reaches the cycle (4,2,1). We recast the conjecture in terms of a denumerable Markov chain with transition matrix P. Assuming that (4,2,1) is the only cycle, but allowing for the possibility of unbounded trajectories, we establish the complete structure of a particular generalized inverse X of I?P and show that the entries of X describe the trajectories and "total stopping times" of integers n. Moreover, the infinite matrix X satisfies properties which, in the case of finite matrices, are the defining properties of the unique group generalized inverse (I?P)^#. The result extends to dynamical systems on ? consisting of points that are fixed, eventually fixed, or have unbounded trajectories. As a consequence, we obtain a generalized inverse that encodes the dynamics of such systems, and for cases in which known general criteria for the existence of (I?P)^# do not apply.     

Properties of the promotion Markov chain on linear extensions

The Tsetlin library is a very well-studied model for the way an arrangement of books on a library shelf evolves over time. One of the most interesting properties of this Markov chain is that its spectrum can be computed exactly and that the eigenvalues are linear in the transition probabilities. This result has been generalized in different ways by various people. In this work, we investigate one of the generalizations given by the extended promotion Markov chain on linear extensions of a poset P introduced by Ayyer et al. (J Algebr Comb 39(4):853–881, 2014). They showed that if the poset P is a rooted forest, the transition matrix of this Markov chain has eigenvalues that are linear in the transition probabilities and described their multiplicities. We show that the same property holds for a larger class of posets for which we also derive convergence to stationarity results.     

On the characterization of generalized inverses by bordered matrices

A method to characterize the class of all generalized inverses of any given matrix A is considered. Given a matrix A and a nonsingular bordered matrix T of A,

$\text{T=}\text{A}\text{P}\text{Q}\text{R}$

the submatrix, corresponding to A, of T^-1 is a generalized inverse of A, and conversely, any generalized inverse of A is obtainable by this method. There are different definitions of a generalized inverse, and the arguments are developed with the least restrictive definition. The characterization of the Moore-Penrose inverse, the most restrictive definition, is also considered.     

Mixing times with applications to perturbed Markov chains

A measure of the “mixing time” or “time to stationarity” in a finite irreducible discrete time Markov chain is considered. The statistic , where {π_j} is the stationary distribution and m_ij is the mean first passage time from state i to state j of the Markov chain, is shown to be independent of the initial state i (so that η_i = η for all i), is minimal in the case of a periodic chain, yet can be arbitrarily large in a variety of situations. An application considering the effects perturbations of the transition probabilities have on the stationary distributions of Markov chains leads to a new bound, involving η, for the 1-norm of the difference between the stationary probability vectors of the original and the perturbed chain. When η is large the stationary distribution of the Markov chain is very sensitive to perturbations of the transition probabilities.     

The first-passage times of phase semi-Markov processes

In this paper, we consider a class of semi-Markov processes, known as phase semi-Markov processes, which can be considered as an extension of Markov processes, but whose times between transitions are phase-type random variables. Based on the theory of generalized inverses, we derive expressions for the moments of the first-passage time distributions, generalizing the results obtained by Kemeny and Snell (1960) for Markov chains.     

On generalized inverses of Boolean Matrices

Generalized inverses of Boolean Matrices are defined and the general form of matrices having generalized inverses is determined. Some structure theorems are proved, from which, some known results are obtained as corollaries. An algorithm to compute a generalized inverse of a matrix, when it exists, is given. The existence of various types of g-inverses is also investigated. All the results are obtained first for the {0,1}-Boolean algebra and then extended to an arbitrary Boolean algebra.     

Studying an overload system using rotation

1. IntroductionThe motivation of writing this paper was from calculating the blocking probability foran overloaded finite system. Our numerical experiments suggested that this probability canbe approximated efficiently by rotating the transition matrix by 180". Some preliminaryresults were obtained and can be found in [11 and [2]. Rotating the transition matrix definesa new Markov chain, which is often called the dual process in the literature, for example,[3--7]. For a finite Markov chain, …     

Markov Chains with finite convergence time

We study the properties of finite ergodic Markov Chains whose transition probability matrix P is singular. The results establish bounds on the convergence time of P^m to a matrix where all the rows are equal to the stationary distribution of P. The results suggest a simple rule for identifying the singular matrices which do not have a finite convergence time. We next study finite convergence to the stationary distribution independent of the initial distribution. The results establish the connection between the convergence time and the order of the minimal polynomial of the transition probability matrix. A queuing problem and a maintenance Markovian decision problem which possess the property of rapid convergence are presented.     

Continue,quit, restart probability model

We discuss a new applied probability model: there is a system whose evolution is described by a Markov chain (MC) with known transition matrix on a discrete state space and at each moment of a discrete time a decision maker can apply one of three possible actions: continue, quit, and restart MC in one of a finite number of fixed “restarting” points. Such a model is a generalization of a model due to Katehakis and Veinott (Math. Oper. Res. 12:262, 1987), where a restart to a unique point was allowed without any fee and quit action was absent. Both models are related to Gittins index and to another index defined in a Whittle family of stopping retirement problems. We propose a transparent recursive finite algorithm to solve our model by performing O(n³) operations.     

A linear-time algorithm for classifying the states of a finite Markov chain

Classifying the states of a finite Markov chain requires the identification of all irreducible closed sets and the set of transient states. This paper presents an algorithm for identifying these states that executes in time O(MAX(|V|, |E|)) where number of states and |E| is the number of positive entries in the Markov matrix. The algorithm finds the closed strongly connected components of the transition graph using a depth-first search.     

Inverses of Boolean matrices

For a Boolean matrix A, a g-inverse of A is a Boolean matrix G satisfying AGA=A, and a Vagner inverse is a g-inverse which in addition satisfies GAG=G. We give algorithms for finding all g-inverses, all Vagner inverses, and all of several other types of inverses including Moore-Penrose inverses. We give a criterion for a Boolean matrix to be regular, and criteria for the various types of inverse to exist. We count the numbers of Boolean matrices having Moore-Penrose and related types of inverses.     

Exponential bounds for discrete-time singularly perturbed Markov chains

This paper develops exponential type upper bounds for scaled occupation measures of singularly perturbed Markov chains in discrete time. By considering two-time scale in the Markov chains, asymptotic analysis is carried out. The cases of the fast changing transition probability matrix is irreducible and that are divisible into l ergodic classes are examined first; the upper bounds of a sequence of scaled occupation measures are derived. Then extensions to Markov chains involving transient states and/or nonhomogeneous transition probabilities are dealt with. The results enable us to further our understanding of the underlying Markov chains and related dynamic systems, which is essential for solving many control and optimization problems.     

Generalized inverses of matrices over a finite field

For a given m × n matrix A of rank r over a finite field F, the number of generalized inverses, of reflexive generalized inverses, of normalized generalized inverses, and of pseudoinverses of A are determined by elementary methods. The more difficult problem of determining which m × n matrices A of rank r over F have normalized generalized inverses and which have pseudoinverses is solved. Moreover, the number of such matrices which possess normalized generalized inverses and the number which possess pseudoinverses are found.     

Ergodic backward stochastic difference equations

We consider ergodic backward stochastic differential equations in a discrete time setting, where noise is generated by a finite state Markov chain. We show existence and uniqueness of solutions, along with a comparison theorem. To obtain this result, we use a Nummelin splitting argument to obtain ergodicity estimates for a discrete time Markov chain which hold uniformly under suitable perturbations of its transition matrix. We conclude with an application of this theory to a treatment of an ergodic control problem.     

A first–passage time random walk distribution with five transition probabilities: a generalization of the shifted inverse trinomial

In this paper a univariate discrete distribution, denoted by GIT, is proposed as a generalization of the shifted inverse trinomial distribution, and is formulated as a first-passage time distribution of a modified random walk on the half-plane with five transition probabilities. In contrast, the inverse trinomial arises as a random walk on the real line with three transition probabilities. The probability mass function (pmf) is expressible in terms of the Gauss hypergeometric function and this offers computational advantage due to its recurrence formula. The descending factorial moment is also obtained. The GIT contains twenty-two possible distributions in total. Special cases include the binomial, negative binomial, shifted negative binomial, shifted inverse binomial or, equivalently, lost-games, and shifted inverse trinomial distributions. A subclass GIT_3,1 is a particular member of Kemp’s class of convolution of pseudo-binomial variables and its properties such as reproductivity, formulation, pmf, moments, index of dispersion, and approximations are studied in detail. Compound or generalized (stopped sum) distributions provide inflated models. The inflated GIT_3,1 extends Minkova’s inflated-parameter binomial and negative binomial. A bivariate model which has the GIT as a marginal distribution is also proposed.     

On the inverse mean first passage matrix problem and the inverse M-matrix problem

The inverse mean first passage time problem is given a positive matrix M∈R^n,n, then when does there exist an n-state discrete-time homogeneous ergodic Markov chain C, whose mean first passage matrix is M? The inverse M-matrix problem is given a nonnegative matrix A, then when is A an inverse of an M-matrix. The main thrust of this paper is to show that the existence of a solution to one of the problems can be characterized by the existence of a solution to the other. In so doing we extend earlier results of Tetali and Fiedler.     

Weak Drazin inverses

A new type of generalized inverse is defined which is a weakened form of the Drazin inverse. These new inverses are called (d)-inverses. Basic properties of (d)-inverses are developed. It is shown that (d)-inverses are often easier to compute than Drazin inverses and can frequently be used in place of the Drazin inverse when studying systems of differential equations with singular coefficients or when studying Marcov chains.