Comparison of channels: criteria for
domination by a symmetric channel
Anuran Makur and Yury Polyanskiy∗

arXiv:1609.06877v2 [] 22 Nov 2017

Abstract
This paper studies the basic question of whether a given channel V can be dominated (in the precise sense of being
more noisy) by a q-ary symmetric channel. The concept of “less noisy” relation between channels originated in network
information theory (broadcast channels) and is defined in terms of mutual information or Kullback-Leibler divergence.
We provide an equivalent characterization in terms of χ2 -divergence. Furthermore, we develop a simple criterion for
domination by a q-ary symmetric channel in terms of the minimum entry of the stochastic matrix defining the channel
V . The criterion is strengthened for the special case of additive noise channels over finite Abelian groups. Finally, it
is shown that domination by a symmetric channel implies (via comparison of Dirichlet forms) a logarithmic Sobolev
inequality for the original channel.
Index Terms
Less noisy, degradation, q-ary symmetric channel, additive noise channel, Dirichlet form, logarithmic Sobolev inequalities.

C ONTENTS
I

Introduction
I-A
Preliminaries . . . . . . . . . . . . . . .
I-B
Channel preorders in information theory
I-C
Symmetric channels and their properties
I-D
Main question and motivation . . . . .

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

2
2
2
4
6

preorder
. . . . .
. . . . .
. . . . .
. . . . .

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

6
7
7
8
8
9

III

Less noisy domination and degradation regions
III-A
Less noisy domination and degradation regions for additive noise channels . . . . . . . . . . . .
III-B
Less noisy domination and degradation regions for symmetric channels . . . . . . . . . . . . . .

10
11
12

IV

Equivalent characterizations of less noisy preorder
IV-A
Characterization using χ2 -divergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
IV-B
Characterizations via the Löwner partial order and spectral radius . . . . . . . . . . . . . . . . .

13
13
14

V

Conditions for less noisy domination over additive noise channels
V-A
Necessary conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
V-B
Sufficient conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16
16
17

VI

Sufficient conditions for degradation over general channels

19

VII

Less noisy domination and logarithmic Sobolev inequalities

22

II

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

Main results
II-A
χ2 -divergence characterization of the less noisy
II-B
Less noisy domination by symmetric channels
II-C
Structure of additive noise channels . . . . . .
II-D
Comparison of Dirichlet forms . . . . . . . . .
II-E
Outline . . . . . . . . . . . . . . . . . . . . . .

VIII Conclusion

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

26

∗ A. Makur and Y. Polyanskiy are with the Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology,
Cambridge, MA 02139, USA (e-mail: a_makur@mit.edu; yp@mit.edu).
This research was supported in part by the National Science Foundation CAREER award under grant agreement CCF-12-53205, and in part by
the Center for Science of Information (CSoI), an NSF Science and Technology Center, under grant agreement CCF-09-39370.
This work was presented at the 2017 IEEE International Symposium on Information Theory (ISIT) [1].

1

Appendix A: Basics of majorization theory

26

Appendix B: Proofs of propositions 4 and 12

27

Appendix C: Auxiliary results

28

References

30
I. I NTRODUCTION

For any Markov chain U → X → Y , it is well-known that the data processing inequality, I(U ; Y ) ≤ I(U ; X),
holds. This result can be strengthened to [2]:
I(U ; Y ) ≤ ηI(U ; X)

(1)

where the contraction coefficient η ∈ [0, 1] only depends on the channel PY |X . Frequently, one gets η < 1 and
the resulting inequality is called a strong data processing inequality (SDPI). Such inequalities have been recently
simultaneously rediscovered and applied in several disciplines; see [3, Section 2] for a short survey. In [3, Section 6],
it was noticed that the validity of (1) for all PU,X is equivalent to the statement that an erasure channel with erasure
probability 1 − η is less noisy than the given channel PY |X . In this way, the entire field of SDPIs is equivalent to
determining whether a given channel is dominated by an erasure channel.
This paper initiates the study of a natural extension of the concept of SDPI by replacing the distinguished role
played by erasure channels with q-ary symmetric channels. We give simple criteria for testing this type of domination
and explain how the latter can be used to prove logarithmic Sobolev inequalities. In the next three subsections, we
introduce some basic definitions and notation. We state and motivate our main question in subsection I-D, and present
our main results in section II.
A. Preliminaries
The following notation will be used in our ensuing discussion. Consider any q, r ∈ N , {1, 2, 3, . . . }. We let
Rq×r (respectively Cq×r ) denote the set of all real (respectively complex) q × r matrices. Furthermore, for any matrix
A ∈ Rq×r , we let AT ∈ Rr×q denote the transpose of A, A† ∈ Rr×q denote the Moore-Penrose pseudoinverse of A,
R(A) denote the range (or column space) of A, and ρ (A) denote the spectral radius of A (which is the maximum
q×q
of the absolute values of all complex eigenvalues of A) when q = r. We let R0
( Rq×q
sym denote the sets of positive
q×q
semidefinite and symmetric matrices, respectively. In fact, R0 is a closed convex cone (with respect to the Frobenius
q×q
norm). We also let PSD denote the Löwner partial order over Rq×q
sym : for any two matrices A, B ∈ Rsym , we write
q×q
A PSD B (or equivalently, A − B PSD 0, where 0 is the zero matrix) if and only if A − B ∈ R0 . To work with
probabilities, we let Pq , {p = (p1 , . . . , pq ) ∈ Rq : p1 , . . . , pq ≥ 0 and p1 + · · · + pq = 1} be the probability simplex
of row vectors in Rq , Pq◦ , {p = (p1 , . . . , pq ) ∈ Rq : p1 , . . . , pq > 0 and p1 + · · · + pq = 1} be the relative interior of
Pq , and Rq×r
sto be the convex set of row stochastic matrices (which have rows in Pr ). Finally, for any (row or column)
vector x = (x1 , . . . , xq ) ∈ Rq , we let diag(x) ∈ Rq×q denote the diagonal matrix with entries [diag(x)]i,i = xi for
each i ∈ {1, . . . , q}, and for any set of vectors S ⊆ Rq , we let conv (S) be the convex hull of the vectors in S.
B. Channel preorders in information theory
Since we will study preorders over discrete channels that capture various notions of relative “noisiness” between
channels, we provide an overview of some well-known channel preorders in the literature. Consider an input random
variable X ∈ X and an output random variable Y ∈ Y, where the alphabets are X = [q] , {0, 1, . . . , q − 1} and
Y = [r] for q, r ∈ N without loss of generality. We let Pq be the set of all probability mass functions (pmfs) of X,
where every pmf PX = (PX (0), . . . , PX (q − 1)) ∈ Pq and is perceived as a row vector. Likewise, we let Pr be the set
of all pmfs of Y . A channel is the set of conditional distributions WY |X that associates each x ∈ X with a conditional
q×r
pmf WY |X (·|x) ∈ Pr . So, we represent each channel with a stochastic matrix W ∈ Rsto
that is defined entry-wise as:
∀x ∈ X , ∀y ∈ Y, [W ]x+1,y+1 , WY |X (y|x)

(2)

where the (x + 1)th row of W corresponds to the conditional pmf WY |X (·|x) ∈ Pr , and each column of W has at least
one non-zero entry so that no output alphabet letters are redundant. Moreover, we think of such a channel as a (linear)
map W : Pq → Pr that takes any row probability vector PX ∈ Pq to the row probability vector PY = PX W ∈ Pr .
One of the earliest preorders over channels was the notion of channel inclusion proposed by Shannon in [4]. Given
s×t
two channels W ∈ Rq×r
sto and V ∈ Rsto for some q, r, s, t ∈ N, he stated that W includes V , denoted W inc V ,
2

r×t
if there exist a pmf g ∈ Pm for some m ∈ N, and two sets of channels {Ak ∈ Rsto
: k = 1, . . . , m} and
s×q
{Bk ∈ Rsto : k = 1, . . . , m}, such that:
m
X
V =
gk Bk W Ak .
(3)
k=1

Channel inclusion is preserved under channel addition and multiplication (which are defined in [5]), and the existence
of a code for V implies the existence of as good a code for W in a probability of error sense [4]. The channel inclusion
preorder includes the input-output degradation preorder, which can be found in [6], as a special case. Indeed, V is an
s×q
r×t
input-output degraded version of W , denoted W iod V , if there exist channels A ∈ Rsto
and B ∈ Rsto
such that
V = BW A. We will study an even more specialized case of Shannon’s channel inclusion known as degradation [7],
[8].
q×s
Definition 1 (Degradation Preorder). A channel V ∈ Rsto
is said to be a degraded version of a channel W ∈ Rq×r
sto
with the same input alphabet, denoted W deg V , if V = W A for some channel A ∈ Rr×s
sto .

We note that when Definition 1 of degradation is applied to general matrices (rather than stochastic matrices), it is
equivalent to Definition C.8 of matrix majorization in [9, Chapter 15]. Many other generalizations of the majorization
preorder over vectors (briefly introduced in Appendix A) that apply to matrices are also presented in [9, Chapter 15].
Körner and Marton defined two other preorders over channels in [10] known as the more capable and less noisy
preorders. While the original definitions of these preorders explicitly reflect their significance in channel coding,
we will define them using equivalent mutual information characterizations proved in [10]. (See [11, Problems 6.166.18] for more on the relationship between channel coding and some of the aforementioned preorders.) We say a
q×s
channel W ∈ Rq×r
sto is more capable than a channel V ∈ Rsto with the same input alphabet, denoted W mc V , if
I(PX , WY |X ) ≥ I(PX , VY |X ) for every input pmf PX ∈ Pq , where I(PX , WY |X ) denotes the mutual information
of the joint pmf defined by PX and WY |X . The next definition presents the less noisy preorder, which will be a key
player in our study.
q×r
Definition 2 (Less Noisy Preorder). Given two channels W ∈ Rsto
and V ∈ Rq×s
sto with the same input alphabet, let
YW and YV denote the output random variables of W and V , respectively. Then, W is less noisy than V , denoted
W ln V , if I(U ; YW ) ≥ I(U ; YV ) for every joint distribution PU,X , where the random variable U ∈ U has some
arbitrary range U, and U → X → (YW , YV ) forms a Markov chain.

An analogous characterization of the less noisy preorder using Kullback-Leibler (KL) divergence or relative entropy
is given in the next proposition.
q×r
Proposition 1 (KL Divergence Characterization of Less Noisy [10]). Given two channels W ∈ Rsto
and V ∈ Rq×s
sto
with the same input alphabet, W ln V if and only if D(PX W ||QX W ) ≥ D(PX V ||QX V ) for every pair of input
pmfs PX , QX ∈ Pq , where D(·||·) denotes the KL divergence.1

We will primarily use this KL divergence characterization of ln in our discourse because of its simplicity. Another
well-known equivalent characterization of ln due to van Dijk is presented below, cf. [12, Theorem 2]. We will derive
some useful corollaries from it later in subsection IV-B.
q×r
Proposition 2 (van Dijk Characterization of Less Noisy [12]). Given two channels W ∈ Rsto
and V ∈ Rq×s
sto with
the same input alphabet, consider the functional F : Pq → R:

∀PX ∈ Pq , F (PX ) , I(PX , WY |X ) − I(PX , VY |X ).
Then, W ln V if and only if F is concave.
The more capable and less noisy preorders have both been used to study the capacity regions of broadcast channels.
We refer readers to [13]–[15], and the references therein for further details. We also remark that the more capable and
less noisy preorders tensorize, as shown in [11, Problem 6.18] and [3, Proposition 16], [16, Proposition 5], respectively.
On the other hand, these preorders exhibit rather counter-intuitive behavior in the context of Bayesian networks (or
directed graphical models). Consider a Bayesian network with “source” nodes (with no inbound edges) X and “sink”
nodes (with no outbound edges) Y . If we select a node Z in this network and replace the channel from the parents of
Z to Z with a less noisy channel, then we may reasonably conjecture that the channel from X to Y also becomes less
noisy (motivated by the results in [3]). However, this conjecture is false. To see this, consider the Bayesian network in
1 Throughout this paper, we will adhere to the convention that ∞ ≥ ∞ is true. So, D(P W ||Q W ) ≥ D(P V ||Q V ) is not violated when
X
X
X
X
both KL divergences are infinity.

3

Fig. 1. Illustration of a Bayesian network where X1 , X2 , Z, Y ∈ {0, 1} are binary random variables, PZ|X2 is a BSC(δ) with δ ∈ (0, 1), and
PY |X1 ,Z is defined by a deterministic NOR gate.


Figure 1 (inspired by the results in [17]), where the source nodes are X1 ∼ Ber 21 and X2 = 1 (almost surely), the
node Z is the output of a binary symmetric channel (BSC) with crossover probability δ ∈ (0, 1), denoted BSC(δ), and
the sink node Y is the output of a NOR gate. Let I(δ) = I(X1 , X2 ; Y ) be the end-to-end mutual information. Then,
although BSC(0) ln BSC(δ) for δ ∈ (0, 1), it is easy to verify that I(δ) > I(0) = 0. So, when we replace the BSC(δ)
with a less noisy BSC(0), the end-to-end channel does not become less noisy (or more capable).
The next proposition illustrates certain well-known relationships between the various preorders discussed in this
subsection.
q×r
Proposition 3 (Relations between Channel Preorders). Given two channels W ∈ Rsto
and V ∈ Rq×s
sto with the same
input alphabet, we have:
1) W deg V ⇒ W iod V ⇒ W inc V ,
2) W deg V ⇒ W ln V ⇒ W mc V .

These observations follow in a straightforward manner from the definitions of the various preorders. Perhaps the
only nontrivial implication is W deg V ⇒ W ln V , which can be proven using Proposition 1 and the data processing
inequality.
C. Symmetric channels and their properties
We next formally define q-ary symmetric channels and convey some of their properties. To this end, we first introduce
some properties of Abelian groups and define additive noise channels. Let us fix some q ∈ N with q ≥ 2 and consider an
Abelian group (X , ⊕) of order q equipped with a binary “addition” operation denoted by ⊕. Without loss of generality,
we let X = [q], and let 0 denote the identity element. This endows an ordering to the elements of X . Each element
x ∈ X permutes the entries of the row vector (0, . . . , q − 1) to (σx (0), . . . , σx (q − 1)) by (left) addition in the Cayley
table of the group, where σx : [q] → [q] denotes a permutation of [q], and σx (y) = x ⊕y for every y ∈ X . So,
corresponding to each x ∈ X , we can define a permutation matrix Px , eσx (0) · · · eσx (q−1) ∈ Rq×q such that:


(4)
[v0 · · · vq−1 ] Px = vσx (0) · · · vσx (q−1)
for any v0 , . . . , vq−1 ∈ R, where for each i ∈ [q], ei ∈ Rq is the ith standard basis column vector with unity in the
(i + 1)th position and zero elsewhere. The permutation matrices {Px ∈ Rq×q : x ∈ X } (with the matrix multiplication
operation) form a group that is isomorphic to (X , ⊕) (see Cayley’s theorem, and permutation and regular representations
of groups in [18, Sections 6.11, 7.1, 10.6]). In particular, these matrices commute as (X , ⊕) is Abelian, and are jointly
unitarily diagonalizable by a Fourier matrix of characters (using [19, Theorem 2.5.5]). We now recall that given a row
vector x = (x0 , . . . , xq−1 ) ∈ Rq , we may define a corresponding X -circulant matrix, circX (x) ∈ Rq×q , that is defined
entry-wise as [20, Chapter 3E, Section 4]:
∀a, b ∈ [q], [circX (x)]a+1,b+1 , x−a⊕b .

(5)

where −a ∈ X denotes the inverse of a ∈ X . Moreover, we can decompose this X -circulant matrix as:
circX (x) =

q−1
X

xi PiT

(6)

i=0

since
write:

Pq−1
i=0

 

Pq−1 
xi PiT a+1,b+1 =
i=0 xi eσi (a) b+1 = x−a⊕b for every a, b ∈ [q]. Using similar reasoning, we can
circX (x) = [P0 y · · · Pq−1 y] = P0 xT · · · Pq−1 xT



T

(7)

T
where y = x0 x−1 · · · x−(q−1) ∈ Rq , and P0 = Iq ∈ Rq×q is the q × q identity matrix. Using (6), we see that X circulant matrices are normal, form a commutative algebra, and are jointly unitarily diagonalizable by a Fourier matrix.
4

Furthermore, given two row vectors x, y ∈ Rq , we can define x circX (y) = y circX (x) as the X -circular convolution of
x and y, where the commutativity of X -circular convolution follows from the commutativity of X -circulant matrices.
A salient specialization of this discussion is the case where ⊕ is addition modulo q, and (X = [q], ⊕) is the
cyclic Abelian group Z/qZ. In this scenario, X -circulant matrices correspond to the standard circulant matrices which
are jointly unitarily diagonalized by the discrete Fourier transform (DFT) matrix. Furthermore, for each x ∈ [q], the
permutation matrix PxT = Pqx , where Pq ∈ Rq×q is the generator cyclic permutation matrix as presented in [19, Section
0.9.6]:
∀a, b ∈ [q], [Pq ]a+1,b+1 , ∆1,(b−a (mod q))
(8)
where ∆i,j is the Kronecker delta function, which is unity if i = j and zero otherwise. The matrix Pq cyclically shifts
any input row vector to the right once, i.e. (x1 , x2 , . . . , xq ) Pq = (xq , x1 , . . . , xq−1 ).
Let us now consider a channel with common input and output alphabet X = Y = [q], where (X , ⊕) is an Abelian
group. Such a channel operating on an Abelian group is called an additive noise channel when it is defined as:
Y =X ⊕Z

(9)

where X ∈ X is the input random variable, Y ∈ X is the output random variable, and Z ∈ X is the additive noise
random variable that is independent of X with pmf PZ = (PZ (0), . . . , PZ (q − 1)) ∈ Pq . The channel transition
probability matrix corresponding to (9) is the X -circulant stochastic matrix circX (PZ ) ∈ Rq×q
sto , which is also doubly
T
stochastic (i.e. both circX (PZ ) , circX (PZ ) ∈ Rq×q
sto ). Indeed, for an additive noise channel, it is well-known that the
pmf of Y , PY ∈ Pq , can be obtained from the pmf of X, PX ∈ Pq , by X -circular convolution: PY = PX circX (PZ ).
We remark that in the context of various channel symmetries in the literature (see [21, Section VI.B] for a discussion),
additive noise channels correspond to “group-noise” channels, and are input symmetric, output symmetric, Dobrushin
symmetric, and Gallager symmetric.
The q-ary symmetric channel is an additive noise channel on the Abelian group (X , ⊕) with noise pmf PZ =
wδ , (1 − δ, δ/(q − 1), . . . , δ/(q − 1)) ∈ Pq , where δ ∈ [0, 1]. Its channel transition probability matrix is denoted
Wδ ∈ Rq×q
sto :
h
q−1 T iT
Wδ , circX (wδ ) = wδ T PqT wδ T · · · PqT
wδ
(10)
which has 1 − δ in the principal diagonal entries and δ/(q − 1) in all other entries regardless of the choice of group
(X , ⊕). We may interpret δ as the total crossover probability of the symmetric channel. Indeed, when q = 2, Wδ
represents a BSC with crossover probability
 δ ∈ [0, 1]. Although Wδ is only stochastic when δ ∈ [0, 1], we will refer to
the parametrized convex set of matrices Wδ ∈ Rq×q
sym : δ ∈ R with parameter δ as the “symmetric channel matrices,”
where each Wδ has the form (10) such that every row and column sums to unity. We conclude this subsection with a
list of properties of symmetric channel matrices.

Proposition 4 (Properties of Symmetric Channel Matrices). The symmetric channel matrices, Wδ ∈ Rq×q
sym : δ ∈ R ,
satisfy the following properties:
1) For every δ ∈ R, Wδ is a symmetric circulant matrix.
2) The DFT matrix Fq ∈ Cq×q , which is defined entry-wise as [Fq ]j,k = q −1/2 ω (j−1)(k−1) for 1 ≤ j, k ≤ q
√
where ω = exp (2πi/q) and i = −1, jointly diagonalizes

 Wδ for every δ ∈ R. Moreover, the corresponding
eigenvalues or Fourier coefficients, {λj (Wδ ) = FqH Wδ Fq j,j : j = 1, . . . , q} are real:

1,
j=1
λj (Wδ ) =
δ
1 − δ − q−1 , j = 2, . . . , q
where FqH denotes the Hermitian transpose of Fq .
3) For all δ ∈ [0, 1], Wδ is a doubly stochastic matrix that has the uniform pmf u , (1/q, . . . , 1/q) as its stationary
distribution: uWδ= u.

T
δ
1
4) For every δ ∈ R\ q−1
, Wδ−1 = Wτ with τ = −δ/ 1 − δ − q−1
, and for δ = q−1
q
q , Wδ = q 11 is unit rank
T
and singular,
where 1 = [1 · · · 1] .

q−1
5) The set Wδ ∈ Rq×q
with the operation of matrix multiplication is an Abelian group.
sym : δ ∈ R\
q


Proof. See Appendix B.

5

D. Main question and motivation
As we mentioned at the outset, our work is partly motivated by [3, Section 6], where the authors demonstrate an
intriguing relation between less noisy domination by an erasure channel and the contraction coefficient of the SDPI (1).
q×(q+1)
q×s
For a common input alphabet X = [q], consider a channel V ∈ Rsto
and a q-ary erasure channel E ∈ Rsto
with
erasure probability  ∈ [0, 1]. Recall that given an input x ∈ X , a q-ary erasure channel erases x and outputs e (erasure
symbol) with probability , and outputs x itself with probability 1 − ; the output alphabet of the erasure channel is
{e} ∪ X . It is proved in [3, Proposition 15] that E ln V if and only if ηKL (V ) ≤ 1 − , where ηKL (V ) ∈ [0, 1] is the
contraction coefficient for KL divergence:
ηKL (V ) ,

sup
PX ,QX ∈Pq
0<D(PX ||QX )<+∞

D (PX V ||QX V )
D (PX ||QX )

(11)

which equals the best possible constant η in the SDPI (1) when V = PY |X (see [3, Theorem 4] and the references
therein). This result illustrates that the q-ary erasure channel E with the largest erasure probability  ∈ [0, 1] (or the
smallest channel capacity) that is less noisy than V has  = 1 − ηKL (V ).2 Furthermore, there are several simple upper
bounds on ηKL that provide sufficient conditions for such less noisy domination. For example, if the `1 -distances between
the rows of V are bounded by 2(1 − α) for some α ∈ [0, 1], then ηKL ≤ 1 − α, cf. [22]. Another criterion follows from
Doeblin minorization [23, Remark III.2]: if for some pmf p ∈ Ps and some α ∈ (0, 1), V ≥ α 1p entry-wise, then
Eα deg V and ηKL (V ) ≤ 1 − α.
To extend these
ideas,
channel Wδ with the largest
 we consider the following question: What is the q-ary symmetric

3
(or
the
smallest
channel
capacity)
such
that
W

V
?
Much
like
the bounds on ηKL in the
value of δ ∈ 0, q−1
δ
ln
q
erasure channel context, the goal of this paper is to address this question by establishing simple criteria for testing ln
domination by a q-ary symmetric channel. We next provide several other reasons why determining whether a q-ary
symmetric channel dominates a given channel V is interesting.
Firstly, if W ln V , then W ⊗n ln V ⊗n (where W ⊗n is the n-fold tensor product of W ) since ln tensorizes, and
n
n
I(U ; YW
) ≥ I(U ; YVn ) for every Markov chain U → X n → (YW
, YVn ) (see Definition 2). Thus, many impossibility
n
results (in statistical decision theory for example) that are proven by exhibiting bounds on quantities such as I(U ; YW
)
n
transparently carry over to statistical experiments with observations on the basis of YV . Since it is common to study
the q-ary symmetric observation model (especially with q = 2), we can leverage its sample complexity lower bounds
for other V .
Secondly, we present a self-contained information theoretic motivation. W ln V if and only if CS = 0, where
CS is the secrecy capacity of the Wyner wiretap channel with V as the main (legal receiver) channel and W as the
eavesdropper channel [24, Corollary 3], [11, Corollary 17.11]. Therefore, finding the maximally noisy q-ary symmetric
channel that dominates V establishes the minimal noise required on the eavesdropper link so that secret communication
is feasible.
Thirdly, ln domination turns out to entail a comparison of Dirichlet forms (see subsection II-D), and consequently,
allows us to prove Poincaré and logarithmic Sobolev inequalities for V from well-known results on q-ary symmetric
channels. These inequalities are cornerstones of the modern approach to Markov chains and concentration of measure
[25], [26].
II. M AIN RESULTS
In this section, we first delineate some guiding sub-questions of our study, indicate the main results that address
them, and then present these results in the ensuing subsections. We will delve into the following four leading questions:
1) Can we test the less noisy preorder ln without using KL divergence?
Yes, we can use χ2 -divergence as shown in Theorem 1.
2) Given a channel V ∈ Rq×q
sto , is there a simple sufficient condition for less noisy domination by a q-ary symmetric
channel Wδ ln V ?
Yes, a condition using degradation (which implies less noisy domination) is presented in Theorem 2.
3) Can we say anything stronger about less noisy domination by a q-ary symmetric channel when V ∈ Rq×q
sto is an
additive noise channel?
Yes, Theorem 3 outlines the structure of additive noise channels in this context (and Figure 2 depicts it).
2A

q-ary erasure channel E with erasure probability  ∈ [0, 1] has channel
capacity
C() = log(q)(1 − ), which is linear and decreasing.


has channel capacity C(δ) = log(q) − H(wδ ), which is convex
q-ary symmetric channel Wδ with total crossover probability δ ∈ 0, q−1
q
and decreasing. Here, H(wδ ) denotes the Shannon entropy of the pmf wδ .
3A

6

4) Why are we interested in less noisy domination by q-ary symmetric channels?
Because this permits us to compare Dirichlet forms as portrayed in Theorem 4.
We next elaborate on these aforementioned theorems.
A. χ2 -divergence characterization of the less noisy preorder
Our most general result illustrates that although less noisy domination is a preorder defined using KL divergence,
one can equivalently define it using χ2 -divergence. Since we will prove this result for general measurable spaces, we
introduce some notation pertinent only to this result. Let (X , F), (Y1 , H1 ), and (Y2 , H2 ) be three measurable spaces,
and let W : H1 × X → [0, 1] and V : H2 × X → [0, 1] be two Markov kernels (or channels) acting on the same
source space (X , F). Given any probability measure PX on (X , F), we denote by PX W the probability measure on
(Y1 , H1 ) induced by the push-forward of PX .4 Recall that for any two probability measures PX and QX on (X , F),
their KL divergence is given by:
 Z


dPX

dPX , if PX  QX
log
D(PX ||QX ) ,
(12)
dQX
 X
+∞,
otherwise
and their χ2 -divergence is given by:
 Z 
2
dPX

dQX − 1, if PX  QX
χ2 (PX ||QX ) ,
 X dQX
+∞,
otherwise

(13)

dPX
where PX  QX denotes that PX is absolutely continuous with respect to QX , dQ
denotes the Radon-Nikodym
X
derivative of PX with respect to QX , and log(·) is the natural logarithm with base e (throughout this paper). Furthermore,
the characterization of ln in Proposition 1 extends naturally to general Markov kernels; indeed, W ln V if and only if
D(PX W ||QX W ) ≥ D(PX V ||QX V ) for every pair of probability measures PX and QX on (X , F). The next theorem
presents the χ2 -divergence characterization of ln .

Theorem 1 (χ2 -Divergence Characterization of ln ). For any Markov kernels W : H1 ×X → [0, 1] and V : H2 ×X →
[0, 1] acting on the same source space, W ln V if and only if:
χ2 (PX W ||QX W ) ≥ χ2 (PX V ||QX V )
for every pair of probability measures PX and QX on (X , F).
Theorem 1 is proved in subsection IV-A.
B. Less noisy domination by symmetric channels
Our remaining results are all concerned with less noisy (and degraded) domination by q-ary symmetric channels.
q×q
Suppose we are given a q-ary symmetric channel Wδ ∈ Rsto
with δ ∈ [0, 1], and another channel V ∈ Rq×q
sto with
common input and output alphabets. Then, the next result provides a sufficient condition for when Wδ deg V .
Theorem 2 (Sufficient Condition for Degradation by Symmetric Channels). Given a channel V ∈ Rq×q
sto with q ≥ 2
and minimum probability ν = min {[V ]i,j : 1 ≤ i, j ≤ q}, we have:
ν
0≤δ≤
⇒ Wδ deg V.
ν
1 − (q − 1)ν + q−1
Theorem 2 is proved in section VI. We note that the sufficient condition in Theorem 2 is tight as there exist channels
ν
V that violate Wδ deg V when δ > ν/(1 − (q − 1)ν + q−1
). Furthermore, Theorem 2 also provides a sufficient
condition for Wδ ln V due to Proposition 3.
4 Here, we can think of X and Y as random variables with codomains X and Y, respectively. The Markov kernel W behaves like the conditional
distribution of Y given X (under regularity conditions). Moreover, when the distribution of X is PX , the corresponding distribution of Y is
PY = PX W .

7

C. Structure of additive noise channels
Our next major result is concerned with understanding when q-ary symmetric channels operating on an Abelian group
(X , ⊕) dominate other additive noise channels on (X , ⊕), which are defined in (9), in the less noisy and degraded
senses. Given a symmetric channel Wδ ∈ Rq×q
sto with δ ∈ [0, 1], we define the additive less noisy domination region of
Wδ as:
Ladd
(14)
Wδ , {v ∈ Pq : Wδ = circX (wδ ) ln circX (v)}
which is the set of all noise pmfs whose corresponding channel transition probability matrices are dominated by Wδ
in the less noisy sense. Likewise, we define the additive degradation region of Wδ as:
add
DW
, {v ∈ Pq : Wδ = circX (wδ ) deg circX (v)}
δ

(15)

which is the set of all noise pmfs whose corresponding channel transition probability matrices are degraded versions
add
of Wδ . The next theorem exactly characterizes DW
, and “bounds” Ladd
Wδ in a set theoretic sense.
δ
Theorem 3 (Additive Less Noisy Domination
Degradation Regions for Symmetric Channels). Given a symmetric
 and
q−1
and q ≥ 2, we have:
channel Wδ = circX (wδ ) ∈ Rq×q
sto with δ ∈ 0, q


add
DW
= conv wδ Pqk : k ∈ [q]
δ



⊆ conv wδ Pqk : k ∈ [q] ∪ wγ Pqk : k ∈ [q]
⊆ Ladd
Wδ ⊆ {v ∈ Pq : kv − uk`2 ≤ kwδ − uk`2 }

where the first set inclusion is strict for δ ∈ 0, q−1
and q ≥ 3, Pq denotes the generator cyclic permutation matrix
q
as defined in (8), u denotes the uniform pmf, k·k`2 is the Euclidean `2 -norm, and:
γ=

1−δ
.
δ
1 − δ + (q−1)
2

q×q
Furthermore, Ladd
: x ∈ X } defined
Wδ is a closed and convex set that is invariant under the permutations {Px ∈ R
add
add
in (4) corresponding to the underlying Abelian group (X , ⊕) (i.e. v ∈ LWδ ⇒ vPx ∈ LWδ for every x ∈ X ).

Theorem 3 is a compilation of several results. As explained at the very end of subsection V-B, Proposition 6 (in
subsection III-A), Corollary 1 (in subsection III-B), part 1 of Proposition 9 (in subsection V-A), and Proposition 11
(in subsection V-B) make up Theorem 3. We remark that according to numerical evidence, the second and third set
inclusions in Theorem 3 appear to be strict, and Ladd
Wδ seems to be a strictly convex set. The content of Theorem 3 and
these observations are illustrated in Figure 2, which portrays the probability simplex of noise pmfs for q = 3 and the
pertinent regions which capture less noisy domination and degradation by a q-ary symmetric channel.
D. Comparison of Dirichlet forms
As mentioned in subsection I-D, one of the reasons we study q-ary symmetric channels and prove Theorems 2 and
3 is because less noisy domination implies useful bounds between Dirichlet forms. Recall that the q-ary symmetric
channel Wδ ∈ Rq×q
sto with δ ∈ [0, 1] has uniform stationary distribution u ∈ Pq (see part 3 of Proposition 4). For any
channel V ∈ Rq×q
sto that is doubly stochastic and has uniform stationary distribution, we may define a corresponding
Dirichlet form:
1
(16)
∀f ∈ Rq , EV (f, f ) = f T (Iq − V ) f
q
T

where f = [f1 · · · fq ] ∈ Rq are column vectors, and Iq ∈ Rq×q denotes the q × q identity matrix (as shown in [25]
or [26]). Our final theorem portrays that Wδ ln V implies that the Dirichlet form corresponding to V dominates the
Dirichlet form corresponding to Wδ pointwise. The Dirichlet form corresponding to Wδ is in fact a scaled version of
the so called standard Dirichlet form:
!2
q
q
X
X
1
1
fk2 −
fk
(17)
∀f ∈ Rq , Estd (f, f ) , VARu (f ) =
q
q
k=1

k=1

which is the Dirichlet form corresponding to the q-ary symmetric channel W(q−1)/q = 1u with all uniform conditional
qδ
pmfs. Indeed, using Iq − Wδ = q−1
(Iq − 1u), we have:
∀f ∈ Rq , EWδ (f, f ) =
8

qδ
Estd (f, f ) .
q−1

(18)

Fig. 2. Illustration of the additive less noisy domination region and additive degradation region for a q-ary symmetric channel when q = 3 and
δ ∈ (0, 2/3): The gray triangle denotes the probability simplex of noise pmfs P3 . The dotted line denotes the parametrized family of noise pmfs of
3-ary symmetric channels {wδ ∈ P3 : δ ∈ [0, 1]}; its noteworthy points are w0 (corner of simplex, W0 is less noisy than every channel), wδ for
some fixed δ ∈ (0, 2/3) (noise pmf of 3-ary symmetric channel Wδ under consideration), w2/3 = u (uniform pmf, W2/3 is more noisy than every
channel), wτ with τ = 1−(δ/2) (Wτ is the extremal symmetric channel that is degraded by Wδ ), wγ with γ = (1−δ)/(1−δ +(δ/4)) (Wγ is a 3ary symmetric
by Wδ but Wδ ln Wγ ), and w1 (edge of simplex). The magenta triangle denotes the additive degradation
 channel that is not degraded

regionconv wδ , wδ P3 , wδ P32 of Wδ . The green convex region denotes the additive less noisydomination region of Wδ , and the yellow region
conv wδ , wδ P3 , wδ P32 , wγ , wγ P3 , wγ P32
is its lower bound while the circular cyan region v ∈ P3 : kv − uk`2 ≤ kwδ − uk`2 (which is
a hypersphere for general q ≥ 3) is its upper bound. Note that we do not need to specify the underlying group because there is only one group of
order 3.

The standard Dirichlet form is the usual choice for Dirichlet form comparison because its logarithmic Sobolev constant
has been precisely computed in [25, Appendix, Theorem A.1]. So, we present Theorem 4 using Estd rather than EWδ .


q×q
Theorem 4 (Domination of Dirichlet Forms). Given the doubly stochastic channels Wδ ∈ Rsto
with δ ∈ 0, q−1
and
q
q×q
V ∈ Rsto , if Wδ ln V , then:
qδ
∀f ∈ Rq , EV (f, f ) ≥
Estd (f, f ) .
q−1
An extension of Theorem 4 is proved in section VII. The domination of Dirichlet forms shown in Theorem 4
has several useful consequences. A major consequence is that we can immediately establish Poincaré (spectral gap)
inequalities and logarithmic Sobolev inequalities (LSIs) for the channel V using the corresponding inequalities for
q×q
q-ary symmetric channels. For example, the LSI for Wδ ∈ Rsto
with q > 2 is:
 (q − 1) log(q − 1)
D f 2 u||u ≤
EWδ (f, f )
(q − 2)δ

(19)

Pq
2
for all f ∈ Rq such that
k=1 fk = q, where we use (54) and the logarithmic Sobolev constant computed in
part 1 of Proposition 12. As shown in Appendix B, (19) is easily established using the known logarithmic Sobolev
constant corresponding to the standard Dirichlet form. Using the LSI for V that follows from (19) and Theorem 4,
we immediately obtain guarantees on the convergence rate and hypercontractivity properties of the associated Markov
semigroup {exp(−t(Iq − V )) : t ≥ 0}. We refer readers to [25] and [26] for comprehensive accounts of such topics.
E. Outline
We briefly outline the content of the ensuing sections. In section III, we study the structure of less noisy domination
and degradation regions of channels. In section IV, we prove Theorem 1 and present some other equivalent characterizations of ln . We then derive several necessary and sufficient conditions for less noisy domination among additive
9

noise channels in section V, which together with the results of section III, culminates in a proof of Theorem 3. Section
VI provides a proof of Theorem 2, and section VII introduces LSIs and proves an extension of Theorem 4. Finally,
we conclude our discussion in section VIII.
III. L ESS NOISY DOMINATION AND DEGRADATION REGIONS
In this section, we focus on understanding the “geometric” aspects of less noisy domination and degradation by
channels. We begin by deriving some simple characteristics of the sets of channels that are dominated by some fixed
channel in the less noisy and degraded senses. We then specialize our results for additive noise channels, and this
add
culminates in a complete characterization of DW
and derivations of certain properties of Ladd
Wδ presented in Theorem
δ
3.
Let W ∈ Rq×r
sto be a fixed channel with q, r ∈ N, and define its less noisy domination region:

LW , V ∈ Rq×r
(20)
sto : W ln V
as the set of all channels on the same input and output alphabets that are dominated by W in the less noisy sense.
Moreover, we define the degradation region of W :

q×r
DW , V ∈ Rsto
: W deg V
(21)
as the set of all channels on the same input and output alphabets that are degraded versions of W . Then, LW and DW
satisfy the properties delineated below.
Proposition 5 (Less Noisy Domination and Degradation Regions). Given the channel W ∈ Rq×r
sto , its less noisy
domination region LW and its degradation region DW are non-empty, closed, convex, and output alphabet permutation
symmetric (i.e. V ∈ LW ⇒ V P ∈ LW and V ∈ DW ⇒ V P ∈ DW for every permutation matrix P ∈ Rr×r ).
Proof.
Non-Emptiness of LW and DW : W ln W ⇒ W ∈ LW , and W deg W ⇒ W ∈ DW . So, LW and DW are
non-empty.
Closure of LW : Fix any two pmfs PX , QX ∈ Pq , and consider a sequence of channels Vk ∈ LW such that Vk → V ∈
Rq×r
sto (with respect to the Frobenius norm). Then, we also have PX Vk → PX V and QX Vk → QX V (with respect to
the `2 -norm). Hence, we get:
D (PX V ||QX V ) ≤ lim inf D (PX Vk ||QX Vk )
k→∞

≤ D (PX W ||QX W )
where the first line follows from the lower semicontinuity of KL divergence [27, Theorem 1], [28, Theorem 3.6,
Section 3.5], and
 the second line holds because Vk ∈ LW . This implies that for any two pmfs PX , QX ∈ Pq , the set
S (PX , QX ) = V ∈ Rq×r
sto : D (PX W ||QX W ) ≥ D (PX V ||QX V ) is actually closed. Using Proposition 1, we have
that:
\
LW =
S (PX , QX ).
PX ,QX ∈Pq

So, LW is closed since it is an intersection of closed sets [29].
Closure of DW : Consider a sequence of channels Vk ∈ DW such that Vk → V ∈ Rq×r
sto . Since each Vk = W Ak
r×r
for some channel Ak ∈ Rr×r
sto belonging to the compact set Rsto , there exists a subsequence Akm that converges by
r×r
(sequential) compactness [29]: Akm → A ∈ Rsto
. Hence, V ∈ DW since Vkm = W Akm → W A = V , and DW is a
closed set.
Convexity of LW : Suppose V1 , V2 ∈ LW , and let λ ∈ [0, 1] and λ̄ = 1 − λ. Then, for every PX , QX ∈ Pq , we have:
D(PX W ||QX W ) ≥ D(PX (λV1 + λ̄V2 )||QX (λV1 + λ̄V2 ))
by the convexity of KL divergence. Hence, LW is convex.
r×r
Convexity of DW : If V1 , V2 ∈ DW so that V1 = W A1 and V2 = W A2 for some A1 , A2 ∈ Rsto
, then λV1 + λ̄V2 =
W (λA1 + λ̄A2 ) ∈ DW for all λ ∈ [0, 1], and DW is convex.
Symmetry of LW : This is obvious from Proposition 1 because KL divergence is invariant to permutations of its input
pmfs.
Symmetry of DW : Given V ∈ DW so that V = W A for some A ∈ Rr×r
sto , we have that V P = W AP ∈ DW for
every permutation matrix P ∈ Rr×r . This completes the proof.


10

While the channels in LW and DW all have the same output alphabet as W , as defined in (20) and (21), we may
extend the output alphabet of W by adding zero probability letters. So, separate less noisy domination and degradation
regions can be defined for each output alphabet size that is at least as large as the original output alphabet size of W .
A. Less noisy domination and degradation regions for additive noise channels
Often in information theory, we are concerned with additive noise channels on an Abelian group (X , ⊕) with X = [q]
and q ∈ N, as defined in (9). Such channels are completely defined by a noise pmf PZ ∈ Pq with corresponding channel
q×q
transition probability matrix circX (PZ ) ∈ Rq×q
sto . Suppose W = circX (w) ∈ Rsto is an additive noise channel with
noise pmf w ∈ Pq . Then, we are often only interested in the set of additive noise channels that are dominated by W .
We define the additive less noisy domination region of W :
Ladd
W , {v ∈ Pq : W ln circX (v)}

(22)

as the set of all noise pmfs whose corresponding channel transition matrices are dominated by W in the less noisy
sense. Likewise, we define the additive degradation region of W :
add
DW
, {v ∈ Pq : W deg circX (v)}

(23)

as the set of all noise pmfs whose corresponding channel transition matrices are degraded versions of W . (These
definitions generalize (14) and (15), and can also hold for any non-additive noise channel W .) The next proposition
add
illustrates certain properties of Ladd
W and explicitly characterizes DW .
Proposition 6 (Additive Less Noisy Domination and Degradation Regions). Given the additive noise channel W =
q×q

circX (w) ∈ Rsto with noise pmf w ∈ Pq , we have:

add
q×q
1) Ladd
: x ∈ X } defined
W and DW are non-empty, closed, convex, and invariant under the permutations {Px ∈ R
add
add
add
add
in (4) (i.e. v ∈ LW ⇒ vPx ∈ LW and v ∈ DW ⇒ vPx ∈ DW for every x ∈ X ).
add
2) DW
= conv ({wPx : x ∈ X }) = {v ∈ Pq : w X v}, where X denotes the group majorization preorder as
defined in Appendix A.

To prove Proposition 6, we will need the following lemma.
Lemma 1 (Additive Noise Channel Degradation). Given two additive noise channels W = circX (w) ∈ Rq×q
sto and
V = circX (v) ∈ Rq×q
sto with noise pmfs w, v ∈ Pq , W deg V if and only if V = W circX (z) = circX (z)W for some
z ∈ Pq (i.e. for additive noise channels W deg V , the channel that degrades W to produce V is also an additive
noise channel without loss of generality).
Proof. Since X -circulant matrices commute, we must have W circX (z) = circX (z)W for every z ∈ Pq . Furthermore,
V = W circX (z) for some z ∈ Pq implies that W deg V by Definition 1. So, it suffices to prove that W deg V implies
V = W circX (z) for some z ∈ Pq . By Definition 1, W deg V implies that V = W R for some doubly stochastic
q×q
channel R ∈ Rsto
(as V and W are doubly stochastic). Let r with rT ∈ Pq be the first column of R, and s = W r
T
with s ∈ Pq be the first column of V . Then, it is straightforward to verify using (7) that:


V = s P1 s P2 s · · · Pq−1 s


= W r P1 W r P2 W r · · · Pq−1 W r


= W r P1 r P2 r · · · Pq−1 r
where the third equality holds because {Px : x ∈ X } are X -circulant matrices which commute with W . Hence, V is
the product of W and an X -circulant stochastic matrix, i.e. V = W circX (z) for some z ∈ Pq . This concludes the
proof.

We emphasize that in Lemma 1, the channel that degrades W to produce V is only an additive noise channel
without loss of generality. We can certainly have V = W R with a non-additive noise channel R. Consider for instance,
V = W = 11T /q, where every doubly stochastic matrix R satisfies V = W R. However, when we consider V = W R
with an additive noise channel R, V corresponds to the channel W with an additional independent additive noise term
associated with R. We now prove Proposition 6.
Proof of Proposition 6.
add
Part 1: Non-emptiness, closure, and convexity of Ladd
W and DW can be proved in exactly the same way as in Proposition
5, with the additional observation that the set of X -circulant matrices is closed and convex. Moreover, for every x ∈ X :
W ln W Px = circX (wPx ) ln W
W deg W Px = circX (wPx ) deg W
11

where the equalities follow from (7). These inequalities and the transitive properties of ln and deg yield the invariance
add
q×q
of Ladd
: x ∈ X }.
W and DW with respect to {Px ∈ R
add
Part 2: Lemma 1 is equivalent to the fact that v ∈ DW
if and only if circX (v) = circX (w) circX (z) for some z ∈ Pq .
add
This implies that v ∈ DW if and only if v = w circX (z) for some z ∈ Pq (due to (7) and the fact that X -circulant
matrices commute). Applying Proposition 14 from Appendix A completes the proof.

We remark that part 1 of Proposition 6 does not require W to be an additive noise channel. The proofs of closure,
add
add
convexity, and invariance with respect to {Px ∈ Rq×q : x ∈ X } hold for general W ∈ Rq×q
sto . Moreover, LW and DW
add
add
are non-empty because u ∈ LW and u ∈ DW .
B. Less noisy domination and degradation regions for symmetric channels
Since q-ary symmetric channels for q ∈ N are additive noise channels, Proposition 6 holds for symmetric channels.
In this subsection, we deduce some simple results that are unique to symmetric channels. The first of these is a
specialization of part 2 of Proposition 6 which states that the additive degradation region of a symmetric channel can
be characterized by traditional majorization instead of group majorization.
Corollary 1 (Degradation Region of Symmetric Channel). The q-ary symmetric channel Wδ = circX (wδ ) ∈ Rq×q
sto for
δ ∈ [0, 1] has additive degradation region:


add
DW
= {v ∈ Pq : wδ maj v} = conv wδ Pqk : k ∈ [q]
δ
where maj denotes the majorization preorder defined in Appendix A, and Pq ∈ Rq×q is defined in (8).
Proof. From part 2 of Proposition 6, we have that:


add
DW
= conv ({wδ Px : x ∈ X }) = conv wδ Pqk : k ∈ [q]
δ


= conv wδ P : P ∈ Rq×q is a permutation matrix
= {v ∈ Pq : w maj v}
where the second and third equalities hold regardless of the choice of group (X , ⊕), because the sets of all cyclic
or regular permutations of wδ = (1 − δ, δ/(q − 1), . . . , δ/(q − 1)) equal {wδ Px : x ∈ X }. The final equality follows
from the definition of majorization in Appendix A.

With this geometric characterization of the additive degradation region, it is straightforward
to find the extremal

.
Indeed,
we compute τ by
symmetric channel Wτ that is a degraded version of Wδ for some fixed δ ∈ [0, 1]\ q−1
q


using the fact that the noise pmf wτ ∈ conv wδ Pqk : k = 1, . . . , q − 1 :
wτ =

q−1
X

λi wδ Pqi

(24)

i=1

for some λ1 , . . . , λq−1 ∈ [0, 1] such that λ1 + · · · + λq−1 = 1. Solving (24) for τ and λ1 , . . . , λq−1 yields:
τ =1−
and λ1 = · · · = λq−1 =

1
q−1 ,

δ
q−1

(25)

which means that:
q−1

1 X
wτ =
wδ Pqi .
(26)
q − 1 i=1


q−1
This is illustrated in Figure 2 for the case where δ ∈ 0, q−1
and τ > q−1
, the symmetric
q
q > δ. For δ ∈ 0, q
channels that are degraded versions of Wδ are {Wγ : γ ∈ [δ, τ ]}. In particular, for such γ ∈ [δ, τ ], Wγ = Wδ Wβ with
δ
β = (γ − δ)/(1 − δ − q−1
) using the proof of part 5 of Proposition 4 in Appendix B.
In the spirit of comparing symmetric and erasure channels as done in [15] for the binary input case, our next result
shows that a q-ary symmetric channel can never be less noisy than a q-ary erasure channel.
q×(q+1)

Proposition 7 (Symmetric Channel 6ln Erasure Channel). For q ∈ N\{1}, given a q-ary erasure channel E ∈ Rsto
with erasure probability  ∈ (0, 1), there does not exist δ ∈ (0, 1) such that the corresponding q-ary symmetric channel
Wδ ∈ Rq×q
sto on the same input alphabet satisfies Wδ ln E .

12

Proof. For a q-ary erasure channel E with  ∈ (0, 1), we always have D(uE ||∆0 E ) = +∞ for u, ∆0 = (1, 0, . . . , 0) ∈
Pq . On the other hand, for any q-ary symmetric channel Wδ with δ ∈ (0, 1), we have D(PX Wδ ||QX Wδ ) < +∞ for
every PX , QX ∈ Pq . Thus, Wδ 6ln E for any δ ∈ (0, 1).

In fact, the argument for Proposition 7 conveys that a symmetric channel Wδ ∈ Rq×q
sto with δ ∈ (0, 1) satisfies
Wδ ln V for some channel V ∈ Rq×r
only
if
D(P
V
||Q
V
)
<
+∞
for
every
P
,
Q
X
X
X
X ∈ Pq . Typically, we are only
sto

interested in studying q-ary symmetric channels with q ≥ 2 and δ ∈ 0, q−1
.
For
example,
the BSC with crossover
q

probability δ is usually studied for δ ∈ 0, 12 . Indeed, the less noisy domination characteristics of the extremal q-ary
q×q
symmetric channels with δ = 0 or δ = q−1
q are quite elementary. Given q ≥ 2, W0 = Iq ∈ Rsto satisfies W0 ln V ,
q×r
and W(q−1)/q = 1u ∈ Rq×q
sto satisfies V ln W(q−1)/q , for every channel V ∈ Rsto on a common input alphabet.
q×(q+1)
For the sake of completeness, we also note that for q ≥ 2, the extremal q-ary erasure channels E0 ∈ Rsto
and
q×(q+1)
q×r
E1 ∈ Rsto
, with  = 0 and  = 1 respectively, satisfy E0 ln V and V ln E1 for every channel V ∈ Rsto
on a
common input alphabet.
The result that the q-ary symmetric channel with uniform noise pmf W(q−1)/q is more noisy than every channel on
the same input alphabet has an analogue concerning additive white Gaussian noise (AWGN) channels. Consider all
additive noise channels of the form:
Y =X +Z
(27)
where X, Y ∈ R,
 the 2input X is uncorrelated with the additive noise Z:2 E [XZ] = 0, and the noise Z has power
for some fixed σZ > 0. Let X = Xg ∼ N (0, σX ) (Gaussian distribution with mean 0 and
constraint E Z 2 ≤ σZ
2
) for some σX > 0. Then, we have:
variance σX


I Xg ; Xg + Z ≥ I Xg ; Xg + Zg
(28)
2
), Zg is independent of Xg , and equality occurs if and only if Z = Zg in distribution [28, Section
where Zg ∼ N (0, σZ
4.7]. This states that Gaussian noise is the “worst case additive noise” for a Gaussian source. Hence, the AWGN
channel is not more capable than any other additive noise channel with the same constraints. As a result, the AWGN
channel is not less noisy than any other additive noise channel with the same constraints (using Proposition 3).

IV. E QUIVALENT CHARACTERIZATIONS OF LESS NOISY PREORDER
Having studied the structure of less noisy domination and degradation regions of channels, we now consider the
problem of verifying whether a channel W is less noisy than another channel V . Since using Definition 2 or Proposition
1 directly is difficult, we often start by checking whether V is a degraded version of W . When this fails, we typically
resort to verifying van Dijk’s condition in Proposition 2, cf. [12, Theorem 2]. In this section, we prove the equivalent
characterization of the less noisy preorder in Theorem 1, and then present some useful corollaries of van Dijk’s
condition.
A. Characterization using χ2 -divergence
Recall the general measure theoretic setup and the definition of χ2 -divergence from subsection II-A. It is wellknown that KL divergence is locally approximated by χ2 -divergence, e.g. [28, Section 4.2]. While this approximation
sometimes fails globally, cf. [30], the following notable result was first shown by Ahlswede and Gács in the discrete
case in [2], and then extended to general alphabets in [3, Theorem 3]:
ηKL (W ) = ηχ2 (W ) ,

sup
PX ,QX
0<χ (PX ||QX )<+∞

χ2 (PX W ||QX W )
χ2 (PX ||QX )

(29)

2

for any Markov kernel W : H1 × X → [0, 1], where ηKL (W ) is defined as in (11), ηχ2 (W ) is the contraction coefficient
for χ2 -divergence, and the suprema in ηKL (W ) and ηχ2 (W ) are taken over all probability measures PX and QX on
(X , F). Since ηKL characterizes less noisy domination with respect to an erasure channel as mentioned in subsection I-D,
(29) portrays that ηχ2 also characterizes this. We will now prove Theorem 1 from subsection II-A, which generalizes
(29) and illustrates that χ2 -divergence actually characterizes less noisy domination by an arbitrary channel.
Proof of Theorem 1. In order to prove the forward direction, we recall the local approximation of KL divergence using
χ2 -divergence from [28, Proposition 4.2], which states that for any two probability measures PX and QX on (X , F):

2
lim+ 2 D λPX + λ̄QX ||QX = χ2 (PX ||QX )
(30)
λ→0 λ

13

where λ̄ = 1 − λ for λ ∈ (0, 1), and both sides of (30) are finite or infinite together. Then, we observe that for any
two probability measures PX and QX , and any λ ∈ [0, 1], we have:


D λPX W + λ̄QX W ||QX W ≥ D λPX V + λ̄QX V ||QX V
since W ln V . Scaling this inequality by

2
λ2

and letting λ → 0 produces:

χ2 (PX W ||QX W ) ≥ χ2 (PX V ||QX V )
as shown in (30). This proves the forward direction.
To establish the converse direction, we recall an integral representation of KL divergence using χ2 -divergence
presented in [3, Appendix A.2] (which can be distilled from the argument in [31, Theorem 1]):5
Z ∞ 2
χ (PX ||QtX )
D(PX ||QX ) =
dt
(31)
t+1
0
1
t
PX + t+1
QX for t ∈ [0, ∞), and both
for any two probability measures PX and QX on (X , F), where QtX = 1+t
sides of (31) are finite or infinite together (as a close inspection of the proof in [3, Appendix A.2] reveals). Hence, for
every PX and QX , we have by assumption:


χ2 PX W ||QtX W ≥ χ2 PX V ||QtX V

which implies that:
Z
0

∞

Z ∞ 2
χ2 (PX W ||QtX W )
χ (PX V ||QtX V )
dt ≥
dt
t+1
t+1
0
⇒ D(PX W ||QX W ) ≥ D(PX V ||QX V ) .

Hence, W ln V , which completes the proof.



B. Characterizations via the Löwner partial order and spectral radius
We will use the finite alphabet setup of subsection I-B for the remaining discussion in this paper. In the finite alphabet
q×s
setting, Theorem 1 states that W ∈ Rq×r
sto is less noisy than V ∈ Rsto if and only if for every PX , QX ∈ Pq :
χ2 (PX W ||QX W ) ≥ χ2 (PX V ||QX V ) .

(32)

This characterization has the flavor of a Löwner partial order condition. Indeed, it is straightforward to verify that for
any PX ∈ Pq and QX ∈ Pq◦ , we can write their χ2 -divergence as:
−1

χ2 (PX ||QX ) = JX diag(QX )

T
JX
.

(33)

where JX = PX − QX . Hence, we can express (32) as:
−1

JX W diag(QX W )

T
W T JX
≥ JX V diag(QX V )

−1

T
V T JX

(34)

for every JX = PX − QX such that PX ∈ Pq and QX ∈ Pq◦ . This suggests that (32) is equivalent to:
−1

W diag(QX W )

−1

W T PSD V diag(QX V )

VT

(35)

for every QX ∈ Pq◦ . It turns out that (35) indeed characterizes ln , and this is straightforward to prove directly. The
next proposition illustrates that (35) also follows as a corollary of van Dijk’s characterization in Proposition 2, and
presents an equivalent spectral characterization of ln .
q×s
q×r
and V ∈ Rsto
Proposition 8 (Löwner and Spectral Characterizations of ln ). For any pair of channels W ∈ Rsto
on the same input alphabet [q], the following are equivalent:
1) W ln V
2) For every PX ∈ Pq◦ , we have:

W diag(PX W )
5 Note

−1

−1

W T PSD V diag(PX V )

that [3, Equation (78)], and hence [1, Equation (7)], are missing factors of

14

1
t+1

VT

inside the integrals.



−1
−1
3) For every PX ∈ Pq◦ , we have R V diag(PX V ) V T ⊆ R W diag(PX W ) W T and:6


†
−1 T
−1
T
V diag(PX V ) V
= 1.
ρ W diag(PX W ) W
Proof. (1 ⇔ 2) Recall the functional F : Pq → R, F (PX ) = I(PX , WY |X ) − I(PX , VY |X ) defined in Proposition 2,
cf. [12, Theorem 2]. Since F : Pq → R is continuous on its domain Pq , and twice differentiable on Pq◦ , F is concave
if and only if its Hessian is negative semidefinite for every PX ∈ Pq◦ (i.e. −∇2 F (PX ) PSD 0 for every PX ∈ Pq◦ )
q×q
[32, Section 3.1.4]. The Hessian matrix of F , ∇2 F : Pq◦ → Rsym
, is defined entry-wise for every x, x0 ∈ [q] as:
∂2F
(PX )
∂PX (x)∂PX (x0 )

 2

∇ F (PX ) x,x0 =

where we index the matrix ∇2 F (PX ) starting at 0 rather than 1. Furthermore, a straightforward calculation shows that:
−1

∇2 F (PX ) = V diag(PX V )

V T − W diag(PX W )

−1

WT

for every PX ∈ Pq◦ . (Note that the matrix inverses here are well-defined because PX ∈ Pq◦ ). Therefore, F is concave
if and only if for every PX ∈ Pq◦ :
−1

W diag(PX W )

W T PSD V diag(PX V )

−1

V T.

This establishes the equivalence between parts 1 and 2 due to van Dijk’s characterization of ln in Proposition 2.
(2 ⇔ 3) We now derive the spectral characterization of ln using part 2. Recall the well-known fact (see [33, Theorem
1 parts (a),(f)] and [19, Theorem 7.7.3 (a)]):

†
Given positive semidefinite matrices A, B ∈ Rq×q
0 , A PSD B if and only if R(B) ⊆ R(A) and ρ A B ≤ 1.
−1
−1
Since W diag(PX W ) W T and V diag(PX V ) V T are positive semidefinite for every PX ∈ Pq◦ , applying this fact


−1
−1
shows that part 2 holds if and only if for every PX ∈ Pq◦ , we have R V diag(PX V ) V T ⊆ R W diag(PX W ) W T
and:


†
−1
−1 T
T
ρ
W diag(PX W ) W
V diag(PX V ) V
≤ 1.
−1

To prove that this inequality is actually an equality, for any PX ∈ Pq◦ , let A = W diag(PX W ) W T and B =

−1
V diag(PX V ) V T . It suffices to prove that: R(B) ⊆ R(A) and ρ A† B ≤ 1 if and only if R(B) ⊆ R(A) and
ρ A† B = 1. The converse direction is trivial, so we only establish the forward direction. Observe that PX A = 1T
†
and PX B = 1T . This implies that 1T A† B = PX (AA† )B = PX B = 1T , where
 (AA )B =† B because R(B) ⊆
†
†
R(A) and AA is the orthogonal projection matrix onto R(A). Since ρ A B ≤ 1 and A B has an eigenvalue
of 1, we have ρ A† B = 1. Thus, we have proved that part 2 holds if and only if for every PX ∈ Pq◦ , we have


−1
−1
R V diag(PX V ) V T ⊆ R W diag(PX W ) W T and:


†
−1
−1 T
T
W diag(PX W ) W
V diag(PX V ) V
= 1.
ρ


This completes the proof.

The Löwner characterization of ln in part 2 of Proposition 8 will be useful for proving some of our ensuing results.
We remark that the equivalence between parts 1 and 2 can be derived by considering several other functionals. For
instance, for any fixed pmf QX ∈ Pq◦ , we may consider the functional F2 : Pq → R defined by:
F2 (PX ) = D(PX W ||QX W ) − D(PX V ||QX V )

(36)

−1

−1

2
which has Hessian matrix, ∇2 F2 : Pq◦ → Rq×q
W T − V diag(PX V ) V T , that does
sym , ∇ F2 (PX ) = W diag(PX W )
not depend on QX . Much like van Dijk’s functional F , F2 is convex (for all QX ∈ Pq◦ ) if and only if W ln V . This is
reminiscent of Ahlswede and Gács’ technique to prove (29), where the convexity of a similar functional is established
[2].
As another example, for any fixed pmf QX ∈ Pq◦ , consider the functional F3 : Pq → R defined by:

F3 (PX ) = χ2 (PX W ||QX W ) − χ2 (PX V ||QX V )
−1

(37)

2
which has Hessian matrix, ∇2 F3 : Pq◦ → Rq×q
W T − 2 V diag(QX V )
sym , ∇ F3 (PX ) = 2 W diag(QX W )
◦
does not depend on PX . Much like F and F2 , F3 is convex for all QX ∈ Pq if and only if W ln V .
6 Note

that [1, Theorem 1 part 4] neglected to mention the inclusion relation R V diag(PX V )−1 V T

15



−1

V T , that


⊆ R W diag(PX W )−1 W T .

Finally, we also mention some specializations of the spectral radius condition in part 3 of Proposition 8. If q ≥ r
and W has full column rank, the expression for spectral radius in the proposition statement can be simplified to:


−1
(38)
ρ (W † )T diag(PX W ) W † V diag(PX V ) V T = 1
using basic properties of the Moore-Penrose pseudoinverse. Moreover, if q = r and W is non-singular, then the MoorePenrose pseudoinverses in (38) can be written as inverses, and the inclusion relation between the ranges in part 3 of
Proposition 8 is trivially satisfied (and can be omitted from the proposition statement). We have used the spectral radius
condition in this latter setting to (numerically) compute the additive less noisy domination region in Figure 2.
V. C ONDITIONS FOR LESS NOISY DOMINATION OVER ADDITIVE NOISE CHANNELS
We now turn our attention to deriving several conditions for determining when q-ary symmetric channels are less
noisy than other channels. Our interest in q-ary symmetric channels arises from their analytical tractability; Proposition
4 from subsection I-C, Proposition 12 from section VII, and [34, Theorem 4.5.2] (which conveys that q-ary symmetric
channels have uniform capacity achieving input distributions) serve as illustrations of this tractability. We focus on
additive noise channels in this section, and on general channels in the next section.
A. Necessary conditions
q×q
We first present some straightforward necessary conditions for when an additive noise channel W ∈ Rsto
with
q×q
q ∈ N is less noisy than another additive noise channel V ∈ Rsto on an Abelian group (X , ⊕). These conditions can
obviously be specialized for less noisy domination by symmetric channels.

Proposition 9 (Necessary Conditions for ln Domination over Additive Noise Channels). Suppose W = circX (w) and
V = circX (v) are additive noise channels with noise pmfs w, v ∈ Pq such that W ln V . Then, the following are true:
1) (Circle Condition) kw − uk`2 ≥ kv − uk`2 .
2) (Contraction Condition) ηKL (W ) ≥ ηKL (V ).
3) (Entropy Condition) H (v) ≥ H (w), where H : Pq → R+ is the Shannon entropy function.
Proof.
Part 1: Letting PX = (1, 0, . . . , 0) and QX = u in the χ2 -divergence characterization of ln in Theorem 1 produces:
2

2

q kw − uk`2 = χ2 (w||u) ≥ χ2 (v||u) = q kv − uk`2
since uW = uV = u, and PX W = w and PX V = v using (7). (This result can alternatively be proved using part 2
of Proposition 8 and Fourier analysis.)
Part 2: This easily follows from Proposition 1 and (11).
Part 3: Letting PX = (1, 0, . . . , 0) and QX = u in the KL divergence characterization of ln in Proposition 1 produces:
log (q) − H (w) = D (w||u) ≥ D (v||u) = log (q) − H (v)


via the same reasoning as part 1. This completes the proof.
We remark that the aforementioned necessary conditions have many generalizations. Firstly, if W, V ∈
doubly stochastic matrices, then the generalized circle condition holds:
≥ V − W q−1

W − W q−1
q

Fro

q

Fro

Rq×q
sto

are
(39)

where W(q−1)/q = 1u is the q-ary symmetric channel whose conditional pmfs are all uniform, and k·kFro denotes the
Frobenius norm. Indeed, letting PX = ∆x = (0, . . . , 1, . . . , 0) for x ∈ [q], which has unity in the (x + 1)th position,
in the proof of part 1 and then adding the inequalities corresponding to every x ∈ [q] produces (39). Secondly, the
q×s
contraction condition in Proposition 9 actually holds for any pair of general channels W ∈ Rq×r
sto and V ∈ Rsto on a
common input alphabet (not necessarily additive noise channels). Moreover, we can start with Theorem 1 and take the
suprema of the ratios in χ2 (PX W ||QX W ) /χ2 (PX ||QX ) ≥ χ2 (PX V ||QX V ) /χ2 (PX ||QX ) over all PX (6= QX ) to
get:
ρmax (QX , W ) ≥ ρmax (QX , V )
(40)
for any QX ∈ Pq , where ρmax (·) denotes maximal correlation which is defined later in part 3 of Proposition 12, cf.
[35], and we use [36, Theorem 3] (or the results of [37]). A similar result also holds for the contraction coefficient for
KL divergence with fixed input pmf (see e.g. [36, Definition 1] for a definition).

16

B. Sufficient conditions
q×q
We next portray a sufficient condition for when an additive noise channel V ∈ Rsto
is a degraded version of a
q×q
symmetric channel Wδ ∈ Rsto . By Proposition 3, this is also a sufficient condition for Wδ ln V .
Proposition 10 (Degradation by Symmetric Channels). Given an additive noise channel V = circX (v) with noise pmf
v ∈ Pq and minimum probability τ = min{[V ]i,j : 1 ≤ i, j ≤ q}, we have:
0 ≤ δ ≤ (q − 1) τ ⇒ Wδ deg V
where Wδ ∈

Rq×q
sto

is a q-ary symmetric channel.

Proof. Using Corollary 1, it suffices to prove that the noise pmf w(q−1)τ maj v. Since 0 ≤ τ ≤ 1q , we must have
0 ≤ (q − 1)τ ≤ q−1
q . So, all entries of w(q−1)τ , except (possibly) the first, are equal to its minimum entry of τ . As
v ≥ τ (entry-wise), w(q−1)τ maj v because the conditions of part 3 in Proposition 13 in Appendix A are satisfied. 
It is compelling to find a sufficient condition for Wδ ln V that does not simply ensure Wδ deg V (such as Proposition
10 and Theorem 2). The ensuing proposition elucidates such a sufficient condition for additive noise channels. The
general strategy for finding such a condition for additive noise channels is to identify a noise pmf that belongs to
add
add
Ladd
Wδ \DWδ . One can then use Proposition 6 to explicitly construct a set of noise pmfs that is a subset of LWδ but
add
strictly includes DWδ . The proof of Proposition 11 finds such a noise pmf (that corresponds to a q-ary symmetric
channel).
Proposition 11 (Less Noisy Dominationby Symmetric
Channels). Given an additive noise channel V = circX (v) with

we
have:
noise pmf v ∈ Pq and q ≥ 2, if for δ ∈ 0, q−1
q



v ∈ conv wδ Pqk : k ∈ [q] ∪ wγ Pqk : k ∈ [q]
then Wδ ln V , where Pq ∈ Rq×q is defined in (8), and:
γ=



1−δ
δ
,
1
.
∈
1
−
δ
q−1
1 − δ + (q−1)
2

Proof. Due to Proposition 6 and {wγ Px : x ∈ X } = {wγ Pqk : k ∈ [q]}, it suffices toprove that Wδ ln Wγ . Since
q−1
δ = 0 ⇒ γ = 1 and δ = q−1
. So, we assume that
⇒ γ = q−1
q
q , Wδ ln Wγ is certainly true for δ ∈ 0, q

δ ∈ 0, q−1
,
which
implies
that:
q


q−1
1−δ
∈
,1 .
γ=
δ
q
1 − δ + (q−1)
2
Since our goal is to show Wδ ln Wγ , we prove the equivalent condition in part 2 of Proposition 8 that for every
PX ∈ Pq◦ :
−1

Wδ diag(PX Wδ )

−1

WδT PSD Wγ diag(PX Wγ )

WγT

⇔ Wγ−1 diag(PX Wγ ) Wγ−1 PSD Wδ−1 diag(PX Wδ ) Wδ−1
⇔ diag(PX Wγ ) PSD Wγ Wδ−1 diag(PX Wδ ) Wδ−1 Wγ
−1

−21

⇔ Iq PSD diag(PX Wγ ) 2 Wτ diag(PX Wδ )Wτ diag(PX Wγ )
−1

−21

⇔ 1 ≥ diag(PX Wγ ) 2 Wτ diag(PX Wδ )Wτ diag(PX Wγ )
⇔ 1 ≥ diag(PX Wγ )

− 12

Wτ diag(PX Wδ )

op

1
2

op

where the second equivalence holds because Wδ and Wγ are symmetric and invertible (see part 4 of Proposition 4
and [19, Corollary 7.7.4]), the third and fourth equivalences are non-singular ∗-congruences with Wτ = Wδ−1 Wγ =
Wγ Wδ−1 and:
γ−δ
τ=
>0
δ
1 − δ − q−1
which can be computed as in the proof of Proposition 15 in Appendix C, and k·kop denotes the spectral or operator
norm.7
q×q
7 Note that we cannot use the strict Löwner partial order 
PSD (for A, B ∈ Rsym , A PSD B if and only if A − B is positive definite) for these
equivalences as 1T Wγ−1 diag(PX Wγ ) Wγ−1 1 = 1T Wδ−1 diag(PX Wδ ) Wδ−1 1.

17

−1

1

It is instructive to note that if Wτ ∈ Rq×q
transition matrix diag(PX Wγ ) 2 Wτ diag(PX Wδ ) 2
sto , then the divergence
p
√
T
T
has right singular vector PX Wδ and left singular vector PX Wγ corresponding to its maximum singular value
of unity (where the square roots are applied entry-wise)–see [36] and the references therein. So, Wτ ∈ Rq×q
sto is a
δ
sufficient condition for Wδ ln Wγ . Since Wτ ∈ Rq×q
if
and
only
if
0
≤
τ
≤
1
if
and
only
if
δ
≤
γ
≤
1
−
sto
q−1 , the
latter condition also implies that Wδ ln Wγ . However, we recall from (25) in subsection III-B that Wδ deg Wγ for
δ
δ
, while we seek some 1 − q−1
< γ ≤ 1 for which Wδ ln Wγ . When q = 2, we only have:
δ ≤ γ ≤ 1 − q−1
γ=

1−δ
δ
=1−
=1−δ
δ
q
−
1
1 − δ + (q−1)
2

which implies that Wδ deg Wγ is true for q = 2. On the other hand, when q ≥ 3, it is straightforward to verify that:


1−δ
δ
γ=
∈ 1−
,1
δ
q−1
1 − δ + (q−1)
2

.
since δ ∈ 0, q−1
q
From the preceding discussion, it suffices to prove for q ≥ 3 that for every PX ∈ Pq◦ :
−21

diag(PX Wγ )

−21

Wτ diag(PX Wδ )Wτ diag(PX Wγ )

Since τ > 0, and 0 ≤ τ ≤ 1 does not produce γ > 1 −
strictly negative entries along the diagonal. Notice that:

δ
q−1 ,

≤ 1.
op

we require that τ > 1 (⇔ γ > 1 −

δ
q−1 )

so that Wτ has

∀x ∈ [q], diag(∆x Wγ ) PSD Wγ Wδ−1 diag(∆x Wδ ) Wδ−1 Wγ
where ∆x = (0, . . . , 1, . . . , 0) ∈ Pq denotes the Kronecker delta pmf with unity at the (x + 1)th position, implies that:
diag(PX Wγ ) PSD Wγ Wδ−1 diag(PX Wδ ) Wδ−1 Wγ

for every PX ∈ Pq◦ , because convex combinations preserve the Löwner relation. So, it suffices to prove that for every
x ∈ [q]:
− 1

− 1
≤1
diag wγ Pqx 2 Wτ diag wδ Pqx Wτ diag wγ Pqx 2
op

where Pq ∈ Rq×q is defined in (8), because ∆x M extracts the (x + 1)th row of a matrix M ∈ Rq×q . Let us define
− 1

− 1
Ax , diag wγ Pqx 2 Wτ diag wδ Pqx Wτ diag wγ Pqx 2 for each x ∈ [q]. Observe that for every x ∈ [q], Ax ∈ Rq×q
0
is
diagonalizable by the real spectral theorem [38, Theorem 7.13], and has a strictly positive eigenvector
porthogonally
wγ Pqx corresponding to the eigenvalue of unity:
q
q
∀x ∈ [q],
wγ Pqx Ax = wγ Pqx
p
so that all other eigenvectors of Ax have some strictly negative entries since they are orthogonal to wγ Pqx . Suppose Ax
is entry-wise non-negative for every x ∈ [q]. Then, the largest eigenvalue (known as the Perron-Frobenius eigenvalue)
and the spectral radius of each Ax is unity by the Perron-Frobenius theorem [19, Theorem 8.3.4], which proves that
kAx kop ≤ 1 for every x ∈ [q]. Therefore, it is sufficient to prove that Ax is entry-wise non-negative for every x ∈ [q].

− 1
Equivalently, we can prove that Wτ diag wδ Pqx Wτ is entry-wise non-negative for every x ∈ [q], since diag wγ Pqx 2
scales the rows or columns of the matrix it is pre- or post-multiplied with using strictly positive scalars.
We now show the equivalent condition below that the minimum possible entry of Wτ diag wδ Pqx Wτ is non-negative:
0 ≤ min

q
X

x∈[q]
r=1
1≤i,j≤q |

[Wτ ]i,r [Wδ ]x+1,r [Wτ ]r,j
=

=

{z
[Wτ diag(wδ Pqx )Wτ ]i,j

}

τ (1 − δ)(1 − τ ) δτ (1 − τ )
δτ 2
+
+ (q − 2)
.
2
q−1
(q − 1)
(q − 1)3

The above equality holds because for i 6= j:
q

q

δ X
δ X
[Wτ ]i,r [Wτ ]r,i ≥
[Wτ ]i,r [Wτ ]r,j
q − 1 r=1 |
{z
} q − 1 r=1
= [Wτ ]2i,r ≥ 0

18

(41)


2
δ
is clearly true (using, for example, the rearrangement inequality in [39, Section 10.2]), and adding 1−δ− q−1
[Wτ ]i,k ≥

δ
[Wτ ]i,p
0 (regardless of the value of 1 ≤ k ≤ q) to the left summation increases its value, while adding 1 − δ − q−1
[Wτ ]p,j < 0 (which exists for an appropriate value 1 ≤ p≤ q as τ > 1) to the right summation decreases its value.
As a result, the minimum possible entry of Wτ diag wδ Pqx Wτ can be achieved with x + 1 = i 6= j or i 6= j = x + 1.
δ
We next substitute τ = (γ − δ)/ 1 − δ − q−1
into (41) and simplify the resulting expression to get:
!



δ
(q − 2) δ (γ − δ)
δ
.
0 ≤ (γ − δ)
−γ
1−δ+
+
1−
2
q−1
q−1
(q − 1)
1−δ
The right hand side of this inequality is quadratic in γ with roots γ = δ and γ = 1−δ+(δ/(q−1)
2 ) . Since the coefficient
2
of γ in this quadratic is strictly negative:


δ
δ
(q − 2) δ
<0⇔1−δ+
2 − 1−δ+ q−1
2 >0
(q − 1)
(q − 1)
|
{z
}
coefficient of γ 2


the minimum possible entry of Wτ diag wδ Pqx Wτ is non-negative if and only if:
δ≤γ≤
where we use the fact that
completes the proof.

1−δ
1−δ+(δ/(q−1)2 )

1−δ
δ
1 − δ + (q−1)
2

δ
≥ 1 − q−1
≥ δ. Therefore, γ =

1−δ
1−δ+(δ/(q−1)2 )

produces Wδ ln Wγ , which


Heretofore we have derived results concerning less noisy domination and degradation regions in section III, and
proven several necessary and sufficient conditions for less noisy domination of additive noise channels by symmetric
channels in this section. We finally have all the pieces in place to establish Theorem 3 from section II. In closing this
section, we indicate the pertinent results that coalesce to justify it.
Proof of Theorem 3. The first equality follows from Corollary 1. The first set inclusion is obvious, and its strictness
follows from the proof of Proposition 11. The second set inclusion follows from Proposition 11. The third set inclusion
follows from the circle condition (part 1) in Proposition 9. Lastly, the properties of Ladd
Wδ are derived in Proposition
6.

VI. S UFFICIENT CONDITIONS FOR DEGRADATION OVER GENERAL CHANNELS
q×q
While Propositions 10 and 11 present sufficient conditions for a symmetric channel Wδ ∈
sto to be less noisy than
 Rq−1
an additive noise channel, our more comprehensive objective is to find the maximum δ ∈ 0, q such that Wδ ln V
for any given general channel V ∈ Rq×r
sto on a common input alphabet. We may formally define this maximum δ (that
characterizes the extremal symmetric channel that is less noisy than V ) as:




q−1
δ ? (V ) , sup δ ∈ 0,
: Wδ ln V
(42)
q

and for every 0 ≤ δ < δ ? (V ), Wδ ln V . Alternatively, we can define a non-negative (less noisy) domination factor
function for any channel V ∈ Rq×r
sto :
µV (δ) ,

sup
PX ,QX ∈Pq :
0<D(PX Wδ ||QX Wδ )<+∞

D (PX V ||QX V )
D (PX Wδ ||QX Wδ )

(43)



with δ ∈ 0, q−1
, which is analogous to the contraction coefficient for KL divergence since µV (0) , ηKL (V ). Indeed,
q
we may perceive PX Wδ and QX Wδ in the denominator of (43) as pmfs inside the “shrunk” simplex conv({wδ Pqk :
k ∈ [q]}), and (43) represents a contraction coefficient of V where the supremum is taken over this “shrunk” simplex.8
For simplicity, consider a channel V ∈ Rq×r
sto that is strictly positive entry-wise, and has domination factor
 function
q−1
+
µV : 0, q−1
→
R
,
where
the
domain
excludes
zero
because
µ
is
only
interesting
for
δ
∈
0,
, and this
V
q
q
exclusion also affords us some analytical simplicity. It is shown in Proposition 15 of Appendix C that µV is always
8 Pictorially,

the “shrunk” simplex is the magenta triangle in Figure 2 while the simplex itself is the larger gray triangle.

19


finite on 0, q−1
, continuous, convex, strictly increasing, and has a vertical asymptote at δ =
q
PX , QX ∈ Pq :
µV (δ) D (PX Wδ ||QX Wδ ) ≥ D (PX V ||QX V )

q−1
q .

Since for every

we have µV (δ) ≤ 1 if and only if Wδ ln V . Hence, using the strictly increasing property of µV : 0,
we can also characterize δ ? (V ) as:
δ ? (V ) = µ−1
V (1)

(44)
q−1
q



→ R+ ,
(45)

where µ−1
V denotes the inverse function of µV , and unity is in the range of µV by Theorem 2 since V is strictly
positive entry-wise.
q×r
We next briefly delineate how one might computationally approximate δ ? (V ) for a given general channel V ∈ Rsto
.
?
From part 2 of Proposition 8, it is straightforward to obtain the following minimax characterization of δ (V ):
δ ? (V ) =

inf

sup

PX ∈Pq◦ δ∈S(PX )

δ

(46)


 
−1
−1
: Wδ diag(PX Wδ ) WδT PSD V diag(PX V ) V T . The infimum in (46) can be naïvely
where S(PX ) = δ ∈ 0, q−1
q
approximated by sampling several PX ∈ Pq◦ . The supremum in (46) can be estimated by verifying collections of rational
(ratio of polynomials) inequalities in δ. This is because the positive semidefiniteness of a matrix is equivalent to the
non-negativity of all its principal minors by Sylvester’s criterion [19, Theorem 7.2.5]. Unfortunately, this procedure
appears to be rather cumbersome.
Since analytically computing δ ? (V ) also seems intractable, we now prove Theorem 2 from section II. Theorem 2
provides a sufficient condition for Wδ deg V (which implies Wδ ln V using Proposition 3) by restricting its attention
?
to the case where V ∈ Rq×q
sto with q ≥ 2. Moreover, it can be construed as a lower bound on δ (V ):
ν
(47)
δ ? (V ) ≥
ν
1 − (q − 1)ν + q−1
where ν = min {[V ]i,j : 1 ≤ i, j ≤ q} is the minimum conditional probability in V .
q×q
Proof of Theorem 2. Let the channel V ∈ Rsto
have the conditional pmfs v1 , . . . , vq ∈ Pq as its rows:

T
V = v1T v2T · · · vqT .

From the proof of Proposition 10, we know that w(q−1)ν maj vi for every i ∈ {1, . . . , q}. Using part 1 of Proposition
13 in Appendix A (and the fact that the set of all permutations of w(q−1)ν is exactly the set of all cyclic permutations
of w(q−1)ν ), we can write this as:
∀i ∈ {1, . . . , q} , vi =

q
X

pi,j w(q−1)ν Pqj−1

j=1

Pq
where Pq ∈ R
is given in (8), and {pi,j ≥ 0 : 1 ≤ i, j ≤ q} are the convex weights such that j=1 pi,j = 1 for
every i ∈ {1, . . . , q}. Defining P ∈ Rq×q
sto entry-wise as [P ]i,j = pi,j for every 1 ≤ i, j ≤ q, we can also write this
9
equation as V = P W(q−1)ν . Observe that:
!
q
X
Y
P =
pi,ji Ej1 ,...,jq
q×q

1≤j1 ,...,jq ≤q

i=1

Qq
where { i=1 pi,ji : 1 ≤ j1 , . . . , jq ≤ q} form a product pmf of convex weights, and for every 1 ≤ j1 , . . . , jq ≤ q:

T
Ej1 ,...,jq , ej1 ej2 · · · ejq
where ei ∈ Rq is the ith standard basis (column) vector that has unity at the ith entry and zero elsewhere. Hence, we
get:
!
q
X
Y
V =
pi,ji Ej1 ,...,jq W(q−1)ν .
1≤j1 ,...,jq ≤q

i=1

q×q
9 Matrices of the form V = P W
are not necessarily degraded versions of W(q−1)ν : W(q−1)ν 6deg V (although
(q−1)ν with P ∈ Rsto
we certainly have input-output degradation: W(q−1)ν iod V ). As a counterexample, consider W1/2 for q = 3, and P = [1 0 0; 1 0 0; 0 1 0],
where the colons separate the rows of the matrix. If W1/2 deg P W1/2 , then there exists A ∈ R3×3
sto such that P W1/2 = W1/2 A. However,
−1
A = W1/2
P W1/2 = (1/4) [3 0 1; 3 0 1; −1 4 1] has a strictly negative entry, which leads to a contradiction.

20



Suppose there exists δ ∈ 0, q−1
such that for all j1 , . . . , jq ∈ {1, . . . , q}:
q
∃Mj1 ,...,jq ∈ Rq×q
sto , Ej1 ,...,jq W(q−1)ν = Wδ Mj1 ,...,jq
i.e. Wδ deg Ej1 ,...,jq W(q−1)ν . Then, we would have:
X

q
Y

1≤j1 ,...,jq ≤q

i=1

V = Wδ

!
pi,ji

Mj1 ,...,jq

{z

|

}

stochastic matrix

which implies that Wδ deg V .
q×q
We will demonstrate that for every j1 , . . . , jq ∈{1, . . . , q}, there exists Mj1 ,...,jq ∈ Rsto
such that Ej1 ,...,jq W(q−1)ν =
ν
1
Wδ Mj1 ,...,jq when 0 ≤ δ ≤ ν/ 1−(q−1)ν+ q−1 . Since 0 ≤ ν ≤ q , the preceding inequality implies that 0 ≤ δ ≤ q−1
q ,
1
1
where δ = q−1
is
possible
if
and
only
if
ν
=
.
When
ν
=
,
V
=
W
is
the
channel
with
all
uniform
conditional
(q−1)/q
q
q
q
pmfs, and W(q−1)/q deg V clearly holds. Hence, we assume that 0 ≤ ν < 1q so that 0 ≤ δ < q−1
q , and establish the
equivalent condition that for every j1 , . . . , jq ∈ {1, . . . , q}:
Mj1 ,...,jq = Wδ−1 Ej1 ,...,jq W(q−1)ν
−δ
using part 4 of Proposition 4. Clearly, all
is a valid stochastic matrix. Recall that Wδ−1 = Wτ with τ = 1−δ−(δ/(q−1))
the rows of each Mj1 ,...,jq sum to unity. So, it remains to verify that each Mj1 ,...,jq has non-negative entries. For any
j1 , . . . , jq ∈ {1, . . . , q} and any i, j ∈ {1, . . . , q}:


Mj1 ,...,jq i,j ≥ ν (1 − τ ) + τ (1 − (q − 1) ν)

where the right hand side is the minimum possible entry of any Mj1 ,...,jq (with equality when j1 > 1 and j2 = j3 =
· · · = jq = 1 for example) as τ < 0 and 1 − (q − 1) ν > ν. To ensure each Mj1 ,...,jq is entry-wise non-negative, the
minimum possible entry must satisfy:
ν (1 − τ ) + τ (1 − (q − 1) ν) ≥ 0
δν
δ (1 − (q − 1) ν)
⇔ ν+
−
≥0
δ
δ
1 − δ − q−1
1 − δ − q−1
and the latter inequality is equivalent to:
δ≤

ν
1 − (q − 1) ν +

ν
q−1

.


This completes the proof.
Rq×q
sto ,

We remark that if V = E2,1,...,1 W(q−1)ν ∈
then this proof illustrates that Wδ deg V if and only if 0 ≤ δ ≤
ν
. Hence, the condition in Theorem 2 is tight when no further information about V is known.
ν/ 1 − (q − 1)ν + q−1
It is worth juxtaposing Theorem 2 and Proposition 10. The upper bounds on δ from these results satisfy:
ν
(48)
ν ≤ (q − 1) ν
| {z }
1 − (q − 1)ν + q−1
|
{z
} upper bound in
upper bound in Theorem 2

Proposition 10

where we have equality if and only if ν = 1q , and it is straightforward to verify that (48) is equivalent to ν ≤ 1q .

Moreover, assuming that q is large and ν = o (1/q), the upper bound in Theorem 2 is ν/ 1 + o (1) + o 1/q 2 = Θ (ν),
while the upper bound in Proposition 10 is Θ (qν).10 (Note that both bounds are Θ (1) if ν = 1q .) Therefore, when
q×q
V ∈ Rq×q
sto is an additive noise channel, δ = O (qν) is enough for Wδ deg V , but a general channel V ∈ Rsto requires
δ = O (ν) for such degradation. So, in order to account for q different conditional pmfs in the general case (as opposed
to a single conditional pmf which characterizes the channel in the additive noise case), we loose a factor of q in the
upper bound on δ. Furthermore, we can check using simulations that Wδ ∈ Rq×q
sto is not in general less noisy than
V ∈ Rq×q
sto for δ = (q − 1)ν. Indeed, counterexamples can be easily obtained by letting V = Ej1 ,...,jq Wδ for specific
values of 1 ≤ j1 , . . . , jq ≤ q, and computationally verifying that Wδ 6ln V + J ∈ Rq×q
sto for appropriate choices of
perturbation matrices J ∈ Rq×q with sufficiently small Frobenius norm.
10 We use the Bachmann-Landau asymptotic notation here. Consider the (strictly) positive functions f : N → R and g : N → R. The little-o notation
is defined as: f (q) = o (g(q)) ⇔ limq→∞ f (q)/g(q) = 0. The big-O notation is defined as: f (q) = O (g(q)) ⇔ lim supq→∞ |f (q)/g(q)| <
+∞. Finally, the big-Θ notation is defined as: f (q) = Θ (g(q)) ⇔ 0 < lim inf q→∞ |f (q)/g(q)| ≤ lim supq→∞ |f (q)/g(q)| < +∞.

21

We have now proved Theorems 1, 2, and 3 from section II. The next section relates our results regarding less noisy
and degradation preorders to LSIs, and proves Theorem 4.
VII. L ESS NOISY DOMINATION AND LOGARITHMIC S OBOLEV INEQUALITIES
Logarithmic Sobolev inequalities (LSIs) are a class of functional inequalities that shed light on several important
phenomena such as concentration of measure, and ergodicity and hypercontractivity of Markov semigroups. We refer
readers to [40] and [41] for a general treatment of such inequalities, and more pertinently to [25] and [26], which
present LSIs in the context of finite state-space Markov chains. In this section, we illustrate that proving a channel
q×q
W ∈ Rq×q
sto is less noisy than a channel V ∈ Rsto allows us to translate an LSI for W to an LSI for V . Thus, important
information about V can be deduced (from its LSI) by proving W ln V for an appropriate channel W (such as a
q-ary symmetric channel) that has a known LSI.
We commence by introducing some appropriate notation and terminology associated with LSIs. For fixed input and
output alphabet X = Y = [q] with q ∈ N, we think of a channel W ∈ Rq×q
sto as a Markov kernel on X . We assume
that the “time homogeneous” discrete-time Markov chain defined by W is irreducible, and has unique stationary
distribution (or invariant measure) π ∈ Pq such that πW = π. Furthermore, we define the Hilbert space L2 (X , π) of
all real functions with domain X endowed with the inner product:
X
∀f, g ∈ L2 (X , π) , hf, giπ ,
π(x)f (x)g(x)
(49)
x∈X
2

2

and induced norm k·kπ . We construe W : L (X , π) → L (X , π) as a conditional expectation operator that takes a
T
function f ∈ L2 (X , π), which we can write as a column vector f = [f (0) · · · f (q − 1)] ∈ Rq , to another function
2
q
W f ∈ L (X , π), which we can also write as a column vector W f ∈ R . Corresponding to the discrete-time Markov
chain W , we may also define a continuous-time Markov semigroup:
q×q
∀t ≥ 0, Ht , exp (−t (Iq − W )) ∈ Rsto

(50)

where the “discrete-time derivative” W −Iq is the Laplacian operator that forms the generator of the Markov semigroup.
The unique stationary distribution of this Markov semigroup is also π, and we may interpret Ht : L2 (X , π) → L2 (X , π)
as a conditional expectation operator for each t ≥ 0 as well.
In order to present LSIs, we define the Dirichlet form EW : L2 (X , π) × L2 (X , π) → R:
∀f, g ∈ L2 (X , π) , EW (f, g) , h(Iq − W ) f, giπ

(51)

which is used to study properties of the Markov chain W and its associated Markov semigroup Ht ∈ Rq×q
sto : t ≥ 0 .
(EW is technically only a Dirichlet form when W is a reversible Markov chain, i.e. W is a self-adjoint operator, or
equivalently, W and π satisfy the detailed balance condition [25, Section 2.3, page 705].) Moreover, the quadratic
form defined by EW represents the energy of its input function, and satisfies:
 

W + W∗
2
(52)
f, f
∀f ∈ L (X , π) , EW (f, f ) = Iq −
2
π


where W ∗ : L2 (X , π) → L2 (X , π) is the adjoint operator of W . Finally, we introduce a particularly important
Dirichlet form corresponding to the channel W(q−1)/q = 1u, which has all uniform conditional pmfs and uniform
stationary distribution π = u, known as the standard Dirichlet form:
Estd (f, g) , E1u (f, g) = COVu (f, g)
!
!
X f (x)g(x)
X f (x)
X g(x)
=
−
q
q
q
x∈X

x∈X

2

(53)

x∈X

for any f, g ∈ L (X , u). The quadratic form defined by the standard Dirichlet form is presented in (17) in subsection
II-D.

q×q
:t≥0
We now present the LSIs associated with the Markov chain W and the Markov semigroup Ht ∈ Rsto
2
it defines. The LSI for the Markov semigroup with constant α ∈ R states that for every f ∈ L (X , π) such that
kf kπ = 1, we have:
 X

1
D f 2 π || π =
π(x)f 2 (x) log f 2 (x) ≤ EW (f, f )
(54)
α
x∈X

22

where we construe µ = f 2 π ∈ Pq as a pmf such that µ(x) = f (x)2 π(x) for every x ∈ X , and f 2 behaves like the
Radon-Nikodym derivative (or density) of µ with respect to π. The largest constant α such that (54) holds:
α(W ) ,

inf

f ∈L2 (X ,π):
kf kπ =1
D(f 2 π||π)6=0

EW (f, f )
D (f 2 π || π)

(55)

is called the logarithmic Sobolev constant (LSI constant) of the Markov chain W (or the Markov chain (W + W ∗ )/2).
Likewise, the LSI for the discrete-time Markov chain with constant α ∈ R states that for every f ∈ L2 (X , π) such
that kf kπ = 1, we have:

1
D f 2 π || π ≤ EW W ∗ (f, f )
(56)
α
where EW W ∗ : L2 (X , π) × L2 (X , π) → R is the “discrete” Dirichlet form. The largest constant α such that (56)
holds is the LSI constant of the Markov chain W W ∗ , α(W W ∗ ), and we refer to it as the discrete logarithmic Sobolev
constant of the Markov chain W . As we mentioned earlier, there are many useful consequences of such LSIs. For
example, if (54) holds with constant (55), then for every pmf µ ∈ Pq :
∀t ≥ 0, D (µHt ||π) ≤ e−2α(W )t D (µ||π)

(57)

where the exponent 2α(W ) can be improved to 4α(W ) if W is reversible [25, Theorem 3.6]. This is a measure of
∗
ergodicity of the semigroup Ht ∈ Rq×q
sto : t ≥ 0 . Likewise, if (56) holds with constant α(W W ), then for every pmf
µ ∈ Pq :
n
∀n ∈ N, D (µW n ||π) ≤ (1 − α(W W ∗ )) D (µ||π)
(58)
as mentioned in [25, Remark, page 725] and proved in [42]. This is also a measure of ergodicity of the Markov chain
W.
Although LSIs have many useful consequences, LSI constants are difficult to compute analytically. Fortunately, the
LSI constant corresponding to Estd has been computed in [25, Appendix, Theorem A.1]. Therefore, using the relation
in (18), we can compute LSI constants for q-ary symmetric channels as well. The next proposition collects the LSI
constants for q-ary symmetric channels (which are irreducible for δ ∈ (0, 1]) as well as some other related quantities.
q×q
Proposition 12 (Constants of Symmetric Channels). The q-ary symmetric channel Wδ ∈ Rsto
with q ≥ 2 has:
1) LSI constant:
(
δ,
q=2
α(Wδ ) =
(q−2)δ
(q−1) log(q−1) , q > 2

for δ ∈ (0, 1].
2) discrete LSI constant:

(
α(Wδ Wδ∗ ) = α(Wδ0 ) =

2δ(1 − δ),
(q−2)(2q−2−qδ)δ
(q−1)2 log(q−1) ,

q=2
q>2


qδ
for δ ∈ (0, 1], where δ 0 = δ 2 − q−1
.
3) Hirschfeld-Gebelein-Rényi maximal correlation corresponding to the uniform stationary distribution u ∈ Pq :
ρmax (u, Wδ ) = 1 − δ −

δ
q−1

q×r
for δ ∈ [0, 1], where for any channel W ∈ Rsto
and any source pmf PX ∈ Pq , we define the maximal
correlation between the input random variable X ∈ [q] and the output random variable Y ∈ [r] (with joint pmf
PX,Y (x, y) = PX (x)WY |X (y|x)) as:

ρmax (PX , W ) ,

sup

E [f (X)g(Y )].

f :[q]→R, g:[r]→R
E[f (X)]=E[g(Y )]=0
E[f 2 (X)]=E[g 2 (Y )]=1

4) contraction coefficient for KL divergence bounded by:

2
δ
δ
1−δ−
≤ ηKL (Wδ ) ≤ 1 − δ −
q−1
q−1
23

for δ ∈ [0, 1].


Proof. See Appendix B.

In view of Proposition 12 and the intractability of computing LSI constants for general Markov chains, we often
q×q
“compare” a given irreducible channel V ∈ Rq×q
sto with a q-ary symmetric channel Wδ ∈ Rsto to try and establish
an LSI for it. We assume for the sake of simplicity that V is doubly stochastic and has uniform stationary pmf (just
like q-ary symmetric channels). Usually, such a comparison between Wδ and V requires us to prove domination of
Dirichlet forms, such as:
qδ
∀f ∈ L2 (X , u) , EV (f, f ) ≥ EWδ (f, f ) =
Estd (f, f )
(59)
q−1
where we use (18). Such pointwise domination results immediately produce LSIs, (54) and (56), for V . Furthermore,
they also lower bound the LSI constants of V ; for example:
α(V ) ≥ α(Wδ ) .

(60)

This is turn begets other results such as (57) and (58) for the channel V (albeit with worse constants in the exponents
since the LSI constants of Wδ are used instead of those for V ). More general versions of Dirichlet form domination
between Markov chains on different state spaces with different stationary distributions, and the resulting bounds on
their LSI constants are presented in [25, Lemmata 3.3 and 3.4]. We next illustrate that the information theoretic notion
of less noisy domination is a sufficient condition for various kinds of pointwise Dirichlet form domination.
Theorem 40 (Domination of Dirichlet Forms). Let W, V ∈ Rq×q
sto be doubly stochastic channels, and π = u be the
uniform stationary distribution. Then, the following are true:
1) If W ln V , then:
∀f ∈ L2 (X , u) , EV V ∗ (f, f ) ≥ EW W ∗ (f, f ) .
T
T
2) If W ∈ Rq×q
0 is positive semidefinite, V is normal (i.e. V V = V V ), and W ln V , then:

3) If W = Wδ ∈ Rq×q
sto

∀f ∈ L2 (X , u) , EV (f, f ) ≥ EW (f, f ) .


and Wδ ln V , then:
is any q-ary symmetric channel with δ ∈ 0, q−1
q
∀f ∈ L2 (X , u) , EV (f, f ) ≥

qδ
Estd (f, f ) .
q−1

Proof.
Part 1: First observe that:

1 T
f Iq − W W T f
q

1 T
2
∀f ∈ L (X , u) , EV V ∗ (f, f ) = f Iq − V V T f
q

∀f ∈ L2 (X , u) , EW W ∗ (f, f ) =

where we use the facts that W T = W ∗ and V T = V ∗ because the stationary distribution is uniform. This implies
that EV V ∗ (f, f ) ≥ EW W ∗ (f, f ) for every f ∈ L2 (X , u) if and only if Iq − V V T PSD Iq − W W T , which is true if
and only if W W T PSD V V T . Since W ln V , we get W W T PSD V V T from part 2 of Proposition 8 after letting
P X = u = PX W = P X V .
Part 2: Once again, we first observe using (52) that:


1 T
W + WT
2
∀f ∈ L (X , u) , EW (f, f ) = f
Iq −
f,
q
2


V +VT
1
f.
∀f ∈ L2 (X , u) , EV (f, f ) = f T Iq −
q
2


So, EV (f, f ) ≥ EW (f, f ) for every f ∈ L2 (X , u) if and only if W + W T /2 PSD V + V T /2. Since W W T PSD
V V T from the proof of part 1, it is sufficient to prove that:
W W T PSD V V T ⇒

W + WT
V +VT
PSD
.
2
2

(61)

Lemma 2 in Appendix C establishes the claim in (61) because W ∈ Rq×q
0 and V is a normal matrix.
 q−1 
Part 3: We note that when V is a normal matrix, this result follows from part 2 because Wδ ∈ Rq×q
,
0 for δ ∈ 0, q
24

as can be seen from part 2 of Proposition 4. For a general doubly stochastic channel V , we need to prove that
qδ
EV (f, f ) ≥ EWδ (f, f ) = q−1
Estd (f, f ) for every f ∈ L2 (X , u) (where we use (18)). Following the proof of part 2,
it is sufficient to prove (61) with W = Wδ :11
V +VT
Wδ2 PSD V V T ⇒ Wδ PSD
2

where Wδ2 = Wδ WδT and Wδ = Wδ + WδT /2. Recall the Löwner-Heinz theorem [43], [44], (cf. [45, Section 6.6,
Problem 17]), which states that for A, B ∈ Rq×q
0 and 0 ≤ p ≤ 1:
A PSD B ⇒ Ap PSD B p

(62)

or equivalently, f : [0, ∞) → R, f (x) = xp is an operator monotone function for p ∈ [0, 1]. Using (62) with p = 21
(cf. [19, Corollary 7.7.4 (b)]), we have:
1
Wδ2 PSD V V T ⇒ Wδ PSD V V T 2
1
T 2
because the Gramian matrix V V T ∈ Rq×q
is the unique positive semidefinite square root matrix of
0 . (Here, V V
V V T .)
Let V V T = QΛQT and (V + V T )/2 = U ΣU T be the spectral decompositions of V V T and (V + V T )/2, where Q
and U are orthogonal matrices with eigenvectors as columns, and Λ and Σ are diagonal matrices of eigenvalues. Since
√
V V T and (V + V T )/2 are both doubly stochastic, they both have the unit norm eigenvector 1/ q corresponding to
the maximum eigenvalue of unity. In fact, we have:


1
1
V +VT
1
1
T 2 1
VV
and
√ =√
√ =√
q
q
2
q
q
1

1

1

where we use the fact that (V V T ) 2 = QΛ 2 QT is the spectral decomposition of (V V T ) 2 . For any matrix A ∈ Rq×q
sym , let
λ1 (A) ≥ λ2 (A) ≥ · · · ≥ λq (A) denote the eigenvalues of A in descending order. Without loss of generality, we assume
1
that [Λ]j,j = λj (V V T ) and [Σ]j,j = λj ((V + V T )/2) for every 1 ≤ j ≤ q. So, λ1 ((V V T ) 2 ) = λ1 ((V + V T )/2) = 1,
√
and the first columns of both Q and U are equal to 1/ q.
From part 2 of Proposition 4, we have Wδ = QDQT = U DU T , where D is the diagonal matrix of eigenvalues
δ
such that [D]1,1 = λ1 (Wδ ) = 1 and [D]j,j = λj (Wδ ) = 1 − δ − q−1
for 2 ≤ j ≤ q. Note that we may use either of
√
the eigenbases, Q or U , because they both have first column 1/ q, which is the eigenvector of Wδ corresponding to
λ1 (Wδ ) = 1 since Wδ is doubly stochastic, and the remaining eigenvector columns are permitted to be any orthonormal
√
δ
basis of span(1/ q)⊥ as λj (Wδ ) = 1 − δ − q−1
for 2 ≤ j ≤ q. Hence, we have:
Wδ PSD V V T
Wδ PSD

 21

1

1

⇔ QDQT PSD QΛ 2 QT ⇔ D PSD Λ 2 ,

V +VT
⇔ U DU T PSD U ΣU T ⇔ D PSD Σ.
2

1

1

In order to show that D PSD Λ 2 ⇒ D PSD Σ, it suffices to prove that Λ 2 PSD Σ. Recall from [45, Corollary
3.1.5] that for any matrix A ∈ Rq×q , we have:12



1 
A + AT
T 2
∀i ∈ {1, . . . , q} , λi AA
.
(63)
≥ λi
2
1

Hence, Λ 2 PSD Σ is true, cf. [46, Lemma 2.5]. This completes the proof.



Theorem 40 includes Theorem 4 from section II as part 3, and also provides two other useful pointwise Dirichlet form
domination results. Part 1 of Theorem 40 states that less noisy domination implies discrete Dirichlet form domination.
In particular, if we have Wδ ln V for some irreducible q-ary symmetric channel Wδ ∈ Rq×q
sto and irreducible doubly
stochastic channel V ∈ Rq×q
sto , then part 1 implies that:
n

∀n ∈ N, D (µV n ||u) ≤ (1 − α(Wδ Wδ∗ )) D (µ||u)

(64)

2
that (61) trivially holds for W = Wδ with δ = (q−1)/q, because W(q−1)/q = W(q−1)/q
= 1u PSD V V T implies that V = W(q−1)/q .
states that for any matrix A ∈ Rq×q , the ith largest eigenvalue of the symmetric part of A is less than or equal to the ith largest singular
value of A (which is the ith largest eigenvalue of the unique positive semidefinite part (AAT )1/2 in the polar decomposition of A) for every
1 ≤ i ≤ q.
11 Note
12 This

25

for all pmfs µ ∈ Pq , where α(Wδ Wδ∗ ) is computed in part 2 of Proposition 12. However, it is worth mentioning that
(58) for Wδ and Proposition 1 directly produce (64). So, such ergodicity results for the discrete-time Markov chain V
do not require the full power of the Dirichlet form domination in part 1. Regardless, Dirichlet form domination results,
such as in parts 2 and 3, yield several functional inequalities (like Poincaré inequalities and LSIs) which have many
other potent consequences as well.
Parts 2 and 3 of Theorem 40 convey that less noisy domination also implies the usual (continuous) Dirichlet form
domination under regularity conditions. We note that in part 2, the channel W is more general than that in part 3, but
the channel V is restricted to be normal (which includes the case where V is an additive noise channel). The proofs of
these parts essentially consist of two segments. The first segment uses part 1, and the second segment illustrates that
pointwise domination of discrete Dirichlet forms implies pointwise domination of Dirichlet forms (as shown in (59)).
This latter segment is encapsulated in Lemma 2 of Appendix C for part 2, and requires a slightly more sophisticated
proof pertaining to q-ary symmetric channels in part 3.
VIII. C ONCLUSION
In closing, we briefly reiterate our main results by delineating a possible program for proving LSIs for certain Markov
q×q
chains. Given an arbitrary irreducible doubly stochastic channel V ∈ Rsto
with minimum entry ν = min{[V ]i,j : 1 ≤
i, j ≤ q} > 0 and q ≥ 2, we can first use Theorem 2 to generate a q-ary symmetric channel Wδ ∈ Rq×q
sto with
ν
such that Wδ deg V . This also means that Wδ ln V , using Proposition 3. Moreover, the
δ = ν/ 1 − (q − 1)ν + q−1
δ parameter can be improved using Theorem 3 (or Propositions 10 and 11) if V is an additive noise channel. We can
then use Theorem 40 to deduce a pointwise domination of Dirichlet forms. Since Wδ satisfies the LSIs (54) and (56)
with corresponding LSI constants given in Proposition 12, Theorem 40 establishes the following LSIs for V :

1
D f 2 u || u ≤
EV (f, f )
(65)
α(Wδ )

1
EV V ∗ (f, f )
(66)
D f 2 u || u ≤
α(Wδ Wδ∗ )
for every f ∈ L2 (X , u) such that kf ku = 1. These inequalities can be used to derive a myriad of important facts
about V . We note that the equivalent characterizations of the less noisy preorder in Theorem 1 and Proposition 8
are particularly useful for proving some of these results. Finally, we accentuate that Theorems 2 and 3 address our
motivation in subsection I-D by providing analogs of the relationship between less noisy domination by q-ary erasure
channels and contraction coefficients in the context of q-ary symmetric channels.
A PPENDIX A
BASICS OF MAJORIZATION THEORY
Since we use some majorization arguments in our analysis, we briefly introduce the notion of group majorization
over row vectors in Rq (with q ∈ N) in this appendix. Given a group G ⊆ Rq×q of matrices (with the operation of
matrix multiplication), we may define a preorder called G-majorization over row vectors in Rq . For two row vectors
x, y ∈ Rq , we say that x G-majorizes y if y ∈ conv ({xG : G ∈ G}), where {xG : G ∈ G} is the orbit of x under the
group G. Group majorization intuitively captures a notion of “spread” of vectors. So, x G-majorizes y when x is more
spread out than y with respect to G. We refer readers to [9, Chapter 14, Section C] and the references therein for a
thorough treatment of group majorization. If we let G be the symmetric group of all permutation matrices in Rq×q ,
then G-majorization corresponds to traditional majorization of vectors in Rq as introduced in [39]. The next proposition
collects some results about traditional majorization.
Proposition 13 (Majorization [9], [39]). Given row vectors x = (x1 , . . . , xq ) , y = (y1 , . . . , yq ) ∈ Rq , let x(1) ≤ · · · ≤
x(q) and y(1) ≤ · · · ≤ y(q) denote the re-orderings of x and y in ascending order. Then, the following are equivalent:
1) x majorizes y, or equivalently, y resides in the convex hull of all permutations of x.
2) y = xD for some doubly stochastic matrix D ∈ Rq×q
sto .
3) The entries of x and y satisfy:
k
X

and

i=1
q
X
i=1

x(i) ≤
x(i) =

k
X
i=1
q
X

y(i) , for k = 1, . . . , q − 1 ,
y(i) .

i=1

When these conditions are true, we will write x maj y.
26

In the context of subsection I-C, given an Abelian group (X , ⊕) of order q, another useful notion of G-majorization
can be obtained by letting G = {Px ∈ Rq×q : x ∈ X } be the group of permutation matrices defined in (4) that is
isomorphic to (X , ⊕). For such choice of G, we write x X y when x G-majorizes (or X -majorizes) y for any two
row vectors x, y ∈ Rq . We will only require one fact about such group majorization, which we present in the next
proposition.
Proposition 14 (Group Majorization). Given two row vectors x, y ∈ Rq , x X y if and only if there exists λ ∈ Pq
such that y = x circX (λ).
Proof. Observe that:
x X y ⇔ y ∈ conv ({xPz : z ∈ X })
⇔ y = λ circX (x) for some λ ∈ Pq
⇔ y = x circX (λ) for some λ ∈ Pq
where the second step follows from (7), and the final step follows from the commutativity of X -circular convolution.



Proposition 14 parallels the equivalence between parts 1 and 2 of Proposition 13, because circX (λ) is a doubly stochastic matrix for every pmf λ ∈ Pq . In closing this appendix, we mention a well-known special case
of such
 group majorization. When (X , ⊕) is the cyclic Abelian group Z/qZ of integers with addition modulo q,
G = Iq , Pq , Pq2 , . . . , Pqq−1 is the group of all cyclic permutation matrices in Rq×q , where Pq ∈ Rq×q is defined in
(8). The corresponding notion of G-majorization is known as cyclic majorization, cf. [47].
A PPENDIX B
P ROOFS OF PROPOSITIONS 4 AND 12
Proof of Proposition 4.
Part 1: This is obvious from (10).
Part 2: Since the DFT matrix jointly diagonalizes all circulant matrices, it diagonalizes every Wδ for δ ∈ R (using part
1). The corresponding eigenvalues are all real because Wδ is symmetric. To explicitly compute these eigenvalues, we
refer to [19, Problem 2.2.P10]. Observe that for any row vector x = (x0 , . . . , xq−1 ) ∈ Rq , the corresponding circulant
matrix satisfies:
!
q−1
q−1
X
X
circZ/qZ (x) =
xk Pqk = Fq
xk Dqk FqH
k=0

k=0

√
= Fq diag( q xFq ) FqH

where the first equality follows from (6) for the group Z/qZ [19, Section 0.9.6], Dq = diag((1, ω, ω 2 , . . . , ω q−1 )), and
Pq = Fq Dq FqH ∈ Rq×q is defined in (8). Hence, we have:
λj (Wδ ) =

q
X

(wδ )k ω (j−1)(k−1)

k=1


=

1,
1−δ−

δ
q−1 ,

j=1
j = 2, . . . , q

where wδ = (1 − δ, δ/(q − 1), . . . , δ/(q − 1)).
Part 3: This is also obvious from (10)–recall that a square stochastic matrix is doubly stochastic if and only if its
stationary distribution is uniform [19, Section 8.7].
−δ
by direct computation:
Part 4: For δ 6= q−1
δ
q , we can verify that Wτ Wδ = Iq when τ = 1−δ− q−1



τ
δ
[Wτ Wδ ]j,j = (1 − τ ) (1 − δ) + (q − 1)
q−1
q−1
= 1 , for j = 1, . . . , q ,
δ (1 − τ ) τ (1 − δ)
τδ
[Wτ Wδ ]j,k =
+
+ (q − 2)
2
q−1
q−1
(q − 1)
= 0 , for j 6= k and 1 ≤ j, k ≤ q .

27

The δ = q−1
q case follows from (10).


is closed over matrix multiplication. Indeed, for , δ ∈ R\ q−1
, we can
Part 5: The set Wδ : δ ∈ R\ q−1
q
q
q−1
δ
straightforwardly verify that W Wδ = Wτ with τ =  + δ − δ − q−1 . Moreover, τ 6= q because Wτ is invertible
(since W and Wδ are invertible using part 4). The set also includes the identity matrix as W0 = Iq , and multiplicative
inverses (using
the associativity of matrix multiplication and the commutativity of circulant matrices
 part 4). Finally,

is an Abelian group.

proves that Wδ : δ ∈ R\ q−1
q
Proof of Proposition 12.
q×q
Part 1: We first recall from [25, Appendix, Theorem A.1] that the Markov chain 1u ∈ Rsto
with uniform stationary
distribution π = u ∈ Pq has LSI constant:
( 1
q=2
Estd (f, f )
2,
α(1u) =
inf
=
.
1− q2
2 u || u)
2
D
(f
f ∈L (X ,u):
log(q−1) , q > 2
kf ku =1
D(f 2 u||u)6=0

qδ
α (1u), which proves part 1.
Now using (18), α(Wδ ) = q−1
T
2
Part 2: Observe that Wδ Wδ∗ = W
 δ Wδ = Wδ = Wδ0 , where the first equality holds because Wδ has uniform
qδ
0
stationary pmf, and δ = δ 2 − q−1 using the proof of part 5 of Proposition 4. As a result, the discrete LSI constant
α(Wδ Wδ∗ ) = α(Wδ0 ), which we can calculate using part 1 of this proposition.
Part 3: It is well-known in
the literature that
ρmax (u, Wδ ) equals the second largest singular value of the divergence
√ −1
√ 
transition matrix diag u
Wδ diag u = Wδ (see [36, Subsection I-B] and the references therein). Hence, from
δ
part 2 of Proposition 4, we have ρmax (u, Wδ ) = 1 − δ − q−1
.
q×r
Part 4: First recall the Dobrushin contraction coefficient (for total variation distance) for any channel W ∈ Rsto
:

ηTV (W ) ,

kPX W − QX W k`1
kPX − QX k`1
PX ,QX ∈Pq :
sup

(67)

PX 6=QX

1
=
max WY |X (·|x) − WY |X (·|x0 )
2 x,x0 ∈[q]

(68)

`1

where k·k`1 denotes the `1 -norm, and the second equality is Dobrushin’s two-point characterization of ηTV [48]. Using
this characterization, we have:
ηTV (Wδ ) =

0
1
max wδ Pqx − wδ Pqx
2 x,x0 ∈[q]

= 1−δ−

`1

δ
q−1

where wδ is the noise pmf of Wδ for δ ∈ [0, 1], and Pq ∈ Rq×q is defined in (8). It is well-known in the literature
(see e.g. the introduction of [49] and the references therein) that:
2

ρmax (u, Wδ ) ≤ ηKL (Wδ ) ≤ ηTV (Wδ ) .

(69)

Hence, the value of ηTV (Wδ ) and part 3 of this proposition establish part 4. This completes the proof.



A PPENDIX C
AUXILIARY RESULTS
Proposition 15 (Properties of Domination FactorFunction). Given a channel V ∈ Rq×r
sto that is strictly positive entry+
wise, its domination factor function µV : 0, q−1
→
R
is
continuous,
convex,
and
strictly increasing. Moreover, we
q
have limδ→ q−1 µV (δ) = +∞.
q


Proof. We first prove that µV is finite on 0, q−1
. For any PX , QX ∈ Pq and any δ ∈ 0, q−1
, we have:
q
q
2

D(PX V ||QX V ) ≤ χ2 (PX V ||QX V ) ≤
2

≤

k(PX − QX )V k`2
ν
2

kPX − QX k`2 kV kop
ν

28

where the first inequality is well-known (see e.g. [36, Lemma 8]) and ν = min {[V ]i,j : 1 ≤ i ≤ q, 1 ≤ j ≤ r}, and:
1
2
k(PX − QX )Wδ k`2
2

2
1
δ
2
≥ kPX − QX k`2 1 − δ −
2
q−1

D(PX Wδ ||QX Wδ ) ≥

where the first inequality follows from Pinsker’s inequality (see e.g. [36, Proof of Lemma 6]), and the second inequality
follows from part 2 of Proposition 4. Hence, we get:


2
2 kV kop
q−1
(70)
∀δ ∈ 0,
, µV (δ) ≤ 
2 .
q
δ
ν 1 − δ − q−1
To prove that µV is strictly increasing, observe that Wδ0 deg Wδ for 0 < δ 0 < δ <
with:
δδ 0
+
δ0
1 − δ0 −
q−1


δ − δ0
q−1
=
∈ 0,
δ0
q
1 − δ 0 − q−1

δ0
p=δ−
0
1−δ −

δ0
q−1

+

1−

δδ 0
q−1
δ0 −

q−1
q ,

because Wδ = Wδ0 Wp

δ0
q−1

where we use part 4 of Proposition 4, the proof of part 5 of Proposition 4 in Appendix B, and the fact that Wp =
Wδ−1
0 Wδ . As a result, we have for every PX , QX ∈ Pq :
D (PX Wδ ||QX Wδ ) ≤ ηKL (Wp ) D (PX Wδ0 ||QX Wδ0 )

using the SDPI for KL divergence, where part 4 of Proposition 12 reveals that ηKL (Wp ) ∈ (0, 1) since p ∈ 0, q−1
.
q
Hence, we have for 0 < δ 0 < δ < q−1
:
q
µV (δ 0 ) ≤ ηKL (Wp ) µV (δ)
(71)
using (43), and the fact that 0 < D (PX Wδ0 ||QX Wδ0 ) < +∞ if and only if 0 < D (PX Wδ ||QX Wδ ) < +∞. This
implies that µV is strictly increasing.
We next establish that µV is convex and continuous. For any fixed PX , QX ∈ Pq such that PX 6= QX , consider
the function δ 7→ D (PX V ||QX V ) /D (PX Wδ ||QX Wδ ) with domain 0, q−1
. This function is convex, because δ 7→
q
D (PX Wδ ||QX Wδ ) is convex by the convexity of KL divergence, and the reciprocal of a non-negative convex function
is convex. Therefore, µV is convex since (43) defines it as a pointwise supremum of a collection of convex functions.
Furthermore, we note that µV is also continuous since a convex function is continuous on the interior of its domain.
Finally, observe that:
limq−1
inf µV (δ) ≥
δ→

q

=

sup

limq−1
inf

PX ,QX ∈Pq δ→
PX 6=QX

sup

q

D (PX V ||QX V )
D (PX Wδ ||QX Wδ )

D (PX V ||QX V )
lim sup D (PX Wδ ||QX Wδ )

PX ,QX ∈Pq
PX 6=QX
δ→ q−1
q

= +∞
where the first inequality follows from the minimax inequality and (43) (note that 0 < D (PX Wδ ||QX Wδ ) < +∞ for
PX 6= QX and δ close to q−1

q ), and the final equality holds because PX W(q−1)/q = u for every PX ∈ Pq .
q×q
Lemma 2 (Gramian Löwner Domination implies Symmetric Part Löwner Domination). Given A ∈ Rq×q
0 and B ∈ R
that is normal, we have:
A + AT
B + BT
A2 = AAT PSD BB T ⇒ A =
PSD
.
2
2

Proof. Since AAT PSD BB T PSD 0, using the Löwner-Heinz theorem (presented in (62)) with p = 21 , we get:
1
1
A = AAT 2 PSD BB T 2 PSD 0

29


q×q
where the first equality holds because A ∈ R0
. It suffices to now prove that (BB T )1/2 PSD B + B T /2, as
the transitive property of PSD will produce A PSD B + B T /2. Since B is normal, B = U DU H by the complex
spectral theorem [38, Theorem 7.9], where U is a unitary matrix and D is a complex diagonal matrix. Using this
unitary diagonalization, we have:
B + BT
= U Re{D} U H
2
since |D| PSD Re{D}, where |D| and Re{D} denote the element-wise magnitude and real part of D, respectively.
This completes the proof.

U |D|U H = BB T

 12

PSD

ACKNOWLEDGMENT
We would like to thank an anonymous reviewer and the Associate Editor, Chandra Nair, for bringing the reference
[12] to our attention. Y.P. would like to thank Dr. Ziv Goldfeld for discussions on secrecy capacity.
R EFERENCES
[1] A. Makur and Y. Polyanskiy, “Less noisy domination by symmetric channels,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Aachen, Germany,
June 25-30 2017, pp. 2463–2467.
[2] R. Ahlswede and P. Gács, “Spreading of sets in product spaces and hypercontraction of the Markov operator,” Ann. Probab., vol. 4, no. 6, pp.
925–939, December 1976.
[3] Y. Polyanskiy and Y. Wu, “Strong data-processing inequalities for channels and Bayesian networks,” in Convexity and Concentration, ser. The
IMA Volumes in Mathematics and its Applications, E. Carlen, M. Madiman, and E. M. Werner, Eds., vol. 161. New York: Springer, 2017,
pp. 211–249.
[4] C. E. Shannon, “A note on a partial ordering for communication channels,” Information and Control, vol. 1, pp. 390–397, 1958.
[5] ——, “The zero error capacity of a noisy channel,” IRE Trans. Inform. Theory, vol. 2, no. 3, pp. 706–715, September 1956.
[6] J. H. Cohen, J. H. B. Kemperman, and G. Zbăganu, Comparisons of Stochastic Matrices with Applications in Information Theory, Statistics,
Economics and Population Sciences. Ann Arbor: Birkhäuser, 1998.
[7] T. M. Cover, “Broadcast channels,” IEEE Trans. Inform. Theory, vol. IT-18, no. 1, pp. 2–14, January 1972.
[8] P. P. Bergmans, “Random coding theorem for broadcast channels with degraded components,” IEEE Trans. Inform. Theory, vol. IT-19, no. 2,
pp. 197–207, March 1973.
[9] A. W. Marshall, I. Olkin, and B. C. Arnold, Inequalities: Theory of Majorization and Its Applications, 2nd ed., ser. Springer Series in Statistics.
New York: Springer, 2011.
[10] J. Körner and K. Marton, “Comparison of two noisy channels,” in Topics in Information Theory (Second Colloq., Keszthely, 1975), Amsterdam:
North-Holland, 1977, pp. 411–423.
[11] I. Csiszár and J. Körner, Information Theory: Coding Theorems for Discrete Memoryless Systems, 2nd ed. New York: Cambridge University
Press, 2011.
[12] M. van Dijk, “On a special class of broadcast channels with confidential messages,” IEEE Trans. Inform. Theory, vol. 43, no. 2, pp. 712–714,
March 1997.
[13] A. El Gamal, “The capacity of a class of broadcast channels,” IEEE Trans. Inform. Theory, vol. IT-25, no. 2, pp. 166–169, March 1979.
[14] C. Nair, “Capacity regions of two new classes of 2-receiver broadcast channels,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Seoul, South
Korea, June 28-July 3 2009, pp. 1839–1843.
[15] Y. Geng, C. Nair, S. Shamai, and Z. V. Wang, “On broadcast channels with binary inputs and symmetric outputs,” IEEE Trans. Inform. Theory,
vol. 59, no. 11, pp. 6980–6989, November 2013.
[16] D. Sutter and J. M. Renes, “Universal polar codes for more capable and less noisy channels and sources,” April 2014, arXiv:1312.5990v3
[].
[17] F. Unger, “Better gates can make fault-tolerant computation impossible,” Electronic Colloquium on Computational Complexity (ECCC), no.
164, November 2010.
[18] M. Artin, Algebra, 2nd ed. New Jersey: Pearson Prentice Hall, 2011.
[19] R. A. Horn and C. R. Johnson, Matrix Analysis, 2nd ed. New York: Cambridge University Press, 2013.
[20] P. Diaconis, Group Representations in Probability and Statistics, S. S. Gupta, Ed. USA: Inst. Math. Stat. Monogr., 1988, vol. 11.
[21] Y. Polyanskiy, “Saddle point in the minimax converse for channel coding,” IEEE Trans. Inform. Theory, vol. 59, no. 5, pp. 2576–2595, May
2013.
[22] J. E. Cohen, Y. Iwasa, G. Rautu, M. B. Ruskai, E. Seneta, and G. Zbăganu, “Relative entropy under mappings by stochastic matrices,” Linear
Algebra Appl., vol. 179, pp. 211–235, January 1993.
[23] M. Raginsky, “Strong data processing inequalities and Φ-Sobolev inequalities for discrete channels,” IEEE Trans. Inform. Theory, vol. 62,
no. 6, pp. 3355–3389, June 2016.
[24] I. Csiszár and J. Körner, “Broadcast channels with confidential messages,” IEEE Trans. Inform. Theory, vol. IT-24, no. 3, pp. 339–348, May
1978.
[25] P. Diaconis and L. Saloff-Coste, “Logarithmic Sobolev inequalities for finite Markov chains,” Ann. Appl. Probab., vol. 6, no. 3, pp. 695–750,
1996.
[26] R. Montenegro and P. Tetali, Mathematical Aspects of Mixing Times in Markov Chains, ser. Found. Trends Theor. Comput. Sci., M. Sudan,
Ed. Boston-Delft: now Publishers Inc., 2006, vol. 1, no. 3.
[27] E. C. Posner, “Random coding strategies for minimum entropy,” IEEE Trans. Inform. Theory, vol. IT-21, no. 4, pp. 388–391, July 1975.
[28] Y. Polyanskiy and Y. Wu, “Lecture notes on information theory,” August 2017, Lecture Notes 6.441, Department of Electrical Engineering and
Computer Science, MIT, Cambridge, MA, USA.
[29] W. Rudin, Principles of Mathematical Analysis, 3rd ed., ser. International Series in Pure and Applied Mathematics. New York: McGraw-Hill,
Inc., 1976.
[30] V. Anantharam, A. A. Gohari, S. Kamath, and C. Nair, “On hypercontractivity and a data processing inequality,” in Proc. IEEE Int. Symp. Inf.
Theory (ISIT), Honolulu, HI, USA, June 29-July 4 2014, pp. 3022–3026.

30

[31] M.-D. Choi, M. B. Ruskai, and E. Seneta, “Equivalence of certain entropy contraction coefficients,” Linear Algebra Appl., vol. 208-209, pp.
29–36, September 1994.
[32] S. Boyd and L. Vandenberghe, Convex Optimization. New York: Cambridge University Press, 2004.
[33] C. St˛epniak, “Ordering of nonnegative definite matrices with application to comparison of linear models,” Linear Algebra Appl., vol. 70, pp.
67–71, October 1985.
[34] R. G. Gallager, Information Theory and Reliable Communication. New York: John Wiley & Sons, Inc., 1968.
[35] A. Rényi, “On measures of dependence,” Acta Math. Hungar., vol. 10, no. 3-4, pp. 441–451, 1959.
[36] A. Makur and L. Zheng, “Bounds between contraction coefficients,” in Proc. 53rd Allerton Conference, Allerton House, UIUC, Illinois, USA,
September 29-October 2 2015, pp. 1422–1429.
[37] O. V. Sarmanov, “Maximal correlation coefficient (non-symmetric case),” Dokl. Akad. Nauk, vol. 121, no. 1, pp. 52–55, 1958.
[38] S. Axler, Linear Algebra Done Right, 2nd ed., ser. Undergraduate Texts in Mathematics. New York: Springer, 2004.
[39] G. H. Hardy, J. E. Littlewood, and G. Pólya, Inequalities, 1st ed. London: Cambridge University Press, 1934.
[40] M. Ledoux, “Concentration of measure and logarithmic Sobolev inequalities,” in Séminaire de Probabilités XXXIII, ser. Lecture Notes in
Mathematics, J. Azéma, M. Émery, M. Ledoux, and M. Yor, Eds., vol. 1709. Berlin, Heidelberg: Springer, 1999, pp. 120–216.
[41] D. Bakry, “Functional inequalities for Markov semigroups,” in Probability Measures on Groups: Recent Directions and Trends, ser. Proceedings
of the CIMPA-TIFR School, Tata Institute of Fundamental Research, Mumbai, India, 2002, S. G. Dani and P. Graczyk, Eds. New Delhi,
India: Narosa Publishing House, 2006, pp. 91–147.
[42] L. Miclo, “Remarques sur l’hypercontractivité at l’évolution de éntropie pour des chaînes de Markov finies,” Séminaire de probabilités de
Strasbourg, vol. 31, pp. 136–167, 1997.
[43] K. Löwner, “Über monotone matrixfunktionen,” Math. Z., vol. 38, no. 1, pp. 177–216, 1934.
[44] E. Heinz, “Beiträge zur störungstheorie der spektralzerlegung,” Math. Ann., vol. 123, pp. 415–438, 1951.
[45] R. A. Horn and C. R. Johnson, Topics in Matrix Analysis. New York: Cambridge University Press, 1991.
[46] P. Diaconis and L. Saloff-Coste, “Nash inequalities for finite Markov chains,” J. Theoret. Probab., vol. 9, no. 2, pp. 459–510, 1996.
[47] A. Giovagnoli and H. P. Wynn, “Cyclic majorization and smoothing operators,” Linear Algebra Appl., vol. 239, pp. 215–225, May 1996.
[48] R. L. Dobrushin, “Central limit theorem for nonstationary Markov chains. I,” Theory Probab. Appl., vol. 1, no. 1, pp. 65–80, 1956.
[49] Y. Polyanskiy and Y. Wu, “Dissipation of information in channels with input constraints,” IEEE Trans. Inform. Theory, vol. 62, no. 1, pp.
35–55, January 2016.

31

