Friday, March 29, 2024
HomeMatlabWhat Is a Stochastic Matrix? – Nick Higham

What Is a Stochastic Matrix? – Nick Higham


A stochastic matrix is an ntimes n matrix with nonnegative entries and unit row sums. If Ainmathbb{R}^{ntimes n} is stochastic then Ae = e, the place e = [1,1,dots,1]^T is the vector of ones. Because of this e is an eigenvector of A equivalent to the eigenvalue 1.

The identification matrix is stochastic, as is any permutation matrix. Listed here are another examples of stochastic matrices:

notag begin{aligned}   A_n &= n^{-1}ee^T, quad textrm{in particular}~~     A_3 = begin{bmatrix}    frac{1}{3} & frac{1}{3} & frac{1}{3}[3pt]    frac{1}{3} & frac{1}{3} & frac{1}{3}[3pt]    frac{1}{3} & frac{1}{3} & frac{1}{3}    end{bmatrix}, qquad (1)   B_n &= frac{1}{n-1}(ee^T -I), quad textrm{in particular}~~     B_3 = begin{bmatrix}              0 & frac{1}{2} & frac{1}{2}[2pt]    frac{1}{2} & 0           & frac{1}{2}[2pt]    frac{1}{2} & frac{1}{2} & 0    end{bmatrix},    qquad (2)   C_n &= begin{bmatrix}             1         &                   &           &          frac{1}{2}      &  frac{1}{2}      &           &          vdots           &  vdots           &ddots     &          frac{1}{n}      &  frac{1}{n}      &cdots     &  frac{1}{n}      end{bmatrix}.   qquad (3) end{aligned}

For any matrix A, the spectral radius rho(A) = max{ |lambda| : lambda mathrm{~is~an~eigenvalue~of~} A } is bounded by rho(A) le |A| for any norm. For a stochastic matrix, taking the infty-norm (the utmost row sum of absolute values) provides rho(A) le 1, so since we all know that 1 is an eigenvalue, rho(A) = 1. It may be proven that 1 is a semisimple eigenvalue, that’s, if there are k eigenvalues equal to 1 then there are k linearly impartial eigenvectors equivalent to 1 (Meyer, 2000, p. 696).

A decrease sure on the spectral radius could be obtained from Gershgorin’s theorem. The ith Gershgorin disc is outlined by |lambda - a_{ii}| le sum_{jne i} |a_{ij}| = 1 - a_{ii}, which means |lambda| ge 2a_{ii}-1. Each eigenvalue lambda lies within the union of the n discs and so should fulfill

notag         2min_i a_{ii}-1 le |lambda| le 1.

The decrease sure is constructive if A is strictly diagonally dominant by rows.

If A and B are stochastic then AB is nonnegative and ABe = Ae = e, so AB is stochastic. Specifically, any constructive integer energy of A is stochastic. Does A^k converge as ktoinfty? The reply is that it does, and the restrict is stochastic, so long as 1 is the one eigenvalue of modulus 1, and this would be the case if all the weather of A are constructive (by Perron’s theorem). The only instance of non-convergence is the stochastic matrix

notag    A = begin{bmatrix} 0 & 1  1 & 0 end{bmatrix},

which has eigenvalues 1 and -1. Since A^2 = I, all even powers are equal to I and all odd powers are equal to A. For the matrix (1), A_n^k = A_n for all k, whereas for (2), B_n^k to A_n as ktoinfty. For (3), C_n^k converges to the matrix with 1 in each entry of the primary column and zeros all over the place else.

Stochastic matrices come up in Markov chains. A transition matrix for a finite homogeneous Markov chain is a matrix whose (i,j) aspect is the likelihood of shifting from state i to state j over a time step. It has nonnegative entries and the rows sum to 1, so it’s a stochastic matrix. In purposes together with finance and healthcare, a transition matrix could also be estimated for a sure time interval, say one yr, however a transition matrix for a shorter interval, say one month, could also be wanted. If A is a transition matrix for a time interval p then a stochastic pth root of A, which is a stochastic answer X of the equation X^p = A, is a transition matrix for a time interval an element p smaller. Subsequently p = 12 (years to months) and p = 7 (weeks to days) are among the many values of curiosity. Sadly, a stochastic pth root could not exist. For instance, the matrix

notag begin{bmatrix}    0 & 1 & 0     0 & 0 & 1     0 & 0 & 1 end{bmatrix}

has no pth roots in any respect, not to mention stochastic ones. But many stochastic matrices do have stochastic roots. The matrix (3) has a stochastic pth root for all p, as proven by Higham and Lin (2011), who give an in depth evaluation of pth roots of stochastic matrices. For instance, to 4 decimal locations,

notag  C_6^{1/7} = begin{bmatrix} 1.000  &        &        &        &        &         0.094  & 0.906  &        &        &        &         0.043  & 0.102  & 0.855  &        &        &         0.027  & 0.050  & 0.103  & 0.820  &        &         0.019  & 0.032  & 0.052  & 0.103  & 0.795  &         0.014  & 0.023  & 0.034  & 0.053  & 0.102  & 0.774   end{bmatrix}.

A stochastic matrix is someday known as a row-stochastic matrix to differentiate it from a column-stochastic matrix, which is a nonnegative matrix for which e^TA = e^T (in order that A^T is row-stochastic). A matrix that’s each row-stochastic and column-stochastic is known as doubly stochastic. A permutation matrix is an instance of a doubly stochastic matrix. If U is a unitary matrix then the matrix with a_{ij} = |u_{ij}|^2 is doubly stochastic. A magic sq. scaled by the magic sum can also be doubly stochastic. For instance,

>> M = magic(4), A = M/sum(M(1,:)) % A is doubly stochastic.
M =
    16     2     3    13
     5    11    10     8
     9     7     6    12
     4    14    15     1
A =
   4.7059e-01   5.8824e-02   8.8235e-02   3.8235e-01
   1.4706e-01   3.2353e-01   2.9412e-01   2.3529e-01
   2.6471e-01   2.0588e-01   1.7647e-01   3.5294e-01
   1.1765e-01   4.1176e-01   4.4118e-01   2.9412e-02
>> [sum(A) sum(A')]
ans =
     1     1     1     1     1     1     1     1
>> eig(A)'
ans =
   1.0000e+00   2.6307e-01  -2.6307e-01   8.5146e-18

References

  • Nicholas J. Higham and Lijing Lin, On pth Roots of Stochastic Matrices, Linear Algebra Appl. 435, 448–463, 2011.
  • Carl D. Meyer, Matrix Evaluation and Utilized Linear Algebra, Society for Industrial and Utilized Arithmetic, Philadelphia, PA, USA, 2000.
RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Most Popular

Recent Comments