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

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

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

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

Two algebraic matrix transformations
with applications to Markov chain analysis

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

JMM'24

January 5, 2024

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

<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>

# Talk's content

1. Introduction

2. Duality concepts

* Power-duals

* Exponential-duals

* Complements

3. An illustration of power-duals applications

4. Conclusions

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

<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>

# Talk's content

## 1 Introduction

## 2 Duality concepts

* Power-duals

* Exponential-duals

* Complements

## 3 An illustration of power-duals applications

## 4 Conclusions

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

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

<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>

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

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

# Starting with Siegmund duality

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

* If we write

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

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

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

or for an i.g. A

$$A \rightarrow \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_34.png" /></figure>

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

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

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

<figure><img src="image_39.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 to face here is the conditions under which such a dual process exists.

* When looking for closed-forms, the original model must have a small number of parameters, otherwise the combinatorics of the problem can make it too hard.

<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>

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

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

## 2 ideas

* First idea in this happens: 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 us 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 appears if we look at **matrix exponentials**.

<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>

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

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

# Talk's content

1. Introduction

2. Duality concepts

* Power-duals

* Exponential-duals

* Complements

3. An illustration of power-duals applications

4. Conclusions

<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>

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

# The power-dual of a matrix

* Let $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 $M$ is a new matrix $\tilde{M}$, also denoted here $\mathcal{PD}(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} $$

and for the last row ($i=n$), we have $(00 \dots 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_61.png" /></figure>
<figure><img src="image_62.png" /></figure>

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

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

<figure><img src="image_65.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_66.png" /></figure>
<figure><img src="image_67.png" /></figure>

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

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

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

# Some properties

* 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: 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}.$$

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

$$\tilde{A}B = \tilde{B}\tilde{A}.$$

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

$$[\tilde{M}^k = \tilde{M}^k], \text{ written also } [\mathcal{P}D(M^k) = \mathcal{P}D(M)^k],$$

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

<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>

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

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

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

# A possible path to compute $M^k$

Instead of

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

we can try

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

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

<figure><img src="image_81.png" /></figure>
<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>

# The exponential-dual of a matrix

* Let $M$ be a square matrix (of reals, 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)$ in these slides, having 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}$ is $(0 \ 0 \ \dots \ 0)$.

* 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_86.png" /></figure>

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

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

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

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

<figure><img src="image_92.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_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>

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

# Some properties

* 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

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

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

$$\hat{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_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>

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

* Let A and B be two square matrices with the same dimension and α 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_105.png" /></figure>

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

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

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

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

# Main result

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

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

In words, the **power-dual** of the exponential of $Mt$ is the exponential of the exponential-dual of $M$ times $t$.

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

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

<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>

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

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

Instead of

$$ M \underset{\uparrow}{\longrightarrow} e^{Mt}, $$
any algorithm

we can try

$$ M \underset{\substack{\uparrow \\ (linear)}}{\longrightarrow} \hat{M} \underset{\substack{\uparrow \\ \text{any algorithm}}}{\longrightarrow} e^{\hat{Mt}} = \widetilde{e^{Mt}} \underset{\substack{\uparrow \\ \text{Inversion Lemma of power-dual}}} {\longrightarrow} e^{Mt} $$

<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>

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

## Other properties of both transformations

* 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.

* 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 (CTMC) $X$ whose Siegmund dual exists, its generator is $\hat{A}$.

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

The corresponding paper for the power-dual and the relations between both transformations is in preparation.

<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>

# Talk's content

1. Introduction

2. Duality concepts

* Power-duals

* Exponential-duals

* Complements

3. An illustration of power-duals applications

4. Conclusions

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

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

<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>
<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>

Useful notation

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_140.png" /></figure>

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

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

<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>

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

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

* 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 = \begin{pmatrix} nw(U) \\ \vdots \\ \dots \end{pmatrix}, $$

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

<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>

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

<figure><img src="image_156.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 they are **similar matrices**.

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

* We can see here, in matrix form, the inverse transformation:

$$M = L^T nw(\tilde{M}^T) R^T \text{ (we used } (nw(M))^T = nw(M^T)).$$

<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>

<figure><img src="image_162.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 & & & & \\ & \ddots & & & \\ & & \tilde{P}_{1,0} & & \\ & & \vdots & \ddots & \\ & & & \tilde{P}_{n-1,0} & \\ & & & & \ddots \\ & & & & & \tilde{P}_{n-1,n} \\ & & & & & \vdots \\ & & & & & & \ddots \\ & & & & & & & \tilde{P}_{n,n} \end{pmatrix}. $$

* We want to compute the absorption probabilities $x_i = P_i(\tilde{X}(\infty) = 0)$, for all state $i$.

* Observe that since all states $\neq 0$, $n$ are transient, then for all state $i$, $P_i(\tilde{X}(\infty) = n) = 1 - x_i$.

<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>

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

* Observation: computing the $x_i$s is a simple linear problem:

* We have that $x_0 = 1$, $x_n = 0$, and for all $i \neq 0, n$,

$$x_i = \tilde{P}_{i,0} + \sum_{j \neq 0, n} \tilde{P}_{i,j}x_j.$$

* The fact that all states $\neq 0, n$ are transient makes that this system has a unique solution.

* Denote $y = (x_1 \dots x_{n-1})$ and $p = (\tilde{P}_{1,0} \dots \tilde{P}_{n-1,0})$.

* In matrix form, the system to solve is $y^T = p^T + \tilde{P}y^T$.

* The solution is $y^T = (I - \tilde{P})^{-1}p^T$.

<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>

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

Absorption probabilities using the power-dual

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

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

* Call $P$ the **unique** matrix whose power-dual is $\tilde{P}$. Property: $P$ is **somewhat stochastic** (that is, $P1^T = 1^T$, but $P$ is not necessarily stochastic).

<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>

<figure><img src="image_186.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 {$zP = z$ and $z1^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 P^\infty = \nu 1^T \pi = \pi$ (associativity), so, $\nu = \pi$.

<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>

* So, once $\pi$ known (by solving the linear system $\pi P = \pi$), we obtain the $x_i$s inverting the relations we have 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 $= \pi_i + \pi_{i+1} + \cdots + \pi_{n-1},$

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

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

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

<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>

Resuming

* To obtain vector $\pi$ we solve the linear system $\pi P = \pi$, as we do when $P$ is, for instance, the t.p.m. of an irreducible chain, 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

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

<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>

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

# Talk's content

1. Introduction

2. Duality concepts

* Power-duals

* Exponential-duals

* Complements

3. An illustration of power-duals applications

4. Conclusions

<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>

<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>

* The power-dual and the exponential-dual extend somehow Sigmund duality 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 matrices.

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

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

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

<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>

Thanks for your time.

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

<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>

# 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:

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

* Whatever the size of the ring and the value of $\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_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>

Consider now the general Markov process with 3 states:

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

Siegmund dual of X:

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

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

<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>

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

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

<figure><img src="image_249.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_250.png" /></figure>

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

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

<figure><img src="image_253.png" /></figure>
<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>

* 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_258.png" /></figure>

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

<figure><img src="image_260.png" /></figure>
<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>

* 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_265.png" /></figure>

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

<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>

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.

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