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

# The power-dual and the exponential-dual of an arbitrary matrix

## Two related algebraic concepts of duality

A. Krinik, CalPoly, Pomona, US, and **G. Rubino**, Inria, Rennes, France

Stochastic Models VII

Bedlewo, Poland, May-June 2023

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

# Talk's content

1. Introduction

2. Duality concepts

* Power-duals

* Exponential-duals

3. An application (power-duals here)

4. Conclusions

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

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

# Talk's content

## 1 Introduction

## 2 Duality concepts

* Power-duals

* Exponential-duals

## 3 An application (power-duals here)

## 4 Conclusions

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

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

# 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 \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_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 specific supplementary properties.

<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

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

# Talk's content

## 1 Introduction

## 2 Duality concepts

* Power-duals

* Exponential-duals

## 3 An application (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>

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

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

<figure><img src="image_62.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 $\mathcal{P}\mathcal{D}(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 $(0 \dots 0 \ 1)$.

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

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

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

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

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

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

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

$$[\tilde{M}^k = \tilde{M}^k]_i, \text{ written also } [PD(M^k) = PD(M)]_i$$

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

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

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

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

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

# A possible path to compute $M^k$

Instead of

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

we can try

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

# 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)$, 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 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_89.png" /></figure>
<figure><img src="image_90.png" /></figure>

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

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

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

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

$$\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_96.png" /></figure>

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

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

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

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

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

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

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

Instead of

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

we can try

$$ M \underset{\uparrow}{\longrightarrow} \hat{M} \underset{\uparrow}{\longrightarrow} e^{\hat{Mt}} = \widetilde{e^{Mt}} \underset{\uparrow}{\longrightarrow} e^{Mt} $$
(linear) any algorithm

Inversion Lemma
of **power-dual**
(linear)

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

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

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.

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

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

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

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

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

# Some references

* Most of these 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 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_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>

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

# Talk's content

1. Introduction

2. Duality concepts

* Power-duals

* Exponential-duals

3. An application (power-duals here)

4. Conclusions

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

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

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

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

* 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_{m+1}) = R_m$.

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

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.

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

# 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 & \\ & \tilde{P}_{1,0} & & & & \\ & & \ddots & & & \\ & & & \tilde{P}' & & \\ & & & & \tilde{P}_{1,n} & \\ & & & & & \tilde{P}_{n-1,n} & \\ & & & & & & 1 \end{pmatrix}. $$

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

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

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

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

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

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

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

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

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

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

<figure><img src="image_188.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 $\bar{P} = L P^T R$, so, $P^T = R \bar{P} L$, which implies that for any integer $\ell \ge 1$,

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

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

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

where $x_i = P_i(\tilde{X}(\infty) = 0)$, for all transient states $i$.

Then, we check that $R \bar{P}^\infty L$ can be written $(1^T\pi)^T$, where for $i = 0, 1, \dots, n-1$, we have $\pi_i = x_i - x_{i+1}$ if we extend the $x_i$s with $x_0 = 1$ and $x_n = 0$.

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

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

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

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

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

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} \quad \pi = x R.$$

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

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

# Talk's content

1. Introduction

2. Duality concepts

* Power-duals

* Exponential-duals

3. An application (power-duals here)

4. Conclusions

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

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

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

Thanks for your time.

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

# 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_234.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_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>

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

Consider now the general Markov process with 3 states:

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

Siegmund dual of $X$:

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

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