Chapter 3.5

Markov Process and Numerical Solution of State Probabilities

(c) Tobias Hossfeld (Aug 2021)

This script and the figures are part of the following book. The book is to be cited whenever the script is used (copyright CC BY-SA 4.0):
Tran-Gia, P. & Hossfeld, T. (2021). Performance Modeling and Analysis of Communication Networks - A Lecture Note. Würzburg University Press.

This script provides the solution of nonstationary and stationary Markov processes. In Python, this can be very efficiently solved. The Markov chain is described completely by the transition rate matrix $Q$ and an initial state $X(0)$.

Transition Rate Matrix $Q$

Let us create a transition rate matrix $Q$ first. The row-wise sum is zero.

Kolmogorov Forward Equation for State Probabilities: Nonstationary Analysis

Now we compute the steady probabilities over time based on Kolmogorov forward equation.

$\frac{d}{dt}X(t) = X(t)Q$

This can be solved with the matrix exponential $e^{tQ}$ and the initial state $X(0)$ at time $t=0$.

$ X(t) = X(0) \cdot e^{tQ} $

The matrix exponential can be computed using scipy.linalg.expm.

Comparison with Steady State Probabilities

The steady state of the system is considered. Then, we obtain $X = \lim_{t \to \infty} X(t)$ and $ \lim_{t \to \infty} \frac{d}{dt}X(t)=0$.

We solve the equation $XQ=0$ and consider $X e = 1$. Therefore, we replace one equation by changing the matrix $Q$ and use the vector $b=(0,\dots,0,1)$. Then, we need to solve $XQ=b$ which means $X=bQ^{-1}$ with the matrix inverse $Q^{-1}$. The matrix $Q$ can be inverted if the determinant is not equal to zero, $det(Q) \neq 0$.

Now, we solve $X\cdot Q_2=b$ which means $X=b\cdot Q_2^{-1}$ with the matrix inverse $Q_2^{-1}$. The result is compared with the nonstationary analysis result for large $t$.