Second-Order Converses via Reverse Hypercontractivity
Jingbo Liu Ramon van Handel Sergio Verdú










-1cm


Second-Order Converses via Reverse Hypercontractivity
This work was supported in part by
NSF Grants CCF-1016625, CCF-0939370, DMS-1148711, by
ARO Grants W911NF-15-1-0479, W911NF-14-1-0094, and by the
Center for Science of Information. The main results of this paper were
initially announced in the conference paper <cit.>, and form a 
part of the first author's Ph.D. thesis at Princeton University
<cit.>.
    Jingbo Liu Ramon van Handel Sergio Verdú
    

=============================================================================================================================================================================================================================================================================================================================================================================================================================



Jingbo Liu, Institute for Data, Systems, and Society, 
Massachusetts Institute of Technology, 77 Massachusetts Avenue, Bldg. 
E18-421, Cambridge, MA 02139, USA; jingbo@mit.edu
Ramon van Handel, Fine Hall 207, Princeton University, Princeton, NJ
08544, USA; rvan@princeton.edu
Sergio Verdú:
verdu@informationtheory.org

94A15; 94A24; 68P30; 62B10; 47D07; 60E15

 A strong converse shows that no procedure can beat the asymptotic (as 
blocklength n→∞) fundamental limit of a given 
information-theoretic problem for any fixed error probability. A 
second-order converse strengthens this conclusion by showing that the 
asymptotic fundamental limit cannot be exceeded by more than 
O(1√(n)). While strong converses are achieved in a broad 
range of information-theoretic problems by virtue of the “blowing-up 
method”—a powerful methodology due to Ahlswede, Gács and Körner 
(1976) based on concentration of measure—this method is fundamentally 
unable to attain second-order converses and is restricted 
to finite-alphabet settings. Capitalizing on reverse hypercontractivity 
of Markov semigroups and functional inequalities, this paper develops the 
“smoothing-out” method, an alternative to the blowing-up approach that
does not rely on finite alphabets and that leads to second-order 
converses in a variety of information-theoretic problems that were out of 
reach of previous methods.












§ INTRODUCTION




 §.§ Overview


What are the fundamental limits of a given data science problem? The 
investigation of such questions typically follows a two-sided analysis. In 
the achievability part, one shows the existence of a procedure 
achieving a certain performance, e.g., error probability. In the 
converse part, one shows that no procedure can accomplish better 
performance than a certain lower bound. This basic structure is common to 
a wide range of problems that span information theory, statistics, and 
computer science. While the study of achievability generally depends 
strongly on the special features of the problem at hand, many converse 
bounds that arise in different areas rely essentially on 
information-theoretic methods.

Frequently, the upper and lower bounds on optimal performance provided by 
the achievability and converse analyses do not coincide. Starting with 
Shannon (1948) <cit.>, the emphasis in information theory has been 
on the analysis of the fundamental limits in the asymptotic regime 
of long blocklengths. In that regime, the gap between many existing 
achievability and converse bounds does vanish and sharp answers can be 
found to questions such as the maximal transmission rate over noisy 
channels and the minimal data compression rate subject to a fidelity 
constraint. The last decade has witnessed a number of 
information-theoretic results (e.g., 
<cit.>), which are applicable 
in the non-asymptotic regime. These results are strongly motivated 
by the need to understand the relevance of asymptotic limits to practical 
systems that may be subject to severe delay constraints, or scenarios 
where the alphabet size or the number of users is large compared to the 
number of channels or sources 
<cit.>.

The development of a non-asymptotic information theory has required new 
and improved methods for investigating fundamental limits. In 
principle, it is not clear that the quantities that determine the 
fundamental limits in the asymptotic regime can accurately describe the 
performance at blocklengths of interest in realistic applications (e.g., 
1000 bits). This has led to the development of nonasymptotic bounds 
that capture more sophisticated distributional information on the relevant 
information quantities. Unfortunately, however, such bounds are often 
difficult to compute. A less accurate but more tractable approach to 
understanding performance at smaller blocklengths is to focus attention on 
so-called second-order analysis, originally pioneered by Wolfowitz 
<cit.> and Strassen <cit.> in the 1960s and 
significantly refined in recent years. In such bounds, the fundamental 
limits in the first-order (linear in the blocklength) asymptotics are 
sharpened by investigating the deviation from this asymptotic behavior to 
second order (square-root of the blocklength). In particular, in those 
situations where the first- and second-order asymptotics can be 
established precisely, the resulting bounds have often proven to be quite 
accurate except for very short blocklengths.

While precise second-order results are available in various basic
information-theoretic problems, more complicated setups, particularly 
those arising in multiuser information theory, have so far eluded 
second-order analysis. One of the challenges that emerged from this line 
of work is the development of second-order converses. Several existing 
approaches to obtaining second-order converses are briefly reviewed in 
Section <ref>; however, to date, a variety of 
information-theoretic problems have remained out of reach of such methods. 
On the other hand, the powerful general methodology introduced in 1976 by 
Ahlswede, Gács, and Körner <cit.> and 
exploited extensively in the classical book <cit.> 
(see also the recent survey <cit.>) has proven 
instrumental for proving converses in network information theory. Although 
this widely used technique yields converse results in a broad range of 
problems almost as a black box, it is fundamentally unable to yield 
second-order converses and is restricted to finite-alphabet settings.

Inspired by a result by Margulis <cit.>, the 
method of Ahlswede, Gács, and Körner is based on a remarkable 
application of the concentration of measure phenomenon on the Hamming cube 
<cit.>, which is known in information theory as the 
“blowing-up lemma”. Historically, this is probably the very first 
application of modern measure concentration to a data science problem. 



One of the main messages of this paper is that, surprisingly, measure 
concentration turns out not to be the right approach after all in this 
original application. Instead, we will revisit the theory of Ahlswede, 
Gács, and Körner based not on the violent “blowing-up” operation, 
but on a new and more pacifist “smoothing out” principle that exploits 
reverse hypercontractivity of Markov semigroups and functional 
inequalities. With this gentler touch, we are able to eliminate the 
inefficiencies of the blowing-up method and obtain second-order converses, 
essentially for free, in many information-theoretic problems that were out 
of reach of previous methods.




 §.§ Weak, strong, and second-order converses



As a concrete basis for discussion, let us consider the basic setup of 
single-user data transmission through noisy channels, in which there is a 
three-way tradeoff between code size, blocklength, and error probability. 
Suppose we wish to transmit an equiprobable message W∈{1,…,M} 
through a noisy channel with given blocklength n.[
	A channel is a sequence of random transformations { 
	P_Y^n|X^n } indexed by blocklength n.]
We encode each possible message using a codebook c_1,…,c_M∈𝒳^n. What is the largest possible size M of the codebook that 
can be decoded with error probability (averaged over equiprobable 
codewords and channel randomness) at most ϵ?
For memoryless channels and in various more general situations,
the maximum code size M^*(n,ϵ) satisfies <cit.>

    ln M^*(n, ϵ) =n C+
    	Q^-1(1-ϵ)√(nV) +o_ϵ(√(n)),

where the capacity C and dispersion V determine the
precise first- and second-order asymptotics, and Q^-1(·) is 
the inverse Gaussian tail probability function. 
For memoryless channels (P_Y^n|X^n = P^⊗ n_Y|X),
channel capacity and dispersion are given, respectively, by the quantities
<cit.>

    C    = max_P_X I (X;Y), 
    
    V    = Var[ _X;Y (X;Y) ],

where _X;Y (a;b) = logd P_Y|X=a/d 
P_Y(b), I(X;Y) = 𝔼 [ _X;Y (X;Y)] is the mutual 
information, and (<ref>) is evaluated for a P_X
that attains the maximum in (<ref>).

To prove a result such as (<ref>), we must address two separate 
questions. The achievability part (that is, the inequality ≥) requires 
us to show existence of a codebook c_1,…,c_M that attains the 
prescribed error probability. This is usually accomplished using the 
probabilistic method due to Shannon <cit.> which analyzes the 
error probability not of a particular code, but rather its average when 
the codebooks are randomly drawn from an auxiliary distribution. For many 
problems in information theory with known first-order asymptotics, an 
achievability bound with ∼√(n) second-order term can be derived 
using random coding in conjunction with other techniques 
<cit.>.

In contrast, the converse part (that is, the inequality ≤) claims that
no code can exceed the size given in (<ref>) for the
given error probability ϵ. The simplest and most widely used tool in converse analyses  is  Fano's inequality
<cit.>, which yields, in the memoryless case, the following
estimate:

    ln M^*(n, ϵ) ≤n/1-ϵ C+ h(ϵ)/1- ϵ,   ϵ∈ (0,1).

Such a bound is called a weak converse: it yields the correct
first-order asymptotics in the limit of vanishing error probability, namely,

    lim_ϵ↓ 0lim_n →∞1/nln M^*(n, ϵ) ≤ C.

 However, (<ref>) does not rule out that transmission rates exceeding C 
 may be feasible for any given nonzero error probability ϵ.
To that end we need a more powerful result known as the strong converse, namely,

    ln M^*(n, ϵ) ≤ nC + o_ϵ(n),   ϵ∈ (0,1),

which can be proved by a variety of methods (e.g.,
<cit.>).
Our interest in this paper is on the even stronger notion of a
second-order converse

    ln M^*(n, ϵ) ≤ nC + O_ϵ(√(n)),
    	   ϵ∈ (0,1),

which not only implies a strong converse (<ref>) but 
yields the √(n) behavior in (<ref>).
We caution that second-order converses do not always yield the 
sharpest possible constant in the √(n)-term; however, they aim to 
capture at least qualitatively various features of the sharp second-order 
asymptotics illustrated by (<ref>).

Of course, the basic data transmission problem that we have discussed here 
for sake of illustration is particularly simple, as the exact second-order 
asymptotics (<ref>) are known. This is not the case in more 
complicated information-theoretic problems. In particular, there are many 
problems in multiuser information theory for which either only weak 
converses are known, or, at most, strong converses have been obtained 
using the blowing-up method. It is precisely in such situations that new 
powerful and robust methods for obtaining second-order converses are 
needed. Next, we
briefly discuss the three main approaches that have been developed in the
literature for addressing such problems.






















  * The goal of the single-shot method (e.g., 
<cit.>) 
is to obtain non-asymptotic achievability and converse bounds without 
imposing any probabilistic structure on either sources or channels. 
Therefore, only the essential features of the problem come into play. 
Those non-asymptotic bounds are expressed not in terms of average 
quantities such as entropy or mutual information, but in terms of 
information spectra, namely the distribution function of 
information densities such as _X;Y (X;Y). When coupled with the 
law of large numbers or the ergodic theorem and with central-limit 
theorem tools, the bounds become second-order tight. The non-asymptotic 
converse bounds for single-user data transmission boil down to the 
derivation of lower bounds on the error probability of Bayesian M-ary 
hypothesis testing followed by anonymization of the actual codebook. 
Often, those lower bounds are obtained by recourse to the analysis of an 
associated auxiliary binary hypothesis testing problem. This converse 
approach has been successfully applied to some problems of multiuser 
information theory such as Slepian-Wolf coding, multiple access 
channels <cit.>, and broadcast channels 
<cit.>. Its application to other network setups is however a 
work in progress. 


  * Type class analysis has been used extensively since 
<cit.> and was popularized by 
<cit.> mainly in the context of error exponents; 
however, it applies also to second-order analysis (see, e.g., 
<cit.>). The idea behind this method is that to obtain lower 
bounds, we may consider a situation where the decoder is artificially 
given access to the type (empirical distribution) of 
the source or channel sequences. Conditioned on each type, the 
distribution is equiprobable on the type class, so the evaluation of the 
conditional error probability is reduced to a combinatorial problem (this 
has been referred to as the “skeleton” or “combinatorial kernel” of the 
information-theoretic problem <cit.>).
However, this combinatorial problem is not easily 
solved in side information problems (without additional ideas such as 
the blowing-up lemma). Moreover, by its nature, the method of types is 
restricted to finite alphabets and memoryless channels.


  * The method using the blowing-up lemma (BUL) of 
Ahlswede-Gács-Körner 
<cit.> 
uses a completely different idea to attain converse bounds: rather than 
try to reduce the given converse problem to a simpler one (e.g., to a 
binary hypothesis testing problem or a codebook that uses a single type), 
the BUL method is in essence a general technique for bootstrapping a 
strong converse from a weak converse. Even when the error probability 
ϵ is fixed, the concentration of measure phenomenon implies that 
all sequences except those in a set of vanishing probability differ in at 
most a fraction o(1) of coordinates from a correctly decoded sequence. 
One can therefore effectively reduce the regime of fixed error probability 
to one of vanishing error probability, where a weak converse suffices, 
with negligible cost. The advantage of this method is that it is very 
broadly applicable. However, as will be discussed below, quantitative 
bounds obtained from this method are always suboptimal and second-order 
converses are fundamentally outside its reach. Moreover, the perturbation 
argument used in this approach is restricted to finite alphabets. 



The single-shot and type class analysis 
methods yield second-order converses, but there are various problems in 
network information theory that have remained so far outside their reach. 
In contrast, the BUL method has been successful in establishing strong 
converses for a wide range of problems, including all settings in 
<cit.> with known single-letter rate region; see 
<cit.>. For some problems in network 
information theory, such as source coding with compressed side information 
<cit.>, BUL remained hitherto the only method for 
establishing a strong converse <cit.>. However, the 
generality of the method comes at the cost of an inherent inefficiency, 
which prevents it from attaining second-order converses and prevents its 
application beyond the finite alphabet setting.

In this paper, we will show that one can have essentially the best of both
worlds: the inefficiency of the blowing-up method can be almost entirely
overcome by revisiting the foundation on which it is based. The resulting
theory provides a canonical approach for proving second-order asymptotic converses and is applicable to a wide
range of information-theoretic problems (including problems with general
alphabets) for which no such results were known.



 §.§ “Blowing up” vs “smoothing out”


In order to describe the core ingredients of our approach, let us begin by
delving into the main elements of the blowing-up method of
Ahlswede, Gács and Körner (a detailed treatment in a toy example will
be given in Section <ref>).

The concentration of measure phenomenon is one of the most important ideas
in modern probability <cit.>. It states that for many
high-dimensional probability measures, almost all points in the space are
within a small distance of any set of fixed probability. This basic
principle may be developed in different settings and has numerous
important consequences; for example, it implies that Lipschitz functions
on high-dimensional spaces are sharply concentrated around their median, a
fact that will not be used in the sequel (but is crucial in many other
contexts). The following modern incarnation of the concentration property
used in the work of Ahlswede-Gács-Körner is due to Marton
<cit.>; see
also <cit.>.
 
Denote the
r-blowup of 𝒜⊆𝒴^n by

    𝒜_r := { v^n∈𝒴^n:
    	d_n(v^n,𝒜)≤ r},

where d_n is the Hamming distance on 𝒴^n. Then

    P^⊗ n[𝒜_r] ≥
    	1-e^-c^2    
    	r=√(n/2)(
    	√(ln1/P^⊗ n[𝒜]) + c),

for any c>0 and any probability measure P on 𝒴.

For example, if n = 5 × 10^9 and P^⊗ n[𝒜] 
= e^-100, we can achieve P^⊗ n[𝒜_r] ≥ 1 - 
e^-100 by letting r = 10^6 = 0.0002 n. Asymptotically, if P^⊗ 
n[𝒜] does not vanish, then P^⊗ n[𝒜_r] → 
1 as long as r≫√(n). In other words, the rather remarkable fact 
is that we can drastically increase the probability of a set by perturbing 
only a very small (≈ n^-1/2) fraction of coordinates of each of 
its elements.

Ahlswede, Gács and Körner realized how to leverage the BUL
 to prove strong converses. Suppose one is in a situation
where a weak converse,  such as (<ref>), can be proved through Fano's inequality
or any other approach. This can
be done in  all information-theoretic problems with known
first-order asymptotics. However, a weak converse only yields the
correct first-order constant when the error probability ϵ is allowed to vanish,
while we are interested in the regime of constant ϵ. Let
𝒜 be the set of correctly decoded sequences, whose probability
is 1-ϵ. By the blowing-up lemma, a very slight blow-up
𝒜_r of this set will already have probability 1-o(1). We now
apply the weak converse argument using 𝒜_r instead of
𝒜. On the one hand, this provides the desired first-order
term in (<ref>), as 1-ϵ is replaced by 1-o(1). On
the other hand, we must pay a price in the argument for replacing the true
decoding set 𝒜 by its blowup 𝒜_r. If
r=o(n), the latter turns out to contribute only to lower order and
thus a strong converse is obtained.

The beauty of this approach is that it provides a very general recipe for
upgrading a weak converse to a strong converse, and is therefore widely
applicable. However, the method has (at least) two significant drawbacks:


  * It is designed to yield a strong converse, not the stronger
second-order asymptotic converse. Therefore, it is not surprising
that it fails to yield  second-order behavior
that we expect from
(<ref>): when optimized, the BUL method appears unable to give
a bound better than O(√(n)log^3/2n)
(e.g., <cit.>). This is already
suggested by Lemma <ref> itself: to obtain a ∼√(n)
second-order term from (<ref>), we would need 𝒜_r
to have probability at least 1-O(n^-1/2). That would require
perturbing at least r∼√(nlog n) coordinates, which already gives
rise to additional logarithmic factors. Thus, the blowing-up operation is
too crude to recover the correct second-order behavior. In Appendix
<ref>, we will show that this is not an inefficiency in the
blowing-up lemma itself, but is in fact an insurmountable problem of
any method that is based on set enlargement.

  * The argument relies essentially on the finite-alphabet setting. This
is not because of the blowing-up lemma, which works for any alphabet
𝒴, but because we must control the price paid for replacing
𝒜 by 𝒜_r.
While Lemma <ref> gives a lower bound on P^⊗ n[𝒜_r]
as a function of P^⊗ n[𝒜],
we can also upper bound P^⊗ n[𝒜_r]
as a function of P^⊗ n[𝒜]  by the
following simple argument, which relies crucially on the finiteness of the alphabet.

 
Suppose that |𝒴| < ∞ and that  P(a) >0 for all a ∈𝒴. Then

    r lnr/n e K≤lnP^⊗ n[𝒜]/P^⊗ n[𝒜_r]≤ 0.

where K = |𝒴|/min_a∈𝒴 P(a). Therefore, if r = o(n), then

    lim_n →∞1/nlnP^⊗ n[𝒜]/P^⊗ n[𝒜_r] = 0.



The right inequality in  (<ref>) follows from 𝒜⊂𝒜_r.
The set 𝒜_r is the overlapping union of spheres centered at the elements of 𝒜,
each of which contains fewer than nr |𝒴|^r elements. This fact, along with the  crude bound

    P^⊗ n (y^n)/P^⊗ n (z^n)≥(
    min_a∈𝒴 P(a)
    )^d_n ( y^n, z^n)

yields

    P^⊗ n[𝒜_r] ≤nrK^r  P^⊗ n[𝒜].

Then, the left inequality in (<ref>) follows from nr≤( e n/r)^r.


The main contribution of this paper is to show that the shortcomings of
the blowing-up method can be essentially eliminated while retaining its
wide applicability. This is enabled by two key ideas that play
a central role in our theory.


  * Functional inequalities.
To prove a weak converse such as (<ref>), one must relate the
relevant information-theoretic quantity (e.g., mutual information) to the
error probability (i.e., the probability of the decoding sets). This
connection is generally made using a data processing inequality. However,
in BUL-type methods, we no longer  work directly with the
original decoding sets, but rather with a perturbation of these that has
better properties. Thus, there is also no reason to restrict attention to
sets: we can replace the decoding set by an arbitrary
function, and then
control the relevant information functionals through their variational
characterization (that is, by convex duality). Unlike the data processing
inequality, such variational characterizations are in principle sharp and
provide a lot more freedom in how to approximate the decoding set.

  * “Smoothing out” vs. “blowing up”. Once one makes the
psychological step of working with functional inequalities, it becomes
readily apparent that the idea of “blowing up” the decoding sets is much
more aggressive than necessary to obtain a strong converse. What turns out
to matter is not the overall size of the decoding set, but only the
presence of very small values of the function  used in the
variational principle. Modifying the indicator function of a set to
eliminate its small values can be accomplished by a much smaller
perturbation than is needed to drastically increase its probability: this
basic insight explains the fundamental inefficiency of the classical BUL
approach.

To implement this idea, we must identify an efficient method to improve the
positivity of an indicator function. To this end, rather than “blowing up”
the set by adding all points within Hamming distance r, we will “smooth
out” the indicator function by averaging it locally over points at distance
∼ r. More precisely, this averaging will be performed by means of a
suitable Markov semigroup, which enables us to apply the reverse
hypercontractivity phenomenon 
<cit.> to establish strong
positivity-improving properties. Such hypercontractivity phenomenon replaces, in our approach,  the
much better known concentration of measure phenomenon that was exploited in
the BUL method. We will show, moreover, that Markov semigroup perturbations
are much easier to control than their blowing-up counterparts, so that our
method extends readily to general alphabets, Gaussian channels, and channels
with memory.

When combined, the above ideas provide a powerful machinery for developing
second-order converses. For example, in the basic data transmission
problem that we discussed at the beginning of Section <ref>, our
method yields

    ln M^* (n, ϵ) ≤ n C
    	+2√(ln1/1-ϵ)√(n(α-1))
    	+ln1/1-ϵ

(cf. Theorem <ref>), where α is a certain quantity
closely related to the dispersion. 
When compared to the exact second-order
asymptotics (<ref>), we see that
the second-order term has the correct scaling not only in the 
blocklength n →∞, but also in the error probability ϵ→ 1 (as 
Q^-1(1-ϵ)∼√(2ln1/1-ϵ) as 
ϵ→ 1). However, our method does not recover the exact 
dispersion in (<ref>); nor does it capture the fact that 
in the small error regime ϵ < 1/2, the second-order term in 
(<ref>) is in fact negative (the second-order term in 
(<ref>) is always positive). While the latter features are not 
directly achievable by the methods of this paper, they can be addressed
by combining our methods with type class analysis <cit.>. The 
details of such a refined analysis are beyond the scope of this paper.

Let us remark that there are various connections between the notions
of (reverse) hypercontractivity and concentration of measure; see, e.g.,
<cit.> and <cit.> in the
continuous case and <cit.> in the discrete
case. However, our present application of reverse hypercontractivity is
different in spirit: we are not using it to achieve concentration but
only a much weaker effect, which is the key to the efficiency of our method.
The sharpness and broad applicability of our method suggests that this may
be the “right” incarnation of the pioneering ideas of
Ahlswede-Gács-Körner: one might argue that the blowing-up method 
succeeded in its aims, in essence, because it approximates the natural smoothing-out 
operation.



 §.§ Organization


We have sketched the main ideas behind our approach in broad terms. To
describe the method in detail, it is essential to get our hands dirty. To
this end, we develop both the blowing-up and smoothing-out approaches in
Section <ref> in the simplest possible toy example: that of binary
hypothesis testing. While this problem is amenable to a (completely
classical) direct analysis, we view it as the ideal pedagogical setting in
which to understand the main ideas behind our general theory. 

The remainder of the paper is devoted to implementing these ideas in 
increasingly nontrivial situations.

In Section <ref>, we use our 
approach to strengthen Fano's inequality with an optimal O(√(n)) 
second-order term. We develop both the discrete and the Gaussian cases, 
and illustrate their utility in applications to broadcast channels and the 
output distribution of good channel codes.

In Section <ref>, we use our approach to strengthen a basic image
size characterization bound of <cit.>, obtaining a
O(√(n)) second-order term. The theory is developed once
again both in the discrete and the Gaussian cases. We illustrate the utility
of our results in applications to hypothesis testing under communication
constraints, and to source coding with compressed side information.

The paper concludes with two appendices. In Appendix <ref>, 
we show that no method based on set enlargement can achieve second-order 
converses. Thus the functional viewpoint of this paper is essential. 
Finally, Appendix <ref> contains proofs of some technical 
results used in section <ref>.




 §.§ Notation


We end this section by collecting common notation that will be used 
throughout the paper. First, we record two conventions that will always be 
in force:


  * All information-theoretic quantities (such as entropy, relative 
entropy, mutual information, etc.) will be defined in base e.

  * In all variational formulas (such as (<ref>), (<ref>), 
(<ref>), (<ref>), etc.) it is implicit in the notation that
we optimize only over functions or measures for which each term of the 
expression inside the supremum are finite.

We use standard information-theoretic notations
for relative entropy D(PQ), conditional relative entropy
D(P_X|UQ_X|U|P_U)= D(P_X|UP_UQ_X|UP_U), mutual information 
I(X;Y), entropy H(X), and differential entropy h(X). 

We denote by ℋ_+(𝒴) the set of nonnegative Borel 
measurable functions on 𝒴, and by 
ℋ_[0,1](𝒴) the subset of 
ℋ_+(𝒴) with range in [0,1]. For a measure ν 
and f∈ℋ_+(𝒴), we write ν(f):=∫ f dν and 
f_p^p = f_L^p(ν)^p = ∫ |f|^p dν. We will frequently 
use f_L^0(ν) := lim_q↓ 0f_L^q(ν) = 
exp(ν(ln f)) for a probability measure ν. The measure of a set is 
denoted as ν[𝒜], and the restriction of a measure to a set 
is denoted μ|_𝒞[𝒜] := 
μ[𝒜∩𝒞]. A random transformation Q_Y|X, 
mapping measures on 𝒳 to measures on 𝒴, is viewed 
as an operator mapping ℋ_+(𝒴) to 
ℋ_+(𝒳) according to 
Q_Y|X(f):=𝔼[f(Y)|X=·] where (X,Y)∼ Q_XY. The 
notation U-X-Y denotes that the random variables U,X,Y form a Markov 
chain. The cardinality of 𝒴 is denoted |𝒴|, and 
x^n denotes the Euclidean norm of a vector x^n∈ℝ^n. 
Finally, y_i denotes the ith element of a sequence or vector, while 
y^i denotes the components up to the ith one (y_j)_j≤ i.




§ PRELUDE: BINARY HYPOTHESIS TESTING




 §.§ Setup

The most elementary setting in which the ideas of this paper can be
developed is the classical problem of binary hypothesis testing. It should
be emphasized that our theory does not prove anything new in this setting:
due to the Neyman-Pearson lemma, the exact form of the optimal tests is
known and thus the analysis is amenable to explicit computation (we will
revisit this point in Section <ref>). Nonetheless, the
simplicity of this setting makes it the ideal toy example in which to
introduce and discuss the main ideas of this paper.

In the binary hypothesis testing problem, we consider two competing 
hypotheses: data is drawn from a probability distribution on 
𝒴, which we know is either P or Q. Our aim is to test, on 
the basis of a data sample, whether it was drawn from P or Q. More 
precisely, a (possibly randomized) test is defined by a function 
f∈ℋ_[0,1](𝒴): when a data sample 
y∈𝒴 is observed, we decide hypothesis P with probability 
f(y), and decide hypothesis Q otherwise. Thus, we must consider two 
error probabilities:

    π_P|Q:=Q(f)=    P  Q 
    π_Q|P:=1 - P(f) =    Q  P

We aim to investigate the fundamental
tradeoff between π_P|Q and π_Q|P
in the case of product measures P← P^⊗ n,
Q← Q^⊗ n; in other words,  what
is the smallest error probability π_P^⊗ n|Q^⊗ n that
may be achieved by a test that satisfies π_Q^⊗ n|P^⊗ n≤ϵ∈ (0,1)? In
this setting, the exact first-order and second-order asymptotics 
are due to Chernoff <cit.> and Strassen <cit.>, respectively, resulting in 

    ln1/π_P^⊗ n|Q^⊗ n =
    	nD(PQ)+Q^-1(1-ϵ)√(nV(PQ)) + 
    	o_ϵ(√(n)),

where V(PQ)=Var_P(lndP/dQ). 





The achievability (≤) part of (<ref>) is straightforward
(see Section <ref>), so the main interest in the proof is
to obtain the converse (≥). In this section, we will illustrate both
the blowing-up method of Ahlswede, Gács and Körner and the new
approach of this paper in the context of this simple problem, and compare
the resulting bounds to the exact second-order asymptotics
(<ref>).



 §.§ The blowing-up method


For simplicity, to illustrate the blowing-up method in the context of the 
binary hypothesis testing problem, we restrict attention to 
deterministic tests f=1_𝒜 for some 
𝒜⊆𝒴 (that is, we decide hypothesis P if 
y∈𝒜 and hypothesis Q otherwise). This is not essential, 
but it simplifies the analysis.

As we mentioned, the blowing-up method is a general technique for 
upgrading weak converses to strong converses. In the present setting, a 
weak converse (for any (P,Q), not necessarily product measures) follows 
in a completely elementary manner from the data processing property of 
relative entropy.



Let P,Q be probability measures on 𝒴 and
𝒜⊆𝒴 define the set of observations for which the deterministic test
decides P. 
If π_Q|P=P[𝒜^c]≤ϵ,
then π_P|Q=Q[𝒜] satisfies 

    ln1/π_P|Q≤D(PQ)+ ln 2/1-ϵ .




By the data processing property of relative entropy, we have

    D ( P  Q    )    ≥
    	P[𝒜]lnP[𝒜]/Q[𝒜] +
    	P[𝒜^c]lnP[𝒜^c]/Q[𝒜^c]
       ≥
    	(1-ϵ)ln1/Q[𝒜]
    	- h(P[𝒜^c]),

where h(ϵ) := -ϵlnϵ - (1-ϵ)ln(1-ϵ) ≤ln 2
is the binary entropy function.


Specializing to product measures P← P^⊗ n,
Q← Q^⊗ n, Lemma <ref> yields

    ln1/π_P^⊗ n|Q^⊗ n≤nD ( P  Q    ) + ln 2/1-ϵ

for any test that satisfies π_Q^⊗ n|P^⊗ n≤ϵ. 
While this is sufficient to conclude the weak converse [if 
π_Q^⊗ n|P^⊗ n→ 0, then π_P^⊗ 
n|Q^⊗ n cannot vanish faster than exp ( - n D ( P  Q ))] 
it falls short of recovering the correct first-order asymptotics in the 
regime of fixed ϵ, as we saw in (<ref>).



























The remarkable idea of Ahlswede, Gács and and Körner is that the 
argument of Lemma <ref> can be significantly improved by
applying the data processing argument (<ref>) not to 
the test set 𝒜 satisfying

    π_Q^⊗ n|P^⊗ n =
    P^⊗ n[𝒜^c]≤ϵ,
 
but to its blow-up
𝒜_r.  Then

    ln1/Q^⊗ n[𝒜_r]≤n D(PQ) + ln 2/P^⊗ n[𝒜_r].

We must now control both the gain and the loss caused by the blowup.
On the one hand, by the blowing-up Lemma <ref>,
P^⊗ n[𝒜_r]=1-o(1) as long as r≫√(n), which
eliminates the 1-ϵ factor in the weak converse (<ref>).
On the other hand, assuming finite alphabets we can invoke Lemma <ref> with r≪ n
and P← Q (we may assume without loss of generality that Q is 
positive on 𝒴) to obtain the strong converse

    ln1/π_P^⊗ n|Q^⊗ n≤
    	nD(PQ) + o_ϵ(n).
 
With a little more effort, we can
optimize the argument over r and quantify the magnitude of the 
lower-order term.

 
Assume |𝒴|<∞.
Any deterministic test between
P^⊗ n and Q^⊗ n on
𝒴^n such that
π_Q^⊗ n|P^⊗ n≤ϵ∈ (0,1)
satisfies

    ln1/π_P^⊗ n|Q^⊗ n≤
    	n D ( P  Q    )  +
    	 O(√(n)log^3/2 n).




By the blowing-up Lemma <ref>, we have (since 3 > √(2) - 1/√(n))

    P^⊗ n[𝒜_r] ≥
    	1-e^-r^2/n  
    	r≥ 3√(nln1/1-ϵ).

Assembling (<ref>) (with P ← Q),  (<ref>)  and (<ref>)
we obtain 

    ln1/π_P^⊗ n|Q^⊗ n≤n D(PQ) + ln 2/1-e^-r^2/n
    	+ r ln K e   n/r.

Choosing r≍√(nlog n) results in (<ref>).


Re-examining the proof of Proposition <ref>, we can easily 
verify that no other choice for the growth of r with n may accelerate 
the decay of the slack term in (<ref>). While the blowing-up 
method almost effortlessly turns a weak converse into a strong one, it 
evidently fails to result in a second-order converse. The rather crude 
bounds provided by Lemmas <ref> and <ref> may be 
expected to be the obvious culprits. It will shortly become evident, 
however, that the inefficiency of the method lies much deeper than 
expected: the major loss occurs already in the very first step (<ref>) 
where we apply the data processing inequality. We will in fact show in 
Appendix <ref> that any method based on the data processing 
inequality necessarily yields a slack term at least of order 
∼√(nlog n). To surmount this obstacle, we have no choice but to 
go back to the drawing board.




 §.§ The smoothing-out method


The aim of this section is to introduce the key ingredients of the new
method proposed in this paper. As will be illustrated throughout this
paper, this method yields  second-order converses while retaining the
broad range of applicability of the blowing-up method. In the following,
there will be no reason to restrict attention to deterministic tests
f=1_𝒜 as in the previous section, so we will consider
arbitrary randomized tests f∈ℋ_[0,1] from now on.



  §.§.§ Functional inequalities


To prove a converse, we must relate the relevant 
information-theoretic quantity D(PQ) to the properties of any given 
test f. This was accomplished above by means of the data processing 
inequality (<ref>). However, as was indicated at the end of the 
previous section, this already precludes us from obtaining sharp 
quantitative bounds. The first idea behind our approach is to replace the 
data processing argument by a different lower bound: we will use 
throughout this paper functional inequalities associated to 
information-theoretic quantities by convex duality. In the present 
setting, the relevant inequality follows from the Donsker-Varadhan 
variational principle for relative entropy <cit.> 
(see, e.g., <cit.>)

    D(PQ) = sup_g∈ℋ_+{ P(ln g)-ln Q(g)}.

Unlike the data
processing inequality, which can only attain equality in trivial
situations, the variational principle (<ref>) always attains
its supremum by choosing g←dP/dQ. Therefore,
unlike the data processing inequality, in principle an application of
(<ref>) need not entail any loss.

What we must now show is how to choose the function g in (<ref>)
to capture the properties of a given test f. Tempting as it is, the
choice g← f is dismal: for example, in the case of
deterministic tests f=1_𝒜, generally P(ln
1_𝒜)=-∞ and we do not even obtain a weak converse.
Instead, inspired by the blowing-up method, we may apply (<ref>) to
a suitably chosen perturbation of f. Let us first develop the
argument abstractly so that we may gain insight into the requisite
properties. Suppose we can design a mapping
T:ℋ_[0,1]→ℋ_[0,1] (which plays the role 
of
the blowing-up operation in the present setting) that
satisfies:


  * For any test f∈ℋ_[0,1] on 𝒴^n
with P^⊗ n(f)≥ 1-ϵ, we have

    P^⊗ n(ln Tf) ≥ -o_ϵ(n).


  * For any test f∈ℋ_[0,1] on 𝒴^n, we have

    ln Q^⊗ n(Tf) ≤ln Q^⊗ n(f) + o(n).


Setting g← Tf in (<ref>) and using
(<ref>) and (<ref>), we immediately deduce a strong
converse: for any test f∈ℋ_[0,1] such that
π_Q^⊗ n|P^⊗ n := P^⊗ n(1-f) ≤ϵ,
the error probability π_P^⊗ n|Q^⊗ n:=Q^⊗
n(f) satisfies (<ref>).
Besides replacing the data processing inequality by the variational
principle, the above logic parallels the blowing-up method:
(<ref>) plays the role of the blowing-up Lemma <ref>,
while (<ref>) plays the role of the counting estimate
(<ref>).

Nonetheless, this apparently minor change of perspective lies at the heart
of our theory. To explain why it provides a crucial improvement, let us
pinpoint the origin of the inefficiency of the blowing-up method. The
purpose of the blowing-up operation is to increase the probability of a
test: given P^⊗ n(f)≥ 1-ϵ, one designs a blow-up
f↦f̃ so that P^⊗ n(f̃)=1-o(1). However, when
we use the the sharp functional inequality (<ref>) rather than the
data processing inequality, we do not need to control P^⊗
n(f̃), but rather P^⊗ n(lnf̃). The latter is
dominated by the small values of f, not by its overall magnitude.
Therefore, an efficient perturbation of f should not seek to blow it up
but only to boost its small values, which may be accomplished at a much
smaller cost than the blowing-up operation. It is precisely this insight
that will allow us to eliminate the inefficiency of the blowing-up method
and attain sharp second-order bounds.

In order to take full advantage of this insight, we must understand how to
design efficient perturbations f↦ Tf. The second key ingredient of
our method is its main workhorse:  a general mechanism to
implement (<ref>) and (<ref>) so that their speed of decay
will be such that the slack term in (<ref>) is in fact O ( n^-1/2).



  §.§.§ Simple semigroups


The essential intuition that arises from the above discussion is that in
order to obtain efficient bounds in (<ref>) and (<ref>),
we must design an operation f↦ Tf that is
positivity-improving: it boosts the small values of f
sufficiently to ensure that P^⊗ n(ln Tf) is not too small. 
In this subsection we design a suitable transformation T, and in 
Section <ref> we show that it achieves the desired goal.


Let 𝒴 be an arbitrary alphabet and let P be any probability
measure thereon.
We say (T_t)_t≥ 0 is a simple semigroup[
	Readers who are unfamiliar with semigroups may ignore this
	terminology; while the semigroup property plays an important role
	in the proof of Theorem <ref>, it is not used
	directly in this paper.
]
with stationary measure P if

    T_tℋ_+(𝒴)→ℋ_+(𝒴),    
    	f↦ e^-tf+(1-e^-t)P(f).

In the i.i.d. case 𝒴←𝒴^n, P←
P^⊗ n we consider their tensor product

    T_t:=[e^-t+(1-e^-t)P]^⊗ n.

We will use T=T_t, for a suitable choice of t, as a
positivity-improving operation.

It is instructive to examine the effect of the operator in (<ref>) 
on indicator functions. For that purpose, we introduce the following 
ad-hoc notation: if (v^n, w^n) ∈𝒴^n ×𝒴^n 
and I ⊂{1, … , n}, then v^n I w^n ∈𝒴^n 
is defined by

    ( v^n I w^n )_i =
    {[     v_i ,     i ∈ I;     w_i , i ∈ I^c . ].

Then, using 

    (aQ+(1-a)P)^⊗ n=
    ∑_I⊂{1, … , n}a^n-|I|(1-a)^|I|P^⊗ IQ^⊗ I^c,

the application of the operator in (<ref>) to the indicator function becomes

    T_t1_𝒜(y^n) =
    	𝔼[1_𝒜(
    	Z^n 𝐈 y^n)],

where I is a random subset
of {1, … , n} obtained by including each element independently
with probability
1-e^-t (in particular, |𝐈|∼Binom(n,1-e^-t)),
and Z^n∼ P^⊗ n is independent of 𝐈.
In contrast, the
blowing-up operation may be expressed in terms of indicator functions as

    1_𝒜_r(y^n) =
    	max_|I|≤ rmax_z^n∈𝒴^n
    	1_𝒜( z^n I y^n).

From this perspective, we see that the semigroup operation is a
smoothing out counterpart of the blowing-up operation:
while the blowing-up operation maximizes the function over a local
neighborhood of size r, the semigroup operation averages the
function over a random neighborhood of size r≈ n(1-e^-t).
What we will gain from smoothing is that it increases the small values
of f (it is positivity-improving) without increasing the total mass
P^⊗ n(T_tf)=P^⊗ n(f), so that the mass under
Q^⊗ n cannot grow too much. In contrast, blowing-up
is designed to increase the mass P^⊗ n(f); but
then the mass under Q^⊗ n becomes large as well, which yields
the suboptimal rate achieved by the blowing-up method.



  §.§.§ Reverse hypercontractivity
 
It is intuitively clear that T_t is positivity improving: it maps
any nonnegative function to a strictly positive function. But the goal of
lower bounding P^⊗ n(ln Tf) is more ambitious.
This 
idea already appears in the probability theory literature in a very
different context: it was realized long ago by Borell
<cit.> that Markov semigroups possess very strong
positivity-improving properties, which are described quantitatively by a
reverse form of the classical hypercontractivity phenomenon. While Borell
was motivated by applications in quantum field theory, we will show in
this paper that reverse hypercontractivity provides a powerful mechanism
that appears almost tailor-made for our present purposes. 

We will presently describe an important generalization of Borell's ideas 
to general alphabets due to Mossel et al. <cit.>, and 
show how it may be combined with the above ideas to obtain sharp 
non-asymptotic converses.

 <cit.>.

Let (T_t)_t≥ 0 be a simple semigroup (<ref>) or an
arbitrary tensor product of
simple semigroups. Then

    T_tf_L^q≥f_L^p

for any 0<q<p<1, f∈ℋ_+, and t≥ln1-q/1-p.
In particular, letting q ↓ 0, we have

    P(ln T_t f) ≥logf_L^p (P).






An estimate of the form (<ref>) is almost immediate from 
(<ref>). 
On the other hand, the estimate (<ref>) will 
now follow from a simple change of measure argument. The following result 
combines these ingredients to derive a second-order converse for binary 
hypothesis testing.

 
Any test between P^⊗ n and Q^⊗ n such that
π_Q^⊗ n|P^⊗ n≤ϵ satisfies

    ln1/π_P^⊗ n|Q^⊗ n≤
    	 n D ( P  Q)
    	+ 2√(ln1/1-ϵ)√(n(α-1))
    	+ln1/1-ϵ,

where α = dP/dQ_∞≥ 1.



We establish (<ref>) and (<ref>) by
choosing T=T_t as defined by (<ref>). We fix any t>0 initialy
and optimize at the end of the proof.

Fix any test f∈ℋ_[0,1](𝒴^n).
To establish (<ref>), note that by (<ref>)

    P^⊗ n(ln T_t f)
    
    
    	   ≥lnf_L^1-e^-t(P^⊗ n)
       ≥1/1-e^-tln P^⊗ n(f)
    	
       ≥(1/t+1)ln P^⊗ n(f),

where (<ref>) used that f∈[0,1] and
(<ref>) follows from e^t≥ 1+t.

On the other hand, to establish (<ref>), we argue as follows:

    Q^⊗ n(T_tf)
    	   =Q^⊗ n((e^-t+(1-e^-t)P)^⊗ nf)
    
       =(e^-tQ+(1-e^-t)P)^⊗ nf
    
       ≤ (e^-t+α(1-e^-t))^nQ^⊗ n(f) 
    
       ≤ e^(α-1)ntQ^⊗ n(f),

where α=dP/dQ_∞≥ 1, and
(<ref>) is just the definition of T_t.

Now assume that the test f satisfies π_Q^⊗ n|P^⊗
n:=P^⊗ n(1-f)≤ϵ. Setting P← P^⊗ n,
Q← Q^⊗ n, and g← T_tf in
(<ref>), we obtain for all t>0

    ln1/π_P^⊗ n|Q^⊗ n≤
    	nD(PQ)
    	+ (1/t+1)ln1/1-ϵ
    	+(α-1)n t

using (<ref>) and (<ref>). 
Minimizing (<ref>) with respect to t yields (<ref>).





Beside resulting in a  second-order converse, the smoothing-out method
has an additional major advantage over the blowing-up method: the
change-of-measure argument (<ref>) is purely measure-theoretic in
nature and sidesteps the counting argument of Lemma <ref>.
No analogue of the latter can hold
beyond the finite alphabet case: indeed, in general alphabets even the
blowup of a set of measure zero will have positive measure, ruling out any
estimate of the form (<ref>). In contrast, the result of Theorem <ref>
holds for any alphabet 𝒴 and requires only a bounded density
assumption. Even the latter assumption is not an essential restriction and
can be eliminated in specific situations by working with semigroups other
than (<ref>). A particularly important example that will be
developed in detail later on in this paper is the case of Gaussian
measures (see, for example, Section <ref>).

The proof of Theorem <ref> illustrates the approach of this
paper in its simplest possible setting. However, the basic ideas that we
have introduced here form the basis of a general recipe that will be
applied repeatedly in the following sections to obtain second-order
 converses in a broad range of applications. The comparison
between the key ingredients of the blowing-up method and the smoothing-out
approach proposed in this paper is summarized in Table <ref>.




  §.§.§ Beyond product measures
 
Throughout this paper we focus for simplicity on stationary memoryless
systems, that is, those defined by product measures. However, our approach
is by no means limited to this setting. For the benefit of the
interested reader, let us briefly sketch in the context of Theorem
<ref> what modifications would be needed to adapt our
approach to general dependent measures. For an entirely different
application of our approach in a dependent setting, see <cit.>.

Consider the problem of testing between two arbitrary (non-product)
hypotheses P_n,Q_n on 𝒴^n. To adapt the proof of Theorem
<ref>, we need to introduce a hypercontractive semigroup with
stationary measure P_n. A natural candidate in this general setting is
the so-called Gibbs sampler T_tf(y^n)=𝔼_y^n[f(Y_t^n)],
where the Markov process Y^n_t is defined by replacing each coordinate
with an independent draw from its conditional distribution
P_Y_i|Y_∖ i (where Y_∖ i:=(Y_j)_j i) at independent
exponentially distributed intervals. It was shown in
<cit.> that any semigroup that satisfies a modified
log-Sobolev inequality is reverse hypercontractive. In particular, such
inequalities may be established for the Gibbs sampler under rather general
weak dependence assumptions <cit.>.

On the other hand, we need to establish an upper bound on
Q_n(T_tf). This may be done as follows. The Gibbs sampler satisfies
the differential equation <cit.>

    d/dt T_tf(y^n) = ∑_i=1^n
    	{P_Y_i|Y_∖ i=y_∖ i(T_tf)-T_tf(y^n)}.

We may therefore estimate for any f∈ℋ_+(𝒴^n)

    d/dt Q_n(T_tf) =
    	∑_i=1^n
    	{Q_n(P_Y_i|Y_∖ i(T_tf))-Q_n(T_tf)}≤ (α-1)n Q_n(T_tf),

where we used the tower property of conditional expectations and we defined

    α :=
    	max_iP_Y_i|Y_∖ i/Q_Y_i|Y_∖ i_∞.

Solving the differential inequality yields precisely the same estimate
Q_n(T_tf)≤ e^(α-1)ntQ_n(f) as was obtained  in
(<ref>) in the product case.

Putting together these estimates, we obtain for any test with
π_Q_n|P_n≤ϵ that

    ln1/π_P_n|Q_n≤
    	n D ( P_n  Q_n)
    	+ √(Cln1/1-ϵ)√(n(α-1))
    	+ln1/1-ϵ,

where C is the modified log-Sobolev constant of P_n.
This extends our approach for the memoryless case to any dependent 
situation where a modified log-Sobolev inequality is available for P_n. 
A deeper investigation of dependent processes is beyond the scope of this 
paper.





 §.§ Achievability and optimality



Theorem <ref> gives a non-asymptotic converse bound for binary
hypothesis testing. To understand whether it is accurate, we also need
an upper bound (achievability). Such a bound was already stated in
(<ref>). To motivate the following discussion, it is
instructive to give a quick proof of the achievability part of
(<ref>).


There exist a sequence of binary hypothesis tests  with π_Q^⊗ n|P^⊗ n≤ϵ such that

    ln1/π_P^⊗ n|Q^⊗ n≥
    	nD(PQ) + Q^-1(1-ϵ)√(nV(PQ))
    	+ o_ϵ(√(n)),

provided that V (PQ) :=Var_P(lndP/dQ)<∞.



 
For typographical convenience we will write
D:=D(PQ) and V:=V(PQ).
By the central limit theorem

    lim_n→∞
    	P^⊗ n[_P^⊗ nQ^⊗ n≥ nD + Q^-1(1-ϵ)√(nV)]
    	= 1-ϵ,

where we have defined the relative information

    _P^⊗ nQ^⊗ n(y^n):=
    lndP^⊗ n/dQ^⊗ n(y^n)
    =∑_i=1^nlndP/dQ(y_i)

whose mean and variance with y^n ∼ P^⊗ n are n D and n V, respectively.
We may therefore choose a deterministic
sequence a_n=o_ϵ(√(n)) such that the deterministic test
f_n=1_𝒜_n defined by

    𝒜={y^n∈𝒴^n:_P^⊗
    	nQ^⊗ n(y^n)
            ≥ nD + Q^-1(1-ϵ)√(nV) - a_n}

satisfies π_Q^⊗ n|P^⊗ n≤ϵ for all n. But
a simple Chernoff bound now yields

    π_P^⊗ n|Q^⊗ n≤
    	e^-nD - Q^-1(1-ϵ)√(nV) + a_n
    	Q^⊗ n(e^_P^⊗ nQ^⊗ n),

and the proof is completed by noting that Q^⊗
n(e^_P^⊗ nQ^⊗ n)=1.


Comparing the achievability bound (<ref>) with our converse
(<ref>), we see that the main features of the second-order
term are captured faithfully by the smoothing-out method, although it fails
to recover the precise constant in the second-order term:
V(PQ) is replaced by its natural uniform
bound V(PQ)≤dP/dQ_∞-1 in our  converse.[
	To see this, use xln^2x≤(x-1)^2 to show
	Var_P(lndP/dQ)≤
	Q(dP/dQln^2dP/dQ)≤ P(dP/dQ-1).]
Beside the optimal order scaling ∼√(n), we recall that the bound 
behaves correctly as a function of ϵ (up to universal constant) 
for large error probabilities ϵ→ 1; cf. the disucussion 
following (<ref>).

As is illustrated by Lemma <ref>, the achievability analysis is 
conceptually simple in the binary hypothesis testing case thanks to the 
Neyman-Pearson lemma which identifies the optimal test. However, in 
information theory optimal procedures are very seldom known explicitly.  
Thus, the methodology we have introduced says nothing new about binary 
hypothesis testing. The point of the present method, however, is that it 
applies broadly in situations where such a direct analysis is far out of 
reach. In particular, in the general setting of Section <ref> 
the present approach is currently the only known method to achieve sharp 
second-order converses in a variety of multiuser information theory 
problems.




§ SECOND-ORDER FANO'S INEQUALITY


The aim of this section is to develop the smoothing-out methodology for
channel coding problems, of which a basic example was discussed in Section
<ref>.

Weak converses for channel coding problems can be obtained in great 
generality (cf. <cit.>): this is the domain of Fano's 
inequality <cit.>, one of the most basic results in information 
theory, which gives an implicit upper bound on the error probability of an 
M-ary hypothesis testing problem.  For discrete memoryless channels, 
when combined with a list decoding argument, the blowing-up method 
strengthens Fano's inequality to a strong converse with 
∼√(n)log^3/2n second-order term 
<cit.>. In this section, we will show that the 
smoothing-out method results in a strong form of Fano's inequality that 
not only attains the optimal ∼√(n) second-order term, but is 
applicable to a much broader class of channels. The power of this 
machinery will be illustrated in two typical applications.

Before we turn to the main results of this section, it is instructive to
give a short proof of a basic form of Fano's inequality.  
Although we state it and prove it for deterministic decoding, it also
holds for stochastic decoders.



Let W∈{1,…,M} be an equiprobable message to be transmitted over
a noisy channel P_Y|X. Let c_1,…,c_M∈𝒳 be the
codewords corresponding to W, and let
𝒟_1,…,𝒟_M⊆𝒴 be the
disjoint decoding sets. Suppose the average probability of
correct decoding satisfies

    1/M∑_m=1^M P_Y|X=c_m[𝒟_m] ≥ 1-ϵ.

Then

    ln M ≤I(W;Y)+ln 2/1-ϵ,

where Y is the output of the channel P_Y|X with input X=c_W.


 
Let Ŵ be the decoded message, that is, Ŵ=c_m when the output
Y∈𝒟_m.
The bound can be shown by reduction to an auxiliary binary hypothesis testing problem:
P ← P_WŴ, Q ← P_W⊗ P_Ŵ.
Then the conclusion follows by applying Lemma <ref> 
with 𝒜={(x,x̂):x=x̂} since I(W;Ŵ)≤ I(W;Y).


The proof of Fano's inequality highlights the connection between the
channel coding problems investigated in this section and the simple
hypothesis testing problem of Section <ref>. In particular, it
suggests that the weak converse (<ref>) may be strengthened to a
strong converse of the form ln M≤ I(W;Y^n) + O(√(n)) in the
setting of memoryless channels P_Y|X←
P_Y^n|X^n:=P_Y|X^⊗ n. Unfortunately, the latter does not
follow from the strong converse obtained in Section <ref> for
binary hypothesis testing. Indeed,  
the framework of Section <ref> does not apply as
 the measures P,Q that appear in the proof of Lemma
<ref> are not product measures even when the channel is
memoryless.
To sidestep this hurdle we will apply the
smoothing-out operation conditionally on X^n: that is, we will introduce
semigroups for which the channel P_Y^n|X^n=x^n is the stationary
measure. The main additional challenge that arises is that the semigroup depends on the channel input
x^n and must therefore be controlled uniformly in x^n.



 §.§ Bounded probability density case


In this section, we consider a random transformation P_X|Y from
𝒳 to 𝒴 and denote by P_Y^n|X^n=x^n:=
P_Y|X=x_1⊗⋯⊗ P_Y|X=x_n the corresponding n-fold memoryless
random transformation. The main assumption of this section is
that there exists a reference probability measure ν on 𝒴 
such that

    α :=
    	sup_x∈𝒳dP_Y|X=x/dν_∞∈ [1,∞).

This assumption is automatically satisfied in the finite alphabet setting
|𝒴|<∞, in which case we may choose ν to be
equiprobable and consequently α≤|𝒴|. However, the
present setting is much more general: it applies to an arbitrary output
alphabet 𝒴 and requires only the existence of bounded
densities.

The main result of this section is the following strong form of Fano's
inequality (cf. Lemma <ref>) exhibiting a √(n) second-order term..


Assume (<ref>) holds. Let W∈{1,…,M} be an equiprobable
message, let c_1,…,c_M∈𝒳^n be the codewords
corresponding to W, and let
𝒟_1,…,𝒟_M⊆𝒴^n be
disjoint decoding sets.  Suppose that

    ∏_m=1^M P_Y^n|X^n=c_m^1/M[𝒟_m]
    	≥ 1-ϵ.

Then

    ln M ≤
    	I(W;Y^n)
    	+2√(ln1/1-ϵ)√(n(α-1))
    	+ln1/1-ϵ,

where Y^n is the output of the memoryless channel P_Y^n|X^n = P^⊗ n_Y|X with input
X^n=c_W.





The geometric average criterion (<ref>) is stronger than the 
average error criterion (<ref>) in Fano's inequality, but is 
weaker than the maximal error criterion min_m 
P_Y^n|X^n=c_m[𝒟_m]≥ 
1-ϵ. Both the average and maximal error criteria are commonly used 
in information theory, and our assumption
(<ref>) is intermediate between these two conventional criteria.

It is natural to ask whether the strong Fano inequality 
(<ref>) remains valid even under the average error 
criterion, like the classical Fano inequality. This is not the case. In 
<cit.>, a general notion of “α-decodability” is 
introduced which subsumes the geometric average criterion, the average 
error criterion, and the maximum error criterion as the special cases 
α=0,1,-∞. It is shown there that α=0 is the critical 
value for the existence of a strong Fano inequality. In this sense, the 
assumption (<ref>) of Theorem <ref> is essentially 
the best possible.

While the strong Fano inequality itself cannot hold under the average 
error criterion, it is possible in some applications of this inequality to 
upgrade the subsequent results to hold under the average error criterion 
by an additional argument known as codebook expurgation. The 
idea behind this method is that if the average error criterion is met, 
then the maximal error criterion will be satisfied on a large subset of 
the codebook obtained by throwing out the worst half of the codewords 
(e.g., <cit.>).

By combining this device with 
Theorem <ref> we can, for example, recover a strong 
converse under the average error criterion for the basic channel coding 
problem of Section <ref>. The expurgation argument cannot be 
applied directly to Theorem <ref>, however, as I(W;Y^n) 
may change significantly when we throw out codewords. Whether or 
not an expurgation argument is feasible depends on the manner in which 
Theorem <ref> is used in a given application.


Before we turn to the proof of Theorem <ref>, let us
prepare for the smoothing-out argument that will appear therein.
For any x∈𝒳, denote by (T_x,t)_t≥ 0 the simple
Markov semigroup on 𝒴 with stationary measure P_Y|X=x:

    T_x,tf:=e^-tf+(1-e^-t)P_Y|X=x(f).

We denote by

    T_x^n,t := T_x_1,t⊗⋯⊗ T_x_n,t

the corresponding product semigroup with stationary measure
P_Y^n|X^n=x^n.


Unlike the simpler setting of Section <ref>,  the semigroup T_x^n,t depends on x^n.
To
work around this issue, we introduce a linear operator Λ_t:ℋ_+(𝒴^n)→ℋ_+(𝒴^n) that
dominates T_x^n,t uniformly over x^n:

    Λ_t :=
    	[e^-t+α(1-e^-t)ν]^⊗ n.

Note that Λ_t is not a Markov semigroup; in particular, its
total mass satisfies

    Λ_t1
    	=(e^-t+α(1-e^-t))^n
    	≤ e^(α-1)nt.

However, Λ_t dominates the semigroups T_x^n,t in the following
sense.


Assume (<ref>) holds.
Then for any f∈ℋ_+(𝒴^n)

    sup_x^n∈𝒳^nT_x^n,tf
    	≤Λ_t f.




The result follows immediately from the definition of T_x^n,t,
Λ_t, and α upon noting that P_Y|X=x(g) ≤αν(g) whenever g≥ 0.


We are now ready for the proof of Theorem <ref>.


Let f_m:=1_𝒟_m and t>0 to be optimized later.
Note that

    I(W;Y^n)
    	   =
    	1/M∑_m=1^M D(P_Y^n|X^n=c_mP_Y^n)
    	
       ≥1/M∑_m=1^M
    	P_Y^n|X^n=c_m(lnΛ_t f_m)
    	-1/M∑_m=1^Mln P_Y^n(Λ_t f_m)

where (<ref>) is from the variational formula (<ref>).

We can lower bound the first term in (<ref>) as follows:

    1/M∑_m=1^M
    	lnΛ_tf_m_L^0(P_Y^n|X^n=c_m)
       ≥1/M∑_m=1^MlnT_c_m,tf_m_L^0(P_Y^n|X^n=c_m)
       ≥1/1-e^-t 1/M∑_m=1^Mln P_Y^n|X^n=c_m(f_m)
    
       ≥
    	-(1/t+1)
    	ln1/1-ϵ

where (<ref>) is from (<ref>);
(<ref>) is from Theorem <ref> and f∈[0,1];
and (<ref>) is from (<ref>) and e^t≥ 1+t.
For the second term in (<ref>), we can estimate

    -1/M∑_m=1^M
    ln P_Y^n(Λ_tf_m)
       ≥
    -
    ln P_Y^n(1/M∑_m=1^M Λ_tf_m)
    
       ≥ln M-(α-1)nt

using Jensen's inequality, ∑_mf_m≤ 1, and (<ref>).
Combining (<ref>), (<ref>), and (<ref>) and optimizing over
t>0 concludes the proof.





 §.§ Gaussian case


The strong Fano inequality of the previous section applies in principle to
arbitrary alphabets 𝒳,𝒴. However, in certain
situations the bounded density assumption (<ref>) may be overly
restrictive, particularly when the alphabets are unbounded. In this
section, we will adapt the argument of the previous section to the
prototypical example where this issue arises, namely, Gaussian channels.
Beside the intrinsic utility of the result, this will illustrate the
broader applicability of the smoothing-out method beyond the simple
semigroup setting exploited so far.

Throughout this section, we consider the random transformation
P_Y|X=x=𝒩(x,1) from ℝ to ℝ, so that
the corresponding memoryless channel is defined by
P_Y^n|X^n=x^n=𝒩(x^n,𝐈_n). In this setting, we have
the following Gaussian analogue of Theorem <ref>. For
later applications to broadcast channels, we consider a slight extension
of the setting of Theorem <ref> to allow stochastic
encoders that use log_2 L random bits.



Let P_Y|X=x=𝒩(x,1).
Consider any encoding function ϕ:[M]×[L]→ℝ^n
and disjoint decoding sets
𝒟_1,…,𝒟_M⊆ℝ^n.
Suppose that

    ∏_w,vP_Y^n|X^n=ϕ(w,v)^1/ML[𝒟_w]
    	≥ 1-ϵ.

Then

    ln M ≤
    	I(W;Y^n)
    	+√(2ln1/1-ϵ)√(n)
    	+ln1/1-ϵ,


 where Y^n is the output of the channel P_Y^n|X^n with input
X^n=ϕ(W,V), and (W,V) is equiprobable on [M]×[L]. 


In the Gaussian setting, it is natural to work not with simple
semigroups but rather with the Ornstein-Uhlenbeck semigroup
with stationary measure 𝒩(x^n,I_n):

    T_x^n,tf(y^n)
    	:=𝔼[f(e^-ty^n+(1-e^-t)x^n
    	+√(1-e^-2t)V^n)],

where V^n∼𝒩(0^n,I_n).
In this setting, Borell <cit.> showed that
reverse hypercontractivity
(<ref>) holds under the even weaker assumption
t≥1/2ln1-q/1-p.

The proof will proceed a little differently than in Section <ref>.
Here, the analogue of Λ_t in (<ref>) is simply
T_0^n,t. Instead of Lemma <ref>,
we will exploit a simple change-of-variable formula: for any f≥ 0, t>0 and x^n∈ℝ^n,
we have

    P_Y^n|X^n=x^n(ln T_0^n,t f)
    	=P_Y^n|X^n=e^-tx^n(ln T_e^-tx^n,t f),

which can be verified directly from  (<ref>).




Let f_w=1_𝒟_w for w∈[M]. Define also X̅^n=e^tX^n,
and denote by Y̅^n the output of the channel P_Y^n|X^n with
input X^n←X̅^n. Note that

    D(P_Y̅^n|W=wP_Y̅^n)
    
       ≥1/L∑_v=1^L
    	P_Y^n|X^n=e^tϕ(w,v)
    	(ln T_0^n,tf_w)
    	-ln P_Y̅^n(T_0^n,tf_w)
    
       =1/L∑_v=1^L
    	P_Y^n|X^n=ϕ(w,v)
    	(ln T_ϕ(w,v),tf_w)
    	-ln P_Y̅^n(T_0^n,tf_w)

for each w, where the key step (<ref>) used (<ref>).

The summand in the first term of the right side of (<ref>) can be bounded using reverse
hypercontractivity for the Ornstein-Uhlenbeck semigroup (<ref>) as


    P_Y^n|X^n=ϕ(w,v)
    	(ln T_ϕ(w,v),tf_w)
    	   ≥1/1-e^-2tln
    	P_Y^n|X^n=ϕ(w,v)(f_w).

Therefore, using assumption (<ref>), we obtain

    1/ML∑_w,v P_Y^n|X^n=ϕ(w,v)
    	(ln T_ϕ(w,v),tf_w)
    	≥ -1/1-e^-2tln1/1-ϵ.

On the other hand, by Jensen's inequality,

    1/M∑_w=1^Mln P_Y̅^n(T_0^n,tf_w)
    	   ≤ln P_Y̅^n(
    	1/M∑_w=1^M
    	T_0^n,tf_w)
    	≤ln1/M,

where we used ∑_w f_w≤ 1. Thus, averaging over w
in (<ref>), we find

    ln M ≤
    	I(W;Y̅^n)
    	+1/1-e^-2tln1/1-ϵ.

We must now bound I(W;Y̅^n) in terms of I(W;Y^n).
To this end,
let G^n∼𝒩(0^n,I_n) be independent of X^n and
note that

    h(Y̅^n)
    	   =h(e^tX^n+G^n)
    	
       =h(X^n+e^-tG^n)+nt
    	
       ≤ h(Y^n)+nt,

where (<ref>) can be seen from the entropy power inequality.
On the other hand,

    h(Y̅^n|W=w)-h(Y^n|W=w)
    	
       =I(Y̅^n;X^n|W=w)
    	-I(Y^n;X^n|W=w) ≥ 0

for every w,
where the equality follows as h(Y̅^n|X^n,W=w)=h(Y^n|X^n,W=w)=h(G^n)
and nonnegativity can be seen from <cit.>.
Combining (<ref>), (<ref>), and (<ref>) and using
e^t≥ 1+t yields

    ln M ≤
    	I(W;Y^n)
    	+(1/2t+1)
    	ln1/1-ϵ + nt,

and the conclusion follows by optimizing over t.



If the geometric average criterion (<ref>) is replaced by the
stronger maximal error criterion, a Gaussian Fano inequality with
∼√(n) second-order term can also be obtained using the
information spectrum method and the Gaussian Poincaré inequality; see
<cit.>. However, beside the stronger
assumption, the resulting bound is much less explicit and does not recover
the correct dependence of the second-order term on the error probability
as ϵ→ 1.




 §.§ Application: output distribution of good channel codes


As a very first application, let us note that Theorem 
<ref> effortlessly gives a sharp non-asymptotic converse 
for the basic data transmission example of Section <ref> for 
discrete memoryless channels. Since by the data processing inequality 

    I(W;Y^n) ≤ 
    	nsup_P_XI(X;Y) =: nC,
 
the maximal code size satisfies 

    ln M^* (n, ϵ)  ≤ nC + 2√(|𝒴|ln1/1-ϵ)√(n)
    	+ln1/1-ϵ,

where we chose the reference measure ν in (<ref>) to be 
uniform on 𝒴. 

It was observed in <cit.> that if a code 
is close
to achieving the upper bound (<ref>) , this places a strong
constraint on what the transmitted message looks like. In particular, it 
was shown there that if an (n,M,ϵ)-code satisfies

    ln M = nC + o(n),

then it is necessarily the case that

    1/nD(P_Y^nP_Y^n^⋆) = o(ϵ),

where 
P_Y^n is the channel output distribution induced by the codebook 
and P_Y^n^⋆:=P_Y^⋆⊗ n and P_Y^⋆ is
the unique maximal mutual information output distribution (note that corresponding optimal input distribution need not be unique).
That is, the output distribution of a good code must approximate the 
capacity-achieving output distribution in the small error probability 
regime. Such a necessary condition for good channel codes sometimes 
provides guidelines for their design. 

Theorem <ref> enables us to develop a sharp quantitative 
form of this phenomenon for any discrete memoryless channel.


Consider a discrete memoryless channel P_Y|X with capacity C. An 
(n,M,ϵ) code (under the maximal error criterion) satisfies

    D(P_Y^nP_Y^n^⋆)
    	≤
    	nC-ln M +
    	2√(|𝒴|ln1/1-ϵ)√(n)
    	+ln1/1-ϵ

where P^⋆_Y^n is the unique capacity achieving output 
distribution defined above.


Two second-order bounds on the approximation error 
D(P_Y^nP_Y^n^⋆) were previously derived in 
<cit.>. In 
<cit.>, an analogue of Theorem 
<ref> is obtained using the blowing-up method; as usual, this 
results in a suboptimal second-order term. However, in 
<cit.> (see 
<cit.> for a sharper formulation) 
a result analogous to Theorem <ref> is obtained with sharp
second-order term under the following assumption (the 
Burnashev condition <cit.>):

    sup_x,x'dP_Y|X=x/dP_Y|X=x'_∞<∞.

Theorem <ref> shows that the Burnashev condition is 
unnecessary: the result holds for any discrete memoryless channel. Its 
proof is completely straightforward; one simply follows the steps in 
<cit.> using the optimal second-order
Fano inequality (Theorem <ref>) in lieu of the blowing-up
argument.


It suffices to note that

    D(P_Y^nP_Y^n^⋆) 
    	   = D(P_Y^n|X^nP_Y^n^⋆|P_X^n) 
    	-I(X^n;Y^n) 
       ≤ nC - I(X^n;Y^n),

where (<ref>) is a well-known identity, and (<ref>) follows 
from 
the saddle point property of the capacity-achieving distribution 
<cit.>.
It remains to bound I(X^n;Y^n) using
Theorem <ref>, where we choose ν in (<ref>) 
to be uniform on 𝒴.



We have stated the above form of Theorem <ref> for simplicity. 
Without any additional difficulty, the finite alphabet assumption may be 
weakened to a bounded density assumption (<ref>) and the maximal 
error criterion may be weakened to the geometric average 
criterion (<ref>). A Gaussian counterpart of 
Theorem <ref> can also be obtained in a similar manner using 
Theorem <ref>, strengthening the result of <cit.> to the geometric average criterion.



By codebook expurgation (cf. Remark <ref>), 
one can slightly modify the strong channel coding 
converse (<ref>) to remain valid even under the average
error criterion. In contrast, the proof of Theorem <ref> relied
on the sharper bound on I(W;Y^n) given in Theorem 
<ref>, and thus the codebook expurgation method does not
apply in this setting. It is shown in <cit.> that the 
geometric average criterion developed here is (in a particular sense) the 
weakest criterion under which Theorem <ref> may hold, so that 
our approach is optimal also in this sense.




 §.§ Application: broadcast channels



Determining the capacity region of general broadcast channels is a 
long-standing open problem in information theory <cit.>. The 
general setting is illustrated in Figure <ref>. A transmitter wishes 
to send messages (W_1,W_2), equiprobable on [M_1]×[M_2], to two 
respective receivers, using n repetitions of the random transformations 
P_Y|X and 
P_Z|X. A code consisting of codewords c_u,v∈𝒳^n (with 
u∈[M_1], v∈[M_2]) is said to be an 
(n,M_1,M_2,ϵ)-code under the average error criterion, if the receivers can reconstruct 
Ŵ_1 and Ŵ_2 from the outputs of their respective 
channels with error probabilities

    ℙ[Ŵ_1≠ W_1]≤ϵ,    ℙ[Ŵ_2≠ W_2]≤ϵ.

The problem of understanding precisely what codebook sizes M_1,M_2 can 
be transmitted with a given error probability remains, in general, an open 
problem. However, we will consider the case of degraded broadcast 
channels which is much better understood. The additional structural 
assumption in this case is that P_Z|X equals the concatenation of 
P_Y|X and a certain random transformation P_Z|Y (or the other way 
around). In particular, in the setting of Gaussian broadcast channels, 
this additional assumption is always satisfied.

The aim of this section is to show how to obtain second-order converses for
both Gaussian and discrete degraded broadcast channels using our methods,
improving the best previously known bounds. To avoid digressions
unrelated to the topic of this paper, we will only sketch 
how Theorems <ref> and <ref> enter
the proofs. The subsequent manipulations of the first-order terms (using the chain rule and the entropy power 
inequality) are standard; we refer to <cit.> for the 
omitted steps and for matching achievability results. 
The maximal error criterion for the broadcast channel reads as

    max_w_1,w_2ℙ[Ŵ_1≠ W_1|(W_1,W_2)=(w_1,w_2)]≤ϵ,
    	
    max_w_1,w_2ℙ[Ŵ_2≠ W_2|(W_1,W_2)=(w_1,w_2)]≤ϵ.

The reduction to the average error criterion for the broadcast channel can also be done by a
codebook expurgation argument, albeit more sophisticated than the single-user setting; see <cit.>.
	
We now introduce the following geometric average decodability criterion for the broadcast channel,
which interpolates the average and the maximal error criteria above (see Remark <ref>).

    ∏_w_1,w_2ℙ^1/M_1M_2[Ŵ_1= W_1|(W_1,W_2)=(w_1,w_2)]≥ 1-ϵ,
    	
    ∏_w_1,w_2ℙ^1/M_1M_2[Ŵ_2= W_2|(W_1,W_2)=(w_1,w_2)]≥ 1-ϵ.

The geometric average criterion integrates seamlessly with our proof, which does not involve an expurgation argument.

We begin by stating the Gaussian result. In the stationary 
memoryless Gaussian broadcast channel, it is assumed that 
P_Y^n|X^n=P_Y|X^⊗ n and P_Z^n|X^n=P_Z|X^⊗ n
with 
P_Y|X=x=𝒩(x,σ_1^2) and 
P_Z|X=x=𝒩(x,σ_2^2). We assume moreover that the 
codewords c∈ℝ^n must satisfy the power constraint 
c^2≤ nP. The signal-to-noise ratios (SNR) of the two channels 
are then defined by S_i:=P/σ_i^2.


Consider a stationary memoryless Gaussian broadcast channel 
with SNRs S_1,S_2∈ (0,∞).
Suppose there exists an (n,M_1,M_2,ϵ)-code (under the geometric average criterion). Then

    ln M_1   ≤ n C(α S_1)
    	+√(2nln1/1-ϵ)
    	+ln1/1-ϵ,
    
    ln M_2   ≤ n C((1-α)S_2/α S_2+1)
    	+√(2nln1/1-ϵ)
    	+ln1/1-ϵ

for some α∈ [0,1], where C(t):=1/2ln(1+t).



We first use Theorem <ref> to obtain[Note that 
	as no power constraint is assumed in Theorem 
	<ref>, its conclusion extends verbatim to 
	channels with arbitrary positive variance by scaling.]

    ln M_1   ≤ I(W_1;Y^n|W_2)
    	+√(2nln1/1-ϵ)
    	+ln1/1-ϵ,
    	
    ln M_2   ≤ I(W_2;Z^n)
    	+√(2nln1/1-ϵ)
    	+ln1/1-ϵ.

To see (<ref>), we first apply Theorem <ref> to obtain:

    ln M_1   ≤ I(W_1;Y^n|W_2=w_2)
    	+√(2nln1/1-ϵ_w_2)
    	+ln1/1-ϵ_w_2,

where we defined

    ϵ_w_2=	1-∏_w_1ℙ^1/M_1[Ŵ_1= W_1|(W_1,W_2)=(w_1,w_2)].

Then we obtain (<ref>) by averaging (<ref>) over w_2 and applying Jensen's inequality:	

    1/M_2∑_w_2√(2nln1/1-ϵ_w_2)   ≤√(2n1/M_2·∑_w_2ln1/1-ϵ_w_2)
       =√(2nln1/∏_w_2(1-ϵ_w_2)^1/M_2)
       ≤√(2nln1/1-ϵ),

where we used the fact that

    ∏_w_2(1-ϵ_w_2)^1/M_2
    =
    ∏_w_1,w_2ℙ^1/M_1M_2[Ŵ_1= W_1|(W_1,W_2)=(w_1,w_2)]
    ≥ 1-ϵ.


Now it remains to bound the mutual 
informations I(W_1;Y^n|W_2) and I(W_2;Z^n) by the respective 
capacities; the proof of this part of the argument is identical that of 
the weak converse <cit.>, and we omit the 
details.


The analogous result in the discrete case is as follows.


Consider a degraded discrete memoryless broadcast channel
(P_Y|X,P_Z|X) and (n,M_1,M_2,ϵ)-code
(under the geometric average criterion). Then

    ln M_1
    	   ≤ n I(X;Y|U)+2√(|𝒴|nln1/1-ϵ)
    	+ln1/1-ϵ,
    
    ln M_2
    	   ≤
    	n I(U;Z)+2√(|𝒵|nln1/1-ϵ)
    	+ln1/1-ϵ

for some distribution P_UX.



The steps are identical to those of Theorem <ref>, modulo the
(trivial) generalization of Theorem <ref> to allow 
stochastic encoders as we did in Theorem <ref>.
The omitted manipulations of the mutual information terms follow 
identically the proof of the weak converse in this setting
<cit.>.


Theorem <ref> appears to be the first second-order converse for 
the discrete degraded broadcast channel, improving the suboptimal converse obtained by the 
blowing-up method <cit.> (cf. 
<cit.>). Our approach further 
extends beyond finite alphabets to the bounded density setting 
(<ref>). For the Gaussian broadcast channel, a strong converse 
with ∼√(n) second-order term was previously obtained in 
<cit.> via the information spectrum method. The present 
bound (<ref>) is sharper; in particular, it has the correct 
asymptotic dependence not only on n →∞ but also on the error probability ϵ→ 1. 




§ SECOND-ORDER IMAGE SIZE CHARACTERIZATION


The aim of this section is to develop the smoothing-out methodology for 
coding problems in network information theory that are proved by the 
“image size characterization” method. This powerful machinery was 
introduced in the original work of Ahlswede, Gács and Körner 
<cit.> for proving a strong converse for source 
coding with side information (cf. Section <ref>), and was 
further developed systematically in the classic monograph of Csiszár and 
Körner <cit.> to enable the 
analysis of a wide variety of source and channel networks.

Unfortunately, the general formulation of the image size method may appear 
rather technical at first sight, particularly if the reader is unfamiliar 
with the classical theory developed in <cit.>. To 
make the theory more accessible, we will first provide some motivating 
discussion and background in Section <ref>. The main results of 
this section, which give second-order forms of the image-size 
characterization method in discrete and Gaussian cases, are given in 
Sections <ref> and <ref>, respectively. Finally, 
we will illustrate the application of our framework in two representative 
applications in Sections <ref> and <ref>.

It should be emphasized that in order to keep this paper to a reasonable 
length, we treat here only the more basic setting of the image size 
problem that appears in the original paper 
<cit.>. However, our methods extend in full 
generality to the theory developed in <cit.>, which 
yields the strong converse property of all source-channel networks with 
known first-order rate region. In the terminology of 
<cit.>, the problem considered here only contains a 
“forward channel” while the general theory allows for the addition of a 
“reverse channel”; in fact, besides yielding second-order converses 
and extending to general alphabets, our methods have the further advantage 
of simplifying certain technical aspects in dealing with the reverse 
channel. A detailed development of our framework for the most general form 
of the image size characterization problem may be found in <cit.>.




 §.§ Synopsis





  §.§.§ A motivating example



Before we introduce the general setting for image size characterization, 
it is instructive to motivate its form through a simple application. To 
this end, let us begin by describing a variant of the binary hypothesis 
testing problem, due to Ahlswede and Csiszár 
<cit.>, in which the image size problem arises 
naturally. After we have developed the general results, we will return to 
this example and provide a second-order converse using our methods 
in Section <ref>.

Suppose 

we are given a joint probability measure Q_XY, and we obtain n 
independent observations drawn from either Q_XY or from 
Q_X⊗ Q_Y.
We would like 
to construct an optimal hypothesis test between these two alternatives:

    H_0    Q_XY^⊗ n,
    
     H_1    Q_X^⊗ nQ_Y^⊗ n.

When stated in this form, this is just a special case of the general 
binary hypothesis testing problem discussed in Section <ref>. In 
particular, for any test 
ℬ⊆𝒳^n×𝒴^n with error 
probability π_1|0:=Q_XY^⊗ n[ℬ^c]≤ϵ, we 
would like to understand how small an error probability 
π_0|1:=Q_X^⊗ nQ_Y^⊗ n[ℬ] can be achieved 
(we will focus here on deterministic tests for simplicity).
In other words, the aim of the binary hypothesis testing problem is to 
understand the quantity

    min_Q_X^nY^n[ℬ]≥ 1-ϵ 
    	Q_X^nQ_Y^n[ℬ].

Both a second-order converse (lower bound) and the matching achievability 
argument (upper bound) follow 
immediately from the results in Section <ref>.

We now, however, add a new ingredient. Suppose only Y^n is directly 
revealed to the statistician; the data X^n is observed elsewhere, and 
must be communicated to the statistician through a (noiseless) 
communication channel with limited capacity. That is, an encoder must 
encode the data X^n into a message W∈[M] that is transmitted 
noiselessly to the statistician; the capacity of the channel limits the 
size of the codebook to M∈ℕ. This situation is illustrated in 
Figure <ref>.
The communication constraint may be described by 
restricting the original binary hypothesis testing problem to a 
special class of tests of the form

    ℬ = ⋃_i=1^M (𝒜_i×ℬ_i)
    	⊆𝒳^n×𝒴^n,

where 𝒜_i={W=i} is the set of strings X^n for 
which the message i is transmitted to the statistician, and 
ℬ_i is the set of strings Y^n for which the statistician 
declares H_0 given that the message i was received.
In this setting, we aim to understand the interplay between the channel 
capacity and the attainable error probabilities of the test.
That is, the aim of the hypothesis testing problem with 
communication constraint is to understand the quantity

    min_Q_X^nY^n[ℬ]≥ 
    	1-ϵ, ℬ as in (<ref>) 
    	Q_X^nQ_Y^n[ℬ].

In accordance with the theme of this paper, we will be concerned 
here with the converse direction only; the achievability argument may be 
found in <cit.>.


In Section <ref>, we will give a second-order 
converse for the problem in (<ref>). For the purposes of the 
present motivating discussion, it will be convenient for simplicity to 
consider the stronger maximum error criterion variant[
	In Section <ref> we reduce the original 
	problem to such a variant by expurgation (cf. 
	Remark <ref>); however, for reasons explained in
	Section <ref>, this must be done carefully to attain 
	the correct rate.] 
of this problem:
how small can Q_X^nQ_Y^n[ℬ|X^n] be made for 
communication-constrained tests (<ref>), given that
Q_X^nY^n[ℬ|X^n]≥ 1-ϵ?
By applying (<ref>), this question can be reformulated as follows: if
we have

    max_x^n∈𝒜_i
    	Q_Y^n|X^n=x^n[ℬ_i^c]≤ϵ,

how small can Q_Y^n[ℬ_i] be made? In this formulation, it is 
not entirely clear how the codebook size M enters the picture. However, 
note that as there are only M codewords, at least one of the codewords 
must have large probability Q_X^n[𝒜_i]≥ 1/M. Therefore, a 
lower bound for the maximal error variant of (<ref>) naturally 
reduces to the problem of understanding the following quantity:

    min_Q_X^n[Q_Y^n|X^n[ℬ']≥ 1-ϵ]≥ 1/M
    	Q_Y^n[ℬ'].

The latter problem, which was originally considered in 
<cit.>, is the most basic form of the image 
size characterization problem that is studied in this section.[
	The name arises from the fact that we think of ℬ_i
	as an “(1-ϵ)-image” of 𝒜_i under the
	random transformation Q_Y^n|X^n <cit.>.
]

The motivation we have given here for the image size problem may appear 
rather specific to binary hypothesis testing with a communication 
constraint. However, just as ideas from binary hypothesis testing form the 
basis for a wide variety of coding problems, the image size problem turns 
out to arise in a broad range of problems in network information theory. 
After developing the general theory, we will discuss in some detail two 
applications: the present hypothesis testing problem with communication 
constraint (Section <ref>) and source coding with 
compressed side information (Section <ref>). Further 
applications are discussed in <cit.>.
Another interesting application to the problem of common 
randomness generation is developed in detail in <cit.>.



  §.§.§ The image size problem



We now turn to the formulation of the basic objects and results that 
will be investigated in this section.

In the following, let Q_Y|X be a given random transformation, and let 
ν and μ_n be positive measures on 𝒴 and 
𝒳^n, respectively. The general problem that will be 
investigated in this section is how to lower bound the ν^⊗ 
n-measure of a set 𝒜⊆Y^n in terms of its
“(1-ϵ)-preimage” under Q_Y^n|X^n:=Q_Y|X^⊗ n.
Instead of the formulation in (<ref>), we find it 
convenient to introduce a Lagrange multiplier c and investigate the
following unconstrained version of the problem: given any
c>0 and ϵ∈(0,1), find an upper bound on the quantity

    sup_𝒜⊆𝒴^n{lnμ_n[Q_Y^n|X^n[𝒜]>1-ϵ]
    	-
    	clnν^⊗ n[𝒜]	
    	}.

To understand the behavior of this quantity, we begin by defining the 
information measure that controls it to first order.


Given positive measures μ on 𝒳 and ν on 𝒴, 
a random transformation Q_Y|X, and constant c>0, we define

    d(μ, Q_Y|X, ν, c):=sup_P_X{cD(P_Yν)-D(P_Xμ)}

where the probability measures P_X,P_Y satisfy P_X→ Q_Y|X→ 
P_Y.



The quantity (<ref>) was called 
“Brascamp-Lieb divergence” in <cit.>.
Let us also note that the largest c>0 for which 
d(Q_X,Q_Y|X,Q_Y,c)=0 is the reciprocal of the strong data 
processing constant of Q_Y|X, cf. 
<cit.>.


To establish the natural connection between (<ref>) and 
(<ref>), let us begin by proving a weak converse. Evidently the method 
of proof has much in common with that of Lemma <ref> and is 
completely elementary (cf. <cit.>).



If ν is a probability measure, then 

    lnμ_n[Q_Y^n|X^n[𝒜]>1-ϵ]
    	-
    	c(1-ϵ)lnν^⊗ n[𝒜]
    	
           ≤ d(μ_n, Q_Y|X^⊗ n, ν^⊗ n, c)
    
    	+cln 2

for every set 𝒜⊆𝒴^n and
c>0, ϵ∈(0,1), Q_Y|X, and positive measure μ_n.



Define the event ℬ and probability measure Q_X^n by

    ℬ={x^n Q_Y^n|X^n=x^n[𝒜]>1-ϵ},
    	    
    	Q_X^n[𝒞]=
    	μ_n[ℬ∩𝒞]/μ_n[ℬ],

and let Q_Y^n be defined by Q_X^n→ Q_Y^n|X^n→ Q_Y^n.
Then

    D(Q_X^nμ_n)=ln1/μ_n[ℬ],

while by the data processing inequality

    D(Q_Y^nν^⊗ n)
    	   ≥ Q_Y^n[𝒜]lnQ_Y^n[𝒜]/ν^⊗ n[𝒜]
    	+
    	Q_Y^n[𝒜^c]lnQ_Y^n[𝒜^c]/ν^⊗ n[𝒜^c]
       ≥
    	(1-ϵ)
    	ln1/ν^⊗ n[𝒜]
    	-h(Q_Y^n[𝒜^c]).

Thus,

    d(μ_n,Q_Y|X^⊗ n,ν^⊗ n)
    	   ≥
    	cD(Q_Y^nν^⊗ n)
    	-D(Q_X^nμ_n)
    
       ≥
    	c(1-ϵ)ln1/ν^⊗ n[𝒜]-ln1/μ_n[ℬ]
    	-cln 2,

which is (<ref>).


Lemma <ref> is a weak converse due to the extraneous factor 
1-ϵ in front of lnν^⊗ n[𝒜] in 
(<ref>), which prevents us from attaining the optimal rate in 
the regime of nonvanishing error probability. Instead, we aim to 
prove a strong converse 

    lnμ_n[Q_Y^n|X^n[𝒜]>1-ϵ]
    	-
    	clnν^⊗ n[𝒜]
    	
           ≤ d(μ_n, Q_Y|X^⊗ n, ν^⊗ n, c)
    
    	+ o_ϵ(n).

Ahlswede, Gács and Körner <cit.> used
the blowing-up method to establish (<ref>) for 
finite alphabets. As usual, such an argument can only attain a 
suboptimal second-order term. In the follows subsections, we will use the 
smoothing-out method to obtain new sharp forms of
(<ref>) that attain both the O(√(n)) 
second-order term, and that may be extended beyond the finite-alphabet 
setting. In particular, we develop the relevant theory for discrete 
channels in Section <ref>, and for Gaussian channels in 
Section <ref>.




  §.§.§ The first-order term



Before we proceed to the main results of this section, we must discuss an 
independent issue that plays an important role in applications of image 
size characterizations. Consider the motivating example 
of hypothesis testing with a communication constraint discussed above.
A lower bound in (<ref>) is readily obtained by applying
Lemma <ref> or (<ref>) with μ_n=Q_X^⊗ 
n. When all measures in d(·) are product measures, it is 
readily evaluated by means of the tensorization property

    d(Q_X^⊗ n, Q_Y|X^⊗ n, Q_Y^⊗ n, c)
    	=n  d(Q_X, Q_Y|X, Q_Y, c)

(a simple proof may be found, for example, in <cit.>). Thus,
to first order, the quantity defined in (<ref>) grows 
linearly in n with rate d(Q_X, Q_Y|X, Q_Y, c) (with the 
optimal choice of Lagrange multiplier c). This is in fact the correct 
growth rate of (<ref>), as is demonstrated in
<cit.>. Unfortunately, 
however, this quantity does not give the correct first-order rate for 
the hypothesis testing problem with communication constraint: the best 
achievability result for the latter has a strictly smaller rate 
than is suggested by the above arguments.

It turns out that the origin of this inefficiency does not lie in 
(<ref>) itself, but rather in the initial argument that
reduced the information-theoretic problem to the study of the quantity 
(<ref>). When the argument is developed 
in detail, we will see that it is not necessary to consider the probability 
of codewords under the full measure Q_X^n, but only under the 
restriction
of this measure to any set 𝒞 of sufficiently high probability.
While the information-theoretic problem is not affected by throwing out
a small probability event, doing so has a significant effect on the 
resulting bounds. In particular,
as was noted in <cit.> in the finite alphabet 
setting, the best possible improvement to the first-order rate is obtained 
by choosing μ_n=Q_X^n|_𝒞_n to be the restriction to a set 
𝒞_n of typical sequences. As we will show in 
Appendices <ref> and <ref> for the discrete and 
Gaussian cases, respectively,[The claim in (<ref>) is the main theme of the conference paper 
<cit.> and the journal paper <cit.>. The proof of (<ref>) in the present paper is based on the concentration of the empirical distribution of X^n, which is similar in spirit to <cit.>. The proof in <cit.> adopts a different convex analysis argument which establishes (<ref>) for general distributions and also determines the exact prefactor in the O(√(n)) term. 
However, for conceptual simplicity we do not adopt the approach of <cit.> in the present paper.] such a choice of μ_n in fact gives rise to 
the estimate

    d(μ_n, Q_Y|X^⊗ n, ν^⊗ n, c)
    	≤
    	n  d^⋆(Q_X, Q_Y|X, ν, c)+O(√(n))

where the modified rate d^⋆(·) is defined as follows.


Given a probability measure Q_X on 𝒳, a positive measure
ν on 𝒴, a random transformation Q_Y|X, and 
constant c>0, we define

    d^⋆(Q_X, Q_Y|X, ν, c) := 
           sup_P_UX P_X=Q_X{cD(P_Y|Uν|P_U)-D(P_X|UQ_X|P_U)}

where the joint distribution of U,X,Y is given by 
P_UXY:=P_UXQ_Y|X.


We observe that it follows immediately from Definitions <ref> and 
<ref> that d^⋆(Q_X, Q_Y|X, ν, c)≤ d(Q_X, 
Q_Y|X, ν, c). Therefore, restricting to a typical set always results in 
an improved bound. It will turn out that the rate (<ref>) captures 
precisely the correct first-order behavior of the information-theoretic 
applications in which image size characterizations will be applied. 
Moreover, as we are able to establish in (<ref>) a second-order term of 
order O(√(n)), the combination of such an estimate with the 
smoothing-out method enables us to attain second-order converses for 
applications of the image size problem. As the methods needed to establish 
(<ref>) are unrelated to the main topic of this paper, we focus 
presently on the smoothing-out method and relegate the proof of
(<ref>) to Appendix <ref>.



 §.§ Discrete case


The aim of this section is to established a non-asymptotic form of 
the strong converse for image size characterization (<ref>) 
in the finite alphabet setting. We will, in fact, initially work in the 
more general bounded density setting as in Section <ref>. We 
specialize subsequently to the finite alphabet setting only in order to 
achieve the appropriate characterization (<ref>) of the first-order 
term.

For the time being, let 𝒳,𝒴 be general alphabets, 
let Q_Y|X be a random transformation from 𝒳 to 
𝒴, and let ν be a probability measure on 𝒴.
We define, as usual, Q_Y^n|X^n:=Q_Y|X^⊗ n, and introduce
the bounded density assumption

    α :=
    	sup_x∈𝒳dQ_Y|X=x/dν_∞∈ [1,∞).

The basic result of this section is the following quantitative form of 
(<ref>).



For any positive measure μ_n on 𝒳^n,
f∈ℋ_[0,1](𝒴^n), η∈(0,1), and c>0,
we have

    lnμ_n[Q_Y^n|X^n(f)≥η]
    	-
    	clnν^⊗ n(f)
    	
           ≤ d(μ_n, Q_Y^n|X^n, ν^⊗ n, c)+
    	2c√(ln1/η)√(n(α-1))
    	+cln1/η.



The proof of Theorem <ref> relies on similar ideas to the 
proof of Theorem <ref>. As a first step, we must develop 
a variational characterization for the quantity d(·), 
generalizing the variational formula (<ref>) for relative entropy.


In the setting of Definition <ref>,

    d(μ, Q_Y|X, ν, c)
    	=sup_f∈ℋ_+(𝒴){lnμ(e^cQ_Y|X(ln f))-clnν(f)}.




There are several proofs in the literature (cf. <cit.>); 
here we give a short proof using (<ref>). First,
for any f, define a probability measure P_X by

    dP_X/dμ=
    	e^cQ_Y|X(ln f)/μ(e^cQ_Y|X(ln f)),

and define P_Y by P_X→ Q_Y|X→ P_Y. Then by (<ref>),
we have

    lnμ(e^cQ_Y|X(ln f))-clnν(f)
    	
       ≤lnμ(e^cQ_Y|X(ln f))+cD(P_Yν)-cP_Y(ln f)
    	
       =cD(P_Yν)-D(P_Xμ).

This proves the ≥ part of (<ref>).

Conversely, for any P_X, we have using (<ref>)

    cD(P_Yν)-D(P_Xμ)
    	
       ≤ cD(P_Yν)-P_X(cQ_Y|X(ln f))+lnμ(e^cQ_Y|X(ln f))
    	
       =lnμ(e^cQ_Y|X(ln f))-clnν(f)

where we chose f=dP_Y/dν.
This proves the ≤ part of (<ref>).


We can now complete the proof of Theorem <ref>. In the 
following, we will use the same semigroup device as in Section 
<ref>: we define the simple semigroup

    T_x,tf:=e^-tf+(1-e^-t)Q_Y|X=x(f)

and its product T_x^n,t := T_x_1,t⊗⋯⊗ T_x_n,t,
and we define the corresponding dominating operator Λ_t 
according to (<ref>). We recall, in particular, the key 
properties (<ref>) and (<ref>) that will also be used in the 
present proof.


We begin by noting that, by the variational principle given in
Proposition <ref>, we can estimate

    ∫g_L^0(Q_Y^n|X^n=x^n)
    	dμ_n(x^n)
    	   =∫ e^Q_Y^n|X^n(ln g) dμ_n
    	
       ≤
    	e^ d(μ_n,Q_Y^n|X^n,ν^⊗ n,c)g_L^1/c(ν^⊗ n)

for any function g∈ℋ_+(𝒴^n) for which the 
integrals are finite.

Now take g=(Λ_tf)^c and observe that by (<ref>),

    g_L^1/c(ν^⊗ n)   ≤ 
    	e^c(α-1)nt[ν^⊗ n(f)]^c.

On the other hand,

    ∫g_L^0(Q_Y^n|X^n=x^n)
    	dμ_n(x^n)
    	
       =
    	∫Λ_tf_L^0(Q_Y^n|X^n=x^n)^c
    	dμ_n(x^n)
    
       ≥∫f_L^1-e^-t(Q_Y^n|X^n=x^n)^c
    	dμ_n(x^n)
       ≥∫ Q_Y^n|X^n(f)^c/1-e^-t
    	dμ_n
       ≥η^c/1-e^-tμ_n[Q_Y^n|X^n(f)≥η],

where (<ref>) used (<ref>) and reverse hypercontractivity 
(Theorem <ref>); (<ref>) used that f∈[0,1]; and
(<ref>) follows from Markov's inequality. Putting together the 
estimates (<ref>), (<ref>), and (<ref>), we have shown 
that for every t>0

    lnμ_n[Q_Y^n|X^n(f)≥η]
    	-
    	clnν^⊗ n(f) 
           ≤ d(μ_n,Q_Y^n|X^n,ν^⊗ n,c)
    	+
    	c/1-e^-tln1/η
    	+
    	c(α-1)nt.

The desired inequality (<ref>) follows using 1/1-e^-t≤1/t+1 and optimizing over t.


As was explained in Section <ref>, it is essential for 
applications of Theorem <ref> to make a judicious choice of 
measure μ_n in order to attain the correct first-order rate of the 
information-theoretic problems of interest. To this end, we now specialize 
to the case of finite alphabets and state a ready-to-use result along 
these lines. The precise construction of μ_n may be found in Appendix 
<ref>.



Let |𝒳|<∞, Q_X be a probability measure on 
𝒳, ν be a probability measure on 𝒴, and
Q_Y|X be a random transformation. Define

    β_X :=1/min_x Q_X(x)∈ [1,∞),

and define α as in (<ref>). Then for any
δ∈ (0,1) and n>3β_Xln|𝒳|/δ,
we may choose a set 𝒞_n⊆𝒳^n with
Q_X^⊗ n[𝒞_n]≥ 1-δ such that

    lnμ_n[Q_Y^n|X^n(f)≥η]
    	-
    	clnν^⊗ n(f)
    
           ≤
    	n  d^⋆(Q_X,Q_Y|X,ν,c)
    	+
    	A√(n)
    	+cln1/η

for all f∈ℋ_[0,1](𝒴^n), c>0, 
η∈(0,1), where we defined
μ_n:=Q_X^⊗ n|_𝒞_n and

    A   :=ln (α^cβ_X^c+1)
    	√(3β_Xln|𝒳|/δ)
    	+
    	2c√((α-1)ln1/η).




This follows immediately by combining Theorem <ref>
and Theorem <ref> in Appendix <ref> (note that 
α_Y defined in the Appendix satisfies α_Y≤α).


While the formulation of Theorem <ref> and Corollary 
<ref> is closer in spirit to the formulation of the 
image-size characterization problem in 
<cit.>, it is worth noting 
that our approach naturally gives rise to a somewhat sharper variant of 
these results that can sometimes be used to obtain cleaner bounds in 
converse proofs. In particular, it is not really necessary to apply the 
Markov inequality (<ref>); we may work directly in applications with 
the following smoother version of the problem (stated, for future 
reference, in the setting of Corollary <ref>).


Let β_X, α, δ, n and μ_n be as in  
Corollary <ref>. Then

    ln∫ Q_Y^n|X^n^c(1+1t)(f)
    	 dμ_n
    	-clnν^⊗ n(f)
    
       ≤
    	n  d^⋆(Q_X,Q_Y|X,ν,c)
    	+ c(α-1)nt
    	+ln(α^cβ_X^c+1)
    	√(3nβ_Xln|𝒳|/δ)

for every c,t>0 and f∈ℋ_[0,1](𝒴^n).



Simply omit the use of Markov's inequality (<ref>) and the subsequent 
optimization over t in the proof of Theorem <ref>.


In the sequel, we will illustrate both 
Corollaries <ref> and <ref> in 
applications.




 §.§ Gaussian case


Beside giving rise to O(√(n)) second-order terms, another key 
advantage of the smoothing-out method is that it is applicable beyond the 
finite alphabet setting. We will presently further illustrate this feature 
by developing a Gaussian analogue of the image size theory of the previous 
section, opening the door to systematic extension of many applications of 
this methodology to the Gaussian setting. The basic result of this section 
is the following Gaussian version of Theorem <ref>.



Let Q_Y|X=x=𝒩(x,1) and 
ν be Lebesgue on ℝ.
Then we have

    lnμ_n[Q_Y^n|X^n(f)>η]
    	-clnν^⊗ n(f)
    	
           ≤ d(μ_n,Q_Y^n|X^n,ν^⊗ n,c)
    	+c√(2nln1/η)
    	+cln1/η

for any positive measure μ_n on ℝ^n,
f∈ℋ_[0,1](ℝ^n), η∈(0,1), and c>0.


The proof uses some ideas that were introduced in Section <ref>. 
In particular, in this section T_x^n,t will denote the 
Ornstein-Uhlenbeck semigroup (<ref>), and we will again exploit 
heavily the change-of-variables formula (<ref>).


Denote by μ̅_n the dilation of μ_n by the factor e^t, that 
is,

    μ̅_n[e^t𝒞]:=μ_n[𝒞]

for any set 𝒞. Applying Proposition <ref>, we can 
estimate

    ∫ e^Q_Y^n|X^n(ln g)
    	dμ̅_n
    	≤
    	e^ d(μ̅_n,Q_Y^n|X^n,ν^⊗ n,c)g_L^1/c(ℝ^n)

for any function g∈ℋ_+(ℝ^n) for which the integrals 
are finite.

Now take g=(T_0^n,tf)^c and observe that

    g_L^1/c(ℝ^n)   = T_0^n,tf_L^1(ℝ^n)^c
       = e^cntf_L^1(ℝ^n)^c
       =e^cnt[ν^⊗ n(f)]^c,

where (<ref>) can be verified using Fubini's theorem and (<ref>).
On the other hand,

    ∫ e^Q_Y^n|X^n(ln g)
    	dμ̅_n
    	   =
    	∫ e^cQ_Y^n|X^n=x^n(ln T_0^n,tf)
    	dμ̅_n(x^n)
    
       =∫
    	e^cQ_Y^n|X^n=e^-tx^n(ln T_e^-tx^n,tf)
    	dμ̅_n(x^n)
    
       =∫T_e^-tx^n,tf_L^0(Q_Y^n|X^n=e^-tx^n)^c
    	dμ̅_n(x^n)
    
       ≥∫f_L^1-e^-2t(Q_Y^n|X^n=e^-tx^n)^c
    	dμ̅_n(x^n)
    
       ≥∫f_L^1(Q_Y^n|X^n=e^-tx^n)^c/1-e^-2t
    	dμ̅_n(x^n)
    
       ≥η^c/1-e^-2tμ̅_n[x^n Q_Y^n|X^n=e^-tx^n(f)>η]
    
       = η^c/1-e^-2tμ_n[Q_Y^n|X^n(f)>η],

where (<ref>) follows from the change of variables formula 
(<ref>);
(<ref>) is from (<ref>) (with the sharp constant for Gaussian 
hypercontractivity, see secion <ref>);
(<ref>) used that f∈[0,1]; and
(<ref>) follows from the definition (<ref>) of μ̅_n.

Combining (<ref>), (<ref>), and (<ref>), we obtain

    lnμ_n[Q_Y^n|X^n(f)>η]
    	-clnν^⊗ n(f)
    
           ≤ d(μ̅_n,Q_Y^n|X^n,ν^⊗ n,c)
    	+inf_t>0{c/1-e^-2tln1/η
    	+cnt}
           ≤ d(μ̅_n,Q_Y^n|X^n,ν^⊗ n,c)
    	+c√(2nln1/η)
    	+cln1/η,

where (<ref>) used 1/1-e^-2t≤1/2t+1.

To conclude the proof, it remains only to show that

    d(μ̅_n,Q_Y^n|X^n,ν^⊗ n,c)
    	≤ d(μ_n,Q_Y^n|X^n,ν^⊗ n,c),

for which we use the following modification of the argument that led to
(<ref>). When P_X^n and μ_n are both scaled by e^t, the
relative entropy D(P_X^nμ_n) remains unchanged. On the other hand,
as D(P_Y^nν^⊗ n)=-h(P_Y^n), the same argument as was 
used in (<ref>) yields D(P_Y̅^nν^⊗ n)≤ 
D(P_Y^nν^⊗ n). Substituting these observations into 
Definition <ref> concludes the proof of (<ref>).


We finally state a ready-to-use Gaussian analogue of Corollary 
<ref>. The precise construction of μ_n may be 
found in Appendix <ref>.


Let Q_XY be any nondegenerate Gaussian measure, and
let ν be the Lebesgue measure on ℝ. Then for any 
δ∈(0,1) and n≥ 20ln2/δ, we may choose a set
𝒞_n⊆ℝ^n with 
Q_X^⊗ n[𝒞_n]≥ 1-δ such that

    lnμ_n[Q_Y^n|X^n(f)>η]-clnν^⊗ n(f)
    
           ≤ n  d^⋆(Q_X,Q_Y|X,ν,c)
    	+√(6nln2/δ)
    	+c√(2nln1/η)
    	+cln1/η

for all f∈ℋ_[0,1](ℝ^n), c>0,
η∈(0,1), where we defined
μ_n:=Q_X^⊗ n|_𝒞_n.



For Q_X=𝒩(0,σ^2) and Q_Y|X=x=𝒩(x,1), this 
follows immediately by combining Theorem <ref>
and Theorem <ref> in Appendix <ref>.

For a general Gaussian measure Q_XY, we argue as follows.
Suppose first that
Q_Y|X=x=𝒩(ax,a^2) for some a 0.
We can reduce to the case already proved by applying
(<ref>) with Ỹ:=Y/a, f̃(y^n)=f(ay^n); as
ν^⊗ n(f)=|a|^nν^⊗ n(f̃) and

    d^⋆(Q_X,Q_Ỹ|X,ν,c)=
    	 d^⋆(Q_X,Q_Y|X,ν,c)+cln|a|

(the latter follows directly from Definition <ref>),
it is readily verified that the 
conclusion of Corollary <ref> remains valid for any a 0.
Now suppose that we further scale X,Y simultaneously by some factor 
b 0; then clearly both sides of (<ref>) remain unchanged.
As any nondegenerate Gaussian measure may be obtained by scaling
X and Y in this manner, the proof is complete.





 §.§ Application: hypothesis testing with a communication constraint



We now revisit the hypothesis testing problem with communication 
constraint introduced in Section <ref>, and show 
how the general framework of Section <ref> enables us to 
achieve a second-order converse in this setting. Let us note that the 
first-order term in the following result gives the correct rate for this 
problem: the matching achievability argument can be found in 
<cit.>.



Let |𝒳|<∞, and consider the hypothesis testing problem 
with communication constraint defined in Section <ref>.
Let ℬ be any test of the form (<ref>) that uses at most 
M codewords and satisfies π_1|0:=Q_XY^⊗ n[ℬ^c]≤ϵ. Then the error probability π_0|1:=Q_X^⊗ 
nQ_Y^⊗ n[ℬ] satisfies

    lnπ_0|1≥    -nsup_U U-X-Y{I(U;Y)
    	I(U;X)≤1/nln M}
       
    	-(
    	2ln(αβ)
    	√(3βln4|𝒳|/1-ϵ)
    	+2√(αln4/1-ϵ))√(n)
    	-2ln4/1-ϵ

for n>3βln4|𝒳|/1-ϵ,
where β := max_x 1/Q_X(x) and 
α:=max_xdQ_Y|X=x/dQ_Y_∞.



We proceed in three steps.

Step 1. We begin with an expurgation argument. Suppose the test
ℬ of the form (<ref>) satisfies π_1|0≤ϵ 
and π_0|1=ρ.
We claim that for any ϵ'∈(0,1-ϵ), we can modify the 
coding scheme such that the error under H_0 is below 
ϵ+ϵ', and the error under H_1 is below 
ρ/ϵ' conditioned on each message.

Indeed, assume without loss of generality that the messages i=1,…,M 
are ordered such that Q_X^nQ_Y^n[ℬ|W=i] is increasing in 
i. Let

    i^† := min{i:Q_X^n[W>i]≤ϵ'},

and define a new test ℬ' that always declares
H_1 upon receiving i>i^†, and coincides with ℬ 
otherwise. Then ℬ' satisfies

    Q_X^nY^n[ℬ^' c] =
    	Q_X^nY^n[ℬ^c∩{W≤ i^†}]+
    	Q_X^n[W>i^†] ≤ϵ+ϵ'.

On the other hand, as Q_X^nQ_Y^n[ℬ'|W=i]=
Q_X^nQ_Y^n[ℬ|W=i] for i≤ i^† and as we assumed 
this quantity is increasing in i, we can estimate

    ϵ'Q_X^nQ_Y^n[ℬ'|W=i]
    	≤
    	Q_X^nQ_Y^n[ℬ∩{W≥ i^†}]
    	≤ρ

for all i=1,…,M (this is trivial for i>i^† as
then Q_X^nQ_Y^n[ℬ'|W=i]=0).
Thus, the claimed properties are satisfied for the modified
test ℬ'.

Step 2. Our aim is to apply Corollary <ref> to 
the modified test ℬ'. Fix for the time being any 
δ∈(0,1-ϵ-ϵ'), and define μ_n as in Corollary 
<ref>. Then

    1-ϵ-ϵ'
    	≤∫ Q_X^nY^n[ℬ'|X^n] dQ_X^n≤∫ Q_X^nY^n[ℬ'|X^n] 
    	dμ_n + δ

by (<ref>). Thus, we may bound, for any c≥ 1, 

    (1-ϵ-ϵ'-δ)^c(1+1/t)≤∫ (Q_X^nY^n[ℬ'|X^n])^c(1+1/t) 
    	dμ_n,

where we used Jensen's inequality and the fact that μ_n is a 
sub-probability measure.

Now denote by ℬ_i'⊆𝒴^n the set of sequences 
y^n for which the test ℬ' declares H_0 upon 
receiving message i (cf. (<ref>)). Then we may crudely estimate

    (1-ϵ-ϵ'-δ)^c(1+1/t)
       ≤∑_i=1^M 
    	∫ (Q_Y^n|X^n[ℬ_i'])^c(1+1/t)  dμ_n
    
       ≤ 
    	e^n d^⋆(Q_X,Q_Y|X,Q_Y,c) +
    	c(α-1)nt +
    	ln(α^cβ^c+1)√(3nβln|𝒳|/δ)∑_i=1^M
    	(Q_Y^n[ℬ_i'])^c

for n>3βln|𝒳|/δ and t>0, where we used 
Corollary <ref> in (<ref>). But as
Q_Y^n[ℬ_i']≤ρ/ϵ' by (<ref>),
we may rearrange the above estimate to obtain

    lnρ≥   
    	-n/c  d^⋆(Q_X,Q_Y|X,Q_Y,c)
    	-ln M/c
       
    	-(α-1)nt 
    	-(1+1/t)ln1/1-ϵ-ϵ'-δ
       
    	-ln(α^cβ^c+1)/c√(3nβln|𝒳|/δ)
    	-ln1/ϵ'.

Finally, making the convenient choices

    ϵ' = 1-ϵ/2,      δ = 1-ϵ/4,

recalling that ρ=π_0|1, and optimizing over t>0 yields

    lnπ_0|1≥   
    	-n/c  d^⋆(Q_X,Q_Y|X,Q_Y,c)
    	-ln M/c
       
    	-(
    	2ln(αβ)
    	√(3βln4|𝒳|/1-ϵ)
    	+2√((α-1)ln4/1-ϵ))√(n)
    	-2ln4/1-ϵ

for n>3βln4|𝒳|/1-ϵ and c≥ 1.

Step 3. To achieve the correct first-order rate it remains to 
optimize (<ref>) over c≥ 1. To this end, let us denote
the rate parameter that appears in (<ref>) by

    θ(R) := 
    	sup_U U-X-Y{I(U;Y)
    	I(U;X)≤ R}.

When we choose ν=Q_Y in Definition <ref>, the latter may be 
written as

    1/c d^⋆(Q_X, Q_Y|X, Q_Y, c)    =
    	sup_U U-X-Y{I(U;Y)-1/cI(U;X)}
       =
    	sup_0≤ R≤ln|𝒳|{θ(R)-R/c},

where we used that I(U;X)≤ln|𝒳|. But is not hard to show that
θ(R) is a concave function of R, cf. <cit.>. Thus, we obtain for any R'≥ 0

    inf_c≥ 1{1/c d^⋆(Q_X, Q_Y|X, Q_Y, c) +
    	R'/c}
    	=
    	
       inf_c>0{1/c d^⋆(Q_X, Q_Y|X, Q_Y, c) +
    	R'/c}
    	= θ(R'),

where we used in the first line that d^⋆(Q_X, Q_Y|X, Q_Y, c)=0 for c≤ 1 by the data processing
inequality I(U;Y)≤ I(U;X); and we used the minimax theorem in 
(<ref>). Setting R'=1/nln M completes the proof.





 §.§ Application: source coding with compressed side information


In this section, we revisit one of the original applications of the 
blowing-up method: the problem of source coding with compressed side 
information <cit.>. Using the 
methods of this section, we will obtain second-order converses for 
the discrete and Gaussian variants of this problem. The present setting is 
a typical example of side information problems, whose converses 
have so far proved to be particularly elusive in non-asymptotic information 
theory (see, e.g., <cit.>). Using the smoothing-out 
method, 
second-order converses can now be obtained by a straightforward 
replacement of the classical blowing-up analysis.







For second-order achievability bounds for side information problems, we 
refer the reader to <cit.>.

The problem that we investigate in this section is illustrated in 
Figure <ref>. Two correlated memoryless sources X^n,Y^n
with distribution Q_X^nY^n=Q_XY^⊗ n are 
encoded into messages W_1∈[M_1],W_2∈[M_2], respectively, and 
transmitted to a decoder. The (noiseless) communication channels are 
rate-constrained
in that they limit the sizes M_1,M_2 of the two codebooks. The decoder 
aims to reconstruct the source Y^n with error 
probability at most ϵ (the side information X^n is not 
reconstructed, but helps decode Y^n due to the correlation between the 
sources). We aim to understand the fundamental interplay between 
M_1,M_2 and ϵ.


We begin by developing a second-order converse in the finite alphabet 
setting.


Let |𝒳|,|𝒴|<∞, ϵ∈ (0,1), and n≥ 
3β_Xln4|𝒳|/1-ϵ,
where β_X is defined in (<ref>).
Then for any encoders f𝒳^n→[M_1],
g𝒴^n→ [M_2], and decoder Ŷ^n 
[M_1]×[M_2]→𝒴^n such that
ℙ[Y^n≠Ŷ^n] ≤ϵ, we have

    ln M_2 
    	   ≥ 
    	n inf_U U-X-Y{H(Y|U) 
    		I(U;X)≤1/nln M_1}
         
    	- (
    		2ln (|𝒴|β_X)
    		√(3β_Xln4|𝒳|/1-ϵ)
    		+ 2√(|𝒴|ln2/1-ϵ))√(n)
    	- 2ln4/1-ϵ.



Note that the first term on the right-hand side of (<ref>) 
corresponds precisely to the rate region for the present problem
(see, e.g., <cit.>).


The proof follows from Corollary <ref> using similar
steps as in <cit.>.
Define for every i∈[M_1] the set

    ℬ_i := {
    	y^n∈𝒴^n
    	y^n=Ŷ^n(i,g(y^n))}

of correctly decoded sequences y^n, given that the side information
message i was received. Then we have by assumption

    Q_X^n[Q_Y^n|X^n[ℬ_f(X^n)]]≥ 1-ϵ.

Thus, for any ϵ'∈ (ϵ,1), we obtain

    Q_X^n[Q_Y^n|X^n[ℬ_f(X^n)]≥ 
    	1-ϵ']
    	≥ 1-ϵ/ϵ'

by applying Markov's inequality to
Q_X^n[1-Q_Y^n|X^n[ℬ_f(X^n)]>ϵ'].

Fix for the time being any δ∈(0,1-ϵ/ϵ') 
such that n>3β_Xln|𝒳|/δ, and define
μ_n as in Corollary <ref>. Then

    μ_n[Q_Y^n|X^n[ℬ_f(X^n)]≥ 
    	1-ϵ']
    	≥ 1-ϵ/ϵ'-δ.

As f takes at most M_1 possible values, there exists i^* such 
that

    μ_n[Q_Y^n|X^n[ℬ_i^*]≥
            1-ϵ'] ≥1-ϵ/ϵ'-δ/M_1

by the union bound. On the other hand, if we let ν be the uniform 
distribution on 𝒴, then we can estimate by the definition of 
ℬ_i

    ν^⊗ n[ℬ_i]
    	=|𝒴|^-n|ℬ_i|≤
    	M_2|𝒴|^-n

for every i. Applying Corollary <ref> with
f=1_ℬ_i^*, η=1-ϵ' yields 

    ln1-ϵ/ϵ'-δ/M_1
    	- cln M_2|𝒴|^-n
       ≤lnμ_n[Q_Y^n|X^n[ℬ_i^*]≥ 1-ϵ']
    	- clnν^⊗ n[ℬ_i^*]
    	
       ≤
    	n  d^⋆(Q_X,Q_Y|X,ν,c) + A√(n)
    	+ cln1/1-ϵ',

where A is defined in (<ref>). Rearranging yields

    ln M_1 + cln M_2 
    	≥   
    	-n{ d^⋆(Q_X,Q_Y|X,ν,c)-cln|𝒴|}
       
    	- √(n)(
    	ln (|𝒴|^cβ_X^c+1)
    	√(3β_Xln4|𝒳|/1-ϵ)
    	+
    	2c√(|𝒴|ln2/1-ϵ))
    	
       
    	- cln2/1-ϵ
    	- ln4/1-ϵ,

for n>3β_Xln4|𝒳|/1-ϵ,
where we made the choices
ϵ'=1+ϵ/2 and
δ=1/2(1-ϵ/ϵ').

It remains to manipulate the first-order terms. Note first that

    d^⋆(Q_X,Q_Y|X,ν,c)-cln|𝒴|
    	   = 
    	sup_U U-X-Y{-cH(Y|U)-I(U;X)}
       =
    	 d^⋆(Q_X,Q_Y|X,Q_Y,c) - cH(Q_Y),

which follows readily from Definition <ref> and
(<ref>). We may therefore follow verbatim the arguments
in Step 3 of the proof of Theorem <ref> to optimize
(<ref>) over c≥ 1, which readily completes the proof of
(<ref>).


We now give a analogue of Theorem <ref> for Gaussian 
sources under quadratic distortion.
We note again that the first-order term of (<ref>) corresponds 
to the known rate region for this problem (e.g., let D_2→∞ in 
<cit.>).


Let 𝒳=𝒴=ℝ,
Q_XY=𝒩(0,([ 1 ρ; ρ 1 ])), and D>0, ϵ∈ (0,1),
n≥ 20ln8/1-ϵ. Then for any encoders
fℝ^n→[M_1], gℝ^n→ 
[M_2], and decoder Ŷ^n [M_1]×[M_2]→ℝ^n
such that ℙ[Y^n-Ŷ^n^2>nD] ≤ϵ, we have

    ln M_2
    	≥n/2ln1-ρ^2+ρ^2e^-2/nln M_1/D
    	-4√(ln8/1-ϵ)√(n)
    	-2ln4/1-ϵ.




Define for every i∈[M_1] the set

    ℬ_i := {
    	y^n∈ℝ^ny^n-Ŷ^n(i,g(y^n))^2≤ nD
    	}

of correctly decoded sequences y^n, given that the side information 
message i was received. Let ϵ'∈(ϵ,1), 
δ∈(0,1-ϵ/ϵ') such that n≥ 
20ln2/δ, define μ_n as in Corollary <ref>, and let 
ν be the Lebesgue measure on ℝ.
Repeating verbatim the arguments in the proof of Theorem 
<ref>, we find that there exists i^* such that

    μ_n[Q_Y^n|X^n[ℬ_i^*]≥
            1-ϵ'] ≥1-ϵ/ϵ'-δ/M_1.

On the other hand, in the present setting, we estimate by the union bound

    ν^⊗ n[ℬ_i] ≤
    	M_2Vol(Ball(0,√(nD)))
    	≤ M_2(2π e D)^n/2.

Applying Corollary <ref> with 
f=1_ℬ_i^*, η=1-ϵ' and rearranging yields

    ln M_1+cln M_2
    	≥   
    	-n{ d^⋆(Q_X,Q_Y|X,ν,c)
    	+c2ln(2π e D)}
       
    	-√(n)(√(6ln8/1-ϵ)
    	+c√(2ln2/1-ϵ))
    	
       
    	-cln2/1-ϵ
    	-ln4/1-ϵ

for n≥ 20ln8/1-ϵ,
where we made the choices
ϵ'=1+ϵ/2 and
δ=1/2(1-ϵ/ϵ').

It remains to manipulate the first-order terms. To this end, we first
note that using (<ref>) in
Appendix <ref> and the subsequent discussion, we may compute

    d^⋆(Q_X,Q_Y|X,ν,c) + c2ln(2π e D)
    	
       =
    	sup_σ∈[0,1]{1/2lnσ^2
    	-c/2ln1-ρ^2+ρ^2σ^2/D}
       =
    	c/2 ϑ^*(-1/c),

where ϑ^* is the convex conjugate of the convex function 
ϑ(x) := ln1-ρ^2+ρ^2e^-x/D for x≥ 0 and
ϑ(x) := +∞ for x<0. Therefore, by convex duality

    inf_c>01/c{ d^⋆(Q_X,Q_Y|X,ν,c) + c2ln(2π e D)
    	+ 1/nln M_1
    	}
       = - 1/2ϑ(2/nln M_1)
    	= - 1/2ln1-ρ^2+ρ^2e^-2/nln M_1/D.

We claim that the same conclusion follows if we take the infimum 
over c≥ 1 only. Indeed, it is readily verified that the function inside 
the supremum in (<ref>) is increasing in σ^2 for any
c<1, so that d^⋆(Q_X,Q_Y|X,ν,c) + c2ln(2π e 
D) = -c/2ln1/D for c<1. Thus, the infimum in 
(<ref>) cannot be attained for c<1. The proof is now readily 
completed using (<ref>) by optimizing
(<ref>) over c≥ 1.







 §.§ Application: one-communicator common randomness generation



In <cit.>, Ahlswede and Csiszár introduced source and channel models for common randomness (CR) generation.
One of the most basic and typical source model is the one communicator model as shown in Figure <ref>.
Two terminals T_0 and T_1, observing X^n and Y^n respectively, wish to generate integers K and K_1, which agree with high probability and are close to a uniform random number.
To achieve this, T_0 is allowed to communicate an integer W_1 to T_1.

Ahlswede and Csiszár proved the (first-order) capacity region of this common randomness generation problem,
i.e. the tradeoff between the limits of 1/nln|𝒦| and 1/nln|𝒲_1|.

In this section we give an O(√(n)) second-order converse.
Armed with the optimal second-order change-of-measure lemma of the present Section <ref>,
we now only need the following result relating the change-of-measure lemma to the performance of the CR generation.
To state this result, let us first introduce the notation (see e.g. <cit.>)

    E_1(μν):=∫| dμ- dν|^+

for nonnegative measures μ and ν, where |·|^+ denotes the positive part of a function.
Note that E_1(μν) is the total variation distance when μ and ν are both probability measures.

Consider the single-shot setup as depicted in Figure <ref>. Suppose that there exist δ_1,δ_2∈(0,1), a stochastic
encoder Q_W|X, and deterministic decoders Q_K|X and
Q_K̂|WY, such that

    ℙ[K=K_1]   ≥ 1-δ_1;
    1/2|Q_K-T_k|   ≤δ_2,

where T_K denotes the equiprobable distribution.
Also, suppose that there exist
μ_X, δ,ϵ'∈(0,1) and c∈(1,∞), d∈(0,∞) such that

    E_1(Q_Xμ_X)
       ≤δ;
    
    μ_X(x Q_Y|X=x(𝒜)≥ 1-ϵ')
       ≤
    2^cexp(d) Q_Y^c(𝒜)

for any 𝒜⊆𝒴. Then, for any
δ_3,δ_4∈(0,1) such that δ_3δ_4=δ_1+δ, we
have

    δ_2≥ 1-δ-δ_3-1/|𝒦|
    -2exp(d/c)
    |𝒲|/(ϵ'-δ_4)
    ^1/c|𝒦|^1-1/c.



Define the joint measure

    μ_XYWKK_1
    :=μ_X Q_Y|XQ_W|XQ_K|XQ_K_1|YW

which we sometimes abbreviate as μ.
Since E_1(Qμ)=E_1(Q_Xμ_X)≤δ,
(<ref>) implies

    μ(K≠ K_1)≤δ_1+δ.

Put

    𝒥:={kμ_K_1|K(k|k)≥ 1-δ_4}.

The Markov inequality implies that
μ_K(𝒥)≥ 1-δ_3. Now for each k∈𝒥, we have

    (1-δ_4)μ_k(k)
    
       ≤μ_KK_1(k,k)
    
       ≤∫_ℱ_kQ_Y|X=x(⋃_w𝒜_wk)
     dμ_X(x)
    
       ≤
    (1-ϵ')μ_K(k)+μ(x Q_Y|X=x(⋃_w𝒜_kw≥ 1-ϵ'))
    
       ≤ (1-ϵ')μ_K(k)
    +2^cexp(d) Q_Y^c(⋃_w𝒜_kw),

where ℱ_k⊆𝒳 is the decoding set for K, and 𝒜_kw is the decoding set for K_1 upon receiving w.
Rearranging,

    (ϵ'-δ_4)^1/cμ_k^1/c(k) ≤ 2
    exp(d/c)Q_Y(⋃_w 𝒜_kw).

Now let μ̃ be the restriction of μ_K on 𝒥. Then summing both sides of (<ref>) over k∈𝒥,
applying the union bound, and noting that {𝒜_kw}_k is a partition of 𝒴 for each w, we obtain

    D_1/c(μ̃T)
       ≤ln |𝒦|-1/1-1/cln2|𝒲|/(ϵ'
    -δ_4)^1/c
         -d/c-1.

The proof is completed invoking Proposition <ref> below and noting that

    E_1(Q_Kμ̃)
    ≤
    E_1(Q_Kμ)
    +E_1(μμ̃)≤δ+δ_3.



Recall that the Rényi divergence of order α≠ 1 between two nonnegative measures μ and ν is defined as

    D_α(μν):=1/α-1ln∫ dμ^α dν^1-α.

The following basic result relating E_1 and the Rényi divergence was used in the proof of Lemma <ref>.

Suppose T is equiprobable on {1,…,M} and μ is a nonnegative measure on the same alphabet. For any α∈(0,1),

    E_1(Tμ)
    ≥
    1-1/M-exp(-(1-α)D_α(μT)).



Consider the optimization problem over nonnegative vector a^M=(a_1,…,a_M):

    minimize f(a^M)   :=∑_m=1^M|1/M-a_m|^+
    
    subject to g(a^M)   :=1/M∑_m=1^M a_m^α≤λ

where λ>0 is some constant. Notice that if a^M and b^M satisfies

    1/M∑_m=1^M a_m= 1/M∑_m=1^M b_k

and that a_m-1/M and b_m-1/M have the same sign, then (since α≤1)

    f(1/2(a^M+b^M))   =1/2(f(a^M)+f(b^M))
    
    
    g(1/2(a^M+b^M))   ≥1/2(g(a^M)+g(b^M)).

This implies that there exists â^M an optimizer of (<ref>) satisfying

    |{m:â_m∈(0,1/M)}|≤ 1.

Moreover for any a^M, define b_m:=a_m 1{a_m<1/M}+1/M1{a_m≥1/M}, then

    f(b^M)   = f(a^M)
    
    
    g(b^M)   ≤(g(a^M)).

Thus, an optimizer â^M of (<ref>) can further be assumed to be of the following form:

    â^M=[1/M,1/M,…,1/M,η,0,0,…,0]

for some 0<η≤1/M, and then it is elementary to show that the optimal value for (<ref>) satisfies

    f≥1-λM^α-1/M.

Thus, we have shown that

    E_1(Tμ)≥ 1-1/M-M^α-1∑_m=1^Mμ^α(m)

as desired.


Now specializing the single-shot result of Lemma <ref> to 
the discrete memoryless case, and using 
Corollary <ref>, 
we obtain the following non-asymptotic second-order converse to the CR generation problem.
Note that the right side of (<ref>) is essentially

    exp(n^⋆/c+A/c√(n))|𝒲|/|𝒦|^1-1/c

where the √(n) term characterizes the correct second-order coding rate.


Consider a stationary memoryless source with per-letter distribution Q_XY.
Let

    β_X   :=1/min_xQ_X(x)∈ [1,∞);
    
    α   :=sup_x Q_Y|X=x/ Q_Y_∞∈ [1,∞);
    
    
    c   ∈ (1,∞).

Suppose that there exist a CR generation scheme (see the setup in
Figure <ref>) for which

    ℙ[K=K_1]   ≥ 1-δ_1∈ (0,1);
    
    1/2|Q_K-T_k|   ≤δ_2∈ (0,1).

Then for any δ_1'∈ (δ_1,1) and
n≥3β_Xln3|𝒳|/δ_1'-δ_1,
we have

    1-δ_2-δ_1'
    ≤1/|𝒦|
    +
    exp(
    n^⋆/c+A/c√(n)+ln4δ_1'+2δ_1/δ_1'-δ_1)|𝒲|/(δ_1'-δ_1/4δ_1'+2δ_1)^1/c|𝒦|^1-1/c,

where we have defined

    A   :=ln(α^cβ_X^c+1)√(3β_Xln3|𝒳|/δ_1'-δ_1)
    +2c√((α-1)ln4δ_1'+2δ_1/δ_1'-δ_1),
    
       :=(Q_X,Q_Y|X,Q_Y,c).



Specialize Lemma <ref> to the stationary memoryless setting:

    Q_XY← Q_XY^⊗ n.

Suppose we first pick the parameter δ_3∈ (δ_1,1) in Lemma <ref> arbitrarily, which in turn
yields the following choices of the other parameters therein:

    δ   =δ_3-δ_1/2;
    
    δ_4   =δ_1+δ_3/2δ_3.

Moveover, let ϵ'=1+δ_4/2 in Lemma <ref>.
Then we invoke Corollary <ref>, with ν=Q_Y and

    η=1-ϵ'.

Then (<ref>) implies that

    1-δ_2-3δ_3-δ_1/2≤1/|𝒦|
    +exp(
    n/c+A/c√(n)+ln4δ_3/δ_3-δ_1)|𝒲|/(
    δ_3-δ_1/4δ_3)^1/c|𝒦|^1-1/c

which is equivalent to (<ref>) upon setting δ_1'=3δ_3-δ_1/2.







§ ACKNOWLEDGEMENTS


Suggestions on the presentation of the paper by Yury Polyanskiy are
greatly appreciated. We thank Wei Yang for discussions on multiple
access channels.






§ DATA PROCESSING CANNOT YIELD SECOND-ORDER CONVERSES




The aim of this appendix is to explain the claim made in Section 
<ref> that second-order converses are fundamentally outside 
the reach of any method that is based on the data processing inequality: 
in particular, the inefficiency of the blowing-up method already appears 
in the very first step in the argument. This claim is little more than the 
Neyman-Pearson lemma in the following disguise.



Let P,Q be probability measures on 𝒴 such that
lndP/dQ_∞<∞.
Then for every δ>0, there exists C_δ>0 independent
of n so that any set
Ã⊆𝒴^n with P^⊗
n[Ã]≥ 1-n^-δ must satisfy ln Q^⊗
n[Ã]≥ -nD(PQ)+C_δ√(nln
n).


Let us first explain why this lemma rules out obtaining sharp bounds by
data processing. Suppose we start our argument by applying the data processing
inquality (<ref>) to an arbitrary set Ã. Then we
obtain (cf. (<ref>))

    ln Q^⊗ n[Ã] ≥
    	-nD(PQ)/P^⊗ n[Ã] - ln 2.

In order to deduce from this a non-asymptotic converse with ∼√(n)
second-order term, we must introduce some operation
𝒜↦Ã that associates to any
deterministic test
𝒜 with P^⊗ n[𝒜]≥ 1-ϵ a
set Ã with the following properties:

    P^⊗ n[Ã]≥ 1-O(n^-1/2),    
    	Q^⊗ n[Ã]≤ e^O(√(n))
    	Q^⊗ n[𝒜].

But Lemma <ref> shows such an operation cannot exist. Indeed, let
𝒜 be a test with P^⊗ n[𝒜]=1-ϵ and
ln Q^⊗ n[𝒜]≤ -nD(PQ) + O(√(n)) as in
Lemma <ref>. Then by Lemma <ref>, any set
Ã such that P^⊗ n[Ã]≥
1-O(n^-1/2) satisfies

    Q^⊗ n[Ã] ≥
    	e^-nD(PQ)+C√(nln n)≥
    	e^C√(nln n)+O(√(n))Q^⊗ n[𝒜],

which contradicts the desired property of the mapping
𝒜↦Ã. The same argument shows
that converses obtained from the data processing inequality can
attain at best a second-order term of order no smaller than
∼√(nlog n).

We conclude this appendix with the proof of Lemma <ref>.


By the Neyman-Pearson lemma, among all sets Ã such that
P^⊗ n[Ã]≥ 1-n^-δ, the probability
Q^⊗ n[Ã] is minimized by

    Ã = {y^n∈𝒴^n:
    	_P^⊗ nQ^⊗ n(y^n) ≥
    	nD(PQ) - γ},

where γ is chosen so that P^⊗ n[Ã]=
1-n^-δ. It therefore suffices to prove a suitable lower bound on
Q^⊗ n[Ã] for this particular choice of
Ã.

We will twice use the classical Kolmogorov lower bound for the tail
of sums of independent random variables <cit.>.
First, this bound implies

    P^⊗ n[_P^⊗ nQ^⊗ n≥
    	nD(PQ)-√(δ V(PQ))√(nln n)]
    	≤ 1-n^-δ

for n sufficiently large (depending on
δ,V(PQ),lndP/dQ_∞), where
V(PQ):=Var_P(lndP/dQ). This shows that we must have
γ≥γ_n := √(δ V(PQ))√(nln n).

On the other hand, we can now estimate

    Q^⊗ n[Ã]    =
    	P^⊗ n(e^-_P^⊗ nQ^⊗ n
    	1_{_P^⊗ nQ^⊗ n≥
            nD(PQ)-γ})
    	
       ≥
    	e^-nD(PQ)+√(δ V(PQ)/4)√(nln n)×
           
    	P^⊗ n[nD(PQ)-12γ_n ≥_P^⊗ nQ^⊗ n≥ nD(PQ)-γ].

But applying again (<ref>), we find that

    P^⊗ n[nD(PQ)-12γ_n ≥_P^⊗ nQ^⊗ n≥ nD(PQ)-γ]
       ≥
    	1-n^-δ
    	- P^⊗ n[
    	_P^⊗ nQ^⊗ n≥ nD(PQ)-12γ_n]
    	≥
    	n^-δ/4-n^-δ.

Consequently ln Q^⊗ n[Ã]
≥ -nD(PQ) + √(δ V(PQ)/4)√(nln n) + O(ln n).





§ BRASCAMP-LIEB DIVERGENCE: AUXILIARY RESULTS







 §.§ Proof of (<ref>) in the discrete case


The aim of this section is to prove the following result.


Let |𝒳|<∞, Q_X be a probability measure on 
𝒳, ν be a probability measure on 𝒴,
and Q_Y|X be a random transformation.
Define

    β_X     := 1/min_x Q_X(x), 
    α_Y     :=
    	dQ_Y/dν_∞.

Then for every δ∈ (0,1) and 
n>3β_Xln|𝒳|/δ,
we may choose a set 𝒞_n⊆𝒳^n with
Q_X^⊗ n[𝒞_n]≥ 1-δ such that 

    d(μ_n,Q_Y|X^⊗ n,ν^⊗ n,c)
    	
           ≤
    	n  d^⋆(Q_X,Q_Y|X,ν,c)
    	+ln (α_Y^cβ_X^c+1)
    	√(3nβ_Xln|𝒳|/δ)

for every c>0, where we defined μ_n:=Q_X^⊗ n|_𝒞_n. 


Let us fix in the sequel (Q_X,Q_Y|X,ν) and c>0, and define

    ϕ(P_X) :=
    	 d^⋆(P_X,Q_Y|X,ν,c)

for any P_X≪ Q_X.
The idea behind the proof Theorem <ref> is roughly as follows. 
Using the chain rule of relative entropy, we will show that d(μ_n,Q_Y|X^⊗ n,ν^⊗ n,c) can be bounded by
a quantity of the form nϕ(P_X), where P_X is a mixture of empirical 
measures of sequences in the support of μ_n. 
Thus, if we choose 𝒞_n to be the set of sequences with 
empirical measure close to Q_X, then Q_X^⊗ 
n[𝒞_n] will be large by the law of large numbers and 
ϕ(P_X)≈ϕ(Q_X)= d^⋆(Q_X,Q_Y|X,ν,c),
completing the proof.

To make these ideas precise, we require quantitative forms of the 
continuity of ϕ and of the law of large numbers. The former is 
provided by the following lemma. Here we adopt the same notations as
in Theorem <ref>.


If P_X≤ (1+ϵ)Q_X for some ϵ∈ [0,1), then

    ϕ(P_X)≤ϕ(Q_X)+
    	ϵln(β_X^c+1α_Y^c).




Let P_X be as in the statement, and let P_U|X be a maximizer for 
(<ref>) (we assume its existence for notational simplicity only;
if a maximizer does not exist, the argument is readily adapted to work
with near-maximizers). We now modify this distribution by allowing U to 
take an additional value as follows: let
𝒰̃=𝒰∪{⋆},
𝒳̃=𝒳, and define
P_ŨX̃ by

    P_Ũ   :=1/1+ϵP_U+ϵ/1+ϵδ_⋆;
    
    
    	P_X̃|Ũ=u   :=P_X|U=u,  ∀ u∈𝒰;
    
    
    	P_X̃|Ũ=⋆   :=
    	1+ϵ/ϵ(Q_X-1/1+ϵP_X)

where δ_⋆ is a point mass on ⋆.
Observe that P_X̃=Q_X,

    D(P_X̃|ŨQ_X|P_Ũ)
    	   =1/1+ϵD(P_X|UQ_X|P_U)
    
         
    	+ϵ/1+ϵD
    	(.1+ϵ/ϵQ_X-1/ϵP_X
    	Q_X)
    
       ≤ D(P_X|UQ_X|P_U) + ϵlnβ_X

where we used D(PQ_X)≤lnβ_X for every probability measure 
P, and

    cD(P_Ỹ|Ũν|P_Ũ)
    	   =c/1+ϵD(P_Y|Uν|P_U)
    
         +cϵ/1+ϵD
    	(.1+ϵ/ϵQ_Y-1/ϵP_Y
    	ν) 
       ≥
    	cD(P_Y|Uν|P_U) -
    	cϵln(β_Xα_Y),

where we used 1/1+ϵ≥ 1-ϵ and

    D(P_Y|Uν|P_U)
    	   =
    	D(P_Y|UQ_Y|P_U)
    	+ 
    	P_Y(lndQ_Ydν)
    	
       ≤ 
    	D(P_X|UQ_X|P_U)
    	+P_Y(lndQ_Ydν)
    	
       ≤ln(β_Xα_Y),

where (<ref>) follows from the data processing inequality and (<ref>) follows since D(P_X|UQ_X|P_U)≤lnβ_X. 
The proof is concluded by subtracting 
(<ref>) from (<ref>).


As a quantitative form of the law of large numbers, we will use the 
following standard result (see, e.g., <cit.>).



Assume that X_1,…,X_n are i.i.d. Ber(p).
Then for any ϵ∈ (0,∞)

    ℙ[∑_i=1^nX_i≥ (1+ϵ)np]
    	≤ e^-1/3min{ϵ^2,ϵ}np.



We can now conclude the proof of Theorem <ref>.


We denote by P_X^n the empirical measure of X^n∼ 
Q_X^⊗ n. Let n>3β_Xln|𝒳|/δ and 
define

    ϵ_n    :=
    	√(3β_X/nln|𝒳|/δ)∈
    	(0,1),
    
    𝒞_n    :={x^nP̂_x^n≤ (1+ϵ_n)Q_X}.

As for each x∈𝒳

    ℙ[P_X^n(x)> (1+ϵ_n)Q_X(x)]
    	≤
    	e^-n/3Q_X(x)ϵ_n^2≤δ/|𝒳|

by Lemma <ref>, it follows by the union bound that
Q_X^⊗ n[𝒞_n]≥ 1-δ.

Now consider any probability measure P_X^n≪μ_n:=Q_X^⊗ 
n|_𝒞_n. Then we can estimate, following essentially
<cit.>,

    cD(P_Y^nν^⊗ n)-D(P_X^nμ_n)
    
       =
    	cD(P_Y^nν^⊗ n)-D(P_X^nQ_X^⊗ n)
    
       =
    	c∑_i=1^nD(P_Y_i|Y^i-1ν|P_Y^i-1)
    	-∑_i=1^nD(P_X_i|X^i-1Q_X|P_X^i-1)
    
       ≤
    	c∑_i=1^nD(P_Y_i|X^i-1ν|P_X^i-1)
    	-∑_i=1^nD(P_X_i|X^i-1Q_X|P_X^i-1)
    
       =n[c D(P_Y_I|IX^I-1ν|P_IX^I-1)
    	-D(P_X_I|IX^I-1Q_X|P_IX^I-1)]
    
       ≤
    	nϕ(P_X_I).

(<ref>) follows from the fact that P_X^n is supported on
𝒞_n; (<ref>) is the chain rule of relative entropy;
(<ref>) follows from the convexity of relative entropy since 
Y_i-X^i-1-Y^i-1 under P_X^nY^n; in (<ref>) we defined I to 
be a random variable uniformly distributed on {1,…,n} and 
independent of X^n,Y^n; and in (<ref>) ϕ is defined in 
(<ref>). But note that P_X_I = P_X^n(P̂_X^n)≤ 
(1+ϵ_n)Q_X as P_X^n is supported on 𝒞_n.
Thus, (<ref>), Lemma <ref> and (<ref>) yield

    d(μ_n,Q_Y|X^⊗ n,ν^⊗ n,c)
    	   =
    	sup_P_X^n≪μ_n{cD(P_Y^nν^⊗ n)-D(P_X^nμ_n)}
       ≤
    	n d^⋆(Q_X,Q_Y|X,ν,c) +
    	ln(β_X^c+1α_Y^c)nϵ_n,

and the proof is complete.





 §.§ Proof of (<ref>) in the Gaussian case



We now prove the following Gaussian analogue of Theorem <ref>.


Let Q_X=𝒩(0,σ^2), let Q_Y|X=x=𝒩(x,1), and 
let ν be the Lebesgue measure on ℝ.
Then for any δ∈(0,1) and n≥ 20ln2/δ, we may 
choose a set 𝒞_n⊆ℝ^n with
Q_X^⊗ n[𝒞_n]≥ 1-δ such that

    d(μ_n,Q_Y|X^⊗ n,ν^⊗ n,c)≤
    	n d^⋆(Q_X,Q_Y|X,ν,c)
    	+√(6nln2/δ)

for any c>0, where we defined μ_n:=Q_X^⊗ n|_𝒞_n.


In the Gaussian case, the choice of typical set 𝒞_n is rather 
simple: it is a spherical shell of radius ∼√(n) and width 
O(1). Controlling the probability of such a spherical shell is a 
standard exercise (cf. <cit.>).



For X^n∼𝒩(0,𝐈_n)
and any t>0

    ℙ[|X^n^2-n|≥ 2√(nt)+2t]≤ 
    	2e^-t.



We now turn to the proof of Theorem <ref>.


Define

    A    := √(6ln2/δ),
    𝒞_n    :=
    	{x^n: n-A√(n)≤1σ^2x^n^2 ≤ 
    	n+A√(n)}.

Then we have Q_X^n[𝒞_n]≥ 1-δ for
n≥ 20ln2/δ by Lemma <ref>.

We proceed similarly to the proof of Theorem <ref> 
(following essentially <cit.>).
Consider any probability measure 
P_X^n≪μ_n:=Q_X^⊗ n|_𝒞_n. Then

    cD(P_Y^nν^⊗ n) - D(P_X^nμ_n) 
       = cD(P_Y^nν^⊗ n) - D(P_X^nQ_X^⊗ n) 
       = cD(P_Y^nν^⊗ n) - D(P_X^nν^⊗ n)
    		+ P_X^n(lndQ_X^⊗ ndν^⊗ n) 
       ≤ h(P_X^n) - ch(P_Y^n) 
    		- nh(Q_X)
    		+ 12A√(n),

where in (<ref>) we used that P_X^n is supported on 
𝒞_n; (<ref>) follows from the definition of relative
entropy; and (<ref>) follows by substituting the explicit form of the 
Gaussian density dQ_X/dν and using the definition of 
𝒞_n.

We now proceed to estimate using the chain rule

    h(P_X^n) - ch(P_Y^n) 
       =∑_i=1^n {h(X_i|X^i-1) - ch(Y_i|Y^i-1)}
       ≤∑_i=1^n {h(X_i|X^i-1) - ch(Y_i|X^i-1)}
        = n{h(X_I|IX^I-1) - ch(Y_I|IX^I-1)}
       ≤ nF((1+A√(n))σ^2),

where in (<ref>) we used concavity of differential entropy;
in (<ref>) we defined I to be uniformly distributed on 
{1,…,n} and independent of everything else; and in
(<ref>) we used that Var(X_I)≤ 
(1+A√(n))σ^2
by the definition of 𝒞_n, with

    F(M) := sup_P_UXVar(X)≤ M{h(X|U)-c h(Y|U)}

(this quantity plays the role of ϕ(P_X) in the present setting).
But note that by the scaling property of the differential entropy, we 
readily obtain

    nF((1+A√(n))σ^2) =
    	nF(σ^2) + 1-c2nln(1+A√(n))
    	≤ 
    	nF(σ^2)+
    	12A√(n).

Combining (<ref>), (<ref>), and (<ref>), we have shown

    d(μ_n,Q_Y|X^⊗ n,ν^⊗ n,c)
    	   =
    	sup_P_X^n≪μ_n{
    	cD(P_Y^nν^⊗ n) - D(P_X^nμ_n)}
       ≤
    	nF(σ^2) - nh(Q_X) + A√(n).

To conclude the proof, it remains to show that

    F(σ^2) - h(Q_X) =
    	 d^⋆(Q_X,Q_Y|X,ν,c).

To this end, we note that arguing as in (<ref>), we may
write Definition <ref> as

    d^⋆(Q_X,Q_Y|X,ν,c) =
    	sup_P_UX P_X=Q_X{h(X|U)-c h(Y|U)} - h(Q_X).

Thus, the inequality ≥ in (<ref>)
is immediate from the definition (<ref>). For the converse
direction we require the fact, proved in <cit.>, that 
for Gaussian channels the supremum in (<ref>) is achieved for
P_UX such that U=0 and X is Gaussian. In particular, 
F(σ^2) = h(X)-ch(Y) with X∼𝒩(0,a^2) for some
a≤σ. Thus, choosing P_UX in (<ref>) 
so that X=U+Z with Z∼𝒩(0,a^2), 
U∼𝒩(0,σ^2-a^2), and U,Z independent yields
≤ in (<ref>).




abbrv


