Some Useful Integral Representations for Information-Theoretic Analyses

Consider the problem of guessing the realization of a random variable, which takes on values in a finite alphabet, using a sequence of yes/no questions of the form “Is $X=x_1$?”, “Is $X=x_2$?”, etc., until a positive response is provided by a party that observes the actual realization of X. Given a distribution of X, a commonly used performance metric for this problem is the expected number of guesses or, more generally, the ${\rho }^{\mathrm{th}}$ moment of the number of guesses until X is guessed successfully. When it comes to guessing random vectors, say, of length n, minimizing the moments of the number of guesses by different (deterministic or randomized) guessing strategies has several applications and motivations in information theory, such as sequential decoding, guessing passwords, etc., and it is also strongly related to lossless source coding (see, e.g., [9,10,11,12,13,19,20,21,22,32,33,34]). In this vector case, the moments of the number of guesses behave as exponential functions of the vector dimension, n, at least asymptotically, as n grows without bound. For random vectors with i.i.d. components, the best achievable asymptotic exponent of the ${\rho }^{\mathrm{th}}$ guessing moment is expressed in [9] by using the Rényi entropy of X of order $\tilde{\rho }:=\frac{1}{1+\rho }$. Arikan assumed in [9] that the distribution of X is known and analyzed the optimal deterministic guessing strategy, which orders the guesses according to nonincreasing probabilities. Refinements of the exponential bounds in [9] with tight upper and lower bounds on the guessing moments for optimal deterministic guessing were recently derived in [19]. In the sequel, we refer to randomized guessing strategies, rather than deterministic strategies, and we aim to derive exact, calculable expressions for their associated guessing moments (as is later explained in this subsection).

Let the random variable X take on values in a finite alphabet $\mathcal{X}$. Consider a random guessing strategy where the guesser sequentially submits a sequence of independently drawn random guesses according to a certain probability distribution, $\tilde{P}(·)$, defined on $\mathcal{X}$. Randomized guessing strategies have the advantage that they can be used by multiple asynchronous agents, which submit their guesses concurrently (see [33,34]).

In this subsection, we consider the setting of randomized guessing and obtain an exact representation of the guessing moment in the form of a one-dimensional integral. Let $x\in \mathcal{X}$ be any realization of X, and let the guessing distribution, $\tilde{P}$, be given. The random number, G, of independent guesses until success has the geometric distribution and so, the corresponding MGF is equal to In view of (9)–(11) and (18), for $x\in \mathcal{X}$ and non-integer $\rho >0$, with ${\alpha }_0:=1$, and for all $j\in \mathbb{N}$ In (20), ${\mathrm{Li}}_{-j}(·)$ is a polylogarithm (see, e.g., Section 25.12 in [31]), which is given by with ${\left(x\frac{\mathrm{d}}{\mathrm{d}x}\right)}^j$ denoting differentiation with respect to x and multiplication of the derivative by x, repeatedly j times. In particular, we have and so on. The function ${\mathrm{Li}}_{-j}(x)$ is a built-in function in the MATLAB and Mathematica software, which is expressed as $\mathrm{polylog}(-j,x)$. By Corollary 1, if $\rho \in (0,1)$, then (19) is simplified to Let P denote the distribution of X. Averaging over X to get the unconditional ${\rho }^{\mathrm{th}}$ moment using (23), one obtains for all $\rho \in (0,1)$, where (24) is obtained by using the substitution $z:=e^{-u}$. A suitable expression of such an integral is similarly obtained, for all $\rho >0$, by averaging (19) over X. In comparison, a direct calculation of the ${\rho }^{\mathrm{th}}$ moment gives The double sum in (25) involves a numerical computation of an infinite series, where the number of terms required to obtain a good approximation increases with $\rho$ and needs to be determined. The right-hand side of (24), on the other hand, involves integration over $[0,1]$. For every practical purpose, however, definite integrals in one or two dimensions can be calculated instantly using built-in numerical integration procedures in MATLAB, Maple, Mathematica, or any other mathematical software tools, and the computational complexity of the integral in (24) is not affected by $\rho$.

As a complement to (19) (which applies to a non-integral and positive $\rho$), we obtain that the ${\rho }^{\mathrm{th}}$ moment of the number of randomized guesses, with $\rho \in \mathbb{N}$, is equal to where (26) follows from (20) and since ${\alpha }_0=1$. By averaging over X,

To conclude, (19) and its simplification in (23) for $\rho \in (0,1)$ give calculable one-dimensional integral expressions for the ${\rho }^{\mathrm{th}}$ guessing moment with any $\rho >0$. This refers to a randomized guessing strategy whose practical advantages were further explained in [33,34]. This avoids the need for numerical calculations of infinite sums. A further simplification for $\rho \in \mathbb{N}$ is provided in (26) and (27), expressed in closed form as a function of polylogarithms.

Let $X_1,\dots ,X_n$ be i.i.d. random variables with an unknown expectation $\theta$ to be estimated, and consider the simple estimator, For given $\rho >0$, we next derive an easily-calculable expression of the ${\rho }^{\mathrm{th}}$ moment of the estimation error.

Let $D_n:={({\widehat{\theta }}_n-\theta )}^2$ and ${\rho }^{\prime }:=\frac{\rho }{2}$. By Theorem 1, if $\rho >0$ is a non-integral multiple of two, then where ${\alpha }_0:=1$, and for all $j\in \mathbb{N}$ (see (11)) By Corollary 1 and (29), if in particular $\rho \in (0,2)$, then the right-hand side of (30) is simplified to and, for all $k\in \mathbb{N}$, In view of (29)–(34), obtaining a closed-form expression for the ${\rho }^{\mathrm{th}}$ moment of the estimation error, for an arbitrary $\rho >0$, hinges on the calculation of the right side of (31) for all $u\ge 0$. To this end, we invoke the identity which is the MGF of a zero-mean Gaussian random variable with variance $\frac{1}{2u}$. Together with (31), it gives (see Appendix B.1) where X is a generic random variable with the same distribution as $X_i$ for all i.

The combination of (30)–(34) enables calculating exactly the ${\rho }^{\mathrm{th}}$ moment $\mathbb{E}\{|{\widehat{\theta }}_n{-\theta |}^{\rho }\}$, for any given $\rho >0$, in terms of a two-dimensional integral. Combining (33) and (36) yields, for all $\rho \in (0,2)$, where we have used the identity ${\int }_{-\infty }^{\infty }\frac{1}{2}{e}^{-\left|\omega \right|}\mathrm{d}\omega =1$ in the derivation of the first term of the integral on the right-hand side of (37).

As an example, consider the case where ${\{X_i\}}_{i=1}^n$ are i.i.d. Bernoulli random variables with where the characteristic function is given by Thanks to the availability of the exact expression, we can next compare the exact ${\rho }^{\mathrm{th}}$ moment of the estimation error $|{\widehat{\theta }}_n-\theta |$, with the following closed-form upper bound (see Appendix B.2) and thereby assess its tightness: which holds for all $n\in \mathbb{N}$, $\rho >0$, and $\theta \in [0,1]$, with

Figure 1 and Figure 2 display plots of $\mathbb{E}|{\widehat{\theta }}_n-\theta |$ as a function of $\theta$ and n, in comparison to the upper bound (40). The difference in the plot of Figure 1 is significant except for the boundaries of the interval $[0,1]$, where both the exact value and the bound vanish. Figure 2 indicates that the exact value of $\mathbb{E}|{\widehat{\theta }}_n-\theta |$, for large n, scales like $\sqrt{n}$; this is reflected by the apparent parallelism of the curves in both graphs and by the upper bound (40).

To conclude, this subsection provides an exact, double-integral expression for the ${\rho }^{\mathrm{th}}$ moment of the estimation error of the expectation of n i.i.d. random variables. In other words, the dimension of the integral does not increase with n, and it is a calculable expression. We further compare our expression with an upper bound that stems from concentration inequalities. Although the scaling of the bound as a polynomial of n is correct, the difference between the exact expression and the bound is significant (see Figure 1 and Figure 2).

Generalized Cauchy distributions, their mathematical properties, and applications are of interest (see, e.g., [6,35,36,37]). The Shannon differential entropy of a family of generalized Cauchy distributions was derived in Proposition 1 in [36], and also, a lower bound on the differential entropy of a family of extended multivariate Cauchy distributions (cf. Equation (42) in [37]) was derived in Theorem 6 in [37]. Furthermore, an exact single-letter expression for the differential entropy of the different family of extended multivariate Cauchy distributions was recently derived in Section 3.1 in [6]. Motivated by these studies, as well as the various information-theoretic applications of Rényi information measures, we apply Theorem 1 to obtain the Rényi (differential) entropy of an arbitrary positive order $\alpha$ for the extended multivariate Cauchy distributions in Section 3.1 in [6]. As we shall see in this subsection, the integral representation for the Rényi entropy of the latter family of extended multivariate Cauchy distributions is two-dimensional, irrespective of the dimension n of the random vector.

Let $X^n=(X_1,\dots ,X_n)$ be a random vector whose probability density function is of the form for a certain function $g:\mathbb{R}\to [0,\infty )$ and a positive constant q such that We refer to this kind of density (see also Section 3.1 in [6]) as a generalized multivariate Cauchy density because the multivariate Cauchy density function is the special case pertaining to the choices $g(x)=x^2$ and $q=\frac{1}{2}(n+1)$. The differential Shannon entropy of the generalized multivariate Cauchy density was derived in Section 3.1 in [6] using the integral representation of the logarithm (1), where it was presented as a two-dimensional integral.

We next extend the analysis of [6] to differential Rényi entropies of an arbitrary positive order $\alpha$ (recall that the differential Rényi entropy is specialized to the differential Shannon entropy at $\alpha =1$ [38]). We show that, for the generalized multivariate Cauchy density, the differential Rényi entropy can be presented as a two-dimensional integral, rather than an n-dimensional integral. Defining we get from (42) (see Section 3.1 in [6]) that For $g(x)={\left|x\right|}^{\theta }$, with a fixed $\theta >0$, (44) implies that In particular, for $\theta =2$ and $q=\frac{1}{2}(n+1)$, we get the multivariate Cauchy density from (42). In this case, it follows from (46) that $Z(t)=\sqrt{\frac{\pi }{t}}$ for $t>0$, and from (45)

For $\alpha \in (0,1)\cup (1,\infty )$, the (differential) Rényi entropy of order $\alpha$ is given by Using the Laplace transform relation, we obtain that, for $\alpha >1$ (see Appendix C), If $\alpha \in (0,1)$, we distinguish between the following two cases:

The proof of the integral expressions of the Rényi entropy of order $\alpha \in (0,1)$, as given in (50)–(54), is provided in Appendix C.

Once again, the advantage of these expressions, which do not seem to be very simple (at least on the face of it), is that they only involve one- or two-dimensional integrals, rather than an expression of an n-dimensional integral (as it could have been in the case of an n-dimensional density).

Consider a channel that is fed by an input vector $X^n=(X_1,\dots ,X_n)\in {\mathcal{X}}^n$ and generates an output vector $Y^n=(Y_1,\dots ,Y_n)\in {\mathcal{Y}}^n$, where $\mathcal{X}$ and $\mathcal{Y}$ are either finite, countably infinite, or continuous alphabets, and ${\mathcal{X}}^n$ and ${\mathcal{Y}}^n$ are their $n^{\mathrm{th}}$ order Cartesian powers. Let the conditional probability distribution of the channel be given by where $r_{Y|X}(·|·)$ and $q_{Y|X}(·|·)$ are given conditional probability distributions of Y given X, $x^n=(x_1,\dots ,x_n)\in {\mathcal{X}}^n$ and $y^n=(y_1,\dots ,y_n)\in {\mathcal{Y}}^n$. This channel model refers to a discrete memoryless channel (DMC), which is nominally given by where one of the transmitted symbols is jammed at a uniformly distributed random time, i, and the transition distribution of the jammed symbol is given by $r_{Y|X}(y_i|x_i)$ instead of $q_{Y|X}(y_i|x_i)$. The restriction to a single jammed symbol is made merely for the sake of simplicity, but it can easily be extended.

We wish to evaluate how the jamming affects the mutual information $I(X^n;Y^n)$. Clearly, when one talks about jamming, the mutual information is decreased, but this is not part of the mathematical model, where the relation between r and q has not been specified. Let the input distribution be given by the product form The mutual information (in nats) is given by For the simplicity of notation, we henceforth omit the domains of integration whenever they are clear from the context. We have, By using the logarithmic expectation in (15) and the following equality (see (55) and (56)): we obtain (see Appendix D.1) where, for $u\ge 0$, Moreover, owing to the product form of $q_n$, it is shown in Appendix D.2 that Combining (60), (62), and (65), we express $h(Y^n|X^n)$ as a double integral over $\mathcal{X}\times \mathcal{Y}$, independently of n (rather than an integration over ${\mathcal{X}}^n\times {\mathcal{Y}}^n$):

We next calculate the differential channel output entropy, $h(Y^n)$, induced by $p_{Y^n|X^n}(·|·)$. From Appendix D.3, where, for all $y\in \mathcal{Y}$,

By (1), the following identity holds for every positive random variable Z (see Appendix D.3): where $M_Z(u):=\mathbb{E}\{e^{uZ}\}$. By setting $Z:=\frac{1}{n}{\sum }_{i=1}^n\frac{w(V_i)}{v(V_i)}$ where ${\{V_i\}}_{i=1}^n$ are i.i.d. random variables with the density function v, some algebraic manipulations give (see Appendix D.3) where Combining (58), (66), and (71), we obtain the mutual information for the channel with jamming, which is given by

We next exemplify our results in the case where q is a binary symmetric channel (BSC) with crossover probability $\delta \in (0,\frac{1}{2})$ and p is a BSC with a larger crossover probability, $\epsilon \in (\delta ,\frac{1}{2}]$. We assume that the input bits are i.i.d. and equiprobable. The specialization of our analysis to this setup is provided in Appendix D.4, showing that the mutual information of the channel $p_{X^n,Y^n}$, fed by the binary symmetric source, is given by where $H_{\mathrm{b}}:[0,1]\to [0,ln2]$ is the binary entropy function with the convention that $0ln0=0$, and denotes the binary relative entropy. By the data processing inequality, the mutual information in (75) is smaller than that of the BSC with crossover probability $\delta$:Figure 3 refers to the case where $\delta ={10}^{-3}$ and $n=128$. Here, $I_q(X^n;Y^n)=87.71\mathrm{nats}$, and $I_p(X^n;Y^n)$ is decreased by 2.88 nats due to the jammer (see Figure 3).

Figure 4 refers to the case where $\delta ={10}^{-3}$ and $\epsilon =\frac{1}{2}$ (referring to complete jamming of a single symbol, which is chosen uniformly at random), and it shows the difference in the mutual information $I(X^n;Y^n)$, as a function of the length n, between the jamming-free BSC with crossover probability $\delta$ and the channel with jamming.

To conclude, this subsection studies the change in the mutual information $I(X^n;Y^n)$ due to jamming, relative to the mutual information associated with the nominal channel without jamming. Due to the integral representations provided in our analysis, the calculation of the mutual information finally depends on one-dimensional integrals, as opposed to the original n-dimensional integrals, pertaining to the expressions that define the associated differential entropies.