# Z-Transform and Discrete Fourier Transform¶

(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

In the analysis and the numerical evaluation of analytical results for discrete-time models, transform methods for discrete-time functions play an important role, e.g. the Discrete Fourier Transform (DFT) and the associated Fast Fourier Transform (FFT).

A comparison with the definition of the Discrete Fourier Transform shows that for the class of finite distributions, the Discrete Fourier Transform can be used instead of the Z-transform.

Accordingly, the inverse Z-transform can be replaced by the inverse Discrete Fourier Transform ($DFT^{-1}$). This allows the use of efficient methods and algorithms for evaluating the Discrete Fourier Transform like the Fast Fourier Transform, which were developed in the context of signal processing.

## Z-Transform¶

The Z-transform of the distribution $x(i)$ of a non-negative discrete random variable $X$ is defined as

$\displaystyle X_{ZT}(z) = ZT\{x(i)\} = \sum_{i=0}^\infty x(i) z^{-i} = E[z^{-X}]$

In the examples, we consider a GEOM(1) distribution. Note that we need to truncate the distribution to get a finite discrete distribution which is supported by the module discreteTimeAnalysis. The Z-transform of the GEOM(1) distribution with $E[A]=\frac{1}{1-\alpha}$ is

$\displaystyle A_{ZT}(z) = \frac{1 - \alpha}{z - \alpha} \quad \text{with } \alpha = 1-\frac{1}{E[A]}$

We compare the closed form $A_{ZT}(z) = \frac{1 - \alpha}{z - \alpha} \quad \text{with } \alpha = 1-\frac{1}{E[A]}$ with the numerical Z-transform.

## Inverse Transform¶

A comparison with the definition of the Discrete Fourier Transform shows that for the class of finite distributions, the Discrete Fourier Transform can be used instead of the Z-transform. Accordingly, the inverse Z-transform can be replaced by the inverse DFT. We use the inverse discrete Fourier transform provided by numpy: numpy.fft.ifft

## Derive Sum of Random Variables using DFT¶

Let $X$ be the sum of two statistically independent discrete random variables $X_1$ and $X_2$ with corresponding distributions $x_1(i)$ and $x_2(i)$. The sum $X = X_1 + X_2$ has the distribution $x(i) = x_1(i) * x_2(i)$ based on the discrete convolution. The Z-transform turns the convolution of the distributions into a multiplication of the transforms.

$\displaystyle X_{ZT}(z) = X_{1,ZT}(z) \cdot X_{2,ZT}(z)$