2 Probability Theory 2 Probability Theory 2.2 Exact Formula for Asymptotic Convergence of Fourier Transform of Uniform Random Variables

2.1 Entropy of Uniformly Quantized Random Variables

This is a consolidated post containing three former posts on the entropy of uniformly quantized random variables.

2.1.1 Entropy of Uniformly Quantized Exponential Distribution

This post is about entropy of discrete stochastic variables that are derived by quantizing continuous stochastic variables. A good introduction to the concept of entropy in Information Theory is in [5].

Let $x\in\{0\}\cup\mathbb{R}^{+}$ be a continuous stochastic variable with $\text{Exponential}(\lambda)$ distribution and let $\hat{x}\in\{0\}\cup\hat{X}$ such that $\hat{X}\subset\mathbb{R}^{+}$ be its uniformly quantized version with step size $\Delta$ . We would like to find the entropy of the discrete stochastic variable $\hat{x}$ , denoted by $H_{\hat{x}}$ , which provides us an estimate of the average number of bits required to encode $\hat{x}$ .

For the continuous stochastic variable $x$ , entropy is not generally defined. However, differential entropy, denoted by $h_{x}$ , plays the same role as entropy for discrete stochastic variables. A well known approximation relating differential entropy of a variable and the entropy of its quantized version is given as follows.

\displaystyle H_{\hat{x}}\approx h_{x}-\log\Delta

(2.1)

Unfortunately, this approximation is only valid for small values of $\Delta$ and breaks down as $\Delta$ increases. For example, for the common case of $\Delta=1$ , the approximation predicts the differential entropy and entropy of the quantized variable to be equal. This is generally not the case.

A common workaround is to use numerical simulations to calculate the $H_{\hat{x}}$ . However, it would be satisfying to have an analytical expression notwithstanding its practical use. As we shall see below, the expression turns out to be quite cumbersome.

Let $\varphi(x)$ and $f(\hat{x})$ denote the probability density and mass functions of $x$ and $\hat{x}$ respectively. They are related as

\displaystyle f(\hat{x})=\int_{\hat{x}-[\hat{x}\neq 0]\frac{\Delta}{2}}^{\hat{% x}+\frac{\Delta}{2}}\varphi(x)dx

(2.2)

. The indicator function $[\hat{x}\neq 0]$ is $0$ when $\hat{x}=0$ and $1$ otherwise, and serves to set the lower bound correctly.

Now onto calculating the negative entropy $-H_{\hat{x}}$ which is given (by definition) as follows. The motivation behind using negative entropy instead of entropy is to avoid (many) negative signs on the right hand side expression.

$\displaystyle-H_{\hat{x}}$	$\displaystyle=\sum_{\hat{x}\in\{0\}\cup\hat{X}}f(\hat{x})\log f(\hat{x})$	(2.3)
	$\displaystyle=\left(\int_{0}^{\frac{\Delta}{2}}\varphi(x)dx\right)\log\left[% \int_{0}^{\frac{\Delta}{2}}\varphi(x)dx\right]$
	$\displaystyle\quad+\sum_{\hat{x}\in\hat{X}}\left(\int_{\hat{x}-\frac{\Delta}{2% }}^{\hat{x}+\frac{\Delta}{2}}\varphi(x)dx\right)\log\left[\int_{\hat{x}-\frac{% \Delta}{2}}^{\hat{x}+\frac{\Delta}{2}}\varphi(x)dx\right]$	(2.4)

Using the definition of the continuous distribution function for Exponential distribution, $\varphi(x)=\lambda e^{-\lambda x}$ , the above equation is simplified as follows.

$\displaystyle-H_{\hat{x}}$	$\displaystyle=\left(1-e^{-\lambda\frac{\Delta}{2}}\right)\log\left[1-e^{-% \lambda\frac{\Delta}{2}}\right]$
	$\displaystyle\quad+\left(e^{\lambda\frac{\Delta}{2}}-e^{-\lambda\frac{\Delta}{% 2}}\right)\log\left[e^{\lambda\frac{\Delta}{2}}-e^{-\lambda\frac{\Delta}{2}}% \right]u_{1}(\lambda)$
	$\displaystyle\quad+\left(e^{\lambda\frac{\Delta}{2}}-e^{-\lambda\frac{\Delta}{% 2}}\right)u_{2}(\lambda)$	(2.5)

With the functions $u_{1,2}(\lambda)$ given by:

	$\displaystyle u_{1}(\lambda)$	$\displaystyle=\sum_{\hat{x}\in\hat{X}}e^{-\lambda\hat{x}}$		(2.6)
	$\displaystyle u_{2}(\lambda)$	$\displaystyle=\sum_{\hat{x}\in\hat{X}}e^{-\lambda\hat{x}}\log e^{-\lambda\hat{% x}}$		(2.7)

Approximate Result

The exact values of $u_{1,2}(\lambda)$ , as we shall see below, are cumbersome. Therefore, we first obtain an approximate result by plugging in the the approximations for $u_{1,2}(\lambda)$ given below into equation (2.5).

	$\displaystyle u_{1}(\lambda)$	$\displaystyle=\frac{1}{\lambda}\sum_{\hat{x}\in\hat{X}}\lambda e^{-\lambda\hat% {x}}\approx\frac{1}{\lambda}\left[\int_{0}^{\infty}\varphi(x)dx-\varphi(0)% \right]=\frac{1}{\lambda}-1$		(2.8)
	$\displaystyle u_{2}(\lambda)$	$\displaystyle=\sum_{\hat{x}\in\hat{X}}e^{-\lambda\hat{x}}\log e^{-\lambda\hat{% x}}\approx-\frac{h_{x}}{\lambda}-\log(\lambda)-\log(\lambda)u_{1}(\lambda)$		(2.9)

The performance of the above approximation may be verified numerically. In the graph below, we hold quantization step size constant at $\Delta=1$ and vary the parameter $\lambda$ . We observe that the approximation is acceptable, i.e. bit difference ¡ 1, for the range $0<\lambda\leq 1.5$ . For higher values of $\lambda$ , the approximation fails.

Exact Result

The exact result, from the graph above, may be obtained by plugging in the exact values for $u_{1,2}(\lambda)$ into equation (2.5). The exact values may be computed starting from the following identities.

$\displaystyle 1$	$\displaystyle=\int_{0}^{\infty}\varphi(x)dx=\int_{0}^{\frac{\Delta}{2}}\varphi% (x)dx+\sum_{\hat{x}\in\hat{X}}\int_{\hat{x}-\frac{\Delta}{2}}^{\hat{x}+\frac{% \Delta}{2}}\varphi(x)dx$	(2.10)
$\displaystyle-h_{x}$	$\displaystyle=\int_{0}^{\infty}\varphi(x)\log\varphi(x)dx$
	$\displaystyle=\int_{0}^{\frac{\Delta}{2}}\varphi(x)\log\varphi(x)dx+\sum_{\hat% {x}\in\hat{X}}\int_{\hat{x}-\frac{\Delta}{2}}^{\hat{x}+\frac{\Delta}{2}}% \varphi(x)\log\varphi(x)dx$	(2.11)

As the derivation is lengthy, we directly present the simplified result below.

	$\displaystyle u_{1}(\lambda)$	$\displaystyle=\frac{e^{-\lambda\frac{\Delta}{2}}}{e^{\lambda\frac{\Delta}{2}}-% e^{-\lambda\frac{\Delta}{2}}}$		(2.12)
	$\displaystyle u_{2}(\lambda)$	$\displaystyle=\frac{-h_{x}-c_{1}-\frac{\Delta}{2}\lambda\left[e^{\lambda\frac{% \Delta}{2}}+e^{-\lambda\frac{\Delta}{2}}\right]u_{1}(\lambda)}{e^{\lambda\frac% {\Delta}{2}}-e^{-\lambda\frac{\Delta}{2}}}$		(2.13)

Where $c_{1}=log(\lambda)-1+\frac{\Delta}{2}\lambda e^{-\lambda\frac{\Delta}{2}}$ . We see that even with a simple distribution function, the exact expressions quickly get out of hand and are unfortunately not short and elegant as one would have expected.

Version History

1.

First published: 3rd Oct. 2015 on aravindhk-math.blogspot.com
2.

Modified: 16th Dec. 2023 – Style updates for LaTeX

2.1.2 Entropy of Uniformly Quantized Laplace and Half-Laplace Distributions

Let $x\in\mathbb{R}$ be a continuous stochastic variable with $\text{Laplace}(0,b)$ distribution and let $\hat{x}\in\hat{X}$ such that $\hat{X}\subset\mathbb{R}$ and $0\in\hat{X}$ be its uniformly quantized version with step size $\Delta$ . We would like to find the entropy of the discrete stochastic variable $\hat{x}$ , denoted by $H_{\hat{x}}$ , which provides us an estimate of the average number of bits required to encode $\hat{x}$ .

Half-Laplace Distribution

Half-Laplace distribution refers to the distribution obtained by folding the zero-mean distribution function along the center. The new distribution is equivalent to the distribution of the stochastic variable $y=|x|$ , i.e. the absolute value of the original Laplace distributed variable.

Let $\varphi(x)$ and $\Phi(x)$ denote the probability distribution function and cumulative distribution function of the Laplace variable $x$ . These are defined as follows.

	$\displaystyle\varphi(x)$	$\displaystyle=\frac{1}{2b}e^{-\frac{\|x\|}{b}}$		(2.14)
	$\displaystyle\Phi(x)$	$\displaystyle=\begin{cases}\frac{1}{2}e^{\frac{x}{b}}&\text{if $x<0$}\\ 1-\frac{1}{2}e^{-\frac{x}{b}}&\text{if $x\geq 0$}\end{cases}$		(2.15)

The half-Laplace cumulative distribution function of $y$ , denoted by $\breve{\Phi}(y)$ , is then given as follows.

	$\displaystyle\breve{\Phi}(y)$	$\displaystyle=\begin{cases}0&\text{if $y=0$}\\ \Phi(y)-\Phi(-y)&\text{if $y>0$}\end{cases}$		(2.16)
		$\displaystyle=1-e^{-\frac{y}{b}}$		(2.17)

The expression in equation (2.17) may be directly recognized as the cumulative distribution function of $\text{Exponential}(1/b)$ . Therefore, the entropy of half-Laplace distribution may be found according to the expressions in Section 2.1.1 with $\lambda=1/b$ .

Laplace Distribution

Let $f(\hat{x})$ denote the probability mass function of the quantized variable $\hat{x}$ . It is related to the probability density function $\varphi(x)$ as follows.

\displaystyle f(\hat{x})=\int_{\hat{x}-\frac{\Delta}{2}}^{\hat{x}-\frac{\Delta% }{2}}\varphi(x)dx

(2.18)

Further, let $\hat{X}{}^{+}\subset\hat{X}$ such that it contains the positive quantized values. The negative entropy $-H_{\hat{x}}$ is given (by definition) as follows. Note that the simplification is possible due to the symmetry of Laplace distribution.

	$\displaystyle-H_{\hat{x}}$	$\displaystyle=\sum_{\hat{x}\in\hat{X}}f(\hat{x})\log f(\hat{x})$		(2.19)
		$\displaystyle=f(0)\log f(0)+2\sum_{\hat{x}\in\hat{X}{}^{+}}f(\hat{x})\log f(% \hat{x})$		(2.20)

By using the definition from equation (2.18) we have the following:

$\displaystyle-H_{\hat{x}}$	$\displaystyle=\left(1-e^{-\frac{\Delta}{2b}}\right)\log\left[1-e^{-\frac{% \Delta}{2b}}\right]$
	$\displaystyle\quad+\left(e^{\frac{\Delta}{2b}}-e^{-\frac{\Delta}{2b}}\right)% \log\left[\frac{1}{2}\left(e^{\frac{\Delta}{2b}}-e^{-\frac{\Delta}{2b}}\right)% \right]v_{1}(b)$
	$\displaystyle\quad+\left(e^{\frac{\Delta}{2b}}-e^{-\frac{\Delta}{2b}}\right)v_% {2}(b)$	(2.21)

With the functions $v_{1,2}(b)$ given by:

	$\displaystyle v_{1}(b)$	$\displaystyle=\sum_{\hat{x}\in\hat{X}{}^{+}}e^{-\frac{\hat{x}}{b}}$		(2.22)
	$\displaystyle v_{2}(b)$	$\displaystyle=\sum_{\hat{x}\in\hat{X}{}^{+}}e^{-\frac{\hat{x}}{b}}\log e^{-% \frac{\hat{x}}{b}}$		(2.23)

Exact Result

The analytical expressions for $v_{1,2}(b)$ may be computed starting from the following identities.

$\displaystyle 1$	$\displaystyle=\int_{-\infty}^{\infty}\varphi(x)dx=2\int_{0}^{\frac{\Delta}{2}}% \varphi(x)dx+2\sum_{\hat{x}\in\hat{X}{}^{+}}\int_{\hat{x}-\frac{\Delta}{2}}^{% \hat{x}+\frac{\Delta}{2}}\varphi(x)dx$	(2.24)
$\displaystyle-h_{x}$	$\displaystyle=\int_{-\infty}^{\infty}\varphi(x)\log\varphi(x)dx$
	$\displaystyle=2\int_{0}^{\frac{\Delta}{2}}\varphi(x)\log\varphi(x)dx+2\sum_{% \hat{x}\in\hat{X}{}^{+}}\int_{\hat{x}-\frac{\Delta}{2}}^{\hat{x}+\frac{\Delta}% {2}}\varphi(x)\log\varphi(x)dx$	(2.25)

Where $h_{x}$ is the differential entropy. Upon simplification, we obtain the following results.

	$\displaystyle v_{1}(b)$	$\displaystyle=\frac{e^{-\frac{\Delta}{2b}}}{e^{\frac{\Delta}{2b}}-e^{-\frac{% \Delta}{2b}}}$		(2.26)
	$\displaystyle v_{2}(b)$	$\displaystyle=\frac{-h_{x}-c_{1}-\frac{\Delta}{2b}\left[e^{\frac{\Delta}{2b}}+% e^{-\frac{\Delta}{2b}}\right]v_{1}(b)}{e^{\frac{\Delta}{2b}}-e^{-\frac{\Delta}% {2b}}}$		(2.27)

Where $c_{1}=log\left(\frac{1}{2b}\right)-1+\frac{\Delta}{2b}e^{-\frac{\Delta}{2b}}$ .

We see that the expressions are quite similar to the ones obtained for Exponential distribution in Section 2.1.1. This is expected as Laplace and Exponential distributions are very closely related.

Version History

1.

First published: 5th Oct. 2015 on aravindhk-math.blogspot.com
2.

Modified: 16th Dec. 2023 – Style updates for LaTeX

2.1.3 Entropy of Sign-Magnitude Coding of Uniformly Quantized Laplacian Variables

This is the third post in series discussing uniform quantization of Laplacian stochastic variables and is about entropy of separately coding sign and magnitude of uniformly quantized Laplacian variables.

We begin by showing that the distribution of the magnitude of uniformly quantized Laplacian variable is the same as the distribution of uniformly quantized magnitude of the Laplacian variable which is shown in Section 2.1.2 to be equivalent to the distribution of a corresponding uniformly quantized Exponential variable.

Let $\hat{x}$ be the uniformly quantized version, with step size $\Delta$ , of a Laplacian variable $x$ with $\text{Laplace}(0,b)$ distribution and let $\hat{m}$ and $\hat{s}$ be the variables denoting magnitude and sign of $\hat{x}$ respectively. We have $\hat{m}=|\hat{x}|\in\{0,\mathbb{Z}^{+}\}$ and $\hat{s}=\text{sign}(\hat{x})\in\{-1,0,+1\}$ .

Let $f_{\hat{x}}(\hat{x})$ and $\Phi_{\hat{x}}(\hat{x})$ denote the probability mass function and cumulative distribution function of $\hat{x}$ respectively. These are given as follows.

	$\displaystyle f_{\hat{x}}(\hat{x})$	$\displaystyle=\begin{cases}1-e^{-\frac{\Delta}{2b}}&\text{if $\hat{x}=0$}\\ \frac{1}{2}e^{-\frac{\|\hat{x}\|}{b}}\left(e^{\frac{\Delta}{2b}}-e^{-\frac{% \Delta}{2b}}\right)&\text{otherwise}\end{cases}$		(2.28)
	$\displaystyle\Phi_{\hat{x}}(\hat{x})$	$\displaystyle=\begin{cases}\frac{1}{2}e^{\frac{\hat{x}}{b}}e^{\frac{\Delta}{2b% }}&\text{if $\hat{x}<0$}\\ 1-\frac{1}{2}e^{\frac{\hat{x}}{b}}e^{-\frac{\Delta}{2b}}&\text{if $\hat{x}\geq 0% $}\end{cases}$		(2.29)

The cumulative distribution function $\Phi_{\hat{m}}(\hat{m})$ of the discrete variable $\hat{m}$ is given as follows

\displaystyle\Phi_{\hat{m}}(\hat{m})=\Phi_{\hat{x}}(\hat{m})-\Phi_{\hat{x}}(-% \hat{m}_{+1})

(2.30)

where $\hat{m}_{+1}=\hat{m}+\Delta$ denotes the quantization point immediately succeeding $\hat{m}$ . Substituting the value of $\Phi_{\hat{x}}(\hat{x})$ from above we have

\displaystyle\Phi_{\hat{m}}(\hat{m})

\displaystyle=1-e^{-\frac{\hat{m}}{b}}e^{-\frac{\Delta}{2b}}

(2.31)

which can be readily seen as the cumulative distribution function of a uniformly quantized Exponential variable $\text{Exponential}(1/b)$ quantized with step size $\Delta$ . Therefore, the entropy of $\hat{m}$ , denoted by $H_{\hat{m}}$ , is as given in Section 2.1.1 . Note that a generic version of the above equivalence may be proven for distributions symmetric around zero.

Next, we find the entropy of the stochastic variable denoting the sign $\hat{s}$ which takes values from the set $\hat{S}=\{+1,0,-1\}$ . Let $f_{\hat{s}}(\hat{s})$ denote the probability mass function of the discrete variable $\hat{s}$ . It is given as follows.

\displaystyle f_{\hat{s}}(\hat{s})=\begin{cases}1-e^{-\frac{\Delta}{2b}}&\text% {if $\hat{s}=0$}\\ \frac{1}{2}e^{-\frac{\Delta}{2b}}&\text{if $\hat{s}=\pm 1.$}\end{cases}

(2.32)

Encoding $\hat{s}=0$ carries no more information than what is contained in $\hat{m}$ as $\hat{s}=0$ if and only if $\hat{m}=0$ . Therefore, we only need to encode the non-zero signs. The entropy of the reduced size alphabet may be computed using the theorem for general case given below.

Let $A=\{\chi_{0},\chi_{1},\cdots,\chi_{n}\}$ be a finite size coding alphabet with corresponding probabilities $P=\{p_{0},p_{1},\cdots,p_{n}\}$ . Now let $D=\{d_{0},d_{1},\cdots,d_{n}\}$ be the probabilities that symbols from $A$ are coded. That is, if $d_{i}=1$ then the i-th symbol is always coded, if $d_{i}=0.5$ then it is coded 50% of the times, and the other 50% of the times it is inferred correctly at the decoder. There are no errors in the decoding process due to the reduced alphabet size. Let

\displaystyle H_{A^{-}}=-\sum_{i=1}^{n}p_{i}d_{i}\log\left(\frac{p_{i}d_{i}}{% \sum_{j}p_{j}d_{j}}\right)

(2.33)

denote the entropy of the reduced size coding alphabet. Then $H_{A^{-}}$ may be given by the straightforward result below.

For the case above for $\hat{s}$ , we set $D=\{1,0,1\}$ , that is, we would not encode the symbol ’0’ but infer it correctly based on the value of $\hat{m}$ . We have entropy of coding $\hat{s}$ using this scheme, denoted by $H_{\hat{S}^{-}}$ , given as follows.

	$\displaystyle H_{\hat{S}^{-}}$	$\displaystyle=-2\frac{1}{2}e^{-\frac{\Delta}{2b}}\log\frac{1}{2}$
		$\displaystyle=e^{-\frac{\Delta}{2b}}\log 2$		(2.34)

Finally, using the values of entropy $H_{\hat{x}}$ and $H_{\hat{m}}$ from Sections 2.1.2 and 2.1.1 and $H_{\hat{S}^{-}}$ from above, we have the following upon simplification.

\displaystyle H_{\hat{x}}=H_{\hat{m}}+H_{\hat{S}^{-}}

(2.35)

Therefore, encoding the magnitude and the reduced sign has the same entropy as encoding the uniformly quantized Laplacian variable.

Version History

1.

First published: 29th Oct. 2015 on aravindhk-math.blogspot.com
2.

Modified: 17th Dec. 2023 – Style updates for LaTeX