<figure><img src="image_1.png" /></figure>

HAL
open science

# On the power-dual and the exponential-dual of a matrix. Applications to Markov chain analysis

Gerardo Rubino

► To cite this version:

Gerardo Rubino. On the power-dual and the exponential-dual of a matrix. Applications to Markov chain analysis. 2024 - Fall Western Sectional Meeting, AMS - American Mathematical Society, Oct 2024, Riverside (CA), United States. hal-04756134

HAL Id: hal-04756134

https://inria.hal.science/hal-04756134v1

Submitted on 28 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

Public Domain
<figure><img src="image_2.png" /></figure>

<figure><img src="image_3.png" /></figure>

<figure><img src="image_4.png" /></figure>

<figure><img src="image_5.png" /></figure>

# On the power-dual and the exponential-dual of a matrix – Applications to Markov chain analysis

G. Rubino, Inria, Rennes, France
(joint work with A. Krinik, CalPoly, Pomona, USA)

2024 Fall Western Sectional Meeting of the AMS

Riverside, October 26, 2024

<figure><img src="image_6.png" /></figure>

<figure><img src="image_7.png" /></figure>

<figure><img src="image_8.png" /></figure>
<figure><img src="image_9.png" /></figure>

<figure><img src="image_10.png" /></figure>

<figure><img src="image_11.png" /></figure>

<figure><img src="image_12.png" /></figure>

# Outline

1/ Introduction

2/ Duality concepts

a/ Power-duals

b/ Exponential-duals

c/ Complements

3/ An application (of power-duals here)

4/ Conclusions

<figure><img src="image_13.png" /></figure>

<figure><img src="image_14.png" /></figure>

<figure><img src="image_15.png" /></figure>

<figure><img src="image_16.png" /></figure>

<figure><img src="image_17.png" /></figure>

<figure><img src="image_18.png" /></figure>

<figure><img src="image_19.png" /></figure>

<figure><img src="image_20.png" /></figure>
<figure><img src="image_21.png" /></figure>

<figure><img src="image_22.png" /></figure>

<figure><img src="image_23.png" /></figure>

<figure><img src="image_24.png" /></figure>

# Outline

1/ **Introduction**

2/ Duality concepts

a/ Power-duals

b/ Exponential-duals

c/ Complements

3/ An application (of power-duals here)

4/ Conclusions

<figure><img src="image_25.png" /></figure>

<figure><img src="image_26.png" /></figure>

<figure><img src="image_27.png" /></figure>
<figure><img src="image_28.png" /></figure>

<figure><img src="image_29.png" /></figure>

<figure><img src="image_30.png" /></figure>

<figure><img src="image_31.png" /></figure>

# Starting with Siegmund duality

* The Siegmund dual of a Markov process $X$ is a probabilistic transformation that **exists if X satisfies specific conditions**.

* If we write

$$X \longrightarrow \text{SiegmundDual}(X),$$

this can be also seen as a mapping between matrices, that is, between transition probability matrices (t.p.m.s) or infinitesimal generators (i.g.s). We can then write, for a t.p.m. $P$,

$$P \longrightarrow \text{SiegmundDual}(P) = \tilde{P},$$

or for an i.g. $A$

$$A \longrightarrow \text{SiegmundDual}(A) = \tilde{A}.$$

The difference in the notation is because **the matrix transformation is slightly different in case of p.t.m.s and of i.g.s.**

<figure><img src="image_32.png" /></figure>

<figure><img src="image_33.png" /></figure>
<figure><img src="image_34.png" /></figure>

<figure><img src="image_35.png" /></figure>

<figure><img src="image_36.png" /></figure>

<figure><img src="image_37.png" /></figure>

# Interest

* In some cases (for instance, for many fundamental queueing models starting with the $M/M/1$ and $M/M/1/H$ ones), the use of Siegmund duality allows for a significantly easier analysis of the transient behavior of a given Markov process, and specifically to obtain closed-form expressions.

* The main problem is the conditions under which there is such a dual process. This is because Siegmund duality looks for new processes in the same Markov family having a specific supplementary property (monotonicity).

<figure><img src="image_38.png" /></figure>

<figure><img src="image_39.png" /></figure>

<figure><img src="image_40.png" /></figure>
<figure><img src="image_41.png" /></figure>

<figure><img src="image_42.png" /></figure>

<figure><img src="image_43.png" /></figure>

<figure><img src="image_44.png" /></figure>

2 ideas here

* First idea: what happens if we define the same mappings for arbitrary square matrices now? In other words, if we ignore any restriction or condition.

* Second idea: looking at things this way forces to abandon probabilistic arguments and to **move to an algebraic point of view**. This appears to be fruitful.

* We call *power-dual* of an arbitrary square matrix the mapping corresponding formally to Siegmund-duality in DTMCs, and *exponential-dual* the one formally corresponding to CTMCs.

* Basically, the **power-dual** appears when we are interested in **matrix powers** and the **exponential-dual** if we look at **matrix exponentials**.

<figure><img src="image_45.png" /></figure>

<figure><img src="image_46.png" /></figure>

<figure><img src="image_47.png" /></figure>
<figure><img src="image_48.png" /></figure>

<figure><img src="image_49.png" /></figure>

<figure><img src="image_50.png" /></figure>

<figure><img src="image_51.png" /></figure>

# Outline

1/ Introduction

2/ Duality concepts

a/ Power-duals

b/ Exponential-duals

c/ Complements

3/ An application (of power-duals here)

4/ Conclusions

<figure><img src="image_52.png" /></figure>

<figure><img src="image_53.png" /></figure>

<figure><img src="image_54.png" /></figure>

<figure><img src="image_55.png" /></figure>

<figure><img src="image_56.png" /></figure>

<figure><img src="image_57.png" /></figure>

<figure><img src="image_58.png" /></figure>
<figure><img src="image_59.png" /></figure>

# The power-dual of a matrix

* Let $\mathcal{M}$ be an arbitrary square matrix of reals (or of complex numbers, etc.) with dimension $n$, indexed on $\{0, 1, \dots, n-1\}$.

* The **power-dual** of $\mathcal{M}$ is a new matrix $\tilde{\mathcal{M}}$, also denoted $\mathcal{PD}(\mathcal{M})$, with dimension $n+1$, indexed on $\{0, 1, \dots, n-1, n\}$, defined as follows: for $i = 0, 1, \dots, n-1$,

$$ \tilde{M}_{i,j} = \begin{cases} \sum_{k=i}^{n-1} M_{j,k} - \sum_{k=i}^{n-1} M_{j-1,k} & \text{if } j \le n-1, \\ 1 - \sum_{k=0}^{n-1} \tilde{M}_{i,k} & \text{when } j = n; \end{cases} $$

for the last row ($i=n$), we have (00...01).

* Example, dimension 2:

$$ M = \begin{pmatrix} a & b \\ c & d \end{pmatrix} \rightsquigarrow \tilde{M} = \begin{pmatrix} a+b & c+d-(a+b) & 1-(c+d) \\ b & d-b & 1-d \\ 0 & 0 & 1 \end{pmatrix} $$

<figure><img src="image_60.png" /></figure>
<figure><img src="image_61.png" /></figure>

<figure><img src="image_62.png" /></figure>

<figure><img src="image_63.png" /></figure>

<figure><img src="image_64.png" /></figure>

* Example, dimension 3:

$$ M = \begin{pmatrix} 1 & -1 & 2 \\ 2 & 0 & -2 \\ 1 & -3 & 3 \end{pmatrix} \rightsquigarrow \tilde{M} = \begin{pmatrix} 2 & -2 & 1 & 0 \\ 1 & -3 & 2 & 1 \\ 2 & -4 & 5 & -2 \\ 0 & 0 & 0 & 1 \end{pmatrix} $$

* A stochastic matrix:

$$ P = \begin{pmatrix} 2/5 & 0 & 3/5 \\ 1/6 & 1/2 & 1/3 \\ 0 & 1/4 & 3/4 \end{pmatrix} \rightsquigarrow \tilde{P} = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 3/5 & 7/30 & 1/6 & 0 \\ 3/5 & -4/15 & 5/12 & 1/4 \\ 0 & 0 & 0 & 1 \end{pmatrix}; $$

as we see, in this case the power-dual is not a stochastic matrix.

* Another stochastic matrix:

$$ P = \begin{pmatrix} 2/5 & 3/5 \\ 1/6 & 5/6 \end{pmatrix} \rightsquigarrow \tilde{P} = \begin{pmatrix} 1 & 0 & 0 \\ 3/5 & 1/15 & 1/3 \\ 0 & 0 & 1 \end{pmatrix}; $$

here, the power-dual is also a stochastic matrix.

<figure><img src="image_65.png" /></figure>
<figure><img src="image_66.png" /></figure>

<figure><img src="image_67.png" /></figure>

<figure><img src="image_68.png" /></figure>

<figure><img src="image_69.png" /></figure>

Example in $C$, dimension 3:

$$ M = \begin{pmatrix} 1 & i & 0 \\ 1-i & 1 & -1 \\ 3 & i & 0 \end{pmatrix} \rightsquigarrow \tilde{M} = \begin{pmatrix} 1+i & -2i & 2(1+i) & -(2+i) \\ i & -i & i & 1-i \\ 0 & -1 & 1 & 1 \\ 0 & 0 & 0 & 1 \end{pmatrix} $$

If $I_k$ is the identity matrix in dimension $k \ge 1$, then, for all $n \ge 1$,

$$ \tilde{I}_n = I_{n+1}. $$

<figure><img src="image_70.png" /></figure>
<figure><img src="image_71.png" /></figure>

<figure><img src="image_72.png" /></figure>

<figure><img src="image_73.png" /></figure>

<figure><img src="image_74.png" /></figure>

# Some properties

* Observe first that if $\tilde{M}$ is the power-dual of matrix $M$, then the sum of the elements of any row of $\tilde{M}$ is 1, and the last row of $\tilde{M}$ is composed only of 0s except for the last element which is 1.

* Inversion Lemma: assume that $\tilde{M}$ is the power-dual of the dimension-$n$ matrix $M$; then, for $0 \le i,j \le n-1$, we have

$$M_{i,j} = \sum_{k=0}^{i} \tilde{M}_{j,k} - \sum_{k=0}^{i} \tilde{M}_{j+1,k}.$$

* If in a square matrix the sum of the elements of any row is 1, it is called a *somewhat stochastic matrix*.

* Remark: if $\tilde{M}$ is an arbitrary somewhat stochastic matrix indexed on $\{0, 1, ..., n\}$, where the last row is $(00...01)$, then, if we consider the matrix $M$ indexed on $\{0, 1, ..., n-1\}$, given by previous formula, the power-dual of $M$ is $\tilde{M}$.

<figure><img src="image_75.png" /></figure>

<figure><img src="image_76.png" /></figure>

<figure><img src="image_77.png" /></figure>
<figure><img src="image_78.png" /></figure>

<figure><img src="image_79.png" /></figure>

<figure><img src="image_80.png" /></figure>

<figure><img src="image_81.png" /></figure>

* Central result: for any two square matrices $A$ and $B$ with the same dimension, we have

$$ \widetilde{AB} = \widetilde{B}\widetilde{A}. $$

* Corollary (and fundamental result): for any square matrix $M$ and any nonnegative integer $k$,

$$ \widetilde{M}^k = \widetilde{M}^k, $$

$$ \boxed{\widetilde{M}^k = \widetilde{M}^k} \text{, written also } \boxed{\widetilde{P}D(M^k) = \widetilde{P}D(M)^k} $$

that is, the power-dual of the $k$th power of $M$ is the $k$th power of $M$'s power-dual.

<figure><img src="image_82.png" /></figure>

<figure><img src="image_83.png" /></figure>

<figure><img src="image_84.png" /></figure>
<figure><img src="image_85.png" /></figure>

<figure><img src="image_86.png" /></figure>

<figure><img src="image_87.png" /></figure>

<figure><img src="image_88.png" /></figure>

# A possible path to compute $M^k$

Instead of

<figure><img src="image_89.png" /></figure>

we can try

<figure><img src="image_90.png" /></figure>

The point here is that in some (interesting) cases, computing the powers of the power-dual is easier than doing the same with the original matrix. See an example presented in the auxiliary slides.

<figure><img src="image_91.png" /></figure>

<figure><img src="image_92.png" /></figure>

<figure><img src="image_93.png" /></figure>
<figure><img src="image_94.png" /></figure>

<figure><img src="image_95.png" /></figure>

<figure><img src="image_96.png" /></figure>

<figure><img src="image_97.png" /></figure>

# Outline

1/ Introduction

2/ Duality concepts

a/ Power-duals

b/ Exponential-duals

c/ Complements

3/ An application (of power-duals here)

4/ Conclusions

<figure><img src="image_98.png" /></figure>

<figure><img src="image_99.png" /></figure>
<figure><img src="image_100.png" /></figure>

<figure><img src="image_101.png" /></figure>

<figure><img src="image_102.png" /></figure>

<figure><img src="image_103.png" /></figure>

# The exponential-dual of a matrix

* Let $M$ be an **arbitrary** square matrix (of real numbers, of complex numbers, ...) with dimension $n$, indexed on $\{0, 1, \dots, n-1\}$. The **exponential-dual** of $M$ is a new matrix $\hat{M}$, also denoted $\mathcal{ED}(M)$, with dimension $n+1$ indexed on $\{0, 1, \dots, n-1, n\}$, defined as follows: for $i < n$,

$$ \hat{M}_{i,j} = \sum_{k=i}^{n-1} M_{j,k} - \sum_{k=i}^{n-1} M_{j-1,k}; $$

the last row of $\hat{M}$ (that is, row $\hat{M}_{n,*}$) is $(00\dots0)$.

* Example, dimension 2:

$$ M = \begin{pmatrix} a & b \\ c & d \end{pmatrix} \rightsquigarrow \hat{M} = \begin{pmatrix} a+b & c+d-(a+b) & -(c+d) \\ b & d-b & -d \\ 0 & 0 & 0 \end{pmatrix} $$

<figure><img src="image_104.png" /></figure>
<figure><img src="image_105.png" /></figure>

<figure><img src="image_106.png" /></figure>

<figure><img src="image_107.png" /></figure>

<figure><img src="image_108.png" /></figure>

* Example, dimension 3:

$$ M = \begin{pmatrix} 1 & 2 & 3 \\ -1 & 2 & -3 \\ 0 & 2 & -2 \end{pmatrix} \rightsquigarrow \tilde{M} = \begin{pmatrix} 6 & -8 & 2 & 0 \\ 5 & -6 & 1 & 0 \\ 3 & -6 & 1 & 2 \\ 0 & 0 & 0 & 0 \end{pmatrix} $$

* An infinitesimal generator:

$$ M = \begin{pmatrix} -\lambda & \lambda \\ \mu & -\mu \end{pmatrix} \rightsquigarrow \tilde{M} = \begin{pmatrix} 0 & 0 & 0 \\ \lambda & -(\lambda + \mu) & \mu \\ 0 & 0 & 0 \end{pmatrix}; $$

as we see, the exponential-dual is also an infinitesimal generator.

* Another infinitesimal generator:

$$ M = \begin{pmatrix} -3 & 1 & 2 \\ 6 & -7 & 1 \\ 1 & 2 & -3 \end{pmatrix} \rightsquigarrow \tilde{M} = \begin{pmatrix} 0 & 0 & 0 & 0 \\ 3 & -9 & 5 & 1 \\ 2 & -1 & -4 & 3 \\ 0 & 0 & 0 & 0 \end{pmatrix}; $$

here, the exponential-dual is not an infinitesimal generator.

<figure><img src="image_109.png" /></figure>

<figure><img src="image_110.png" /></figure>
<figure><img src="image_111.png" /></figure>

<figure><img src="image_112.png" /></figure>

<figure><img src="image_113.png" /></figure>

<figure><img src="image_114.png" /></figure>

# Some properties

* Observe first that if $\hat{M}$ is the exponential-dual of matrix $M$, then the sum of the elements of any row of $\hat{M}$ is 0, and the last row of $\hat{M}$ is composed only of 0s.

* Inversion Lemma: $0 \le i, j \le n-1$, we have

$$M_{i,j} = \sum_{k=0}^{i} \hat{M}_{j,k} - \sum_{k=0}^{i} \hat{M}_{j+1,k}.$$

* Important result: for any two square matrices $A$ and $B$ with the same dimension, we have

$$\widehat{AB} = \hat{B}\hat{A}.$$

Corollary: for any square matrix $M$ and any integer $k \ge 1$,

$$\widehat{M}^k = \hat{M}^k.$$

In words, the exponential-dual of the $k$th power of $M$ is the $k$th power of $M$'s exponential-dual.

<figure><img src="image_115.png" /></figure>

<figure><img src="image_116.png" /></figure>
<figure><img src="image_117.png" /></figure>

<figure><img src="image_118.png" /></figure>

<figure><img src="image_119.png" /></figure>

<figure><img src="image_120.png" /></figure>

* Let $A$ and $B$ be two square matrices with the same dimension, and $\alpha$ be a scalar. We have

$$ \widehat{A+B} = \widehat{A} + \widehat{B}, \quad \widehat{\alpha A} = \alpha \widehat{A}. $$

* Let $(M_k)_{k \ge 0}$ a matrix sequence, with $M_k \to M$ as $k \to \infty$. Then,

$$ \widehat{M_k} \to \widehat{M} \text{ as } k \to \infty. $$

If $\sum_{k \ge 0} M_k = M$, then

$$ \sum_{k \ge 0} \widehat{M_k} = \sum_{k \ge 0} \widehat{M_k} = \widehat{M}. $$

<figure><img src="image_121.png" /></figure>

<figure><img src="image_122.png" /></figure>

<figure><img src="image_123.png" /></figure>

<figure><img src="image_124.png" /></figure>

<figure><img src="image_125.png" /></figure>

<figure><img src="image_126.png" /></figure>
<figure><img src="image_127.png" /></figure>

<figure><img src="image_128.png" /></figure>

<figure><img src="image_129.png" /></figure>

<figure><img src="image_130.png" /></figure>

# Main result

* Let $M$ be an arbitrary square matrix. Using previous properties, we obtain

$$ \boxed{e^{\hat{M}t} = \widetilde{e^{Mt}}} \quad \text{also written} \quad \boxed{\mathcal{PD}(e^{Mt}) = e^{\mathcal{E}\mathcal{D}(M)t}}. $$

In words, the power-dual of the exponential of $Mt$ is the exponential of the exponential-dual of $Mt$.

* This result explains why the evaluation of the power-dual also appears when we work on matrix exponentials.

* In this short presentation we skipped some other technical points that are needed to prove previous theorem.

<figure><img src="image_131.png" /></figure>
<figure><img src="image_132.png" /></figure>

<figure><img src="image_133.png" /></figure>

<figure><img src="image_134.png" /></figure>

<figure><img src="image_135.png" /></figure>

# A path to compute $e^{Mt}$

Instead of

$$ M \xrightarrow[\uparrow]{\longrightarrow} e^{Mt}, $$
any algorithm

we can try

$$ M \xrightarrow[\uparrow]{\longrightarrow} \hat{M} \xrightarrow[\uparrow]{\longrightarrow} e^{\hat{M}t} = \widetilde{e^{Mt}} \xrightarrow[\uparrow]{\longrightarrow} e^{Mt} $$
(linear) any algorithm

Inversion Lemma
of power-dual
(linear)

The point here is that in some (interesting) cases, computing the exponential of the exponential-dual of $M$ is easier than computing $M$'s exponential.

<figure><img src="image_136.png" /></figure>

<figure><img src="image_137.png" /></figure>

<figure><img src="image_138.png" /></figure>
<figure><img src="image_139.png" /></figure>

<figure><img src="image_140.png" /></figure>

<figure><img src="image_141.png" /></figure>

<figure><img src="image_142.png" /></figure>

# Outline

1/ Introduction

2/ Duality concepts

a/ Power-duals

b/ Exponential-duals

c/ Complements

3/ An application (of power-duals here)

4/ Conclusions

<figure><img src="image_143.png" /></figure>

<figure><img src="image_144.png" /></figure>
<figure><img src="image_145.png" /></figure>

<figure><img src="image_146.png" /></figure>

<figure><img src="image_147.png" /></figure>

<figure><img src="image_148.png" /></figure>

Other general properties:

* If $P$ is a stochastic matrix, then the first row of $\tilde{P}$ is $(1 \ 0 \ 0 \ \dots \ 0)$.
  Recall that $\tilde{P}$ doesn't need to be stochastic.

* If $A$ is an infinitesimal generator, then the first row of $\hat{A}$ is $(0 \ 0 \ \dots \ 0)$.
  Recall that $\hat{A}$ doesn't need to be an infinitesimal generator.

* Let $M$ be an arbitrary (square) matrix with dimension $n$. Let $W_k$ be the matrix with dimension $k$, composed of 0s except for its last column, only composed of 1s. Then,

$$ \tilde{M} = \hat{M} + W_{n+1}. $$

* Connection with the dual of a Markov process as defined by Siegmund in 1976 and developed in Anderson's book: if $A$ is the infinitesimal generator of a Markov process (in the sense of a Continuous Time Markov Chain) $X$ whose Siegmund dual exists, its generator is $\hat{A}$.

<figure><img src="image_149.png" /></figure>

<figure><img src="image_150.png" /></figure>
<figure><img src="image_151.png" /></figure>

<figure><img src="image_152.png" /></figure>

<figure><img src="image_153.png" /></figure>

<figure><img src="image_154.png" /></figure>

Some references

* Many of these definitions and results were already presented in the talk "The power-dual and the exponential-dual of a matrix" given at the virtual JMM'21 meeting.

* The details for the theory corresponding to the exponential-dual transformation only, have been published in "The exponential-dual matrix method: Applications to Markov chain analysis", AMS Contemporary Mathematics Series, Vol. 774, pages 217-235, 2021.

<figure><img src="image_155.png" /></figure>

<figure><img src="image_156.png" /></figure>

<figure><img src="image_157.png" /></figure>
<figure><img src="image_158.png" /></figure>

<figure><img src="image_159.png" /></figure>

<figure><img src="image_160.png" /></figure>

<figure><img src="image_161.png" /></figure>

# Outline

1/ Introduction

2/ Duality concepts

a/ Power-duals

b/ Exponential-duals

c/ Complements

3/ An application (of power-duals here)

4/ Conclusions

<figure><img src="image_162.png" /></figure>

<figure><img src="image_163.png" /></figure>

<figure><img src="image_164.png" /></figure>
<figure><img src="image_165.png" /></figure>

<figure><img src="image_166.png" /></figure>

<figure><img src="image_167.png" /></figure>

<figure><img src="image_168.png" /></figure>

## Two particular matrices

Let $M$ be a matrix having dimension $n \ge 2$ and let us define two auxiliary matrices $L$ and $R$, also of dimension $n$, as follows:

* $L_{i,j} = 1 (i \le j)$, where $1(S)$ is the indicator function of statement $S$ (it is equal to 1 if $S$ is true, and to 0 if it is false);

* concerning matrix $R$, we have, for $0 \le i \le n-1$, $R_{i,i} = 1$, then, for $0 \le i \le n-2$, $R_{i,i+1} = -1$, and for the rest of the matrix the elements are all equal to 0.

For instance, in dimension 4,

$$L = \begin{pmatrix} 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \end{pmatrix}$$

and

$$R = \begin{pmatrix} 1 & -1 & 0 & 0 \\ 0 & 1 & -1 & 0 \\ 0 & 0 & 1 & -1 \\ 0 & 0 & 0 & 1 \end{pmatrix}.$$

<figure><img src="image_169.png" /></figure>

<figure><img src="image_170.png" /></figure>

<figure><img src="image_171.png" /></figure>

<figure><img src="image_172.png" /></figure>

<figure><img src="image_173.png" /></figure>

<figure><img src="image_174.png" /></figure>
<figure><img src="image_175.png" /></figure>

<figure><img src="image_176.png" /></figure>

<figure><img src="image_177.png" /></figure>

<figure><img src="image_178.png" /></figure>

* Matrices $L$ and $R$ are invertible (observe that $|L| = |R| = 1$), and when they have the same dimension, $RL = I$ ($R$ is the inverse of $L$ and vice versa).

* Recall that given a matrix $U$, we denote by $nw(U)$ (and we say the "northwest" of $U$) the matrix obtained from $U$ by removing its last row and column. "Graphically",

$$U = \left( \begin{array}{c|c} \text{nw}(U) & \\ \vdots & \\ \text{nw}(U) & \\ \vdots & \\ \text{nw}(U) & \end{array} \right).$$

For instance, if we write $L_h$ or $R_h$ for previous matrices when their dimension is $h$, we have $nw(L_{n+1}) = L_n$ and $nw(R_{m+1}) = R_m$.

* Another immediate fact: for any matrix $M$, we have $nw(\hat{M}) = nw(M)$ (see also slide 22).

<figure><img src="image_179.png" /></figure>

<figure><img src="image_180.png" /></figure>

<figure><img src="image_181.png" /></figure>
<figure><img src="image_182.png" /></figure>

<figure><img src="image_183.png" /></figure>

<figure><img src="image_184.png" /></figure>

<figure><img src="image_185.png" /></figure>

More “exercises”

• If

$$
L = \begin{pmatrix}
1 & 1 & 1 & 1 \\
0 & 1 & 1 & 1 \\
0 & 0 & 1 & 1 \\
0 & 0 & 0 & 1
\end{pmatrix},
$$

then

$$
\tilde{L} = \begin{pmatrix} 4 & -1 & -1 & -1 & 0 \\ 3 & 0 & -1 & -1 & 0 \\ 2 & 0 & 0 & -1 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{pmatrix}, \quad \text{and} \quad \hat{L} = \begin{pmatrix} 4 & -1 & -1 & -1 & -1 \\ 3 & 0 & -1 & -1 & -1 \\ 2 & 0 & 0 & -1 & -1 \\ 1 & 0 & 0 & 0 & -1 \\ 0 & 0 & 0 & 0 & 0 \end{pmatrix}.
$$

<figure><img src="image_186.png" /></figure>

<figure><img src="image_187.png" /></figure>

<figure><img src="image_188.png" /></figure>

<figure><img src="image_189.png" /></figure>

<figure><img src="image_190.png" /></figure>

<figure><img src="image_191.png" /></figure>
<figure><img src="image_192.png" /></figure>

<figure><img src="image_193.png" /></figure>

<figure><img src="image_194.png" /></figure>

<figure><img src="image_195.png" /></figure>

• If

$$R = \begin{pmatrix} 1 & -1 & 0 & 0 \\ 0 & 1 & -1 & 0 \\ 0 & 0 & 1 & -1 \\ 0 & 0 & 0 & 1 \end{pmatrix},$$

then

$$\tilde{R} = \begin{pmatrix} 0 & 0 & 0 & 1 & 0 \\ -1 & 1 & 0 & 1 & 0 \\ 0 & -1 & 1 & 1 & 0 \\ 0 & 0 & -1 & 2 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{pmatrix}, \quad \text{and} \quad \tilde{R} = \begin{pmatrix} 0 & 0 & 0 & 1 & -1 \\ -1 & 1 & 0 & 1 & -1 \\ 0 & -1 & 1 & 1 & -1 \\ 0 & 0 & -1 & 2 & -1 \\ 0 & 0 & 0 & 0 & 0 \end{pmatrix}.$$

<figure><img src="image_196.png" /></figure>

<figure><img src="image_197.png" /></figure>

<figure><img src="image_198.png" /></figure>

<figure><img src="image_199.png" /></figure>

<figure><img src="image_200.png" /></figure>

<figure><img src="image_201.png" /></figure>

<figure><img src="image_202.png" /></figure>
<figure><img src="image_203.png" /></figure>

<figure><img src="image_204.png" /></figure>

<figure><img src="image_205.png" /></figure>

<figure><img src="image_206.png" /></figure>

# Similarity property

* Matrix version of the power-dual **definition**: $M^T$ and $nw(\tilde{M})$ verify

$$nw(\tilde{M}) = L M^T R,$$

meaning that $M^T$ and $nw(\tilde{M})$ are **similar** matrices, so, $M$ and $nw(\tilde{M})$ are also **similar**

Since $nw(\tilde{M}) = nw(\tilde{M})$, $M$ and $nw(\tilde{M})$ are also similar.

* For instance, as a corollary, we have that the spectrums of $M$ and of $nw(\tilde{M}) = nw(\tilde{M})$ are identical.

<figure><img src="image_207.png" /></figure>

<figure><img src="image_208.png" /></figure>

<figure><img src="image_209.png" /></figure>
<figure><img src="image_210.png" /></figure>

<figure><img src="image_211.png" /></figure>

<figure><img src="image_212.png" /></figure>

<figure><img src="image_213.png" /></figure>

# An application of the power-dual: the gambler ruin problem

* Let $\tilde{X}$ be a Markov chain with $n+1$ states labelled $0, 1, \dots, n$, where states $0$ and $n$ are absorbing and states $1$ to $n-1$ are transient.

* Let $\tilde{P}$ be the transition probability matrix of $\tilde{X}$. Matrix $\tilde{P}$ has the following structure:

$$ \tilde{P} = \begin{pmatrix} 1 & 0 & \dots & 0 \\ \tilde{P}_{1,0} & \ddots & \ddots & \tilde{P}_{1,n} \\ \vdots & & \ddots & \vdots \\ \tilde{P}_{n-1,0} & \dots & \dots & \tilde{P}_{n-1,n} \\ 0 & 0 & \dots & 1 \end{pmatrix}. $$

* We want to compute the absorption probabilities $x_i = P_i(\tilde{X}(\infty) = 0)$, for any state $i$ of $\tilde{X}$. We obviously have $x_0 = 1$ and $x_n = 0$; the interesting case is $i$ transient (that is, $1 \le i \le n-1$).

<figure><img src="image_214.png" /></figure>

<figure><img src="image_215.png" /></figure>

<figure><img src="image_216.png" /></figure>
<figure><img src="image_217.png" /></figure>

<figure><img src="image_218.png" /></figure>

<figure><img src="image_219.png" /></figure>

<figure><img src="image_220.png" /></figure>

* Let us put a name on $nw(\tilde{P})$, say $\bar{P}$, that is,

$$ \tilde{P} = \left( \begin{array}{c|c} \bar{P} & \vdots \\ \hline \vdots & \vdots \end{array} \right). $$

* Call $P$ the unique matrix whose power-dual is $\tilde{P}$.

Property: $P$ is **somewhat stochastic** (straightforward result).

Recall that $P$ need not to be stochastic.

<figure><img src="image_221.png" /></figure>

<figure><img src="image_222.png" /></figure>
<figure><img src="image_223.png" /></figure>

<figure><img src="image_224.png" /></figure>

<figure><img src="image_225.png" /></figure>

<figure><img src="image_226.png" /></figure>

* **Result:** there exists a vector $\pi$ with dimension $n$ such that matrix $P^\ell \to 1^T\pi$ as $\ell \to \infty$, where $\pi 1^T = 1$.

**Sketch of proof:** we know that $\tilde{P} = L P^T R$, so, $P^T = R \tilde{P} L$, which implies that for any integer $\ell \ge 1$,

$$ (P^T)^\ell = R \tilde{P}^\ell L. $$

Now, by construction of $\tilde{P}$, we have that

$$ \tilde{P}^\infty = \begin{pmatrix} 1 & 0 & \dots & 0 \\ x_1 & & & \\ x_2 & & & \\ \vdots & & & \\ x_{n-1} & & & \end{pmatrix}. $$

Then, we multiply this by $R$ on the left and by $L$ on the right, that is, we compute $R \tilde{P}^\infty L$. This can be written $(1^T\pi)^T$, where $\pi_i = x_i - x_{i+1}$ for $i = 0, 1, \dots, n-1$.

<figure><img src="image_227.png" /></figure>

<figure><img src="image_228.png" /></figure>

<figure><img src="image_229.png" /></figure>
<figure><img src="image_230.png" /></figure>

<figure><img src="image_231.png" /></figure>

<figure><img src="image_232.png" /></figure>

<figure><img src="image_233.png" /></figure>

How to obtain vector $\pi$? (observe that we have $\pi 1^T = 1$ but that some components of $\pi$ can be negative).

* **Result:** the system {$xP = x$ and $x1^T = 1$} has a unique solution, and the solution is $\pi$.

**Sketch of proof:** we first prove that $\pi P = \pi$, for instance, by writing the sequence $(p(k))_{k \ge 0}$ defined by $p(k) = \alpha P^k$ where $\alpha$ satisfies $\alpha 1^T = 1$ but is otherwise arbitrary, then making $k \to \infty$ in $p(k+1) = p(k)P$.

Then, if $\nu$ is a vector such that $\nu = \nu P$ and $\nu 1^T = 1$, again, after observing that $\nu P^k = \nu$ and making $k \to \infty$, we get $\nu P^\infty = \nu$, but $\nu = \nu P^\infty = \nu 1^T \pi = \pi$ (associativity), so, $\nu = \pi$.

<figure><img src="image_234.png" /></figure>

<figure><img src="image_235.png" /></figure>

<figure><img src="image_236.png" /></figure>
<figure><img src="image_237.png" /></figure>

<figure><img src="image_238.png" /></figure>

<figure><img src="image_239.png" /></figure>

<figure><img src="image_240.png" /></figure>

* So, once $\pi$ known (by solving the linear system $\pi P = \pi$ plus $\pi 1^T = 1$), we obtain the $x_i$s by inverting the relations going from $x$ to $\pi$:

* $x_1 = 1 - \pi_0$,

* $x_2 = 1 - \pi_0 - \pi_1,$

* $x_i = 1 - (\pi_0 + \pi_1 + \cdots + \pi_{i-1})$, or, equivalently, $x_i = \pi_i + \pi_{i+1} + \cdots + \pi_{n-1}$, ...

* $x_{n-1} = \pi_{n-1}$.

<figure><img src="image_241.png" /></figure>

<figure><img src="image_242.png" /></figure>
<figure><img src="image_243.png" /></figure>

<figure><img src="image_244.png" /></figure>

<figure><img src="image_245.png" /></figure>

<figure><img src="image_246.png" /></figure>

Resuming

So, to compute the absorption probabilities x,

* We first compute $\pi$, by solving the linear system $\pi P = \pi$ plus $\pi 1^T = 1$, as we do when $P$ is, for instance, the t.p.m. of an irreducible chain and we want the stationary distribution, even if here, we can have negative elements in $P$ (and in the solution $\pi$).

* Then, we apply previous formulas. These can be simply written in matrix form as

$$x = \pi L \quad \text{and} \quad \pi = x R.$$

<figure><img src="image_247.png" /></figure>

<figure><img src="image_248.png" /></figure>

<figure><img src="image_249.png" /></figure>
<figure><img src="image_250.png" /></figure>

<figure><img src="image_251.png" /></figure>

<figure><img src="image_252.png" /></figure>

<figure><img src="image_253.png" /></figure>

Remark

* Observe that going back to the initial gambler ruin problem (slide 30), we obtain the $x_i$s, for $i$ transient, by solving the linear system

$$x_i = \tilde{P}_{i,0} + \sum_{j=1}^{n-1} \tilde{P}'_{i,j} x_j,$$

for $1 \le i \le n-1$.

* Let us denote $\tilde{v} = (\tilde{P}_{1,0} \dots \tilde{P}_{n-1,0})$. The linear system is, in matrix form, $x^T = \tilde{v}^T + \tilde{P}'x^T$.

* So, using the power-dual, we have changed our linear system, from the initial one using matrix $\tilde{P}'$ (dimension $n-1$) to a new one with matrix $P$ (dimension $n$).

<figure><img src="image_254.png" /></figure>

<figure><img src="image_255.png" /></figure>

<figure><img src="image_256.png" /></figure>
<figure><img src="image_257.png" /></figure>

<figure><img src="image_258.png" /></figure>

<figure><img src="image_259.png" /></figure>

<figure><img src="image_260.png" /></figure>

# Outline

1/ Introduction

2/ Duality concepts

a/ Power-duals

b/ Exponential-duals

c/ Complements

3/ An application (of power-duals here)

4/ Conclusions

<figure><img src="image_261.png" /></figure>

<figure><img src="image_262.png" /></figure>
<figure><img src="image_263.png" /></figure>

<figure><img src="image_264.png" /></figure>

<figure><img src="image_265.png" /></figure>

<figure><img src="image_266.png" /></figure>

* The power-dual and the exponential-dual extend somehow Sigmund dual to arbitrary matrices, so, at the same time, they move the transformation from Markov processes to general linear algebra.

* Sometimes, the transformation simplifies significantly the analysis, that is, working with these duals is, in some cases, much easier than with the original data.

* Main task that remains to be explored (work in progress): the case of infinite state spaces / infinite matrices (linear operators).

<figure><img src="image_267.png" /></figure>

<figure><img src="image_268.png" /></figure>
<figure><img src="image_269.png" /></figure>

<figure><img src="image_270.png" /></figure>

<figure><img src="image_271.png" /></figure>

<figure><img src="image_272.png" /></figure>

Thanks for your time.

<figure><img src="image_273.png" /></figure>

<figure><img src="image_274.png" /></figure>

<figure><img src="image_275.png" /></figure>
<figure><img src="image_276.png" /></figure>

<figure><img src="image_277.png" /></figure>

<figure><img src="image_278.png" /></figure>

<figure><img src="image_279.png" /></figure>

# On Siegmund dual's existence (Markov processes)

* This concerns the historical origin of this work, in the stochastic processes area.

* For instance, consider an homogeneous “ring” illustrated here for 3 states (continuous time):

<figure><img src="image_280.png" /></figure>

* Whatever the size of the ring and the value of rate $\lambda$, the associated Markov process has no Siegmund dual (for those familiar with duality in Markov processes, the problem is the monotonicity condition that doesn't hold here).

<figure><img src="image_281.png" /></figure>

<figure><img src="image_282.png" /></figure>

<figure><img src="image_283.png" /></figure>
<figure><img src="image_284.png" /></figure>

<figure><img src="image_285.png" /></figure>

<figure><img src="image_286.png" /></figure>

<figure><img src="image_287.png" /></figure>

Consider now the general Markov process with 3 states:

<figure><img src="image_288.png" /></figure>

Siegmund dual of X:

<figure><img src="image_289.png" /></figure>

Here, the Siegmund dual exists iff $Q_{1,0} > Q_{2,0}$ and $Q_{1,2} > Q_{0,2}$.

Observe that the existence conditions depend on how the states are labelled by integers.

<figure><img src="image_290.png" /></figure>

<figure><img src="image_291.png" /></figure>

<figure><img src="image_292.png" /></figure>
<figure><img src="image_293.png" /></figure>

<figure><img src="image_294.png" /></figure>

<figure><img src="image_295.png" /></figure>

<figure><img src="image_296.png" /></figure>

An example where duality helps

Consider here the *M/M/1/H* queue plus "catastrophes" (or failures) as shown in the following Markovian graph:

<figure><img src="image_297.png" /></figure>

<figure><img src="image_298.png" /></figure>

<figure><img src="image_299.png" /></figure>
<figure><img src="image_300.png" /></figure>

<figure><img src="image_301.png" /></figure>

<figure><img src="image_302.png" /></figure>

<figure><img src="image_303.png" /></figure>

* Take $H = 4$, to shorten the slides. Denote $\Lambda = \lambda + \mu + \gamma$. We have

$$A = \begin{pmatrix} -\lambda & \lambda & 0 & 0 & 0 \\ \mu + \gamma & -\Lambda & \lambda & 0 & 0 \\ \gamma & \mu & -\Lambda & \lambda & 0 \\ \gamma & 0 & \mu & -\Lambda & \lambda \\ \gamma & 0 & 0 & \mu & -(\mu + \gamma) \end{pmatrix}$$

* If we move to discrete time using Uniformization, the computation of $e^{At}$ translates into that of evaluating $U^k$, where using the notation $p = \lambda/\Lambda$, $q = \mu/\Lambda$, $r = \gamma/\Lambda$, matrix $U = I - A/\Lambda$ is

$$U = \begin{pmatrix} q+r & p & 0 & 0 & 0 \\ q+r & 0 & p & 0 & 0 \\ r & q & 0 & p & 0 \\ r & 0 & q & 0 & p \\ r & 0 & 0 & q & p \end{pmatrix}$$

The powers of $U$ are hard to obtain in closed-form here.

<figure><img src="image_304.png" /></figure>

<figure><img src="image_305.png" /></figure>

<figure><img src="image_306.png" /></figure>
<figure><img src="image_307.png" /></figure>

<figure><img src="image_308.png" /></figure>

<figure><img src="image_309.png" /></figure>

<figure><img src="image_310.png" /></figure>

* If we use the exponential-dual (plus Uniformization), we must compute the powers of

$$P = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 \\ p & 0 & q & 0 & 0 & r \\ 0 & p & 0 & q & 0 & r \\ 0 & 0 & p & 0 & q & r \\ 0 & 0 & 0 & p & q+r & r \\ 0 & 0 & 0 & 0 & 0 & 1 \end{pmatrix}$$

Due to those '1' at the corners, the use of lattice path combinatorics is much easier here than with matrix *U* of previous slide. This is an example of situation where we can develop symbolically the computations until the end.

* The infinite case can also be solved in the same way.

<figure><img src="image_311.png" /></figure>

<figure><img src="image_312.png" /></figure>

<figure><img src="image_313.png" /></figure>
<figure><img src="image_314.png" /></figure>

<figure><img src="image_315.png" /></figure>

<figure><img src="image_316.png" /></figure>

<figure><img src="image_317.png" /></figure>

The formal solution of the ODEs (Chapman-Kolmogorov equations) is given below, using the notation $\rho = \lambda/\mu$, for the case of the queue starting empty at time 0 (the general case is similar while more complex):

$$p_j(t) = \pi_j - \frac{2\mu\rho^{j/2}}{H+1} \sum_{1 \le h \le H} \left\{ \frac{e^{-(\lambda+\mu+\gamma-2\sqrt{\lambda\mu}\cos(\frac{h\pi}{H+1}))t}}{\lambda+\mu+\gamma-2\sqrt{\lambda\mu}\cos(\frac{h\pi}{H+1})} \times \sqrt{\rho}\sin\left(\frac{h\pi}{H+1}\right) \left[ \sin\left(\frac{jh\pi}{H+1}\right) - \sqrt{\rho}\sin\left(\frac{(j+1)h\pi}{H+1}\right) \right] \right\}.$$

In the formula, $\pi_j$ denotes $p_j(\infty)$ (steady-state), easy to evaluate symbolically in this model.

<figure><img src="image_318.png" /></figure>