# Steady-state Distributions of Somewhat Stochastic Matrices

Alain Krinik, Gerardo Rubino, David Beecher, Heba Ayeda

► To cite this version:

Alain Krinik, Gerardo Rubino, David Beecher, Heba Ayeda. Steady-state Distributions of Somewhat Stochastic Matrices. 2023 - 7th Conference on Stochastic Models, Institute of Mathematics, Polish Academy of Sciences, May 2023, Będlewo, Poland. pp.1-66. [hal-04389349](https://hal-INRA.hal.sciences.polsl.pl/hal-04389349v1)

HAL Id: hal-04389349

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

Submitted on 11 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
Steady-state Distributions of Somewhat Stochastic Matrices

Alan Krinik*, Gerardo Rubino, David Beecher, Heba Ayeda

California State Polytechnic University, Pomona

Dedication: To Pawel Lorek

Stochastic Models VII

Będlewo, Poland

Monday, May 29 - Friday, June 2, 2023
# Sylvester's Eigenvalue Expansion Formula for $M^k$

Assume $M$ is a real $n \times n$ matrix that has $n$ known distinct eigenvalues $\omega_1, \omega_2, \dots, \omega_n$. Then

$$ M^k = A_1\omega_1^k + A_2\omega_2^k + A_3\omega_3^k + \dots + A_n\omega_n^k \quad (1) $$

where $k = 0, 1, 2, \dots$ and $A_1, A_2, \dots, A_n$ are constant $n \times n$ coefficient matrices called spectral projectors (Meyer) or Frobenius covariants.

$$ M^k(i,j) = A_1(i,j)\omega_1^k + A_2(i,j)\omega_2^k + A_3(i,j)\omega_3^k + \dots + A_n(i,j)\omega_n^k $$

where $0 \le i, j \le n-1$ for $s = 1, 2, 3, \dots, n$.

Note: $A_s$ is the matrix outer product, $c^2 \vec{R}_s \vec{L}_s$, where $\vec{R}_s$ and $\vec{L}_s$ are right & left eigenvectors of matrix $M$ and where $\vec{L}_s$ and $\vec{R}_s$ are scaled by a constant $c$ so that their dot product $c^2 \vec{L}_s \cdot \vec{R}_s = 1$.
When the eigenvalues of our matrix *M* are not distinct, then a more general form of Sylvester's Eigenvalue Expansion Formula must be used

$$ M^k = \sum_{i=1}^{n} A_i \sum_{j=0}^{m_i-1} \binom{k}{j} (\omega_i)^{k-j} (M - \omega_i I)^j \quad (2) $$

where *n* is the dimension of *M* and *m_i* is the multiplicity of the *i*th eigenvalue. [Wik19b].
All matrices that appear in the following definitions are assumed to be real square matrices. Definitions 1 & 2 are conventional. Definitions 3 & 4 are comparatively new.

**Definition 1.** A sequence of matrices $A_k$ converge to a matrix $L$ if and only if $[A_k]_{ij} \to L_{ij}$ as $k \to \infty$ for all $i, j$.

**Definition 2.** A Markov chain with one-step transition probability matrix $P$ has a conventional steady-state distribution $\vec{\pi}$ if and only if $\lim_{k \to \infty} P^k = L$, where $L$ is a stochastic matrix and the rows of $L$ are identically $\vec{\pi}$.

**Definition 3.** A matrix $P$ is defined to be somewhat stochastic if the sum of each row of $P$ is 1. Note that the entries of $P$ are permitted to be negative. [ĆJ15]

**Definition 4.** A somewhat stochastic matrix $P$ has a steady state distribution $\vec{\pi}$ if $\lim_{k \to \infty} P^k = L$ where the rows of $L$ are identically $\vec{\pi}$. Note that while the entries of $\vec{\pi}$ are permitted to be negative, the sum of the entries of $\vec{\pi}$ still equal one.
When does $\lim_{k \to \infty} A^k$ exists in Terms of the Eigenvalues of Matrix A?

Let $B = \{\omega \in \mathbb{C} : |\omega| < 1 \text{ or } \omega = 1\}$, which is the open unit ball centered at the origin and the number 1.

**Theorem 1.** Let $A$ be a square matrix with complex entries. Then $\lim_{k \to \infty} A^k$ exists if and only if both of the following conditions hold:

* Every eigenvalue of $A$ is an element of $B$.

* If $1$ is an eigenvalue of $A$, then the dimension of the eigenspace corresponding to $1$ equals the algebraic multiplicity of $1$.

**Remark 1.** Friedberg, Insel, and Spence discuss different proofs of Theorem 1 on page 284 of [FIS18].
**Theorem 2.** Suppose $P$ is a finite-dimensional, one-step transition probability matrix of a Markov chain. The Markov chain has a steady state distribution if and only if every eigenvalue of $P$ is an element of $B$ and the eigenvalue $\omega = 1$ of $P$ has algebraic multiplicity 1.

**Theorem 3.** Suppose $S$ is a finite-dimensional, somewhat stochastic matrix. $S$ has a steady-state distribution if and only if every eigenvalue of $S$ is an element of $B$ and the eigenvalue $\omega = 1$ of $S$ has algebraic multiplicity 1.

**Theorem 4 (Classical).** Suppose $P$ is a finite-dimensional, one-step transition probability matrix of an irreducible Markov chain. The Markov chain has a steady-state distribution $\vec{\pi}$ if and only if the Markov chain has a stationary distribution $\vec{\pi}$ and is aperiodic [HPS72] [KS76].
For simplicity, we assume $P$ is $4 \times 4$ and satisfies Sylvester's eigenvalue expansion with distinct eigenvalues $\omega_1, \omega_2, \omega_3, \omega_4 \in B$ where $\omega_1 = 1$ and $B = \{\omega \in \mathbb{C} : |\omega| < 1 \text{ or } \omega = 1\}$ and $|\omega_2|, |\omega_3|, |\omega_4| < 1$:

$$P^k = A_1\omega_1^k + A_2\omega_2^k + A_3\omega_3^k + A_4\omega_4^k$$

So $\lim_{k \to \infty} P^k = A_1 = c^2 \vec{R}_1 \vec{L}_1$ where $\vec{R}_1 = \vec{I}$ and $\vec{L}_1$ are the right and left eigenvectors of $P$ corresponding to $\omega_1 = 1$, then

$$A_1 = c^2 \vec{R}_1 \vec{L}_1 = c^2 \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} \begin{bmatrix} l_1 & l_2 & l_3 & l_4 \end{bmatrix} = c^2 \begin{bmatrix} l_1 & l_2 & l_3 & l_4 \\ l_1 & l_2 & l_3 & l_4 \\ l_1 & l_2 & l_3 & l_4 \\ l_1 & l_2 & l_3 & l_4 \end{bmatrix}$$
Since $\mathcal{P}$ is stochastic, it follows that $\mathcal{P}^k$ is also stochastic and this implies
that the $\lim_{k \to \infty} \mathcal{P}^k$ is also stochastic. Therefore, $A_1$ is stochastic and the
rows form the steady-state distribution $\pi$ of $\mathcal{P}$ by Definition 2. This
conclusion still holds for non-distinct eigenvalues using equation (2) in
place of equation (1).

**Remark 2.** The proof of the converse of Theorem 3 for somewhat
stochastic matrices is essentially the same proof as the converse of
Theorem 2 for stochastic matrices.
Suppose *P* has a double eigenvalue root 1. Using equation (2)

$$
\begin{align*}
P^k &= \sum_{i=1}^{n} A_i \sum_{j=0}^{m_i-1} \binom{k}{j} (\omega_i)^{k-j} (P - \omega_i I)^j \\
&= A_1 [I + k(P-I)] + A_{1'} [I + k(P-I)] \\
&\quad + \sum_{i=3}^{n} A_i \sum_{j=0}^{m_i-1} \binom{k}{j} (\omega_i)^{k-j} (P - \omega_i I)^j \\
&= (A_1 + A_{1'}) [I + k(P-I)] + \sum_{i=3}^{n} A_i \sum_{j=0}^{m_i-1} \binom{k}{j} (\omega_i)^{k-j} (P - \omega_i I)^j
\end{align*}
$$

SO

$$
\lim_{k \to \infty} P^k = (A_1 + A_{1'})
$$
$$ \lim_{k \to \infty} P^k = (A_1 + A_{1'}) $$

This leads to a contradiction because if $P$ converges in distribution by Definition 2, then its limit is a matrix of rank 1. However, $A_1 + A_{1'}$ has rank 2 by [rh], which is the contradiction. This argument also applies to show that if $P$ has a steady-state distribution by **Definition 2**, then $P$ can only have eigenvalue 1 with algebraic multiplicity 1.

**Remark 3.** Using **Theorem 3**, we will be able to develop an alternative method to find Gambler's Ruin probabilities. This will be explained later as a consequence of algebraic Duality Theory. For now, we illustrate steady-state distributions (**Definition 4**) for somewhat stochastic matrices that are $2 \times 2$.
Example 1: General 2 × 2 Real Matrix

Consider the following transition diagram where P is a stochastic matrix:

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

$$P = \begin{bmatrix} 1-p & p \\ q & 1-q \end{bmatrix}$$

P has eigenvalues $\omega_1 = 1$ and $\omega_2 = 1 - p - q$, and the Sylvester expansion:

$$P^k = A_1\omega_1^k + A_2\omega_2^k$$

$$= \begin{bmatrix} \frac{q}{p+q} & \frac{p}{p+q} \\ \frac{q}{p+q} & \frac{p}{p+q} \end{bmatrix} (1)^k + \begin{bmatrix} \frac{p}{p+q} & -\frac{p}{p+q} \\ -\frac{q}{p+q} & \frac{q}{p+q} \end{bmatrix} (1-p-q)^k$$
For illustration, consider the following somewhat stochastic transition

matrix: $P = \begin{bmatrix} -\frac{1}{2} & \frac{3}{2} \\ \frac{1}{3} & \frac{2}{3} \end{bmatrix}$ where $p = \frac{3}{2}$, $q = \frac{1}{3}$, and $p+q = \frac{3}{2} + \frac{1}{3} = \frac{11}{6}$.

As before, the eigenvalues are $\omega_1 = 1$ and $\omega_2 = 1 - p - q = 1 - \frac{3}{2} - \frac{1}{3} = -\frac{1}{6}$.
By letting $k \to \infty$ in Sylvester's Eigenvalue Expansion, we obtain the
following:

$$ \lim_{k \to \infty} P^k = \lim_{k \to \infty} (A_1 \omega_1^k + A_2 \omega_2^k) = A_1 = \begin{bmatrix} \frac{q}{p+q} & \frac{p}{p+q} \\ \frac{q}{p+q} & \frac{p}{p+q} \end{bmatrix} = \begin{bmatrix} \frac{2}{11} & \frac{9}{11} \\ \frac{2}{11} & \frac{9}{11} \end{bmatrix} = L $$

So by **Definition 4**, $P$ has a steady state distribution $\vec{\pi} = \begin{bmatrix} \frac{2}{11} & \frac{9}{11} \end{bmatrix}$.
When does this behavior happen?
We need $-1 < \omega_2 < 1$, which means $-1 < 1 - p - q < 1$. This implies we are in the following slanted strip:

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

The Steady State Distribution of $P = \begin{bmatrix} 1-p & p \\ q & 1-q \end{bmatrix}$ is $\vec{\pi} = \begin{bmatrix} \frac{q}{p+q} & \frac{p}{p+q} \\ \frac{p}{p+q} & \frac{q}{p+q} \end{bmatrix}$ when $-1 < 1 - p - q < 1$.
For convenience, we describe this result for a 4-state irreducible one-step transition probability matrix $P$. Assume $\vec{\pi} = [\pi_0 \ \pi_1 \ \pi_2 \ \pi_3]$ is its unique stationary distribution and suppose $\tilde{P}$ is as defined below:

$$P = \begin{bmatrix} P_{00} & P_{01} & P_{02} & P_{03} \\ P_{10} & P_{11} & P_{12} & P_{13} \\ P_{20} & P_{21} & P_{22} & P_{23} \\ P_{30} & P_{31} & P_{32} & P_{33} \end{bmatrix} \quad \tilde{P} = \begin{bmatrix} P_{00}-1 & P_{01} & P_{02} & 1 \\ P_{10} & P_{11}-1 & P_{12} & 1 \\ P_{20} & P_{21} & P_{22}-1 & 1 \\ P_{30} & P_{31} & P_{32} & 1 \end{bmatrix}$$

Then $\tilde{P}$ is invertible and $\vec{\pi} = [0 \ 0 \ 0 \ 1] \tilde{P}^{-1}$. Moreover

$$\pi_0 = \frac{N_0}{D}$$

$$\pi_1 = \frac{N_1}{D}$$

$$\pi_2 = \frac{N_2}{D}$$

$$\pi_3 = \frac{N_3}{D}$$

where $N_i = \tilde{M}_{i3}$, $\tilde{M}_{ij}$ is the minor of the $ij$ entry of $\tilde{P}$, and $D$ is the determinant of $\tilde{P}$. The result is due to Mihoc (1934) and can be found in [Pyk03]; special thanks to Stewart Ethier for this reference.
Example 2: The Dual Matrix of a Birth-Death Matrix

$$
\text{Suppose } P = \begin{bmatrix} 0 & 0 & 0 & 0 \\ 0.7 & 0.3 & 0 & 0 \\ 0.2 & 0.6 & 0.2 & 0 \\ 0 & 0.7 & 0.3 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}
$$

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

$$
P^* = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0.3 & 0.5 & 0.2 & 0 \\ 0 & 0.2 & 0.1 & 0.7 \\ 0 & 0 & 0 & 1 \end{bmatrix}
$$

<figure><img src="image_4.png" /></figure>
Assume $P= [P_{i,j}]$ for $i, j$ going from 0, 1, ..., $H$ is a $(H+1) \times (H+1)$ stochastic matrix. Suppose that the $(H+2) \times (H+2)$ matrix $P^* = [P_{i,j}^*]$ where:

$$P_{i,j}^* = \sum_{s=i+1}^{H} [P_{j+1,s} - P_{j,s}]$$

is also a stochastic matrix under the following conventions:

$$\bullet \ P_{-1,s} = 0 \text{ if } -1 < s \le H$$

$$\bullet \ P_{H,H}^* = 1$$

$$\bullet \ P_{i,H}^* = 1 - \sum_{s=0}^{H-1} P_{i,s}^*$$

Then $P^*$ is called the dual matrix of $P$. Note that $P^*$ may not exist as a stochastic matrix. $P$ and $P^*$ have the same set of eigenvalues, see [Lyc18].
# Solving $P^{(k)}$ Using the Duality Theorem

Once we solve the $P^*$ we can use the Duality Theorem to calculate each element of our $P$ matrix

$$ P_{i,j}^{*(k)} = \sum_{s=i+1}^{H} [P_{j+1,s}^{(k)} - P_{j,s}^{(k)}] \qquad P_{i,j}^{(k)} = \sum_{s=i}^{H} [P_{j,s}^{*(k)} - P_{j-1,s}^{(k)}] \quad (3) $$

for $n \ge 0$ and for all states $i, j = 0, 1, 2, \dots, H$ with the conventions:

$$ P_{-1,s}^{(k)} = 0 \text{ if } s > -1 $$

$$ P_{H,H}^{*(k)} = 1 $$
In particular, the finite time Gambler's Ruin probability is:

$$P_{i,-1}^{*(k)} = \sum_{s=i+1}^{H} P_{0,s}^{(k)} \quad \text{where } i = 0, 1, 2, \dots, H-1. \quad (4)$$

Assume $P$ is the 1-step transition probability matrix of an irreducible finite Markov chain, then we know (see [HPS72]) there exists a steady state distribution:

$$\vec{\pi} = [\pi(0), \pi(1), \pi(2), \dots, \pi(H)]$$

And then

$$\lim_{k \to \infty} \sum_{s=i+1}^{H} P_{0,s}^{(k)} = \sum_{s=i+1}^{H} \lim_{k \to \infty} P_{0,s}^{(k)} = \sum_{s=i+1}^{H} P_{0,s}^{(\infty)} = \sum_{s=i+1}^{H} \pi(s) = \lim_{k \to \infty} P_{i-1}^{*(k)} = P_{i-1}^{*(\infty)}$$

where $P_{i,-1}^{*(\infty)}$ is the Gambler's Ruin probability starting at $i$ and ending at $-1$ in infinite time. So

$$P_{i,-1}^{*(\infty)} = \sum_{s=i+1}^{H} \pi(s) \quad (5)$$
Example 3: Gambler's Ruin Probabilities Using Duality

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

By our Algorithm, *P* has the following steady-state distribution

$$P = \begin{bmatrix} 0.75 & 0.05 & 0.05 & 0.15 \\ 0.5 & 0.1 & 0.05 & 0.35 \\ 0.4 & 0.1 & 0.05 & 0.45 \\ 0.2 & 0.05 & 0.05 & 0.7 \end{bmatrix} \qquad \begin{array}{l} \pi(0) = 0.504 \quad \pi(1) = 0.055 \\ \pi(2) = 0.05 \quad \pi(3) = 0.391 \end{array}$$
∞-Time Gambler's Ruin Probabilities Using Duality Theory

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

By the Duality Theorem, it follows

$$P^* = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 \\ 0.25 & 0.25 & 0.1 & 0.2 & 0.2 \\ 0.2 & 0.2 & 0.1 & 0.25 & 0.25 \\ 0.15 & 0.2 & 0.1 & 0.25 & 0.3 \\ 0 & 0 & 0 & 0 & 1 \end{bmatrix}$$

$$P_{0,-1}^{*(\infty)}(p) = \pi(1) + \pi(2) + \pi(3) = 0.496$$

$$P_{1,-1}^{*(\infty)}(p) = \pi(2) + \pi(3) = 0.441$$

$$P_{2,-1}^{*(\infty)}(p) = \pi(3) = 0.391$$
## Example 4: Starting with a Dual Markov Chain

Consider the following transition diagram of a conventional five-state Markov chain having two absorbing states.

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

$$ P^* = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 \\ 0.25 & 0.25 & 0.1 & 0.2 & 0.2 \\ 0.15 & 0.2 & 0.1 & 0.25 & 0.3 \\ 0.2 & 0.2 & 0.1 & 0.25 & 0.25 \\ 0 & 0 & 0 & 0 & 1 \end{bmatrix} $$

$$ P_{0,-1}^{*(\infty)}(p) = \pi(1) + \pi(2) + \pi(3) $$

$$ P_{1,-1}^{*(\infty)}(p) = \pi(2) + \pi(3) $$

$$ P_{2,-1}^{*(\infty)}(p) = \pi(3) $$
<figure><img src="image_8.png" /></figure>

By our Algorithm, $P$ has the unconventional "steady-state" distribution

$$ P = \begin{bmatrix} 0.75 & 0.1 & -0.05 & 0.2 \\ 0.5 & 0.15 & -0.05 & 0.4 \\ 0.4 & 0.15 & -0.05 & 0.5 \\ 0.2 & 0.1 & -0.05 & 0.75 \end{bmatrix} $$
$$ \begin{array}{l} \pi(0) = 0.491 \qquad \pi(1) = 0.103 \\ \pi(2) = -0.05 \qquad \pi(3) = 0.456 \\ \text{Eigenvalues:} \\ \omega_1 = 1 \qquad \omega_2 = 1/20 \\ \omega_3 = 11/20 \qquad \omega_4 = 0 \end{array} $$
<figure><img src="image_9.png" /></figure>

By the Duality Theorem, it follows

$$P_{0,-1}^{*(\infty)}(p) = \pi(1) + \pi(2) + \pi(3) = 0.103 - 0.05 + 0.457 = 0.509$$

$$P_{1,-1}^{*(\infty)}(p) = \pi(2) + \pi(3) = -0.05 + 0.457 = 0.407$$

$$P_{2,-1}^{*(\infty)}(p) = \pi(3) = 0.457$$
# General Gambler's Ruin Problem Solved Using Duality

The Gambler's Ruin diagram can be thought of as the dual transition diagram of a general *n*-state chain with one-step transition probability matrix *P*. We let the figure below represent a Markov chain having 2 absorbing states and *n* − 2 transient states.

<figure><img src="image_10.png" /></figure>
The Dual transition diagram on the previous slide has the corresponding one-step transition probability matrix

$$ P^* = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 \\ P_{0,}^* - 1 & P_{0,}^* - 0 & P_{0,}^* - 1 & P_{0,}^* - 2 & P_{0,}^* - 3 \\ P_{1,}^* - 1 & P_{1,}^* - 1 & P_{1,}^* - 1 & P_{1,}^* - 2 & P_{1,}^* - 3 \\ P_{2,}^* - 1 & P_{2,}^* - 1 & P_{2,}^* - 1 & P_{2,}^* - 2 & P_{2,}^* - 3 \\ P_{3,}^* - 1 & P_{3,}^* - 1 & P_{3,}^* - 1 & P_{3,}^* - 2 & P_{3,}^* - 3 \\ 0 & 0 & 0 & 0 & 1 \end{bmatrix} $$

The kth power of $P^*$ can be represented as:

$$ (P^*)^k = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 \\ P_{0,}^{*(k)} - 1 & P_{0,}^{*(k)} - 0 & P_{0,}^{*(k)} - 1 & P_{0,}^{*(k)} - 2 & P_{0,}^{*(k)} - 3 & P_{0,}^{*(k)} - 4 \\ P_{1,}^{*(k)} - 1 & P_{1,}^{*(k)} - 1 & P_{1,}^{*(k)} - 1 & P_{1,}^{*(k)} - 2 & P_{1,}^{*(k)} - 3 & P_{1,}^{*(k)} - 4 \\ P_{2,}^{*(k)} - 1 & P_{2,}^{*(k)} - 1 & P_{2,}^{*(k)} - 1 & P_{2,}^{*(k)} - 2 & P_{2,}^{*(k)} - 3 & P_{2,}^{*(k)} - 4 \\ P_{3,}^{*(k)} - 1 & P_{3,}^{*(k)} - 1 & P_{3,}^{*(k)} - 1 & P_{3,}^{*(k)} - 2 & P_{3,}^{*(k)} - 3 & P_{3,}^{*(k)} - 4 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix} $$

where $P_{i,j}^{*(k)}$ are the k-step transition probabilities.
the center matrix of $P^*$ is $C^*$ as shown below:

$$C^* = \begin{bmatrix} P_{0,0}^* & P_{0,1}^* & P_{0,2}^* & P_{0,3}^* \\ P_{1,0}^* & P_{1,1}^* & P_{1,2}^* & P_{1,3}^* \\ P_{2,0}^* & P_{2,1}^* & P_{2,2}^* & P_{2,3}^* \\ P_{3,0}^* & P_{3,1}^* & P_{3,2}^* & P_{3,3}^* \end{bmatrix}$$

and

$$(C^*)^k = \begin{bmatrix} P_{0,0}^{*(k)} & P_{0,1}^{*(k)} & P_{0,2}^{*(k)} & P_{0,3}^{*(k)} \\ P_{1,0}^{*(k)} & P_{1,1}^{*(k)} & P_{1,2}^{*(k)} & P_{1,3}^{*(k)} \\ P_{2,0}^{*(k)} & P_{2,1}^{*(k)} & P_{2,2}^{*(k)} & P_{2,3}^{*(k)} \\ P_{3,0}^{*(k)} & P_{3,1}^{*(k)} & P_{3,2}^{*(k)} & P_{3,3}^{*(k)} \end{bmatrix}$$
Note that

$$ \lim_{k \to \infty} (C^*)^k = \begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix} \qquad (6) $$

because states 0, 1, 2, and 3 are all transient states. Suppose $C^*$ has distinct eigenvalues $\omega_0, \omega_1, \omega_2, \omega_3$, then by Sylvester's eigenvalue expansion:

$$ (C^*)^k = C_0^* \omega_0^k + C_1^* \omega_1^k + C_2^* \omega_2^k + C_3^* \omega_3^k $$

where $C_0^*, C_1^*, C_2^*, C_3^*$ are the spectral projectors of $C^*$. By (6), it follows that $|\omega_0|, |\omega_1|, |\omega_2|, |\omega_3| < 1$.
We assume the original system has one-step transition probability matrix *P* where *P* is somewhat stochastic.

<figure><img src="image_11.png" /></figure>
Since it is known that the matrix of the original system, $P$, and $P^*$ have the same set of eigenvalues, see [Lyc18], it follows that the eigenvalues of $P$ are $1, \omega_0, \omega_1, \omega_2$, and $\omega_3$. Assuming these eigenvalues are distinct, the Sylvester eigenvalue expansion of $P^k$ is

$$P^k = A_{-1} + A_0\omega_0^k + A_1\omega_1^k + A_2\omega_2^k + A_3\omega_3^k$$

And so

$$\lim_{k \to \infty} P^k = A_{-1} \qquad (7)$$

because $|\omega_0|, |\omega_1|, |\omega_2|, |\omega_3| < 1$. In other words, from the equation (7) and Definition 4, $P$ has a steady-state distribution, even though some of the entries may be negative.
**Remark 4.** Finding the preceding steady-state distribution of $P$ as shown in Equation (7) provides an alternative approach to find infinite time Gambler's Ruin probabilities using Equation (5) even when some entries of $P$ may be negative.

**Remark 5.** Another classical method for determining infinite time Gambler's Ruin probabilities uses the Fundamental Matrix approach given in [KS76].

**Remark 6.** Gambler's Ruin probabilities have historically been by determined by solving a system of linear recurrences, see [HPS72].
Xiaoxiao Eigenvalues

<figure><img src="image_12.png" /></figure>
Suppose $P^*$ is any conventional $n$-state Markov chain having exactly two absorbing states and $n-2$ transient states, then $P$ is a somewhat stochastic matrix that has a single root of unity in its characteristic polynomial and all the remaining eigenvalues lie within the open unit disk on the complex plane. By Theorem 3, $P$ has a steady-state distribution $\pi$. $\pi$ may be found by determining the spectral projector of $P$ corresponding to eigenvalue $\omega = 1$. This implies a solution of the infinite gambler's ruin probability for $P^*$ using the duality equation (5).

If the eigenvalues and the eigenvectors of $P^*$ are also known, then by the Sylvester eigenvalue expansion (1) or the generalized Sylvester eigenvalue expansion (2), $P_{i,j}^{*(k)}$ is explicitly known. It follows by the Duality Theorem (3), $P_{i,j}^{(k)}$ is also known. So by equation (4), the finite-time gambler's ruin probabilities are explicitly known.
## Therefore we have studied and have some results:

* when $P^*$ is a tridiagonal Toeplitz matrix

* when $P^*$ is a tridiagonal matrix with alternating entries along the diagonals

* when $P^*$ is a symmetric, pentadiagonal, Toeplitz matrix

* when $P^*$ is a pentadiagonal, Toeplitz matrix with zeros along the first subdiagonal and first superdiagonal.

## An interesting element of our duality solution today is the inclusion of somewhat stochastic matrices. The extension of our approach to finding the absorption probability in an infinite state Markov chain setting is still in progress.
## Example 5: Negative Probabilities - Infinite State Space

The next example extends our example on negative probabilities to an infinite number of states. Consider the following diagram for the dual matrix $P^*$

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

With the conditions

$$0 < q, p < 1$$

$$p + q = 1$$
## Example 5: Negative Probabilities - Infinite State Space

We can regard the conventional Markov Chain on the previous slide to be the dual of another Markov system. Using the definition of Duality, the transition probabilities of the original Markov system include some *negative probabilities* as shown in the figure below

<figure><img src="image_14.png" /></figure>
## Example 5: Negative Probabilities - Infinite State Space

The one-step transition probability matrix $P$ of the preceding figure looks like this

$$P = \begin{bmatrix} 1 & -q/2 & q/2 & 0 & 0 & 0 & \dots \\ 1 & -q & 0 & q & 0 & 0 & \dots \\ q & p-q & 0 & q & 0 & 0 & \dots \\ 0 & 0 & p & 0 & q & 0 & \dots \\ 0 & 0 & 0 & p & 0 & q & \dots \\ 0 & 0 & 0 & 0 & p & 0 & \dots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{bmatrix}$$

To find the stationary distribution $\pi$ of $P$, we assume the following,

$$1 = \pi(0) + \pi(1) + \pi(2) + \pi(3) + \pi(4) + \dots \quad \text{where } q < p \quad (*)$$

Solving $\pi = \pi P$ gives us the following algebraic relations

$$\pi(1) = -\frac{q^2}{2(q^2 + p)} \pi(0)$$

$$\pi(2) = \frac{q}{2(q^2 + p)} \pi(0)$$

$$\pi(k) = \frac{q^2}{2(q^2 + p)} \left(\frac{q}{p}\right)^{k-3} \pi(0)$$

for $k \ge 3$. To solve for $\pi(0)$, substitute the preceding equations into (*)
We find that

$$
\begin{align*}
1 &= \left[ 1 - \frac{q^2}{2(q^2 + p)} + \frac{q}{2(q^2 + p)} \right] \pi(0) + \left[ 1 + \frac{q}{p} + \left(\frac{q}{p}\right)^2 + \dots \right] \frac{q(1 - q^2 - p)}{2p(q^2 + p)} \pi(0) \\
&= \left[ 1 - \frac{q^2}{2(q^2 + p)} + \frac{q}{2(q^2 + p)} \right] \pi(0) + \left( \frac{1}{1 - q/p} \right) \frac{q^2}{2(q^2 + p)} \pi(0) \\
&= \left[ 1 - \frac{q^2}{2(q^2 + p)} + \frac{q}{2(q^2 + p)} + \left( \frac{1}{1 - q/p} \right) \frac{q^2}{2(q^2 + p)} \right] \pi(0)
\end{align*}
$$

and so

$$
\pi(0) = \left[ 1 - \frac{q^2}{2(q^2 + p)} + \frac{q}{2(q^2 + p)} + \left( \frac{1}{1 - q/p} \right) \frac{q^2}{2(q^2 + p)} \right]^{-1}
$$

Simplifying and substituting $p$ in terms of $q$ by $p = 1 - q$

$$
\pi(0) = \frac{4q^2 - 6q^2 + 6q - 2}{3q^2 - 4q^2 + 5q - 2}
$$

$$
\pi(1) = - \frac{q^2}{2(q^2 - q + 1)} \pi(0)
$$

$$
\pi(2) = \frac{q}{2(q^2 - q + 1)} \pi(0)
$$
and for $k \ge 3$

$$ \pi(k) = \frac{q^2}{2(q^2 - q + 1)} \left( \frac{q}{1-q} \right)^{k-3} \pi(0) $$

Substituting $\pi(0) = (4q^3 - 6q^2 + 6q - 2)/(3q^3 - 4q^2 + 5q - 2)$ gives:

$$ P_{0,-1}^{*(\infty)}(q) = 1 - \pi(0) = 1 - \frac{4q^3 - 6q^2 + 6q - 2}{3q^3 - 4q^2 + 5q - 2} $$

$$ P_{1,-1}^{*(\infty)}(q) = 1 - \pi(0) - \pi(1) = 1 - \left(1 - \frac{q^2}{2(q^2 - q + 1)}\right) \frac{4q^3 - 6q^2 + 6q - 2}{3q^3 - 4q^2 + 5q - 2} $$

$$ P_{2,-1}^{*(\infty)}(q) = 1 - \pi(0) - \pi(1) - \pi(2) $$

$$ = 1 - \left(1 - \frac{q^2}{2(q^2 - q + 1)} + \frac{q}{2(q^2 - q + 1)}\right) \frac{4q^3 - 6q^2 + 6q - 2}{3q^3 - 4q^2 + 5q - 2} $$

$$ P_{3,-1}^{*(\infty)}(q) = 1 - \pi(0) - \pi(1) - \pi(2) - \pi(3) $$

$$ = 1 - \left(1 - \frac{q^2}{2(q^2 - q + 1)} + \frac{q}{2(q^2 - q + 1)} + \frac{q^2}{2(q^2 - q + 1)}\right) \frac{4q^3 - 6q^2 + 6q - 2}{3q^3 - 4q^2 + 5q - 2} $$
<figure><img src="image_15.png" /></figure>

William J Anderson, *Continuous-time markov chains: An applications-oriented approach*, Springer Science & Business Media, 2012.

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

Chris Bernhardt, *Powers of positive matrices*, Mathematics Magazine **91** (2018), no. 3, 218–227.

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

Branko Ćurgus and Robert I Jewett, *Somewhat stochastic matrices, The American Mathematical Monthly* **122** (2015), no. 1, 36–42, DOI: 10.4169/amer.math.monthly.122.01.36.

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

Stefan Felsner and Daniel Heldt, *Lattice path enumeration and toeplitz matrices*, Journal of Integer Sequences **18** (2015), no. 2, 3.

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

Sephen H. Friedberg, Arnold J. Insel, and Lawrence E. Spence, *Linear algebra*, 5th ed., Pearson, New Jersey, 2018.
<figure><img src="image_20.png" /></figure>

Andrzej Granas and James Dugundji, *Fixed point theory*, vol. 14, Springer, 2003.

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

Paul G. Hoel, Sidney C. Port, and Charles J. Stone, *Introduction to stochastic processes*, Mifflin, 1972. MR 358879

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

Alan Krinik et al., *Explicit transient probabilities of various markov models*, AMS Contemporary Mathematics Series **774** (2021), 97–151. MR 4344296

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

Alan Krinik, Carrie Mortensen, and Gerardo Rubino, *Connections between birth-death processes*, Lecture Notes in Pure and Applied Mathematics (2004), 219–240.

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

Alan Krinik, Gerardo Rubino, Daniel Marcus, Randall J Swift, Hassan Kasfy, and Holly Lam, *Dual processes to solve single server systems*, Journal of Statistical Planning and Inference **135** (2005), no. 1, 121–147.
<figure><img src="image_25.png" /></figure>

John G Kemeny and James Laurie Snell, *Finite markov chains: with a new appendix" generalization of a fundamental matrix", Springer, 1976.

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

A C Krinik and K Shun, *Markov processes with constant transition rates of size one & two*, vol. 5, Journal of Statistical Theory and Practice, 2011.

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

Paweł Lorek, *Generalized gambler's ruin problem: explicit formulas via siegmund duality*, Methodology and Computing in Applied Probability **19** (2017), no. 2, 603–613.

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

Samuel Lyche, *On deep learning and neural networks*, Master's thesis, California State Polytechnic University, Pomona, 2018.

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

Carl D Meyer, *Matrix analysis and applied linear algebra*, vol. 71, Siam, 2000.
<figure><img src="image_30.png" /></figure>

Gopal Mohanty, *Lattice path counting and applications*, Academic Press, 2014.

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

Cleve Moler and Charles Van Loan, *Nineteen dubious ways to compute the exponential of a matrix, twenty-five years later*, SIAM review **45** (2003), no. 1, 3–49.

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

Uyen Nguyen, *Tridiagonal stochastic matrices*, Master's thesis, California State Polytechnic University, Pomona, 2017.

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

Ronald Pyke, *On random walks and diffusions related to parrondo's games*, Lecture Notes-Monograph Series (2003), 185–216.

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

Marc Renault, *Four proofs of the ballot theorem*, Mathematics magazine **80** (2007), no. 5, 345–352.
<figure><img src="image_35.png" /></figure>

robjohn (https://math stackexchange.com/users/13854/robjohn),
*Rank of sum of rank-1 matrices*, Mathematics Stack Exchange,
URL:https://math stackexchange.com/q/707245 (version:
2014-03-10).

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

Gerard Rubino and Alan Krinik, *The exponential-dual matrix method: Applications to markov chain analysis*, AMS Contemporary Mathematics Series **774** (2021), 217–235.

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

Eugene Seneta, *Coefficients of ergodicity: structure and applications*,
*Advances in applied probability* **11** (1979), no. 3, 576–590.

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

Wikipedia contributors, *Frobenius covariant — Wikipedia, the free encyclopedia*, 2019, [Online; accessed 27-May-2020].

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

______, *Sylvester's formula — Wikipedia, the free encyclopedia*,
2019, [Online; accessed 27-May-2020].
Thank
you!
For the case of $p = 2/3$ and $q = 1/3$, $\pi(0)$ and the stationary distribution become

$$\pi(0) = \frac{7}{9}$$

$$\pi(1) = -\frac{1}{18}$$

$$\pi(2) = \frac{1}{6}$$

$$\pi(3) = \frac{1}{18}$$

$$\pi(4) = \frac{1}{36}$$

$$\pi(k) = \frac{1}{18} \left(\frac{1}{2}\right)^{k-3}$$
<figure><img src="image_40.png" /></figure>

Stationary Distribution
<figure><img src="image_41.png" /><figcaption>Absorption Probabilities</figcaption></figure>
**Theorem.** Let $A \in M_{n \times n}(\mathbb{C})$ satisfy the following two conditions.

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

* Every eigenvalue of $A$ is contained in $S$.

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

* $A$ is diagonalizable.

Then $\lim_{m \to \infty} A^m$ exists. See page 284-285 of Friedberg's Linear Algebra [FIS18].
Example 6

Consider the following dual transition diagram where $0 < p, q < 1$ and $p+q=1$

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

and corresponding dual transition matrix $P^*$

$$P^* = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 & \cdots \\ 0 & 0 & p & q & 0 & 0 & 0 & \cdots \\ q/2 & q/2 & 0 & p & 0 & 0 & 0 & \cdots \\ 0 & q & 0 & 0 & p & 0 & 0 & \cdots \\ 0 & 0 & 0 & 0 & 0 & p & q & \cdots \\ 0 & 0 & 0 & q/2 & q/2 & 0 & p & \cdots \\ 0 & 0 & 0 & 0 & q & 0 & 0 & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \end{bmatrix}$$
Taking the dual of the dual we obtain the following generalized diagram for the original system:

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

with the corresponding original matrix $P$

$$P = \begin{bmatrix}
1 & -q/2 & q/2 & 0 & 0 & 0 & \dots \\
1 & -q & 0 & q & 0 & 0 & \dots \\
q & p-q & 0 & q & 0 & 0 & \dots \\
0 & 0 & p & q & -q/2 & q/2 & 0 & \dots \\
0 & 0 & 0 & 1 & -q & 0 & q & \dots \\
0 & 0 & 0 & q & p-q & 0 & q & \dots \\
0 & 0 & 0 & 0 & 0 & p & q & \dots \\
0 & 0 & 0 & 0 & 0 & 0 & 1 & \dots \\
\vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots
\end{bmatrix}$$
By solving the system $\vec{\pi}P = \vec{\pi}$ we obtain the following for the stationary distribution

$$ \pi(1) = -qC(q)\pi(0) $$

$$ \pi(2) = C(q)\pi(0) $$

$$ \pi(3) = qC(q)\pi(0) $$

And in general, the following formulas will give us any distribution probability, for $k = 0, 1, 2, 3, ...$:

$$ \pi(3k + 1) = -[qC(q)]^{k+1}\pi(0) \quad (8) $$

$$ \pi(3k + 2) = q^k C(q)^{k+1} \pi(0) \quad (9) $$

$$ \pi(3k + 3) = [qC(q)]^{k+1}\pi(0) \quad (10) $$

Where

$$ C(q) = \frac{q}{2(q^2 - q + 1)} \quad (11) $$
Since the terms of the form $\pi(3k + 1)$ and $\pi(3k + 3)$ form a telescoping series, and knowing $\sum_{n=0}^{\infty} \pi(n) = 1$, produces the following equation:

$$1 = \pi(0) + \sum_{k=0}^{\infty} \pi(3k + 2) = \pi(0) + \pi(0) \sum_{k=0}^{\infty} q^k C(q)^{k+1} = \pi(0) \left[ 1 + \sum_{k=0}^{\infty} q^k C(q)^{k+1} \right]$$

Therefore

$$\pi(0) = \frac{1}{1 + \sum_{k=0}^{\infty} q^k C(q)^{k+1}} = \frac{1}{1 + C(q) \sum_{k=0}^{\infty} q^k C(q)^k}$$

Using the formula for the sum of a geometric series, we obtain

$$\pi(0) = \frac{q^2 - 2q + 2}{q^2 - q + 2} \qquad (12)$$

In general, for $k = 0, 1, 2, 3, \dots$,
$$P_{0,-1}^{*(\infty)}(q) = 1 - \pi(0)$$

$$P_{3k+1,-1}^{*(\infty)}(q) = 1 - \pi(0) + [qC(q)]^{k+1}\pi(0) - \pi(0)C(q) \left[ \frac{q^k C(q)^k - 1}{qC(q) - 1} \right]$$

$$P_{3k+2,-1}^{*(\infty)}(q) = 1 - \pi(0) + [qC(q)]^{k+1}\pi(0) - \pi(0)C(q) \left[ \frac{q^{k+1}C(q)^{k+1} - 1}{qC(q) - 1} \right]$$

$$P_{3k+3,-1}^{*(\infty)}(q) = 1 - \pi(0) - \pi(0)C(q) \left[ \frac{q^{k+1}C(q)^{k+1} - 1}{qC(q) - 1} \right]$$

Substituting $C(q) = \frac{q}{2(q^2-q+1)}$ from equation (?) and $\pi(0) = \frac{q^2-2q+2}{q^2-q+2}$ from equation (5), we obtain the first 4 absorption probabilities:

$$P_{0,-1}^{*(\infty)}(q) = 1 - \pi(0) = \frac{q}{q^2 - q + 2}$$

$$P_{1,-1}^{*(\infty)}(q) = 1 - \pi(0) - \pi(1) = \frac{q^4 + 2q}{2(q^2 - q + 1)(q^2 - q + 2)}$$

$$P_{2,-1}^{*(\infty)}(q) = 1 - \pi(0) - \pi(1) - \pi(2) = \frac{q^4 - q^3 + 2q^2}{2(q^2 - q + 1)(q^2 - q + 2)}$$

$$P_{3,-1}^{*(\infty)}(q) = 1 - \pi(0) - \pi(1) - \pi(2) - \pi(3) = \frac{q^3}{2(q^2 - q + 1)(q^2 - q + 2)}$$
For $q = 1/3$, we obtain the following numerical example for the dual chain

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

With absorption probabilities

$$P_{0,-1}^{*(\infty)} = \frac{3}{16}$$

$$P_{1,-1}^{*(\infty)} = \frac{55}{224}$$

$$P_{2,-1}^{*(\infty)} = \frac{1}{14}$$

$$P_{3,-1}^{*(\infty)} = \frac{3}{224}$$

$$P_{3k+1,-1}^{*(\infty)} = \left(\frac{55}{224}\right) \frac{1}{14^k} \qquad P_{3k+2,-1}^{*(\infty)} = \frac{1}{14^{k+1}} \qquad P_{3k+3,-1}^{*(\infty)} = \left(\frac{3}{16}\right) \frac{1}{14^{k+1}} \qquad k = 0, 1, 2, 3, \dots$$

where the original chain is shown below

<figure><img src="image_47.png" /></figure>
Assume $M$ is a real $n \times n$ matrix that has $n$ known distinct eigenvalues $\omega_1, \omega_2, \dots, \omega_n$. Then

$$ M^k = A_1\omega_1^k + A_2\omega_2^k + A_3\omega_3^k + \dots + A_n\omega_n^k \quad (13) $$

where $k = 0, 1, 2, \dots$ and $A_1, A_2, \dots, A_n$ are constant $n \times n$ coefficient matrices called spectral projectors (Meyer) or Frobenius covariants.

$$ M^k(i,j) = A_1(i,j)\omega_1^k + A_2(i,j)\omega_2^k + A_3(i,j)\omega_3^k + \dots + A_n(i,j)\omega_n^k $$

where $0 \le i, j \le n-1$ for $s = 1, 2, 3, \dots, n$.

Note: $A_s$ is the matrix outer product, $c^2 \vec{R}_s \vec{L}_s$, where $\vec{R}_s$ and $\vec{L}_s$ are right & left eigenvectors of matrix $M$ and where $\vec{L}_s$ and $\vec{R}_s$ are scaled by a constant $c$ so that their dot product $c^2 \vec{L}_s \cdot \vec{R}_s = 1$.
Example 7: Unconventional Infinite Markov Processes

Consider the $M^{X_2}/M^{Y_2}/1$ process shown below

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

with the Q matrix of this Markov Process being

$$Q = \begin{bmatrix} -(\lambda + \beta) & & & & & & 0 & & & \\ \mu & -(\lambda + \beta + \mu) & & & & & & 0 & & & \\ \gamma & & \lambda & & & & & \beta & & & \\ 0 & & & -(\lambda + \beta + \mu + \gamma) & & & & \lambda & & & \\ 0 & & & & -(\lambda + \beta + \mu + \gamma) & & & & \lambda & & \\ \vdots & \vdots & & \vdots & \vdots & -(\lambda + \beta + \mu + \gamma) & & & & & \\ \vdots & \vdots & & \vdots & \vdots & \vdots & -(\lambda + \beta + \mu + \gamma) & & & & \end{bmatrix}$$
Constructing the rate matrix $Q^*$ for the dual process gives us

$$Q^* = \begin{bmatrix} 0 & 0 & 0 & 0 & \dots \\ \lambda + \beta & -(\lambda + \beta + \mu) & \mu - \gamma & \gamma & \dots \\ \beta & \lambda & -(\gamma + \beta + \mu + \gamma) & \mu & \dots \\ 0 & \beta & \lambda & -(\gamma + \beta + \mu + \gamma) & \dots \\ \vdots & \vdots & \vdots & \vdots & \ddots \end{bmatrix}$$

Note that there is an off-diagonal entry in $Q^*$ that could theoretically be negative, $\mu - \gamma$. Thus we assume $\mu > \gamma$ so that the dual process exists and is a well-defined Markov process. Using the $Q^*$ matrix we may draw its state transition rate diagram as follows:

<figure><img src="image_49.png" /></figure>
# Major Theorem

Consider the $M^{X_2}/M^{Y_2}/1$ process as shown in the previous two slides. This process has a steady-state distribution iff

$$2\beta + \lambda < 2\gamma + \mu$$

When the steady state distribution exists, it may be represented as

$$\pi(n) = c_2 r_2^n + c_3 r_3^n \qquad n \ge 0$$

where

$$\rho_n^* = 1 - \pi(0) - \pi(1) - \dots - \pi(n-1) \quad \text{or} \quad P_{n,0}^{*(\infty)} = \sum_{k=n}^{\infty} \pi(k)$$

where

$$r_2 = -\frac{a}{3} - 2\sqrt{U} \cos\left(\frac{\theta}{3} + \frac{4\pi}{3}\right) \qquad r_3 = -\frac{a}{3} - 2\sqrt{U} \cos\left(\frac{\theta}{3} + \frac{2\pi}{3}\right) \\ c_2 = \frac{\left(\frac{\beta}{r_3} - \gamma r_3\right)(1-r_2)(1-r_3)}{(r_3-r_2)[2\gamma(r_2+r_3)+\mu]} \qquad c_3 = \frac{\left(\frac{\beta}{r_2} - \gamma r_2\right)(1-r_2)(1-r_3)}{(r_2-r_3)[2\gamma(r_2+r_3)+\mu]}$$
and where

$$U = \frac{a^2 - 3b}{9}$$

$$V = \frac{2a^3 - 9ab + 27c}{54}$$

$$\theta = \cos^{-1}\left(\frac{V}{\sqrt{U^3}}\right)$$

$$a = \frac{\mu + \gamma}{\gamma}$$

$$b = -\frac{\beta + \lambda}{\gamma}$$

$$c = -\frac{\beta}{\gamma}$$

Furthermore, whenever $(\lambda/\mu)^2 = \beta/\gamma$, the steady state distribution exists iff

$$\frac{\lambda}{\mu} < 1$$

$$\frac{\beta}{\gamma} < 1$$

In this special case, the steady state distribution may then be simplified to

$$\pi(n) = \left(1 - \frac{\lambda}{\mu}\right) \left(\frac{\lambda}{\mu}\right)^n$$

$$n \ge 0$$

for the conventional case where $\mu - \gamma \ge 0$, from [KS11].
# First Numerical Example

If we let $\lambda = 3$, $\beta = 1$, $\mu = 6$, $\gamma = 4$, our values become

$$r_2 = -0.1771 \qquad r_3 = 0.\frac{1}{2}$$

$$c_2 = 0 \qquad c_3 = \frac{1}{2}$$

and the values of the steady state distribution become

$$\pi(0) = \frac{1}{2} \qquad \pi(1) = \frac{1}{4} \qquad \pi(2) = \frac{1}{8}$$

$$\pi(3) = \frac{1}{16} \qquad \pi(4) = \frac{1}{32} \qquad \pi(5) = \frac{1}{64}$$

and so the absorption probabilities become

$$P_{1,0}^{*(\infty)} = \frac{1}{2} \qquad P_{2,0}^{*(\infty)} = \frac{1}{4}$$

$$P_{3,0}^{*(\infty)} = \frac{1}{8} \qquad P_{4,0}^{*(\infty)} = \frac{1}{16}$$
<figure><img src="image_50.png" /></figure>

For $\lambda = 3, \beta = 1, \mu = 6, \gamma = 4$
Second Numerical Example

If we let $\lambda = 1$, $\beta = 1$, $\mu = 2$, $\gamma = 4$, our values become

$$r_2 = -0.2929 \qquad r_3 = \frac{1}{2}$$

$$c_2 = 0 \qquad c_3 = \frac{1}{2}$$

and the values of the steady state distribution become

$$\pi(0) = \frac{1}{2} \qquad \pi(1) = \frac{1}{4} \qquad \pi(2) = \frac{1}{8}$$

$$\pi(3) = \frac{1}{16} \qquad \pi(n) = \frac{1}{2n+1}$$

and so the absorption probabilities become

$$P_{1,0}^{*(\infty)} = \frac{1}{2} \qquad P_{2,0}^{*(\infty)} = \frac{1}{4}$$

$$P_{3,0}^{*(\infty)} = \frac{1}{8} \qquad P_{n,0}^{*(\infty)} = \frac{1}{2^n}$$
<figure><img src="image_51.png" /></figure>

For $\lambda = 1, \beta = 1, \mu = 2, \gamma = 4$
* Siegmund duality provides a precise way to calculate Gambler's Ruin probabilities and absorption probabilities (as opposed to simulations and matrix approximations)

* This methodology still "works" using algebraic duality as described in Rubino & Krinik [RK21] and past JMM presentations when Siegmund duality doesn't exist. We demonstrated in two cases.

* **Case 1:** The dual chain or process is conventional and the original chain or process is "unconventional". Unconventional means that the chain or process has negative one-step transition probabilities (or rates) or the chain has a somewhat stochastic stationary distribution.
As the eigenvector corresponding to $\omega = 1$ is $\vec{R}_1 = \vec{1}$, when we construct the spectral projector corresponding to $\omega = 1$ we find that the rows are identical:

$$A_{-1} = c^2 \vec{R}_1 \vec{L}_1 = c^2 \begin{bmatrix} r_1 \\ r_2 \\ r_3 \\ r_4 \end{bmatrix} \begin{bmatrix} l_1 & l_2 & l_3 & l_4 \end{bmatrix} \text{ where } \begin{bmatrix} r_1 \\ r_2 \\ r_3 \\ r_4 \end{bmatrix} = \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} \\ = c^2 \begin{bmatrix} r_1 l_1 & r_1 l_2 & r_1 l_3 & r_1 l_4 \\ r_2 l_1 & r_2 l_2 & r_2 l_3 & r_2 l_4 \\ r_3 l_1 & r_3 l_2 & r_3 l_3 & r_3 l_4 \\ r_4 l_1 & r_4 l_2 & r_4 l_3 & r_4 l_4 \end{bmatrix} = c^2 \begin{bmatrix} l_1 & l_2 & l_3 & l_4 \\ l_1 & l_2 & l_3 & l_4 \\ l_1 & l_2 & l_3 & l_4 \\ l_1 & l_2 & l_3 & l_4 \end{bmatrix}$$

Since $P$ is somewhat stochastic, it follows that $P^k$ is also somewhat stochastic and this implies that the $\lim_{k \to \infty} P^k$ is also somewhat stochastic. Therefore, $A_{-1}$ is somewhat stochastic and the rows form the steady-state distribution $\vec{\pi}$ of $P$.
# Summary and Future Work

* **Case 2:** The original chain or process is conventional and the dual chain or process is unconventional.

* Gambler's Ruin probabilities and absorption probabilities are "correct" as checked by simulations or matrix approximations.

* **Much more to do:**

* Since negative probabilities are useful, we need to interpret them beyond being just signed measures.

* For example, we know positive recurrent conventional Markov chains have a unique stationary distribution. Does a similar result hold for somewhat stochastic matrices, see [ĆJ15] for some progress in this direction.