<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. AMS Spring Eastern Sectional Meeting 2023, AMS, Apr 2023, Virtual conference, United States. hal-04381185

HAL Id: hal-04381185

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

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>

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

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

Connecting irreducible
and absorbing Markov chains

G. Rubino, Inria, Rennes, France

AMS Spring Eastern Sectional Meeting

Virtual, April 1st, 2023

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

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

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

Talk's content

1. CTMC X: a single absorbing state

2. Pseudo-aggregation

3. Connecting X with an irreducible $Y^{(i)}$

4. Using cuts

5. X: several absorbing states

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

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

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

# Introduction

* This is a follow-up of the talk given at the JMM'23 meeting last January.

* It is about connecting irreducible and absorbing Markov chains. One possible connection is using Sigmund's duality and variants (or extensions) of the same idea.

* Here, we will describe simple ways of building direct relationships between these two classes of stochastic processes, and between some of the available tools for working with them. They concern only the steady-state behavior in the irreducible case, not transients.

* To simplify the presentation, we will work with the finite case only. We will illustrate the talk first with continuous time models, later with discrete time ones; the results are basically the same.

* The corresponding paper will be uploaded soon to arXiv. I will send a short email to the participants to this session as well as to the participants at previous one during JMM'23.

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

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

Talk's content

1. CTMC X: a single absorbing state

2. Pseudo-aggregation

3. Connecting X with an irreducible $Y^{(i)}$

4. Using cuts

5. X: several absorbing states

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

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$).

* In the irreducible case, we will focus on the steady-state distribution of the process. In discrete time, the main object of interest is the absorption time $\mathcal{T}$:

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

In words, $\mathcal{T}$ is the time taken by $X$ to get absorbed.

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

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

* As for the irreducible case, we will not look at the distribution of $T$, we will focus on its mean, $\mathbb{E}(T) =: \tau$, and the conditional $\mathbb{E}_i(T) = \mathbb{E}(T | X(0) = i) =: \tau_i$. Since $\tau_a = 0$, we have $\mathbb{E}(T) = \sum_{i \in T} \alpha_i \tau_i$.

* To compute the $\tau_i$s (and $\tau$): we have a **simple linear system** to solve.

* If $S_X$: the total time spent by $X$ in state $x$, $= \int_0^T 1(X(t) = x) dt$, $\mathbb{E}(S_X) =: \sigma_X$ or $\mathbb{E}_i(S_X) =: \sigma_{i,x}$ are also **simple linear problems**.

* Many other targets are often of interest in applications:

* mean total time spent by $X$ in a subset of transient states;

* $\mathbb{E}(T^2)$ and $\mathbb{E}(S_X^2)$, for example;

* when there are more than one absorbing state, say $a_1, a_2, \dots$, $P_i(X(\infty) = a_1), \mathbb{E}(T | X(\infty) = a_1)$ and $\mathbb{E}(T^2 | X(\infty) = a_1)$, etc.

* All of them are **easy to solve**, **mathematically speaking** (numerically, it depends on model's size, stiffness of the involved matrices, etc.).

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

<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. CTMC X: a single absorbing state

2. Pseudo-aggregation

3. Connecting X with an irreducible $Y^{(i)}$

4. Using cuts

5. X: several absorbing states

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

Key tool: 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, $\mathbb{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_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>

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

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

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

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

Talk's content

1. CTMC X: a single absorbing state

2. Pseudo-aggregation

3. Connecting X with an irreducible Y⁽¹⁾

4. Using cuts

5. X: several absorbing states

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

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, we have Fact 3: $\pi_a^{(i)} > 0$.

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

Relations between X and Y, Y⁽¹⁾

* 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

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

or equivalently,

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

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

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

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

$$ \tau_i = \frac{1 - \pi_a^{(i)}}{r \pi_a^{(i)}}, $$

or equivalently,

$$ \pi_a^{(i)} = \frac{1}{1 + r \tau_i}. $$

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

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

Similarly, reasoning in $Y$ now, we have

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

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

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

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

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

# Applications

(i) Analyzing an absorbing chain X using Y or the $Y^{(i)}$s, and viceversa.

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

(iii) 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).

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

In the rest of the talk, we will only illustrate some aspects of (iv) and then, of (i).

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

Talk's content

1. CTMC X: a single absorbing state

2. Pseudo-aggregation

3. Connecting X with an irreducible $Y^{(i)}$

4. Using cuts

5. X: several absorbing states

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

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

# Cuts in irreducible chains

* The point here is the equilibrium in the "probability flow" through the border of a cut.

* 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 will explore here equivalent relations, in some sense, defined on absorbing chains.

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

First, two examples in the irreducible case

* In the stable $M/M/1$ (or in the $M/M/1/H$, out of the borders), the equilibrium equation at state $n \ge 1$ is

$$ (\lambda + \mu)\pi_n = \lambda\pi_{n-1} + \mu\pi_{n+1}. $$

Using the cut $\{0, 1, \dots, n\}, \{n+1, n+2, \dots\}$ (I call it a "vertical" cut), we directly obtain

$$ \lambda\pi_n = \mu\pi_{n+1}. $$

* Now, consider a stable $M/H_K/1$ queue with arrival rate $\lambda$ and service time c.d.f. $F(x) = \sum_{k=1}^{K} \alpha_k (1 - e^{-\mu_k})$ (we say that this is a Hyperexponential distribution with K phases, implicitly assuming that if $k \ne j$, $\mu_k \ne \mu_j$).

If we define $N(t) = \#$ of customers at time $t$, and $Ph(t)$ = phase of the server at time $t$, the vector $(N(t), Ph(t))$ is Markov.

Let us denote $G(z) = \sum_{n \ge 0} P(N(\infty) = n)z^n$.

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

* Using the equilibrium equations, or the PK-formula in terms of transforms, we obtain the expression

$$G(z) = \frac{(1 - \rho)(1 - z) \sum_{k=1}^{K} \alpha_k (\varphi_k - 1) E_k(z)}{\sum_{k=1}^{K} \alpha_k (\varphi_k - 1) E_k(z) - zE_0(z)},$$

where

$$\varphi_k = \frac{\lambda + \mu_k}{\mu_k}, \quad E_0(z) = \Pi_{k=1}^{K}(\varphi_k - z), \quad E_k(z) = \Pi_{j=1, j \neq k}^{K}(\varphi_j - z)$$

* Observe that in previous expression, there must be a pole at $z = 1$, which means that we must find the result of dividing the denominator by $1-z$.

* Using the standard “vertical” cut as for the $M/M/1$, we directly obtain

$$G(z) = \frac{(1 - \rho) \sum_{k=1}^{K} \alpha_k (\varphi_k - 1) E_k(z)}{\sum_{k=1}^{K} \alpha_k E_k(z) - E_0(z)}.$$

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

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

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

Central idea in this section

* Start with some X having an absorbing state.

* Build the associated irreducible chain Y, use cuts in Y and equilibrium through them, and see if they correspond to new relations in X.

* The answer is positive, and we find in that way new relations concerning specific time expectations in X.

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

# Preliminary relations

* We are in the same setting as at the beginning, with chains X (absorbing), Y and $Y^{(i)}$ (both irreducible, or having a recurrent class that always includes the state absorbing in X).

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

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

* 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 \mathcal{T}$,

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

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

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

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

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} = $ 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_239.png" /></figure>

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

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

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

* We also have $E_i(N_{B,a}) = P_i(X \text{ gets absorbed from } B)$.

* From these, we obtain

$$E_i(N_{B,C}) = E_i(N_{C,B}) + P_i(X \text{ gets absorbed from } C) \quad (i \in B).$$

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

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

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

Second result

* Similarly as before, and deconditioning,

$$ \mathbb{E}(N_{B,C}) + \mathbb{P}(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}) + \mathbb{P}(X \text{ gets absorbed from } C). $$

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

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

Talk's content

1. CTMC X: a single absorbing state

2. Pseudo-aggregation

3. Connecting X with an irreducible $Y^{(i)}$

4. Using cuts

5. X: several absorbing states

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

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

Example

* We will limit the presentation to a discussion around an example.

* To change, let us consider now the gambler ruin problem in discrete time, in the following homogeneous case:

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

* Goal: to compute the probabilities of absorption

$$ \delta_j = \mathbb{P}_j(X(\infty) = 0), $$

for $j = 1, 2, \dots, n-1$.

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

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

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

Direct computation of the $\delta_{j,s}$

Linear system to solve:

$$ \bullet \delta_1 = q + r\delta_1 + p\delta_2 $$

$$ \bullet \text{ for } j = 2, 3, \dots, n-2: \quad \delta_j = q\delta_{j-1} + r\delta_j + p\delta_{j+1} $$

$$ \bullet \delta_{n-1} = q\delta_{n-2} + r\delta_{n-1} $$

Replacing $r$ by $1-p-q$, dividing by $q$ and using $\psi = p/q$, we obtain

$$ \bullet (1+\psi)\delta_1 = 1 + \psi\delta_2 $$

$$ \bullet \text{ for } j = 2, 3, \dots, n-2: \quad (1+\psi)\delta_j = \delta_{j-1} + \psi\delta_{j+1} $$

$$ \bullet (1+\psi)\delta_{n-1} = \delta_{n-2} $$

We observe that this is basically an order 2 linear recurrence. Once solved, we obtain $j = 1, 2, \dots, n-1$,

$$ \delta_j = \frac{\psi^{n-j} - 1}{\psi^n - 1}, \quad \text{if } \psi \neq 1; $$

if $\psi = 1$ (if $p = q$), then $\delta_j = 1 - j/n$.

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

Using the construction introduced before

* Extending the previous results to the case of any number of absorbing states, choosing one of the transient states, say $i$, we build $Y^{(i)}$ depicted here:

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

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

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

Linear system to solve for $\pi = \pi^{(i)}$ here, using “vertical” cuts:

$$ \bullet \ u \pi_0 = q \pi_1 $$

$$ \bullet \ \text{for } j = 1, 2, \dots, i-1: \quad p \pi_j + u \pi_0 = q \pi_{j+1} $$

$$ \bullet \ \text{for } k = i, i+1, \dots, n-2: \quad p \pi_k = q \pi_{k+1} + v \pi_n $$

$$ \bullet \ p \pi_{n-1} = v \pi_n $$

Now, we directly have a basically order 1 recurrence problem to solve.

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

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

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

* Following a similar approach as previously discussed in previous 2 sections, we obtain that

$$ \delta_i = \frac{u \pi_0}{u \pi_0 + v \pi_n} $$

* This can be further simplified, but no room here to go into the details.

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

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

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

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

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

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

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

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

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