Multiplicative Reversible Version of the Transition Matrix; Spectral Representation

At first we will discuss a method enabling us to transform (ergodic) transition matrices such that the resulting matrix is reversible.

• Let ${\mathbf{P}}=(p_{ij})$ be an irreducible and aperiodic (but not necessarily reversible) transition matrix and let ${\boldsymbol{\pi}}=(\pi_1,\ldots,\pi_\ell)^\top$ be the corresponding stationary initial distribution such that $\pi_i>0$ for all $i\in E$.
• Moreover, we consider the stochastic matrix $\widetilde{\mathbf{P}}=(\widetilde p_{ij})$ where

  $$\widetilde p_{ij}=\frac{\pi_j p_{ji}}{\pi_i}\;,$$ (99)

  
  
  i.e., $\widetilde{\mathbf{P}}={\mathbf{D}}^{-2}{\mathbf{P}}^\top{\mathbf{D}}^2$ where ${\mathbf{D}}={\,{\rm diag}}(\sqrt{\pi_i})$ is also an irreducible and aperiodic transition matrix having the same stationary initial distribution ${\boldsymbol{\pi}}=(\pi_1,\ldots,\pi_\ell)^\top$.
• The pair $({\mathbf{M}},{\boldsymbol{\pi}})$, where the stochastic matrix ${\mathbf{M}}=(m_{ij})$ is given by ${\mathbf{M}}={\mathbf{P}}\widetilde{\mathbf{P}}$, is reversible as we observe
  $$\pi_i m_{ij}=\pi_i\sum\limits_{k=1}^\ell p_{ik}\;\frac{\pi_jp_{jk... ...=\pi_j\sum\limits_{k=1}^\ell p_{jk}\;\frac{\pi_ip_{ik}}{\pi_k}=\pi_j m_{ji}\,.$$

Definition

$\;$ The matrix ${\mathbf{M}}={\mathbf{P}}\widetilde{\mathbf{P}}$ is called the multiplicative reversible version of the transition matrix ${\mathbf{P}}$.

Remarks

 

• All eigenvalues $\theta_{{\mathbf{M}},1},\ldots,\theta_{{\mathbf{M}},\ell}$ of ${\mathbf{M}}$ are real and in $[0,1]$ because ${\mathbf{M}}$ has the same eigenvalues as the symmetric and nonnegative definite matrix ${\mathbf{M}}^*={\mathbf{D}}{\mathbf{M}}{\mathbf{D}}^{-1}$, where
  $$m_{ij}^*=\frac{\sqrt{\pi_i}}{\sqrt{\pi_j}}\; m_{ij} =\frac{\sqrt{... ...t{\pi_k}}\; p_{ik}\Bigr)\Bigl(\frac{\sqrt{\pi_j}}{\sqrt{\pi_k}}\; p_{jk}\Bigr)$$
  and hence
  $${\mathbf{M}}^*={\mathbf{D}}{\mathbf{M}}{\mathbf{D}}^{-1}=\bigl({\... ...f{D}}^{-1}\bigr) \bigl({\mathbf{D}}{\mathbf{P}}{\mathbf{D}}^{-1}\bigr)^\top\,.$$

• As a consequence, the symmetric matrix ${\mathbf{M}}^*$ is diagonalizable and the right and left eigenvectors ${\boldsymbol{\phi}}_i^*$ and ${\boldsymbol{\psi}}_i^*$ can be chosen such that
  • ${\boldsymbol{\phi}}_i^*={\boldsymbol{\psi}}_i^*$ for all $i\in E$
  • the vectors ${\boldsymbol{\phi}}^*_1,\ldots,{\boldsymbol{\phi}}^*_\ell$ are an orthonormal basis in $\mathbb{R}^\ell$.
• Then ${\boldsymbol{\phi}}_1,\ldots,{\boldsymbol{\phi}}_\ell$ and ${\boldsymbol{\psi}}_1,\ldots,{\boldsymbol{\psi}}_\ell$, where

  $${\boldsymbol{\phi}}_i={\mathbf{D}}^{-1}{\boldsymbol{\phi}}^*_i \qquad {\boldsymbol{\psi}}_i={\mathbf{D}}{\boldsymbol{\psi}}^*_i\,,\qquad\forall\, i\in E\,,$$ (100)

  
  
  are right and left eigenvectors of ${\mathbf{M}}$, respectively, as for every $i\in E$
  $${\mathbf{M}}{\boldsymbol{\phi}}_i={\mathbf{M}}{\mathbf{D}}^{-1}{\... ...hbf{M}},i}{\boldsymbol{\phi}}^*_i=\theta_{{\mathbf{M}},i}{\boldsymbol{\phi}}_i$$
  and
  $${\boldsymbol{\psi}}_i^\top{\mathbf{M}}=\bigl({\mathbf{D}}{\boldsy... ...i}}^*_i)^\top{\mathbf{D}}=\theta_{{\mathbf{M}},i}{\boldsymbol{\psi}}_i^\top\,.$$

This yields the following spectral representation of the multiplicative reversible version ${\mathbf{M}}$ obtained from the transition matrix ${\mathbf{P}}$; see also the spectral representation given by formula (30).

Theorem 2.15   $\;$ For arbitrary $n\in\mathbb{N}$ and ${\mathbf{x}}\in\mathbb{R}^\ell$

$${\mathbf{M}}^n{\mathbf{x}}=\sum\limits_{i=1}^\ell\theta_{{\mathbf{M}},i}^n{\boldsymbol{\phi}}_i{\boldsymbol{\psi}}_i^\top{\mathbf{x}}\,.$$ (101)

where ${\boldsymbol{\phi}}_i$ and ${\boldsymbol{\psi}}_i$ are the right and left eigenvectors of ${\mathbf{M}}$ defined in $(\ref{eig.vek.emm})$.

Proof

 

• As the (right) eigenvectors ${\boldsymbol{\phi}}_1,\ldots,{\boldsymbol{\phi}}_\ell$ of ${\mathbf{M}}$ defined in (100) are also a basis in $\mathbb{R}^\ell$, for every ${\mathbf{x}}\in\mathbb{R}^\ell$ there is a (uniquely determined) vector $\bigl(x_1^{\rm (r)},\ldots,x_\ell^{\rm (r)}\bigr)^\top\in\mathbb{R}^\ell$ such that
  $${\mathbf{x}}=\sum\limits_{i=1}^\ell x_i^{\rm (r)}{\boldsymbol{\phi}}_i\,.$$

• Furthermore, we have ${\mathbf{M}}{\boldsymbol{\phi}}_i=\theta_{{\mathbf{M}},i}{\boldsymbol{\phi}}_i$ and hence ${\mathbf{M}}^n{\boldsymbol{\phi}}_i=\theta_{{\mathbf{M}},i}^n{\boldsymbol{\phi}}_i$ for arbitrary $i\in E$ and $n\in\mathbb{N}$.
• Thus we obtain
  $${\mathbf{M}}^n{\mathbf{x}}= \sum\limits_{i=1}^\ell x_i^{\rm (r)} ... ...ts_{i=1}^\ell x_i^{\rm (r)}\theta^n_{{\mathbf{M}},i} {\boldsymbol{\phi}}_i \,.$$

• On the other hand, (100) implies for arbitrary $i\in E$ and ${\mathbf{x}}\in\mathbb{R}^\ell$

  $${\boldsymbol{\psi}}_i^\top{\mathbf{x}}=\bigl({\mathbf{D}}{\boldsy... ...l({\boldsymbol{\psi}}_i^*\bigr)^\top {\boldsymbol{\phi}}_j^* = x_i^{\rm (r)}\,,$$ (102)

  
  
  where the last equality takes into account that ${\boldsymbol{\psi}}_i^*={\boldsymbol{\phi}}_i^*$ for all $i\in E$ and that the eigenvectors ${\boldsymbol{\phi}}^*_1,\ldots,{\boldsymbol{\phi}}^*_\ell$ von ${\mathbf{M}}^*$ are an orthonormal basis of $\mathbb{R}^\ell$.
• This proves the spectral representation (101).
  
  $\Box$