Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Finite Transition Matrix Equations: Some Easy Results & Sundry Questions
Posted:
Jun 9, 2011 7:25 AM


Finite transition matrices will be called A and also later M. They will have K rows corresponding to the K states of a Markov chain. Matrix entries are real, nonnegative and each of the K rows of A sums to 1. For simplicity, it is assumed A has K distinct, possibly complex, eigenvalues: lamda1lamdaK.
For illustration only, in the examples and results below (i) K will equal 3 or 8 (ii) all the chains will have one absorbing state, that is A has one row with just one nonzero element equal to 1.
This post considers the general problem of given a transition matrix A find a transition matrix M such that M to the power n equals A. For illustration only , in the examples below, n will be 2 or 12 and the elements of A will be transition probabilities based on, possibly adjusted, annual published data. For those interested in the financial applications, to monthly (or quarterly) stub periods, John Hull¹s excellent book, ³Options ,Futures and Other Derivatives²,6th edition, 2006 provides more background on credit risk migration matrices .
In general, given a transition matrix A, there is not always an exact solution even of M.M = A where it is required that M be a transition matrix. Consider a transition matrix A with K = 3 and six nonzero entries at the (1,1),(1,2),(2,1),(2,2),(2,3) and (3,3) positions respectively 0.9, 0.1, 0.1, 0.8, 0.1 and 1.0. It is clear that no transition matrix M, with its associated chain, satisfies M.M = A: by considering the zero at the (1,3) position of A and thence the (1,2) and (2,3) entries in M. Does anyone know theoretical conditions for an exact solution to such equations, I assume unique, when one exists?
In general amazingly good approximate solutions, for example in the case of diagonally dominant K=8, credit migration matrices, involves using only the eigensystem of A and sensible rounding. I vaguely recall, the approach described below, was mentioned at an S&P presentation in London very many years ago, for credit migration matrices, A . Does anyone know appropriate book or paper references? Is this approach best in some norm sense? How does performance depend on (i) the diagonal dominance of A and (ii) sparseness of A?
If D is a matrix of normalised eigenvectors of A and InvD its inverse then InvD.A.D = Diag[lamda1,,lamdaK]: the diagonalised matrix of eigenvalues. Good approximate solutions to the general problem can be obtained from a matrix X where X = D. (Diag [lamda1,.., lamdaK] ^ (1/ n)).InvD. In general, X will not be a transition matrix or even real but replacing all negative and complex entries with 0 and adjusting the diagonal elements of N to produce row sums equal to 1 consistently produces an amazingly good M.
Finally I should perhaps note (i) the ³Homer Simpson² solution of dividing offdiagonal elements of A by n and adjusting (increasing) the diagonal elements so that row sums equal 1 (ii) the approaches to producing riskneutral probabilities which may reduce diagonal dominance : see ³Synthetic CDOs², C.C.Mounfield, CUP,2009.



