# Information Spectrum Converse for Minimum Entropy Couplings and Functional
Representations

Yanina Y. Shkel∗ ${}^{\href https://orcid.org/0000-0002-2575-1762}$ $\&$ Anuj
Kumar Yadav∗${}^{\href https://orcid.org/0000-0001-7763-3787}$
($*$) : The paper follows alphabetical author order. Both the authors have
equally contributed to this work. {yanina.shkel<EMAIL_ADDRESS>
School of Computer & Communication Sciences,
École Polytechnique Fédérale de Lausanne (EPFL)
Switzerland

###### Abstract

Given two jointly distributed random variables $(X,Y)$, a functional
representation of $X$ is a random variable $Z$ independent of $Y$, and a
deterministic function $g(\cdot,\cdot)$ such that $X=g(Y,Z)$. The problem of
finding a minimum entropy functional representation is known to be equivalent
to the problem of finding a minimum entropy coupling where, given a collection
of probability distributions $P_{1},\dots,P_{m}$, the goal is to find a
coupling $X_{1},\dots,X_{m}$ ($X_{i}\sim P_{i})$ with the smallest entropy
$H_{\alpha}(X_{1},\dots,X_{m})$. This paper presents a new information
spectrum converse, and applies it to obtain direct lower bounds on minimum
entropy in both problems. The new results improve on all known lower bounds,
including previous lower bounds based on the concept of majorization. In
particular, the presented proofs leverage both - the information spectrum and
the majorization - perspectives on minimum entropy couplings and functional
representations.

###### Contents

  1. I Introduction
    1. I-A Functional Representation Lemma
    2. I-B Minimum Entropy Coupling
  2. II Preliminaries
    1. II-A Notations
    2. II-B Problem Formulation
    3. II-C Prior Work
  3. III Main Results
    1. III-A Information Spectrum Converse
    2. III-B Lower bounds on Shannon and Rényi Entropy
  4. IV Comparison of Lower Bounds
    1. IV-A Analytical Comparison
    2. IV-B Numerical Comparison
    3. IV-C Concluding Remarks
  5. V Proof of Theorem 1
  6. -A Proof of Lemma 1:
  7. -B Proof of Lemma 2 and 3
  8. -C Proof of Corollary 1:

##  I Introduction

###  I-A Functional Representation Lemma

The Functional Representation Lemma (FRL) [1] states that it is possible to
decompose a random variable $X$ into an arbitrarily correlated random variable
$Y$ and a residual random variable $Z$, independent of $Y$. More precisely,
given any pair of random variables $(X,Y)\sim P_{XY}$, there exists a random
variable $Z$, independent of $Y$ such that $X$ is a deterministic function of
$(Y,Z)$. FRL has been widely used in proving various results in multi-user
information theory [2, 3, 4], privacy and secrecy [5], and entropic causal
inference [6, 7].

Several properties of functional representations have been studied in the
literature. One such property of functional representations is the mutual
information $I(X;Z)$. Bounds on $I(X;Z)$ have been studied in [4] in the form
of a strong functional representation lemma. This problem has also been
studied in [8] and [9] with applications to one-shot channel simulation with
unlimited common randomness. It has been applied to prove the result on
constrained min-max remote prediction [10] and to prove the asymptotic
achievability in Gelfand-Pinsker’s Theorem [11]. A closely related line of
work is the setting of privacy funnel function [12, 13, 14, 15, 16]. Here, the
goal is to maximize $I(X;Z)$ while enforcing the Markov chain
$Y\leftrightarrow X\leftrightarrow Z$. The motivation is to have perfect
privacy for the information $Y$ while realizing maximum information about $X$,
see [5, 15, 16] for connections with FRL.

Another important property, which is the focus of this paper, is the entropy
of the residual random variable $Z$. The minimization of $H(Z)$ has been
applied in identifying the direction of causality [6, 7], and the compression
length in a variable and fixed length secure compression [5, 17]. It could
also be applied to studying a noisy communication channel [18], if the goal is
to minimize the entropy of the noise source. Lower entropy of $Z$ also means
that less auxiliary randomness is needed to construct it from $(X,Y)$. This is
of prime importance as randomness does not come for free and various expensive
methods have been designed to generate it in practical systems [19, 20].

###  I-B Minimum Entropy Coupling

The minimum entropy coupling problem aims to find the joint distribution
$(P_{X_{1}X_{2}\cdots X_{m}})$ with minimum joint Rényi entropy
$H_{\alpha}(X_{1},X_{2},\dots,X_{m})$, given the $m$ marginal distributions
$X_{1}\sim P_{1},X_{2}\sim P_{2},\dots,X_{m}\sim P_{m}$ (see Definition 2).
This problem has been widely studied in [21, 22, 23, 24] and is closely
related to the functional representation lemma. It has been shown in [7, 24]
that finding the minimum entropy of $Z$ is the same as solving the minimum
entropy coupling problem for the marginal distributions
$\\{P_{X|Y=y}\\}_{y\in{\cal Y}}$ (see Lemma 1 and Appendix for details). Thus,
the lower bounds on $H(Z)$ provided in this paper are also lower bounds on the
joint entropy in the minimum entropy coupling problem.

Additional scenarios where the problem of minimum entropy coupling arises
include the entropic causal inference [7, 6], dimension reduction [25],
contingency tables and transportation polytopes in [26, 27] and randomness
generation [19, 20]. The computation of the minimum entropy coupling was shown
to be NP-hard in [22] and [25]. In [21], it is shown that any coupling has the
joint entropy at least $H(\land_{i=1}^{m}P_{i})$, where $\land$ denotes the
greatest lower bound with respect to the majorization of probability
distributions. A polynomial-time approximation algorithm for the construction
of coupling within $\left\lceil{\log m}\right\rceil$ bits from
$H(\land_{i=1}^{m}P_{i})$ is also provided in [21]. Li [24] improved upon the
result of [21] by providing construction of a coupling with joint entropy
being within $2-2^{2-m}$ bits from the $H(\land_{i=1}^{m}P_{i})$. Recently,
Compton [28] showed that the greedy coupling algorithm provided in [6] is
always within $\log_{2}(e)$ bits from $H(\land_{i=1}^{m}P_{i})$ which further
improves upon the result in [24] for $m>2$.

In this paper, we focus on lower bounds on the Rényi entropy $H_{\alpha}(Z)$
(or equivalently $H_{\alpha}(X_{1},X_{2},\dots,X_{m})$) for every
$\alpha\in[0,\infty)$, and prove a new converse in terms of the information
spectrum of $Z$. This converse improves upon the information spectrum converse
in [5] and the majorization converse in [21] for Rényi entropy of any order
$\alpha$. Similar results have also been recently studied in a parallel work
by Compton et. al in [29] (see Remark 1 for details).

The rest of the paper is organized as follows. In Section II, we state our
notation, formulate the problem, and review the known lower bounds. We present
our main results in Section III. In Section IV, we compare all the lower
bounds and make concluding remarks. Finally, we postpone some of the proofs to
Section V and the Appendix.

##  II Preliminaries

###  II-A Notations

We denote the probability mass function (PMF) of a random variable using a
capital letter, say $P$, while the probability of an event is denoted using
the bold-face letter $\mathbb{P}$ and the expectation of a random variable is
denoted with $\mathbb{E}$. Given a random variable $X$, its support (and sets
in general) is denoted by ${\cal X}$, while a realization is denoted by lower
case letter, for example, $x\in{\cal X}$. The information of a random variable
$X$ is

$\displaystyle\imath_{X}(x):=\log\frac{1}{P_{X}(x)}\quad\forall x\in{\cal X},$
(1)

where all logarithms have base two unless specified otherwise. The bold-face
$\mathbb{F}_{X}$ denotes the cumulative distribution function (CDF) of $X$.
With some abuse of notation, we use $\mathbb{F}_{\imath_{X}}$ to denote the
CDF of the information $\imath_{X}(X)$ of $X$; $\mathbb{F}_{\imath_{X}}$ is
also known as the information spectrum of $X$. Recall that the Shannon entropy
of a random variable $X$ can be written as

$\displaystyle H(X)=\mathbb{E}\left[\imath_{X}(X)\right].$ (2)

Similarly, the Rényi entropy of $X$ can be written as

$\displaystyle H_{\alpha}(X)$
$\displaystyle=\frac{1}{1-\alpha}\log\left(\mathbb{E}\left[2^{(1-\alpha)\imath_{X}(X)}\right]\right)$
(3)

for $\alpha\in[0,1)\cup(1,\infty)$ and $H_{\alpha}(X):=H(X)$ for $\alpha=1$.
Given a random variable $X$ with PMF $P_{X}$ we also use the notation
$H(P_{X})$ and $H_{\alpha}(P_{X})$ to denote $H(X)$ and $H_{\alpha}(X)$.

Given two PMFs $P=(p_{1},p_{2},\cdots)$ and $Q=(q_{1},q_{2},\cdots)$ with
countably infinite supports, let the probability masses for both be given in
non-increasing order, that is $p_{1}\geq p_{2}\dots$ and $q_{1}\geq
q_{2}\dots$. Then, we say that the distribution $P$ majorizes $Q$, or
$Q\preceq_{m}P$, if

$\displaystyle\sum_{i=1}^{k}q_{i}\leq\sum_{i=1}^{k}p_{i}$ (4)

for all $k\in\\{1,2,\dots\\}$. In the case that $P$ and $Q$ have finite
supports with different cardinalities, we apply the same definition by padding
both the PMFs with zeros.

###  II-B Problem Formulation

Consider two jointly distributed random variables $(X,Y)\sim P_{XY}$ taking
values in a countable set ${\cal X}$ and a finite set ${\cal Y}$,
respectively. Recall that the Functional Representation Lemma [1, 5, 4] says
that there exists a random variable $Z$ taking values in some set ${\cal Z}$,
such that

  1. 1.

$X$ is a deterministic function of $Y$ and $Z$ i.e.,

$\displaystyle H(X|Y,Z)=0$ (5)

  2. 2.

$Y$ and $Z$ are independent of each other i.e.,

$\displaystyle I(Y;Z)=0.$ (6)

In other words, $X$ can be represented as a deterministic function of two
independent random variables $Y$ and $Z$.

######  Definition 1 (Minimum Entropy Functional Representation).

The minimum Rényi entropy of functional representation of $(X,Y)\sim P_{XY}$
is

$\displaystyle{H}^{\star}_{\alpha}(P_{XY}):=\inf_{P_{Z|XY}\colon\begin{subarray}{c}H(X|Y,Z)=0,\\\
I(Y;Z)=0\end{subarray}}H_{\alpha}(Z)$ (7)

for $\alpha\in[0,\infty)$.

The coupling of $m$ PMFs $P_{1},P_{2},\dots,P_{m}$ refers to a joint
distribution of $P_{X_{1}X_{2}\cdots X_{m}}$ subject to the constraints
$X_{i}\sim P_{i}$ for all $i\in\\{1,2,\dots,m\\}$.

######  Definition 2 (Minimum Entropy Coupling).

The minimum Rényi entropy of a coupling of a set of PMFs is

$\displaystyle H^{\ast}_{\alpha}(P_{1},\dots$
$\displaystyle,P_{m})\\!:=\\!\inf_{P_{X_{1}X_{2}\cdots X_{m}}\colon{X_{i}}\sim
P_{i}}H_{\alpha}(X_{1},\dots,X_{m})$ (8)

for $\alpha\in[0,\infty)$.

######  Lemma 1.

Let $(X,Y)\sim P_{XY}$ be jointly distributed random variables with ${\cal
Y}=\\{y_{1},\dots,y_{m}\\}$. Then

$\displaystyle{H}^{\star}_{\alpha}(P_{XY})=H^{\ast}_{\alpha}(P_{X|Y=y_{1}},\dots,P_{X|Y=y_{m}}).$
(9)

That is, the problem of finding the functional representation with the minimum
entropy is a minimum entropy coupling problem.

###### Proof.

The lemma is proved in [6, 24]. For the sake of completeness, the proof is
presented in the Appendix. ∎

We state all results in terms of the functional representation conditions for
the remainder of the paper. However, in light of Lemma 1, we see that the same
results also apply to the minimum entropy coupling problem.

###  II-C Prior Work

It is shown in [21] that

$\displaystyle{H}^{\star}_{\alpha}(P_{XY})\geq H_{\alpha}(\land_{y\in{\cal
Y}}P_{X|Y=y})$ (10)

where $\land$ represents the greatest lower bound with respect to
majorization, $\preceq_{m}$, of the set $\\{P_{X|Y=y}\\}_{y\in{\cal Y}}$. For
details, refer to [30, 21]. Likewise, [5, 21] independently presented the
following lower bound for $\alpha=1$,

$\displaystyle H^{\star}_{\alpha}(P_{XY})\geq\sup_{y\in{\cal
Y}}H_{\alpha}(P_{X|Y=y}).$ (11)

Although the general case is not addressed in [5, 21], this lower bound could
readily be extended to Rényi Entropy of order $\alpha\in[0,\infty)$, see
Section III and Appendix for details.

The following information spectrum converse is essentially shown in [5]. Let
$Z$ be any random variable satisfying (5) and (6). Then, for any real valued
$t\in[0,\infty)$ and $\tau>0$,

$\displaystyle\mathbb{P}[{\imath_{Z}(Z)\\!>t}]\geq$
$\displaystyle\sup_{y\in{\cal
Y}}\mathbb{P}[\imath_{X|Y}(X|Y)\\!>t\\!+\\!\tau|Y\\!=\\!y]\\!-\\!\exp(-\tau).$
(12)

Our main contribution in this work is to strengthen (12) by removing the
dependence on $\tau$, as well as to leverage this new information spectrum
converse in order to get direct lower bounds on
${H}^{\star}_{\alpha}(P_{XY})$.

##  III Main Results

###  III-A Information Spectrum Converse

######  Theorem 1.

Let $(X,Y)$ be jointly distributed random variables supported on countable
$\cal X$ and countable $\cal Y$. Consider any random variable $Z$ that
satisfies (5) and (6). Then, for any real-valued $t\in[0,\infty)$ we have,

$\displaystyle\mathbb{P}[\imath_{Z}(Z)>t]\geq\sup_{y\in{\cal
Y}}\mathbb{P}[\imath_{X|Y}(X|Y)>t|Y=y].$ (13)

The proof of Theorem 1 is given in Section V. In this paper, we focus on
countable $\cal X$ and finite $\cal Y$, though the results of Theorem 1 could
be extended to a more general setting.

In order to connect Theorem 1 to the majorization lower bound (10), we propose
a similar definition with the ordering based on the information spectrum.

######  Definition 3 ($\preceq_{\imath}$).

Consider two PMFs $P$ and $Q$ with countably infinite supports. We write
$Q\preceq_{\imath}P$, if the information spectrum of $Q$ lower bounds the
information spectrum of $P$. In other words, let $U\sim Q$ and $V\sim P$. Then

$\displaystyle\mathbb{P}\left[\imath_{U}(U)\leq
t\right]\leq\mathbb{P}\left[\imath_{V}(V)\leq t\right]$ (14)

or equivalently,

$\displaystyle\mathbb{P}\left[\imath_{U}(U)>t\right]\geq\mathbb{P}\left[\imath_{V}(V)>t\right]$
(15)

for all $t\in[0,\infty)$.

The following lemmas connect the above definition to the definition of
majorization.

######  Lemma 2.

Given two PMFs $Q$ and $P$ we have that

$\displaystyle Q\preceq_{\imath}P\Rightarrow Q\preceq_{m}P$ (16)

where $\preceq_{m}$ denotes majorization.

The proof of Lemma 2 is based on standard induction arguments, see Appendix
for details. (See also [31], where this result was independently proven.)

Note that in general, the reverse is not true: it is possible to have
$Q\preceq_{m}P$ but not $Q\preceq_{\imath}P$.

######  Lemma 3.

Let $\\{P_{1},\dots,P_{m}\\}$ be a finite collection of PMFs supported on
finite $\\{{\cal S}_{1},\dots,{\cal S}_{m}\\}$ and let

$\displaystyle{\cal F}=\\{Q\colon Q\preceq_{\imath}P_{i}\quad\forall
i\in\\{1,\dots,m\\}\\}.$ (17)

There exists $Q^{\ast}\in{\cal F}$ such that $Q\preceq_{m}Q^{\ast}$ for all
$Q\in{\cal F}$. In addition, $Q^{\ast}$ could be computed using a greedy
algorithm with complexity linear in $\sum_{i=1}^{m}|{\cal S}_{i}|$. This
result could also be extended for a countable set $\\{{\cal S}_{1},{\cal
S}_{2},\dots\\}$. We leave the complete details for future work.

The idea behind the greedy construction of $Q^{\ast}$ is as follows. We
construct $Q^{\ast}=(q^{\ast}_{1},q^{\ast}_{2},\dots)$ with $q^{\ast}_{1}\geq
q^{\ast}_{2}\dots$ in a greedy way. First, assign

$\displaystyle q^{\ast}_{1}=\min_{i\in\\{1,\dots,m\\}}\left\\{\max_{s\in{\cal
S}_{i}}P_{i}(s)\right\\}.$ (18)

This is the maximum value we can assign to $q^{\ast}_{1}$ while satisfying the
information spectrum constraint defined by $\cal F$. We continue with this
strategy: at each step $k$ we assign the maximum possible value to
$q^{\ast}_{k}$ until the total probability of all $q^{\ast}_{k}$ reaches one.
The fact that this distribution majorizes all other $Q\in{\cal F}$ is proven
using a standard induction argument. Likewise, the number of steps the
algorithm needs to take is linear in $\sum_{i=1}^{m}|{\cal S}_{i}|$, since the
constraints defined by $\cal F$ is a step function with at most steps
$\sum_{i=1}^{m}|{\cal S}_{i}|$, see the Appendix.

###  III-B Lower bounds on Shannon and Rényi Entropy

While Theorem 1 does not provide direct lower bounds on
$H^{\star}_{\alpha}(P_{XY})$, the next two corollaries could be used to
compute such lower bounds.

######  Corollary 1.

Let $(X,Y)\sim P_{XY}$ be jointly distributed random variables supported on
countable $\cal X$ and countable $\cal Y$. Then

$\displaystyle H^{\star}_{\alpha}(P_{XY})\geq K_{\alpha}(P_{XY})$ (19)

for any $\alpha\in[0,\infty)$, where

$\displaystyle K_{\alpha}(P_{XY})$
$\displaystyle:=\begin{cases}\frac{1}{1-\alpha}\log\left[1+\int_{0}^{\infty}J_{\alpha}(t)dt\right],&\text{if
}\alpha\in[0,1)\vspace{2mm}\\\ &\text{or }\alpha\in(1,\infty)\\\
\int_{0}^{\infty}G(t)dt,&\alpha=1\end{cases}$ (20) $\displaystyle\mbox{ with
}G(t)$ $\displaystyle:=\sup_{y\in{\cal Y}}\mathbb{P}[\imath_{X|Y}(X|Y)>t|Y=y]$
(21) $\displaystyle\mbox{ and }J_{\alpha}(t)$ $\displaystyle:=\ln
2(1-\alpha)G(t)2^{(1-\alpha)t}.$ (22)

###### Proof.

Theorem 1 could be restated as

$\displaystyle 1-\mathbb{F}_{\imath_{Z}}(t)\geq G(t).$ (23)

Recall that for any non-negative random variable $V$, its expectation could be
related to its CDF via

$\displaystyle\mathbb{E}[V]=\int_{0}^{\infty}(1-\mathbb{F}_{V}(t))dt,$ (24)

see, for example [32]. Since $\imath_{Z}(Z)\geq 0$, we have that

$\displaystyle H(Z)$
$\displaystyle=\mathbb{E}[\imath_{Z}(Z)]=\int_{0}^{\infty}\Big{(}1-\mathbb{F}_{\imath_{Z}}(t)\Big{)}\geq\int_{0}^{\infty}G(t)dt,$
(25)

where (25) follows from (23). Equation (19) is proved similarly for
$\alpha\in[0,1)\cup(1,\infty)$, see Appendix for details. ∎

We remark that Corollary 1 is different from all other lower bounds in this
paper in that it does not involve computing the entropy of a random variable.
For example, we compute the expectation of a random variable with CDF $1-G(t)$
in order to obtain a lower bound on Shannon entropy ($\alpha=1$). In general,
there may not be an information random variable with this CDF. The next
corollary incorporates this additional constraint in its application of
Theorem 1.

######  Corollary 2.

Let $(X,Y)$ be jointly distributed random variables supported on finite $\cal
X$ and finite $\cal Y$. Further, let the parameter $\alpha\in[0,\infty)$.
Then,

$\displaystyle H^{\star}_{\alpha}(P_{XY})\geq\inf_{Q\in{\cal
F}}H_{\alpha}(Q)=H_{\alpha}(Q^{\ast})$ (26)

where ${\cal F}=\\{Q\colon Q\preceq_{\imath}P_{X|Y=y}\forall y\in{\cal Y}\\}$
and $Q^{\ast}\in{\cal F}$ is as given in Lemma 3.

###### Proof.

The first inequality is a restatement of Theorem 1 using the relation
$\preceq_{\imath}$. According to Lemma 3, $Q^{\ast}$ majorizes every
distribution in $\cal F$. Rényi Entropy is Schur concave [33] with respect to
majorization: that is, if $Q\preceq_{m}P$ then $H_{\alpha}(Q)\geq
H_{\alpha}(P)$. Thus, $Q^{\ast}$ achieves the infimum over $\cal F$. ∎

######  Remark 1.

Additionally, Note that for $\alpha=1$, these result have also been shown in a
parallel work [29] using ‘profile method’. Our Corollary 1 and Corollary 2 are
equivalent to Theorem $3.3$ and Theorem $5.5$ in [29], respectively. The
authors also showed that these results also hold for a concave function
$F:\mathbb{R}^{d}\rightarrow\mathbb{R}$, such that
$F(p_{1},p_{2},p_{3},...,p_{n}):=\sum_{i=1}^{n}f(p_{i})$, where
$f:\mathbb{R}\rightarrow\mathbb{R}$ is a non-negative and concave function
satisfying $f(0)=0$.

##  IV Comparison of Lower Bounds

###  IV-A Analytical Comparison

The following theorem compares the lower bounds in Corollary 1 and 2 to (10)
and (11).

######  Theorem 2.

Let $(X,Y)$ be jointly distributed random variables supported on finite $\cal
X$ and finite $\cal Y$. Let

$\displaystyle{\cal F}=\\{Q\colon Q\preceq_{\imath}P_{X|Y=y}\quad\forall
y\in{\cal Y}\\},$ (27)

with $Q^{\ast}\in{\cal F}$ as in Lemma 3. Let $K_{\alpha}(P_{XY})$ be as in
Corollary 1. We make the following statements for all $\alpha\in[0,\infty)$:

  1. 1.

In general, we have that

$\displaystyle H_{\alpha}(Q^{\ast})$ $\displaystyle\geq
K_{\alpha}(P_{XY})\geq\sup_{y\in{\cal Y}}H_{\alpha}(P_{X|Y=y})$ (28)

and,

$\displaystyle H_{\alpha}(Q^{\ast})$ $\displaystyle\geq
H_{\alpha}(\land_{y\in{\cal Y}}P_{X|Y=y})$ (29)
$\displaystyle\geq\sup_{y\in{\cal Y}}H_{\alpha}(P_{X|Y=y}).$ (30)

  2. 2.

If there exists $y\in{\cal Y}$ such that
$P_{X|Y=y}\preceq_{\imath}P_{X|Y=\hat{y}}$ for all ${\hat{y}}\in{\cal Y}$,
then

$\displaystyle H_{\alpha}(Q^{\ast})$ $\displaystyle=K_{\alpha}(P_{XY})$ (31)
$\displaystyle=H_{\alpha}(\land_{y\in{\cal Y}}P_{X|Y=y})$ (32)
$\displaystyle=\sup_{y\in{\cal Y}}H_{\alpha}(P_{X|Y=y}).$ (33)

  3. 3.

If there exists $y\in{\cal Y}$ such that $P_{X|Y=y}\preceq_{m}P_{X|Y=\hat{y}}$
for all ${\hat{y}}\in{\cal Y}$, then

$\displaystyle H_{\alpha}(\land_{y\in{\cal Y}}P_{X|Y=y})=\sup_{y\in{\cal
Y}}H_{\alpha}(P_{X|Y=y}).$ (34)

In particular, in light of (28), this implies that

$\displaystyle H_{\alpha}(Q^{\ast})$ $\displaystyle\geq K_{\alpha}(P_{XY})\geq
H_{\alpha}(\land_{y\in{\cal Y}}P_{X|Y=y}).$ (35)

###### Proof.

To see (29), note that for all $y\in{\cal Y}$ we have the following relation

$\displaystyle Q^{\ast}\preceq_{m}\land_{y\in{\cal
Y}}P_{X|Y=y}\preceq_{m}P_{X|Y=y}.$ (36)

The relations holds by Lemma 2 together with $Q^{\ast}\in\cal F$, and the fact
that $\land_{y\in{\cal Y}}P_{X|Y=y}$ is the greatest lower bound with respect
to majorization. Therefore, (29) holds by Schur concavity of Rényi entropy. As
already observed in [21], (30) and (34) hold by the same application of
majorization and Schur concavity.

Let $U\sim Q^{\ast}$. We state the rest of the proof for the $\alpha=1$ case.
The other cases follow analogously. For (28), we have that

$\displaystyle H(Q^{\ast})$
$\displaystyle=\int_{0}^{\infty}\mathbb{P}[\imath_{U}(U)>t]dt$ (37)
$\displaystyle\geq\int_{0}^{\infty}\sup_{y\in{\cal
Y}}\mathbb{P}[\imath_{X|Y}(X|Y)>t|Y=y]dt$ (38)
$\displaystyle\geq\sup_{y\in{\cal
Y}}\int_{0}^{\infty}\mathbb{P}[\imath_{X|Y}(X|Y)>t|Y=y]dt$ (39)
$\displaystyle=\sup_{y\in{\cal Y}}H(P_{X|Y=y})$ (40)

where (38) follows since $Q^{\ast}\in{\cal F}$, and (37) and (40) follow from
(24). If there exists $y\in{\cal Y}$ such that
$P_{X|Y=y}\preceq_{\imath}P_{X|Y=\hat{y}}$ for all ${\hat{y}}\in{\cal Y}$ then
$P_{X|Y=y}$ will have the same information spectrum as $Q^{\ast}$, and (38)
and (39) become equalities. This shows that
$H_{\alpha}(Q^{\ast})=K_{\alpha}(P_{XY})=\sup_{y\in{\cal
Y}}H_{\alpha}(P_{X|Y=y})$. Finally, (32) holds by (34) and Lemma 2. ∎

###  IV-B Numerical Comparison

As we see in Theorem 2, the lower bound in Corollary 2 outperforms all other
lower bounds. It is not clear how Corollary 1 compares to (10), in general.
Numerical evaluations show that Corollary 1 outperforms (10) for low values of
$\alpha$, but is outperformed by (10) for high values of $\alpha$. This is
demonstrated by the following numerical example which has been carefully
chosen to highlight the nuances between the different lower bounds.

$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$1.6$$1.8$$2$$2.2$$2.4$$2.6$$2.8$$3$$3.2$$\alpha$$\text{Renyi
entropy of order }\alpha$Greedy Upper bound [6]Lower Bound in Corollary 2Lower
Bound in Corollary 1Lower Bound (10)Lower Bound (11)$\text{Min entropy
(}\alpha\text{ = }\infty\text{)}$ Figure 1: Lower bound on Rényi entropy for
the collection of distributions in Example 1. Note that Corollary 2
outperforms all the other lower bounds, while Corollary 1 outperforms (10) for
$\alpha\leq 3.445$.

######  Example 1 (Rényi entropy).

Let $(X,Y)$ be jointly distributed random variables with ${\cal
X}=\\{1,\dots,6\\}$, ${\cal Y}=\\{y_{1},y_{2},y_{3}\\}$ and the conditional
PMF,

$\displaystyle P_{X|Y}(\cdot|y_{1})$
$\displaystyle=[0.5,0.125,0.125,0.125,0.125,0]$ (41) $\displaystyle
P_{X|Y}(\cdot|y_{2})$ $\displaystyle=[0.4,0.4,0.1,0.1,0,0]$ (42)
$\displaystyle P_{X|Y}(\cdot|y_{3})$
$\displaystyle=[0.35,0.35,0.25,0.04,0.005,0.005].$ (43)

Then,

$\displaystyle\land_{y\in{\cal
Y}}P_{X|Y=y}\\!=\\![0.35,0.275,0.125,0.125,0.12,0.005],$ $\displaystyle
Q^{\ast}\\!=\\![0.35,0.15,0.125,0.125,0.1,0.1,0.04,0.005,0.005].$

The comparison of lower bounds on Rényi entropy for this example is provided
in Figure 1.

Observe that the lower bounds (10) and (11) cannot exceed $\log|{\cal X}|$
because they are limited to distribution with support size of ${\cal X}$.
Corollaries 1 and 2, however, take into account possible support size
enlargement for the functional representation variable $Z$. This can be seen
in Figure 1 for $\alpha=0$ (that is, log of the support size). This advantage
of Corollaries 1 and 2 is even more apparent for binary supported distribution
in the following example, see also Figure 2.

$0$$5\cdot
10^{-2}$$0.1$$0.15$$0.2$$0.25$$0.3$$0.35$$0.4$$0.45$$0.5$$0.4$$0.5$$0.6$$0.7$$0.8$$0.9$$1$$1.1$$1.2$$1.3$$1.4$pShannon
EntropyGreedy Upper bound [6]Lower Bound in Corollary 2Lower Bound in
Corollary 1Lower Bound (10)Lower Bound (11) Figure 2:  Lower bound on Shannon
entropy for collections of distributions (indexed by $p$) in Example 2. Note
that Corollary 2 matches the upper bound and is therefore exactly
$H_{1}^{\star}(P_{XY})$. Lower bounds (10) and (11) match for this example.

######  Example 2 (Binary Support Size).

Let $(X,Y)$ be jointly distributed random variables with $|{\cal X}|=|{\cal
Y}|=2$ and the conditional PMF,

$\displaystyle P_{X|Y}(\cdot|y_{1})$ $\displaystyle=[0.9,0.1]\mbox{ and
}P_{X|Y}(\cdot|y_{2})=[1-p,p]$ (44)

where $p\in[0,0.5]$. Then,

$\displaystyle\land_{y\in{\cal Y}}P_{X|Y=y}=\begin{cases}[0.9,0.1],&p\leq
0.1\\\ [1-p,p],&p>0.1\end{cases}$ (45)

and

$\displaystyle Q^{\ast}=\begin{cases}[0.9,0.1-p,p],&p\leq 0.1\\\
[1-p,p-0.1,0.1],&p>0.1.\end{cases}$ (46)

The comparison of lower bounds on Shannon entropy for this example is provided
in Figure 2.

###  IV-C Concluding Remarks

In order to provide context for the lower bounds in Figures 1 and 2 we include
a plot of an upper bound. A number of theoretical upper bounds are available,
see for example, [24, 21, 5, 6]. We implement the construction from [6] for
our examples. We leave the question of improved theoretical upper bounds to
future work and believe that combining information spectrum and majorization
techniques could also be a fruitful strategy for this problem.

##  V Proof of Theorem 1

###### Theorem 1.

Let’s begin by fixing a $y\in{\cal Y}$ and a real-valued $t\in[0,\infty)$.
Now, let us define

$\displaystyle{\cal X}_{y}$ $\displaystyle:=\\{x\in{\cal
X}:{P}_{X|Y}(x|y)>0\\}$ (47) $\displaystyle\mbox{ and }{\cal X}_{y,t}$
$\displaystyle:=\\{x\in{\cal X}_{y}:{P}_{X|Y}(x|y)<2^{-t}\\}$ (48)
$\displaystyle=\\{x\in{\cal X}_{y}:t<{\imath}_{X|Y}(x|y)<\infty\\}.$ (49)

Define also

$\displaystyle{\cal Z}_{t}$ $\displaystyle:=\\{z\in{\cal
Z}:{P}_{Z}(z)<2^{-t}\\}=\\{z\in{\cal Z}:{\imath}_{Z}(z)>t\\}.$ (50)

Recall that $X$ is a deterministic function of $Y$ and $Z$ i.e., for some
$g:{\cal Y}\times{\cal Z}\rightarrow{\cal X}$, we have $X=g(Y,Z)$. Further,
define ${\cal Z}_{y}(x):=\\{z\in{\cal Z}:g(y,z)=x\\}$ and observe that

$\displaystyle P_{X|YZ}(x|y,z)=\begin{cases}1&,\mbox{ if }z\in{\cal
Z}_{y}(x)\\\ 0&,\mbox{ if }z\not\in{\cal Z}_{y}(x)\end{cases}$ (51)

i.e., for $y\in{\cal Y}$ fixed as above, every element of ${\cal X}_{y}$ maps
to a disjoint subset of ${\cal Z}$. Therefore,

$\displaystyle{P}_{X|Y}(x|y)$ $\displaystyle=\sum_{z\in{\cal
Z}}P_{X|YZ}(x|y,z){P}_{Z|Y}(z|y)$ (52) $\displaystyle=\sum_{z\in{\cal
Z}_{y}(x)}P_{X|YZ}(x|y,z){P}_{Z|Y}(z|y)$ (53)
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\sum_{z\in{\cal
Z}_{y}(x)}{P}_{Z|Y}(z|y)\stackrel{{\scriptstyle(b)}}{{=}}\sum_{z\in{\cal
Z}_{y}(x)}{P}_{Z}(z).$ (54)

Eq. (52) follows by the law of total probability. Eq. (53) and (54)(a) follow
from 51, while (54)(b) follows from the fact that $Y$ and $Z$ are independent.
Putting everything together,

$\displaystyle\mathbb{P}$
$\displaystyle[\imath_{X|Y}(X|Y)>t|Y=y]=\sum_{x\in{\cal
X}_{y,t}}{P}_{X|Y}(x|y)$ (55)
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\sum_{x\in{\cal
X}_{y,t}}\sum_{z\in{\cal
Z}_{y}(x)}{P}_{Z}(z)\stackrel{{\scriptstyle(b)}}{{=}}\sum_{z\in\bigcup_{x\in{\cal
X}_{y,t}}{\cal Z}_{y}(x)}{P}_{Z}(z)$ (56)
$\displaystyle\stackrel{{\scriptstyle}}{{\leq}}\sum_{z\in{\cal
Z}_{t}}{P}_{Z}(z)\stackrel{{\scriptstyle}}{{=}}\mathbb{P}[\imath_{Z}(Z)>t].$
(57)

Eq. (56)(a) follows from (54), Eq (56)(b) follows since every element of
${\cal X}_{y}$ maps to a disjoint subset of ${\cal Z}$, Eq. (57) follows from
noting that $\forall$ $z\in\bigcup_{x\in{\cal X}_{y,t}}{\cal Z}_{y}(x)$, we
have $P_{Z}(z)<2^{-t}$ and therefore $\bigcup_{x\in{\cal X}_{y,t}}{\cal
Z}_{y}(x)\subseteq{\cal Z}_{t}$.

Thus, we have shown that

$\displaystyle\mathbb{P}\left[\imath_{Z}(Z)>t\right]\geq\mathbb{P}\left[\imath_{X|Y}(X|Y)>t|Y=y\right].$
(58)

Since (58) holds for $\forall$ $y\in{\cal Y}$, it holds for the supremum over
${\cal Y}$.
∎

## References

  * [1] A. El Gamal and Y.-H. Kim, _Network Information Theory_. Cambridge University Press, 2011.
  * [2] B. Hajek and M. Pursley, “Evaluation of an achievable rate region for the broadcast channel,” _IEEE Transactions on Information Theory_ , vol. 25, no. 1, pp. 36–46, 1979.
  * [3] F. Willems and E. van der Meulen, “The discrete memoryless multiple-access channel with cribbing encoders,” _IEEE Transactions on Information Theory_ , vol. 31, no. 3, pp. 313–327, 1985.
  * [4] C. T. Li and A. E. Gamal, “Strong functional representation lemma and applications to coding theorems,” in _2017 IEEE International Symposium on Information Theory (ISIT)_ , 2017, pp. 589–593.
  * [5] Y. Y. Shkel, R. S. Blum, and H. V. Poor, “Secrecy by design with applications to privacy and compression,” _IEEE Transactions on Information Theory_ , vol. 67, no. 2, pp. 824–843, 2021.
  * [6] M. Kocaoglu, A. Dimakis, S. Vishwanath, and B. Hassibi, “Entropic causal inference,” _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 31, no. 1, Feb. 2017. [Online]. Available: https://ojs.aaai.org/index.php/AAAI/article/view/10674
  * [7] S. Compton, K. Greenewald, D. A. Katz, and M. Kocaoglu, “Entropic causal inference: Graph identifiability,” in _Proceedings of the 39th International Conference on Machine Learning_ , ser. Proceedings of Machine Learning Research, K. Chaudhuri, S. Jegelka, L. Song, C. Szepesvari, G. Niu, and S. Sabato, Eds., vol. 162. PMLR, 17–23 Jul 2022, pp. 4311–4343. [Online]. Available: https://proceedings.mlr.press/v162/compton22a.html
  * [8] P. Harsha, R. Jain, D. McAllester, and J. Radhakrishnan, “The communication complexity of correlation,” _IEEE Trans. Inf. Theor._ , vol. 56, no. 1, p. 438–449, jan 2010. [Online]. Available: https://doi.org/10.1109/TIT.2009.2034824
  * [9] M. Braverman and A. Garg, “Public vs private coin in bounded-round information,” in _Automata, Languages, and Programming_ , J. Esparza, P. Fraigniaud, T. Husfeldt, and E. Koutsoupias, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2014, pp. 502–513.
  * [10] C. T. Li, X. Wu, A. Ozgur, and A. El Gamal, “Minimax learning for remote prediction,” in _2018 IEEE International Symposium on Information Theory (ISIT)_ , 2018, pp. 541–545.
  * [11] S. Gel’Fand, “Coding for channels with random parameters,” _Probl. Contr. Inform. Theory_ , vol. 9, no. 1, pp. 19–31, 1980.
  * [12] A. Makhdoumi, S. Salamatian, N. Fawaz, and M. Médard, “From the information bottleneck to the privacy funnel,” in _2014 IEEE Information Theory Workshop (ITW 2014)_ , 2014, pp. 501–505.
  * [13] F. d. P. Calmon, A. Makhdoumi, M. Médard, M. Varia, M. Christiansen, and K. R. Duffy, “Principal inertia components and applications,” _IEEE Transactions on Information Theory_ , vol. 63, no. 8, pp. 5011–5038, Aug 2017.
  * [14] S. Asoodeh, M. Diaz, F. Alajaji, and T. Linder, “Information extraction under privacy constraints,” _Information_ , vol. 7, no. 1, 2016. [Online]. Available: https://www.mdpi.com/2078-2489/7/1/15
  * [15] B. Rassouli and D. Gündüz, “Information-theoretic privacy-preserving schemes based on perfect privacy,” 2023. [Online]. Available: https://arxiv.org/abs/2301.11754
  * [16] A. Zamani, T. J. Oechtering, and M. Skoglund, “On the privacy-utility trade-off with and without direct access to the private data,” 2022. [Online]. Available: https://arxiv.org/abs/2212.12475
  * [17] Y. Y. Shkel and H. V. Poor, “A compression perspective on secrecy measures,” _IEEE Journal on Selected Areas in Information Theory_ , vol. 2, no. 1, pp. 163–176, 2021.
  * [18] C. E. Shannon, “A mathematical theory of communication,” _The Bell System Technical Journal_ , vol. 27, no. 3, pp. 379–423, 1948.
  * [19] D. Knuth and A. Yao, _Algorithms and Complexity: New Directions and Recent Results_. Academic Press, 1976, ch. The complexity of nonuniform random number generation.
  * [20] J. Roche, “Efficient generation of random variables from biased coins,” in _Proceedings. 1991 IEEE International Symposium on Information Theory_ , 1991, pp. 169–169.
  * [21] F. Cicalese, L. Gargano, and U. Vaccaro, “Minimum-entropy couplings and their applications,” _IEEE Transactions on Information Theory_ , vol. 65, no. 6, pp. 3436–3451, 2019.
  * [22] M. Kovačević, I. Stanojević, and V. Šenk, “On the entropy of couplings,” _Information and Computation_ , vol. 242, pp. 369–382, 2015\. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0890540115000450
  * [23] A. Painsky, S. Rosset, and M. Feder, “Memoryless representation of markov processes,” in _2013 IEEE International Symposium on Information Theory_ , 2013, pp. 2294–298.
  * [24] C. T. Li, “Efficient approximate minimum entropy coupling of multiple probability distributions,” _IEEE Transactions on Information Theory_ , vol. 67, no. 8, pp. 5259–5268, 2021.
  * [25] M. Vidyasagar, “A metric between probability distributions on finite sets of different cardinalities and applications to order reduction,” _IEEE Transactions on Automatic Control_ , vol. 57, no. 10, pp. 2464–2477, 2012.
  * [26] J. A. D. Loera and E. D. Kim, “Combinatorics and geometry of transportation polytopes: An update,” _arXiv: Combinatorics_ , 2013.
  * [27] A. Dobra and S. E. Fienberg, “Bounds for cell entries in contingency tables given marginal totals and decomposable graphs.” _Proceedings of the National Academy of Sciences of the United States of America_ , vol. 97 22, pp. 11 885–92, 2000.
  * [28] S. Compton, “A tighter approximation guarantee for greedy minimum entropy coupling,” in _2022 IEEE International Symposium on Information Theory (ISIT)_ , 2022, pp. 168–173.
  * [29] S. Compton, D. Katz, B. Qi, K. Greenewald, and M. Kocaoglu, “Minimum-entropy coupling approximation guarantees beyond the majorization barrier,” in _Proceedings of The 26th International Conference on Artificial Intelligence and Statistics_ , ser. Proceedings of Machine Learning Research, F. Ruiz, J. Dy, and J.-W. van de Meent, Eds., vol. 206. PMLR, 25–27 Apr 2023, pp. 10 445–10 469. [Online]. Available: https://proceedings.mlr.press/v206/compton23a.html
  * [30] A. W. Marshall, I. Olkin, and B. C. Arnold, “Inequalities: Theory of majorization and its applications,” 1980.
  * [31] C. T. Li, “Infinite divisibility of information,” _IEEE Transactions on Information Theory_ , vol. 68, no. 7, pp. 4257–4271, 2022.
  * [32] B. Hajek, _Random Processes for Engineers_. Cambridge University Press, 2015.
  * [33] J. E. Peari’c, F. Proschan, and Y. L. Tong, “Convex functions, partial orderings, and statistical applications,” 1992.

###  -A Proof of Lemma 1:

###### Lemma 1.

Let the set ${\cal Y}:=\\{y_{1},y_{2},y_{3},\cdots,y_{|{\cal Y}|}\\}$. Recall
that $X$ is a deterministic function of $Y$ and $Z$. Thus,

$\displaystyle X=g(Y,Z).$

For a fixed $y\in{\cal Y}$, we define the random variable $X_{y}$ as

$\displaystyle X_{y}$ $\displaystyle:=g(y,Z)$ $\displaystyle=g_{y}(Z)$

for some function $g_{y}:{\cal Z}\rightarrow{\cal X}$.
Further, note that the random variable $X_{y}$ is distributed according to
$P_{X|Y=y}$. Now,

$\displaystyle H(Z,g_{y_{1}}(Z),g_{y_{2}}(Z),\cdots,g_{y_{|{\cal Y}|}}(Z))$
$\displaystyle=H(g_{y_{1}}(Z),g_{y_{2}}(Z),\cdots,g_{y_{|{\cal Y}|}}(Z))$
$\displaystyle+H(Z|g_{y_{1}}(Z),g_{y_{2}}(Z),\cdots,g_{y_{|{\cal Y}|}}(Z)).$
(59)

Also,

$\displaystyle H(Z,g_{y_{1}}(Z),g_{y_{2}}(Z),\cdots,g_{y_{|{\cal Y}|}}(Z))$
$\displaystyle=H(Z)+H(g_{y_{1}}(Z),g_{y_{2}}(Z),\cdots,g_{y_{|{\cal
Y}|}}(Z)|Z)$ (60) $\displaystyle=H(Z).$ (61)

From (59) and (61), we have

$\displaystyle H(Z)$ $\displaystyle\geq
H(g_{y_{1}}(Z),g_{y_{2}}(Z),\cdots,g_{y_{|{\cal Y}|}}(Z))$
$\displaystyle=H(X_{y_{1}},X_{y_{2}},\cdots,X_{y_{|{\cal Y}|}})$ (62)
$\displaystyle\geq\inf_{P_{X_{1}X_{2}\cdots X_{m}}\colon{X_{i}}\sim
P_{i}}H(X_{y_{1}},X_{y_{2}},\cdots,X_{y_{|{\cal Y}|}}).$ (63)

Note that Eq. (62) holds for every random variable $Z$ satisfying (5) and (6),
and for every joint distribution of the random variables
$(X_{y_{1}},X_{y_{2}},\cdots,X_{y_{|{\cal Y}|}})$. Therefore, the best
possible lower bound on $H(Z)$ is obtained by minimizing the joint entropy
$H(X_{y_{1}},X_{y_{2}},\cdots,X_{y_{|{\cal Y}|}})$, which is equivalent to
solving the minimum entropy coupling problem given the random variables
$X_{y_{1}},X_{y_{2}},\cdots,X_{y_{|{\cal Y}|}}$ distributed according to
$P_{X|Y=y_{1}},P_{X|Y=y_{2}},\cdots,P_{X|Y=y_{|{\cal Y}|}}$, respectively.

######  Remark 2.

The above proof can be easily extended for the Rényi entropy of order
$\alpha\in[0,1)\cup(1,\infty)$.
Let $Z,g_{y_{1}}(Z),g_{y_{2}}(Z),\cdots,g_{y_{|{\cal Y}|}}$ be random
variables as above, then

$\displaystyle H_{\alpha}(Z,g_{y_{1}}(Z),g_{y_{2}}(Z),\cdots,g_{y_{|{\cal
Y}|}}(Z))$ $\displaystyle=H_{\alpha}(Z)$ $\displaystyle\geq
H_{\alpha}(g_{y_{1}}(Z),g_{y_{2}}(Z),\cdots,g_{y_{|{\cal Y}|}}).$ (64)

Note that Equation 64 holds from noting that for any two random variables $X$
and $Y$, the following holds $H_{\alpha}(X,Y)\geq H_{\alpha}(X)$ and
$H_{\alpha}(X,Y)\geq H_{\alpha}(Y)$. Further, if $Y=f(X)$ then
$H_{\alpha}(X,Y)=H_{\alpha}(X)\geq H_{\alpha}(Y)$.
Thus, we have the following result from (64):

$\displaystyle H_{\alpha}(Z)\geq\inf_{P_{X_{1}X_{2}\cdots
X_{m}}\colon{X_{i}}\sim
P_{i}}H_{\alpha}(X_{y_{1}},X_{y_{2}},\cdots,X_{y_{|{\cal Y}|}}).$ (65)

∎

###  -B Proof of Lemma 2 and 3

###### Lemma 2.

Define

$\displaystyle t_{i}=\log\frac{1}{q_{i}}\mbox{ and
}s_{i}=\log\frac{1}{p_{i}},$ (66)

and note that $t_{1},t_{2},\dots$ and $s_{1},s_{2},\dots$ are both increasing
sequences. We prove the claim by induction.

For the base case, suppose $p_{1}<q_{1}$ and note that this implies that
$s_{1}>t_{1}$. Then

$\displaystyle q_{1}$ $\displaystyle\leq\mathbb{P}\left[\imath_{U}(U)\leq
t_{1}\right]\leq\mathbb{P}\left[\imath_{V}(V)\leq t_{1}\right]=0$ (67)

which is a contradiction. Therefore $p_{1}\geq q_{1}$.

For the inductive step, assume that for some $k$

$\displaystyle\sum_{i=1}^{k}q_{i}\leq\sum_{i=1}^{k}p_{i}.$ (68)

If $p_{k+1}\geq q_{k+1}$, then we are done. Else, for the case
$p_{k+1}<q_{k+1}$, we note that $s_{k+1}>t_{k+1}$. Then

$\displaystyle\sum_{i=1}^{k+1}q_{i}$
$\displaystyle\leq\mathbb{P}\left[\imath_{U}(U)\leq
t_{k+1}\right]\leq\mathbb{P}\left[\imath_{V}(V)\leq t_{k+1}\right]$ (69)
$\displaystyle=\sum_{i=1}^{k}1\\{s_{i}\leq
t_{k}\\}p_{i}<\sum_{i=1}^{k+1}p_{i}.$ (70)

This completes the proof. ∎

###### Lemma 3.

Define

$\displaystyle
G(t):=\max_{i\in\\{1,\dots,m\\}}\mathbb{P}[\imath_{S_{i}}(S_{i})>t]$ (71)

where $S_{i}\sim P_{i}$. Note $G(t)$ is an increasing step function that goes
from zero to one in at most $\sum_{i=1}^{m}|{\cal S}_{i}|$ steps. Also note
that every $Q\in{\cal F}$ satisfies

$\displaystyle\sum_{i=1}^{k}q_{i}\leq G\left(\log\frac{1}{q_{k}}\right)$ (72)

where, again, we assume $q_{1}\geq q_{2}\geq q_{3}\dots$.

We construct $Q^{\ast}=(q^{\ast}_{1},q^{\ast}_{2},q^{\ast}_{3},\dots)$ with
$q^{\ast}_{1}\geq q^{\ast}_{2}\geq q^{\ast}_{3}\dots$ in a greedy way. First,
assign

$\displaystyle q^{\ast}_{1}=\min_{i\in\\{1,\dots,m\\}}\left\\{\max_{s\in{\cal
S}_{i}}P_{i}(s)\right\\}.$ (73)

This is the maximum value we can assign to $q^{\ast}_{1}$ while satisfying the
information spectrum constraint (72). We continue with this strategy: at each
step $k$ we assign the maximum possible value to $q^{\ast}_{k}$ until the
total probability of all $q^{\ast}_{k}$ reaches one. We claim that the
algorithm will terminate in at most $2\sum_{i=1}^{m}|{\cal S}_{i}|$
iterations. Indeed, for every ‘step’ in $G(t)$, the algorithm can assign at
most two probability values to $Q^{\ast}$ before it needs to start assigning
smaller values and move on to the next ‘step’.

We also claim that the resulting distribution $Q^{\ast}$ will majorize all
other distributions that satisfy the information spectrum constraint (72). To
this end, let $Q\in{\cal F}$ be arbitrary such distribution. We show that
$Q\preceq_{m}Q^{\ast}$ inductively. For the base case, we have that
$q^{\ast}_{1}\geq q_{1}$ since by construction we assigned the maximum
possible value to $q^{\ast}_{1}$.
For the inductive step, assume that for some integer $k$ we have that
$\sum_{i=1}^{k}q_{k}\leq\sum_{i=1}^{k}q^{\ast}_{k}$. If $q^{\ast}_{k+1}\geq
q_{k+1}$, we are done. Otherwise, define

$\displaystyle t_{k+1}=\log\frac{1}{q^{\ast}_{k+1}}\mbox{ and
}s_{k+1}=\log\frac{1}{q_{k+1}},$ (74)

and note that $s_{k+1}<t_{k+1}$ and $G(s_{k+1})\leq G(t_{k+1})$. Let

$\displaystyle g_{k+1}=G(s_{k+1})-\sum_{i=1}^{k}q^{\ast}_{i}$ (75)

and note that $g_{k+1}<q_{k+1}$. This is a consequence of the greedy
construction; if this was not the case, we would assign $q_{k+1}$ to
$q^{\ast}_{k+1}$. Also, $q^{\ast}_{k+1}\geq g_{k+1}$, again by the property of
the greedy construction. This is because we could always assign the value of
$g_{k+1}$ to $q^{\ast}_{k+1}$ without violating the information spectrum
constraint. Thus we have that

$\displaystyle\sum_{i=1}^{k}q^{\ast}_{i}+q^{\ast}_{k+1}\geq
G(s_{k+1})\geq\sum_{i=1}^{k+1}q_{i}$ (76)

and this completes the proof.

∎

###  -C Proof of Corollary 1:

###### Corollary 1.

######  Remark 3.

Note that the slightly modified version of Equation (58) i.e.,

$\displaystyle\mathbb{P}\Big{[}\imath_{Z}(Z)\geq t\Big{]}\geq\sup_{y\in{\cal
Y}}\mathbb{P}\Big{[}\imath_{X|Y}(X|Y)\geq t|Y=y\Big{]}$ (77)

is also true. The proof follows via the same construction except the fact that
the definitions of the sets ${\cal X}_{s,t}$ and ${\cal Z}_{t}$ does not
involves the strict inequality.

From equation (3), we have

$\displaystyle H_{\alpha}(Z)=$
$\displaystyle\frac{1}{1-\alpha}\log\Big{(}\mathbb{E}[\imath^{\alpha}_{Z}(Z)]\Big{)}$
(78)

where,

${\imath^{\alpha}_{Z}}(Z):=2^{(1-\alpha)\imath_{Z}(Z)}$

Case 1: $\alpha\in[0,1)$:

From Theorem (1), we have:

$\displaystyle\mathbb{P}[\imath_{Z}(Z)>t]$ $\displaystyle\geq\sup_{y\in{\cal
Y}}\mathbb{P}[\imath_{X|Y}(X|Y)>t|Y=y]$ $\displaystyle=G(t)$

Note that
$\mathbb{P}[2^{(1-\alpha)\imath_{Z}(Z)}>2^{(1-\alpha)t}]=\mathbb{P}[\imath_{Z}(Z)>t]$
holds for $0\leq\alpha<1$. Therefore,

$\displaystyle\mathbb{P}[\imath^{\alpha}_{Z}(Z)>t^{\prime}]\geq G(t)$ (79)

where $t^{\prime}:=2^{(1-\alpha)t}$.
Now,

$\displaystyle\mathbb{E}[\imath^{\alpha}_{Z}(Z)]$
$\displaystyle\stackrel{{\scriptstyle}}{{=}}\int_{0}^{\infty}\Big{(}1-\mathbb{F}_{\imath^{\alpha}_{Z}}(t^{\prime})\Big{)}dt^{\prime}$
(80)
$\displaystyle\stackrel{{\scriptstyle}}{{=}}\int_{0}^{\infty}\mathbb{P}[\imath^{\alpha}_{Z}(Z)>t^{\prime}]dt^{\prime}$
$\displaystyle\stackrel{{\scriptstyle}}{{=}}\int_{0}^{1}\mathbb{P}[\imath^{\alpha}_{Z}(Z)>t^{\prime}]dt^{\prime}+\int_{1}^{\infty}\mathbb{P}[\imath^{\alpha}_{Z}(Z)>t^{\prime}]dt^{\prime}$
$\displaystyle\stackrel{{\scriptstyle}}{{=}}1+\int_{1}^{\infty}\mathbb{P}[\imath^{\alpha}_{Z}(Z)>t^{\prime}]dt^{\prime}$
(81)
$\displaystyle\stackrel{{\scriptstyle}}{{\geq}}1+\int_{1}^{\infty}G(t)dt^{\prime}$
(82) $\displaystyle\stackrel{{\scriptstyle}}{{=}}1+(1-\alpha)\ln
2\int_{0}^{\infty}G(t)2^{(1-\alpha)t}dt.$ (83)

Here,

  1. (80)

follows from noting that $\imath^{\alpha}_{Z}(Z)>0$ and (24).

  2. (81)

follows from noting that $\imath^{\alpha}_{Z}(Z)\in[1,\infty)$ for
$\alpha\in[0,1)$.

  3. (82)

follows from equation (79).

  4. (83)

follows from the change of variables in integration.

On substituting equation (83) in equation (78), we have

$\displaystyle H_{\alpha}(Z)$
$\displaystyle\geq\frac{1}{1-\alpha}\log\Bigg{[}1+(1-\alpha)\ln
2\int_{0}^{\infty}G(t)2^{(1-\alpha)t}dt\Bigg{]}$ (84)
$\displaystyle=\frac{1}{1-\alpha}\log\Bigg{[}1+\int_{0}^{\infty}J_{\alpha}(t)dt\Bigg{]}.$

This completes the proof for the case of $0\leq\alpha<1$.

Case 2: $\alpha\in(1,\infty)$:

Here, we will use the modified version (cf. Remark (3)) of Theorem (1) i.e.,

$\displaystyle\mathbb{P}\Big{[}\imath_{Z}(Z)\geq t\Big{]}\geq\sup_{y\in{\cal
Y}}\mathbb{P}\Big{[}\imath_{X|Y}(X|Y)\geq t|Y=y\Big{]}:=G^{{}^{\prime}}(t)$

Note that $\mathbb{P}[2^{(1-\alpha)\imath_{Z}(Z)}\leq
2^{(1-\alpha)t}]=\mathbb{P}[\imath_{Z}(Z)\leq t]$ holds for $\alpha>1$.
Therefore,

$\displaystyle\mathbb{P}[\imath^{\alpha}_{Z}(Z)\leq t^{\prime}]\geq
G^{{}^{\prime}}(t)$ (85)

where $t^{\prime}:=2^{(1-\alpha)t}$.
Now,

$\displaystyle\mathbb{E}[\imath^{\alpha}_{Z}(Z)]$
$\displaystyle\stackrel{{\scriptstyle}}{{=}}\int_{0}^{\infty}\Big{(}1-\mathbb{F}_{\imath^{\alpha}_{Z}}(t^{\prime})\Big{)}dt^{\prime}$
(86)
$\displaystyle\stackrel{{\scriptstyle}}{{=}}\int_{0}^{\infty}\Big{(}1-\mathbb{P}[\imath^{\alpha}_{Z}(Z)\leq
t^{\prime}]\Big{)}dt^{\prime}$
$\displaystyle\stackrel{{\scriptstyle}}{{=}}\int_{0}^{1}\Big{(}1-\mathbb{P}[\imath^{\alpha}_{Z}(Z)\leq
t^{\prime}]\Big{)}dt^{\prime}$ $\displaystyle\hskip
42.67912pt+\int_{1}^{\infty}\Big{(}1-\mathbb{P}[\imath^{\alpha}_{Z}(Z)\leq
t^{\prime}]\Big{)}dt^{\prime}$
$\displaystyle\stackrel{{\scriptstyle}}{{=}}\int_{0}^{1}\Big{(}1-\mathbb{P}[\imath^{\alpha}_{Z}(Z)\leq
t^{\prime}]\Big{)}dt^{\prime}$ (87)
$\displaystyle\stackrel{{\scriptstyle}}{{\leq}}\int_{0}^{1}\Big{(}1-G^{{}^{\prime}}(t)\Big{)}dt^{\prime}$
(88) $\displaystyle\stackrel{{\scriptstyle}}{{=}}(\alpha-1)\ln
2\int_{0}^{\infty}(1-G^{{}^{\prime}}(t))2^{(1-\alpha)t}dt$ (89)
$\displaystyle\stackrel{{\scriptstyle}}{{=}}1+(1-\alpha)\ln
2\int_{0}^{\infty}G^{{}^{\prime}}(t)2^{(1-\alpha)t}dt$ (90)

Here,

  1. (86)

follows from noting that $\imath_{Z}(Z)\geq 0$ and (24).

  2. (87)

follows from noting that $\imath^{\alpha}_{Z}(Z)\in(0,1)$ for
$\alpha\in(1,\infty)$.

  3. (88)

follows from equation (85).

  4. (89)

follows from the change of variables of integration.

On substituting equation (90) in equation (78), we have

$\displaystyle H_{\alpha}(Z)\geq\frac{1}{1-\alpha}\log\Bigg{[}1+(1-\alpha)\ln
2\int_{0}^{\infty}G^{{}^{\prime}}(t)2^{(1-\alpha)t}dt\Bigg{]}$ (91)

######  Remark 4.

Note that the information spectrum CDF of a discrete random variable is
discontinuous or right continuous (step function). Therefore, the computation
of the integral in (84) and (91) yields the same value.

Therefore, we have:

$\displaystyle
H_{\alpha}(Z)\geq\frac{1}{1-\alpha}\log\Bigg{[}1+\int_{0}^{\infty}J_{\alpha}(t)dt\Bigg{]}.$

This completes the proof for the case of $\alpha>1$.
∎