# Power Method¶

(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. https://doi.org/10.25972/WUP-978-3-95826-153-2

## Discrete-time Markov Chain¶

We consider a discrete-time Markov chain (DTMC): A stochastic process $\{X(t),\, t > 0\}$ is considered which has the Markov property at discrete (not necessarily equidistant) points in time $\{t_n, \, n=0,1,\dots\}$. Thus, we obtain a sequence of random variables $\{X(t_0), X(t_1), \dots \}$. The value of the next random variable $X(t_{n+1})$ depends only on the current random variable $X(t_n)$, but not on other random variables in the past (Markov property). This discrete-time stochastic process is denoted by $\{X(t_n),\, n=0,1,\dots\}$ and called a discrete-time Markov process. Thereby, the random variables $X(t_n)$ may be discrete or continuous. For the analysis of M/GI/1 and GI/M/1, the considered state space is the number of customers and therefore discrete. Such a discrete-time Markov process with discrete values is called discrete-time Markov chain.

For the M/GI/1 and GI/M/1 delay systems, the method of embedded Markov chain is used which provides a DTMC. A recursive equation which determines the state probability vector $\vec{X}_{n+1}$ of the next embedding point out of the current state probability vector $\vec{X}_{n}$:

$\vec{X}_{n+1} = \vec{X}_{n} \cdot \matrix{P}$ ( general state transition equation )

which uses the transition probability matrix $\matrix{P}$.

## Power Method¶

A numerical robust method to derive the steady state probabilities $\vec{X}$ for DTMC is the power method. Starting from an initial vector for state probabilities $\vec{X}_{0}$ and using the general state transition equation to numerically determine the state vectors $\vec{X}_{1}, \dots, \vec{X}_{n}, \vec{X}_{n+1}$ at the embedding times $t_{1}, \ldots, t_{n}$, $t_{n+1}$, until the steady state is reached.

In practice, the statistical equilibrium is considered as reached by a predefined termination condition (e.g. if $|E[X(t_{n + 1})] - E[X(t_n)]| < \epsilon=10^{-6}$) which is checked after each iteration step. This power method is a numerically robust method for the analysis of state probabilities.

A requirement for the numerical computation in practice is a finite number of states.

## Transition Matrix¶

We define a transition matrix $\matrix{P}$ (which corresponds to an M/GI/1 delay system with certain parameters, see the next notebook). The row-wise sum is one.

## Visualization of the Power Method Iterations¶

The system is initialized with an empty system through proper definition of $X_0$. Then the iteration is conducted for several times and the resulting state probabilities at the embedding time instants are depicted.

## Implementation of the Power Method¶

### Stop Condition¶

Now, the iteration is continued until a certail stop condition is fulfilled. Typical examples for stop conditions are as follows.

• difference of means: $\left|E[X_{n+1}] - E[X_{n}] \, \right| < \epsilon$
• difference of standard deviations: $\left|Std[X_{n+1}] - Std[X_{n}] \, \right| < \epsilon$
• or combinations of means and standard deviations, or ...

### Power Method Definition¶

The implemenation of the power method is straightforward. It requires the start condition $X_0$ and the transition matrix $\mathcal{P}$ as well as a stopping condition.

### Example¶

Two different stop conditions are used and the resulting system state probabilities at embedding time instants are plotted.