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

HAL
open science

# Connecting irreducible and absorbing Markov chains

Gerardo Rubino

► To cite this version:

Gerardo Rubino. Connecting irreducible and absorbing Markov chains. JMM 2023 - Joint Mathematics Meetings, AMS, Jan 2023, Boston (MA), United States. hal-04381154

HAL Id: hal-04381154

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

Submitted on 9 Jan 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>

Connecting irreducible
and absorbing Markov chains

G. Rubino, Inria, Rennes, France

JMM 2023

Boston, January 7, 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 Computing in an absorbing chain

2 Connecting absorbing and irreducible chains

3 Cuts in absorbing chains

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

# Introduction

* In the quantitative analysis of systems, two broad territories appear: performance analysis ("how much" the system does, *assuming it is perfect*) and dependability studies (how it behaves face to failures and in some cases repairs, *ignoring its work, its performance*).

* In performance, most analysis are done with irreducible models, stable and in equilibrium. In dependability, studies are done both with reducible models (typically when there is no repair facility, or when repairs are *partial*) and irreducible ones, both in their transient phase, and, assuming stability, in equilibrium.

* We are going to discuss connections between irreducible and absorbing models, in equilibrium for the former, and looking at what happens during the models' "life-times" (time before absorption) for the latter.

* This will be done around the main tool for these tasks, Markovian models, and in continuous time because this is the usual setting in applications (but everything holds also in the discrete time case).

* To simplify the presentation, we will work with the finite case mainly.

* The corresponding paper will be uploaded soon to arXiv.

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

Talk's content

1 Computing in an absorbing chain

2 Connecting absorbing and irreducible chains

3 Cuts in absorbing chains

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

Initial model X

* Let X be a Continuous Time Markov Chain (CTMC) with finite state space $\mathcal{X}$, transition rates $Q_{x,y}$, a single state $a \in \mathcal{X}$ absorbing and the rest of states transient. We denote by $\mathcal{T}$ the set of transient states. We denote $\alpha_x = \mathbb{P}(X(0) = x)$, with $\alpha_a = 0$.

* We denote by $P_{x,y}$ the corresponding probability transition rates from $x$ to $y$, that is, $P_{x,y} = Q_{x,y}/d_x$ for any state $x \in \mathcal{T}$ and all $y$, where $d_x = \text{departure rate from } x, = \sum_y Q_{x,y}$. For state $a$ we set $P_{a,a} = 1$ ($P_{a,x} = 0$ for all $x \neq a$).

* The absorption time $T$ of $X$ is

$$T = \inf\{t \ge 0: X(t) = a\} = \int_0^\infty 1(X(t) \ne a) \, dt.$$

In words, $T$ is the time taken by $X$ to get absorbed.

* We will be mainly interested in its mean, $\mathbb{E}(T)$, and the conditional means $\mathbb{E}_i(T) = \mathbb{E}(T | X(0) = i) =: \tau_i$. Since $\tau_a = 0$, we have $\mathbb{E}(T) = \sum_{i \in \mathcal{T}} \alpha_i \tau_i$.

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

Total sojourn time in the transient states

Let $S_x$ be the total time spent by $X$ in state $x$ until absorption, that is,

$$S_x = \int_0^T 1(X(t) = x) \, dt.$$

Observe that $S_a = 0$ and that

$$T = \sum_{x \in T} S_x.$$

We are interested in the mean

$$\sigma_x = \mathbb{E}(S_x)$$

and in the conditional mean

$$\sigma_{i,x} = \mathbb{E}_i(S_x).$$

Note that $\sigma_a = 0$, $\sigma_{i,a} = 0$ for all state $i$, and $\sigma_{a,x} = 0$ for all state $x$.

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

We have the following immediate obvious relations coming from previous definitions:

$$ \mathbb{E}(T) = \sum_{i \in T} \alpha_i \tau_i $$

and

$$ \mathbb{E}(T) = \sum_{x \in T} \sigma_x . $$

We also have

$$ \sum_{i \in T} \alpha_i \sigma_{i,x} = \sigma_x $$

and

$$ \sum_{x \in T} \sigma_{i,x} = \tau_i . $$

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

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

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

Computing the conditional $\tau_i$s

To obtain the $\tau_x$s, we must solve the following linear system: for all $i \in \mathcal{T}$,

$$ \tau_i = h_i + \sum_{j \in \mathcal{T}} P_{i,j} \tau_j $$

where $h_i$ is the mean holding time in state $i$, that is, $h_i = 1/d_i$, with $d_i$ the departure rate from $i$.

In matrix terms, define vector $\tau$ as the row vector of the $\tau_i$s, matrix $H = \text{diag}(h_i)$, vector $\mathbf{1} = (1, 1, ..., 1)$, and $P = (P_{x,y})$, everything indexing on the subset of transient states $\mathcal{T}$.

We can then write

$$ \tau^{\text{T}} = (\dots, \tau_i, \dots)^{\text{T}} = H \mathbf{1}^{\text{T}} + P \tau^{\text{T}}. $$

From this,

$$ \tau^{\text{T}} = (I - P)^{-1} H \mathbf{1}^{\text{T}}. $$

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

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

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

# Computing the conditional $\sigma_{i,x}$s

To compute the $\sigma_{i,x}$s, we have to solve the following linear system:

$$ \text{if } i \neq x \text{ and } i, x \neq a, \quad \sigma_{i,x} = \sum_{j: j \neq a} P_{i,j} \sigma_{j,x} $$

$$ \text{for all } x \neq a, \quad \sigma_{x,x} = h_x + \sum_{j: j \neq a} P_{x,j} \sigma_{j,x} $$

In matrix terms, if $\sigma = (\sigma_{i,x})$,

$$ \sigma = H + P\sigma, $$

which leads to

$$ \sigma = (I - P)^{-1} H. $$

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

# Comments

* Once $\sigma$ known, we have

$$ ( \dots, \sigma_x, \dots ) = \alpha \sigma \, , $$

where the row vector $\alpha$ is also indexed on $\mathcal{T}$.

* Then,

$$ \tau^{\mathrm{T}} = \sigma \mathbf{1}^{\mathrm{T}} $$

and

$$ \mathbb{E}(\mathcal{T}) = \alpha \tau^{\mathrm{T}} = \alpha \sigma \mathbf{1}^{\mathrm{T}} = \alpha (I - P)^{-1} H \mathbf{1}^{\mathrm{T}} . $$

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

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

Talk's content

1 Computing in an absorbing chain

2 Connecting absorbing and irreducible chains

3 Cuts in absorbing chains

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

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

Absorbing → irreducible

* From X we build Y by adding transitions from a to any $x \in T$ with rate $r\alpha_x$ ($r > 0$ is arbitrary).

* Fact 1: Y has a single recurrent class but it may have transient states. Its stationary distribution is denoted by $\pi$.

* Fact 2: $\pi_a > 0$.

* We also denote by $Y^{(i)}$ the same type of construction but simply adding a single transition from a to $i \in T$, with rate r.

* Facts 1 and 2 hold obviously for $Y^{(i)}$, whose stationary distribution is denoted by $\pi^{(i)}$; in particular, $\pi_a^{(i)} > 0$.

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

# Pseudo-aggregation

* Let $U$ be an irreducible CTMC with state space $U$ and transition rates $Q$, ergodic, and $P = (B_0, B_1, B_2, ...)$ a partition of $U$; the stationary distribution of $U$ is $\pi$.

* Define $V$, the pseudo-aggregation of $U$ with respect to $P$, as the CTMC defined on $P$ with rates $R$ given by

$$R_{B,B'} = \frac{\sum_{x \in B} \pi_x Q_{x,B'}}{\pi_B},$$

plus, if needed, $P(V(0) = B) = \pi_B$.

* Then, $V$ is ergodic, with stationary distribution $\pi'$, where for any $B \in P$, $\pi'_B = \sum_{x \in B} \pi_x = \pi_B$.

* See that $V$ is Markov by construction. The aggregation of $U$ w.r.t. $P$ is, in general, not Markovian (in general, it is “nothing”).

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

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

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

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

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

Some references

Concerning pseudo-aggregation and their context, see

* "*Sojourn times in Finite Markov processes*", G. Rubino and B. Sericola, Journal of Applied Probability, 26, pages 744-756, 1989.

and then

* "*A finite characterization of weak lumpable Markov processes. Part I: the discrete time case*", G. Rubino and B. Sericola, Stochastic Processes and their Applications, 38, pages 195-204, 1991.

* "*A finite characterization of weak lumpable Markov processes. Part II: the continuous time case*", G. Rubino and B. Sericola, Stochastic Processes and their Applications, 45, pages 115-125, 1993.

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

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

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

Relations between X and Y, Y<sup>(i)</sup>

* Consider the pseudo-aggregation of Y into two macro-states a and b, where the latter is the result of collapsing all the transient states.

* The mean (the holding) time of this new 2-state process in state b is $E(T)$ and we have the following balance relation

$$ \pi_b \frac{1}{E(T)} = \pi_a r, $$

where $\pi_b = \sum_{i: i \neq a} \pi_i$.

* Replacing $\pi_b$ by $1 - \pi_a$, we get

$$ \mathbb{E}(T) = \frac{1 - \pi_a}{r \pi_a}, $$

or equivalently,

$$ \pi_a = \frac{1}{1 + r \mathbb{E}(T)}. $$

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

• If we use $Y^{(i)}$ instead of $Y$, we obtain

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

or equivalently,

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

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

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

* If we fix a state *i* and use the regenerative properties of $Y^{(i)}$ w.r.t. *a*, we obtain

$$ \frac{\sigma_{i,x}}{1+r} = \pi_x^{(i)}. $$

Similarly, reasoning similarly in $Y$ now, we have

$$ \frac{\sigma_x}{\frac{1}{r} + \mathbb{E}(T)} = \pi_x. $$

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

Conclusion

* Given an absorbing Markov chain X as before, we can compute the quantities $E(T)$ and $\sigma_x$ for all state x by working with the irreducible model Y.

* We can also go the other way, computing in an absorbing model by working with an irreducible one.

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

Applications

(i) New fast numerical techniques to compute the stationary distribution of irreducible chains.

(ii) New tools to compute bounds of quantities calculated using the stationary distribution of irreducible chains (for instance, the stationary probability of being in a subset of states).

(iii) New results for absorbing models similar to the balance relations through cuts in irreducible ones.

In the rest of the talk, we will develop only point (iii).

<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 Computing in an absorbing chain

2 Connecting absorbing and irreducible chains

3 Cuts in absorbing chains

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

# Cuts in irreducible chains

* Typical example: if $U$ is an irreducible and ergodic chain with transition rates $Q$ and stationary distribution $\pi$, and $(A, B)$ a partition of $U$'s state space, then we have the balance equation

$$ \sum_{x \in A} \pi_x Q_{x,B} = \sum_{y \in B} \pi_y Q_{y,A}, $$

which can be read “in equilibrium, the probabilistic flow from $A$ to $B$ equals the probabilistic flow from $B$ to $A$”.

* We explore here equivalent relations, in some sense, defined on absorbing chains.

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

# Preliminary relations

* We are in the same setting as at the beginning, with chains X (absorbing), Y and $Y^{(i)}$ (both irreducible).

* We fix $i \in T$ and, in $Y^{(i)}$, we write the equilibrium relation for every state $x \neq a$:

$$ \pi_x^{(i)} d_x = \sum_{y: y \neq a} \pi_y^{(i)} Q_{y,x} + \pi_a^{(i)} r1(x = i). $$

* We know that $\pi_z^{(i)} = r\sigma_{i,z}\pi_a^{(i)}$, for $z \neq a$. Putting this in previous relation, we get, for every state $x \neq a$,

$$ \sigma_{i,x} d_x = \sum_{y: y \neq a} \sigma_{i,y} Q_{y,x} + 1(x = i). $$

* Multiplying by $\alpha_i$ and summing on $i \in T$, we obtain

$$ \text{for all } x \neq a, \quad \sigma_x d_x = \sum_{y: y \neq a} \sigma_y Q_{y,x} + \alpha_x . $$

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

As a side effect, with a little algebra, we have

$$ \sum_{x: x \neq a} \sigma_{i,x} Q_{x,a} = 1 $$

and multiplying by $\alpha_i$ and summing on $i \in T$,

$$ \sum_{y: y \neq a} \sigma_y Q_{y,a} = 1. $$

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

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

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

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

First result

* Let us decompose the transient states of $X$ into two non-empty classes $B$ and $C$. Choose some state $i \in B$ and consider, in process $Y^{(i)}$, the equilibrium relation w.r.t. the partition $\{B, C \cup \{a\}\}$. Use then the bridges between $X$, $Y$, $Y^{(i)}$, and obtain

$$ \sum_{j \in B} \sigma_{i,j} (Q_{j,C} + Q_{j,a}) = \sum_{k \in C} \sigma_{i,k} Q_{k,B} + 1 . $$

* Different formulation: let $N_{B,C}$ be the r.v. "\# of transitions from $B$ to $C$ in process $X$ before absorption", and analogously for $N_{C,B}$, $N_{B,a}$ and $N_{C,a}$. Observe that $N_{B,a} + N_{C,a} = 1$, so, $N_{B,a}$ and $N_{C,a}$ are two (dependent) Binary random variables.

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

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

* Choosing $i \in B$, we have $\sum_{j \in B} \sigma_{i,j} Q_{j,C} = \mathbb{E}_i(N_{B,C})$, $\sum_{k \in C} \sigma_{i,k} Q_{k,B} = \mathbb{E}_i(N_{C,B})$ and $\sum_{j \in B} \sigma_{i,j} Q_{j,a} = \mathbb{E}_i(N_{B,a})$.

* We also have $\mathbb{E}_i(N_{B,a}) = \mathbb{P}_i(X \text{ gets absorbed from } B)$.

* From these, we obtain

$$ \mathbb{E}_i(N_{B,C}) = \mathbb{E}_i(N_{C,B}) + \mathbb{P}_i(X \text{ gets absorbed from } C) \quad (i \in B). $$

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

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

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

Second result

• Similarly as before, and deconditionning,

$$ \mathbb{E}(N_{B,C}) + \Pr(X \text{ gets absorbed from } B) = \mathbb{E}(N_{C,B}) + \alpha(B) . $$

• By symmetry, we also have

$$ \mathbb{E}(N_{B,C}) + \alpha(C) = \mathbb{E}(N_{C,B}) + \Pr(X \text{ gets absorbed from } C). $$

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

Comment

* In the paper, all the details and also examples illustrating the different sets of results.

* There will also be some material about the other applications of the connections between absorbing and irreducible chains.

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

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

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