next up previous contents
Next: Frequency Analysis Up: Spectral Analysis of Markov Previous: Spectral Analysis of Markov

Perron's Formula

Perron's Formula expresses the elements ai j(n) of the n-th power An of a $m \times m$ square matrix A in terms of the eigenvalues and minor determinants of A. An eigenvalue $\lambda_k$ with multiplicity $\rho_k$ of A is a root with multiplicity $\rho_k$of the characteristic polynomial2.3 $A(\lambda)=\vert\lambda I_m - A\vert$, where Im is the identity matrix. Denote the minor of a matrix A which arises from deleting the i-th row and j-th column by Ai j and denote the so-called minor of the determinant $A(\lambda)$ which equals (-1)i+j times the determinant of the minor of $(\lambda I_m - A)_{j i}$by $A_{i j}(\lambda)$. Note the correct order of i and j in the latter definition. From [49, p. 16] we cite the following theorem:

Theorem 2.15 (Perron's Formula)   Let $\lambda_0,\lambda_1,\ldots,\lambda_\mu$ be the eigenvalues of a $m \times m$matrix A with multiplicities $\rho_0,\ldots,\rho_\mu$, respectively. Define for every $k \in \{0,\ldots,\mu\}$ a polynomial $\pi_k$ of degree $m-\rho_k$by $A(\lambda)=(\lambda - \lambda_k)^{\rho_k} \pi_k(\lambda)$. Then for all $(i,j) \in S^2={\rm I\!N}_m^2$, and for all $n \in {\rm I\!N}_0$,

\begin{displaymath}a_{i j}^{(n)}=\sum_{k=0}^\mu \frac{1}{(\rho_k -1)!}
...A_{i j}(\lambda)}{\pi_k (\lambda)}

As we will see below, Perron's formula is particularly useful if the matrix A has a maximal eigenvalue $\lambda_0=1$ with multiplicity 1 and if all other eigenvalues satisfy $\vert\lambda_k\vert<1$. This justifies the following definition and lemma which we cite from [49, pp. 21 and 46].

Definition 2.10   A chain $(S,{\rm I\!P})$ is called regular if ${\rm I\!P}$ has a maximal eigenvalue $\lambda_0=1$with multiplicity 1 and all other eigenvalues satisfy $\vert\lambda_k\vert<1$. The chain is called positively regular if, in addition, all the numbers Pj are strictly positive.

Lemma 2.16   A chain is regular (positively regular) if and only if there exists an integer nsuch that for at least one $j \in S$ (for all $j \in S$) and for all $i \in S$ the probability p(n)i j>0. If a regular chain is irreducible, it is positively regular.

For a proof see [49, Theorem 14.I and 14.II]. The next corollary, which follows trivially from the definitions of irreducibility and aperiodicity, gives an important class of positively regular chains.

Corollary 2.17   Irreducible aperiodic chains are positively regular.

By Corollary 2.17 the transition matrix ${\rm I\!P}$ of an irreducible aperiodic chain has an eigenvalue $\lambda_0=1$with multiplicity 1and satisfies $\vert\lambda_i\vert < \lambda_0$ for all $1 \le i \le \mu$. In this case, Perron's formula for the n'th power of ${\rm I\!P}$ assumes the following form, see [49, p. 19]:

p_{i j}^{(n)}=P_{j} + \sum_{k=1}^\mu \frac{1}{(\rho_k -1)!}
..._{i j}(\lambda)}{\pi_k (\lambda)}
\right]_{\lambda=\lambda_k}, \end{displaymath} (2.6)


P_{j}=\frac{{\rm I\!P}_{j j}(1)}{\sum_{i=1}^m {\rm I\!P}_{i i}(1)}. \end{displaymath} (2.7)

Here $p^{(n)}_{i j} \to P_{j}$ as $n \to \infty$ since the remaining term

\sum_{k=1}^\mu \frac{1}{(\rho_k -1)!}
...}_{i j}(\lambda)}{\pi_k (\lambda)}
\right]_{\lambda=\lambda_k} \end{displaymath} (2.8)

tends to zero on behalf of $\vert\lambda_k\vert<1$, $k \in \{1,\ldots,\mu\}$, see [49, p. 21].

Since the irreducible aperiodic chain $(S,{\rm I\!P})$ has a finite state space here, we already know from Lemma 2.8 that for all pairs $(i,j) \in S^2$ of states the n'th order transition probabilities p(n)i j tend to the probabilities Pj of the stable distribution ${\bf P}=(P_{1},\ldots,P_{m})$, i.e. it holds $\lim_{n \to \infty} p^{(n)}_{i j} =P_{j}$. By Lemma 2.7, the stable distribution is representable as Pi = 1/Ei[Ti]. Thus we get the following two representations for the stable distribution ${\bf P}=(P_{1},\ldots,P_{m})$:

P_{j} = 1/E_j[T_j] = \frac{{\rm I\!P}_{j j}(1)}{\sum_{i=1}^m
{\rm I\!P}_{i i}(1)},\quad i \in S. \end{displaymath} (2.9)

Moreover, in [49, Chapter 3] it is shown that (2.7) also represents the stable distribution in the case of a periodic irreducible chain although the remaining term (2.8) will not tend to zero in this case due to the existence of eigenvalues $\lambda_k \not=1$ with $\vert \lambda_k \vert=1$, recall Theorem 2.14.

next up previous contents
Next: Frequency Analysis Up: Spectral Analysis of Markov Previous: Spectral Analysis of Markov
Stefan Wegenkittl