<span><span> First and Second Order Asymptotics in Covert Communication with </span></span>

<span><span> We study <span>the first- and </span> second-order asymptotics of covert communication <span>with </span> over binary-input for three different metrics of covertness. When covertness is measured in terms of the relative entropy between the channel output distributions induced with and without communication, we characterize the exact second-order asymptotics of the number of bits that can be reliably transmitted with a probability of error less than $\epsilon$ and a relative entropy less than $\delta$. When covertness is measured in terms of the variational distance between the channel output distributions or in terms of the probability of missed detection for fixed probability of false alarm, we establish bounds on the second-order asymptotics. <span>For all three metrics, we show that achieves the optimal first-order asymptotics among all codes; for relative entropy, we show that also achieves the optimal second-order asymptotics among all constant composition codes.</span> The main conceptual contribution of this paper is to clarify how the choice of a covertness metric impacts the information-theoretic limits of the number of covert and reliable bits. The main technical contribution underlying our results is a detailed analysis of the probability of existence of a code satisfying the reliability and covertness criteria.</span></span>

Introduction {#sec:introduction}
============

While most information-theoretic security works to date have revolved around the issues of confidentiality and authentication @Bloch2011 [@InfoTheoreticSec; @Jorswieck2015], the growing concern around mass communication surveillance programs has reignited interest in investigating the covertness of communications, also known as . In problems, the objective is to hide the presence of communication and not necessarily to prevent information leakage about the messages transmitted. Following the analysis of with space-time codes @Hero2003, recent works have established the information-theoretic limits of covert communications over noisy channel @Bash2013 [@Korzhik2005]. In particular, building upon concepts from steganography @Cachin2004 [@Korzhik2005], @Bash2013 has proved the existence of a "square-root law" for covert communication, which essentially states that no more than $O(\sqrt{n})$ bits can be communicated covertly over $n$ channel uses of a memoryless channel.

The square-root law of covert communication has been refined in several follow-up works @Che2013; in particular, the information-theoretic limits are now known for classical discrete and Gaussian memoryless channels @Bloch2016a [@Wang2016b], classical-quantum channels @Wang2016c [@Sheikholeslami2016], and multiple access channels @Arumugam2016, when covertness is measured in terms of the relative entropy between the channel output distributions induced with and without communication. Note that the choice of relative entropy as a metric for covertness is guided in part by the natural connection between relative entropy and information-theoretic metrics, such as entropy and mutual information, which have been largely explored in the context of information-theoretic security @Hou2014.

The contribution of the present paper is twofold. First, as an attempt to develop operational characterizations of covertness, we study the information-theoretic limits of covert communication for alternative metrics, including variational distance, and probability of missed detection. Second, motivated by the likely time-limited nature of covert communications, we make a first step towards a finite transmission length analysis and extend the first-order analysis of information-theoretic limits to second-order asymptotics. The specific results developed in the present paper focus on binary-input to simplify analytical expressions and are the following.

-   We characterize the exact second-order asymptotics of the maximum number of reliable and covert bits that can be transmitted <span><span> using constant composition codes</span></span> with average error probability $\epsilon$ and *relative entropy* $\delta$ between channel output distributions with and without communication (Theorem \[th:main\_result\_d\]); this corrects an unfortunate error in the conference version @Bloch2016, in which we claimed erroneous second-order asymptotics for arbitrary codes. <span><span> This result confirms the first-order optimality of over all codes @Bloch2016b and the second-order optimality of among all constant composition codes.</span></span>

-   <span><span> We characterize bounds for the second-order asymptotics of the maximum number of reliable and covert bits that can be transmitted <span><span> using constant composition codes</span></span> with average error probability $\epsilon$ and *variational distance* $\delta$ between channel output distributions with and without communication (Theorem \[th:main\_result\_tv\]). This results shows the first-order optimality of among all codes.</span></span>

-   <span><span> Finally, we characterize bounds for the second-order asymptotics of the maximum number of reliable and covert bits that can be transmitted <span><span> using constant composition codes</span></span> with average error probability $\epsilon$ and probability of missed detection $1-\alpha-\delta$ when $\alpha$ is the adversary's probability of false alarm (Theorem \[th:main\_result\_beta\]). This results shows again the first-order optimality of among all codes.</span></span>

<span><span> The restriction of our results to constant composition codes might seem a strong limitation, but the motivation is twofold. First, as discussed in Appendix \[sec:effect-aver-prob\], there is no strong converse for average probability of error when arbitrary codeword weights are allowed. Second, our achievability proofs rely on , which may be viewed as a highly structured subset of constant composition codes amenable to practical code design @Bloch2016b. In that regard, our results have some operational relevance and provide useful benchmarks of performance.</span></span>

The second-order asymptotics obtained with a relative entropy metric for covertness are what could have been expected by extrapolating the results of channel coding in the finite length regime @Polyanskiy2010 to the first-order asymptotics of covert communication @Bloch2016a [@Wang2016b]; however, the proof requires specific techniques beyond those used to study the first-order asymptotics of covert communications <span><span> and second-order asymptotics of classical communication</span></span>. First, as already mentioned, the achievability proof relies on codes @Bloch2016b instead of random codes. Second, <span><span> unlike the analysis of the second-order asymptotics of reliable and secure communications @Polyanskiy2010 [@Yang2016], we have to deal here with parameters capturing reliability and covertness, with the latter appearing in the first-order asymptotics; more specifically,</span></span> the optimal coding scheme identified in @Bloch2016a exploits a code with a bin structure, in which each bin forms a reliability code for the legitimate channel indexed by the secret key, while the overall code forms a resolvability code for the adversary's channel. To guarantee <span><span> a</span></span> positive probability of existence of a code with the desired characteristics, we resort to concentration of measure inequalities such as McDiarmid's Inequality and carefully analyze the probability of error. We point out that our current results only identify the second-order asymptotics for the number of transmitted message bits and do not characterize the second-order asymptotics for the number of key bits.

The remainder of the paper is organized as follows. In Section \[sec:main-result\], we formally introduce the model of covert communication and state our main results. In Section \[sec:covert-comm-results\], we develop a series of general results that form the basis of our analysis of covert communication. In Section \[sec:covert-comm-with-kl\], Section \[sec:secon-order-covert-tv\], and Section \[sec:covert-comm-missed-detection\], we exploit the results of Section \[sec:covert-comm-results\] to study a relative entropy metric, variational distance metric, and probability of missed-detection metric for covertness, respectively. In Section \[sec:conclusion\], we conclude the paper with a discussion of possible further extensions and improvements.

Model and main results {#sec:main-result}
======================

Notation {#sec:notation}
--------

Throughout the paper, $\log$ and $\exp$ should be understood in base $e$. Moreover, random variables are denoted with upper case letters, e.g. $X$, while their realization are denoted with lower case letters, e.g., $x$. The distribution of a random variable such as $X$ is denoted by $P_X$. Calligraphic letters are used for sets, e.g., $\mathcal{X}$, and boldface fonts are used for vectors e.g., $\textbf{x}$. For two integers $a$ and $b$, if $a{\leqslant}b$, we define ${\ensuremath{\llbracket{a},{b}\rrbracket}}{\ensuremath{\triangleq}}\{a, a+1, \cdots, b-1, b\}$; otherwise ${\ensuremath{\llbracket{a},{b}\rrbracket}} {\ensuremath{\triangleq}}\emptyset$. For any distribution $P$ over $\mathcal{X}$, $P^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}$ denotes the product distribution over $\mathcal{X}^n$, i.e., $P^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}(\textbf{x}) {\ensuremath{\triangleq}}\prod_{i=1}^n P(x_i)$. For two distributions $P$ and $Q$ over the same set $\mathcal{X}$, we define the quantities $$\begin{aligned}
{{{\mathbb{D}}\!\left({P\VertQ}\right)}} &{\ensuremath{\triangleq}}\sum_x P(x) \log \frac{P(x)}{Q(x)} \quad\text{(relative entropy)}\\
{{{\mathbb{V}}\!\left(P, Q\right)}} &{\ensuremath{\triangleq}}\frac{1}{2}\sum_x |P(x) - Q(x)| \quad\text{(variational distance)}\\
\chi_2(P||Q) &{\ensuremath{\triangleq}}\sum_{x} \frac{(P(x)-Q(x))^2}{Q(x)}\quad\text{(chi-squared distance)}\\
\beta_{\alpha}(P, Q) &{\ensuremath{\triangleq}}\inf_{T \subset \mathcal{X}: P({{\color{black} {{\mathcal{X}}}\setminus}}T) {\leqslant}\alpha} Q(T) \quad\text{(optimal probability of missed detection)}.\end{aligned}$$ The notation $P\ll Q$ means that $P$ is absolutely continuous $Q$, i.e., if $Q(x)=0$ for some $x\in \mathcal{X}$, then $P(x) = 0$. A $(\mathcal{X}, W_{Y|X}, \mathcal{Y})$ consists of a finite input alphabet $\mathcal{X}$, a finite output alphabet $\mathcal{Y}$, and a transition probability $W_{Y|X}$ where $W_{Y|X}(y|x)$ indicates the probability of obtaining $y$ at the output given that $x$ is transmitted at the input. For a $(\mathcal{X}, W_{Y|X}, \mathcal{Y})$ and two distributions $P_X$ and $Q_Y$ on $\mathcal{X}$ and $\mathcal{Y}$, we define $$\begin{aligned}
\label{eq:I_def}
P_Y(y) &{\ensuremath{\triangleq}}\sum_x P_X(x) W_{Y|X}(y|x),\\
I(P_X, W_{Y|X}) &{\ensuremath{\triangleq}}\sum_{x, y}  P_X(x) W_{Y|X}(y|x) \log \frac{W_{Y|X}(y|x)}{P_Y(y)},\end{aligned}$$ and for any $\gamma$, $$\begin{aligned}
F_{XY|Q_Y}(\gamma) &{\ensuremath{\triangleq}}{{\mathbb{P}_{W_{Y|X}P_X}}{\left(\log \frac{W_{Y|X}(Y|X)}{Q_Y(Y) }{\leqslant}\gamma\right)}} = \sum_{x, y} P_X(x) W_{Y|X} (y|x) {\ensuremath{\mathds{1}\!\left\{\log \frac{W_{Y|X}(y|x)}{Q_Y(y) }{\leqslant}\gamma\right\}}},\\
F_{XY}(\gamma) &{\ensuremath{\triangleq}}F_{XY|P_Y}(\gamma),\\
\overline{F}_{XY}(\gamma) &{\ensuremath{\triangleq}}1-F_{XY}(\gamma).\end{aligned}$$ Moreover, given codewords $\{x_i\}_{i=1}^M \in {{\mathcal{X}}}^M$ and a uniform random variable $W\in{\ensuremath{\llbracket{1},{M}\rrbracket}}$, $\widehat{P}_{WXY}$ denotes the joint distribution induced on $(W, X, Y)$, i.e., $$\begin{aligned}
\widehat{P}_{WXY}(w, x, y) {\ensuremath{\triangleq}}\frac{1}{M}{\ensuremath{\mathds{1}\!\left\{x_w = x\right\}}} W_{Y|X}(y|x).\end{aligned}$$ For any discrete random variable $A$, let $\mu_A {\ensuremath{\triangleq}}\min_{a: {{\mathbb{P}_{}}{\left(A=a\right)}} > 0} {{\mathbb{P}_{}}{\left(A=a\right)}}$. <span><span> For a real number $x$, we also define the $Q$-function $Q(x) {\ensuremath{\triangleq}}\int_{x}^\infty \frac{1}{\sqrt{2\pi}} e^{-\frac{x^2}{2}} \text{d}x$ and $[x]^+ {\ensuremath{\triangleq}}\max(0, x)$. Moreover, for sequences $\{a_n\}$, $\{b_n\}$, and $\{c_n\}$, we have $a_n = b_n + O(c_n)$ if and only if there exists a constant $K$ independent of $n$ such that $|a_n - b_n| {\leqslant}K c_n$ for all $n$. </span></span> Finally, for $\textbf{x}\in\mathcal\{0,1\}^n$, ${\ensuremath{\mbox{wt}(\textbf{x})}}$ denotes the weight of $\mathbf{x}$ defined as $|\{i\in{\ensuremath{\llbracket{1},{n}\rrbracket}}:x_i=1\}|$.

Model and main results {#sec:model-main-results}
----------------------

We consider the situation illustrated in Fig. \[fig:model\], in which a legitimate transmitter communicates with a legitimate receiver over a $({{\mathcal{X}}},W_{Y|X},{{\mathcal{Y}}})$, in the presence of an adversary who observes communication through another $({{\mathcal{X}}},W_{Z|X},{{\mathcal{Z}}})$, where $\mathcal{X}$, $\mathcal{Y}$ and $\mathcal{Z}$ are assumed to be finite. Furthermore, in order to simplify the analytical expressions of the results, we assume in the sequel that ${{\mathcal{X}}}=\{0,1\}$, where $0$ is an "innocent symbol" corresponding to the expected input of the channel if no communication were taking place. The extension beyond binary-inputs is briefly outlined in Section \[sec:conclusion\]. We also denote the output distribution induced by each input symbol by $$\begin{aligned}
P_0{\ensuremath{\triangleq}}W_{Y|X=0},&\quad   P_1{\ensuremath{\triangleq}}W_{Y|X=1},\displaybreak[0]\\
Q_0{\ensuremath{\triangleq}}W_{Z|X=0},&\quad Q_1{\ensuremath{\triangleq}}W_{Z|X=1},\end{aligned}$$ where it is assumed that $Q_1 \ll Q_0$, $P_1 \ll P_0$ and $Q_1\neq Q_0$. These assumptions are <span><span> necessary for our results to hold. In fact, without $Q_1 \ll Q_0$, covert communication is impossible as some input symbols detect the use of the non-innocent symbol with probability one. At the other extreme, if $Q_1 = Q_0$ then no detector can distinguish the use of innocent and non-innocent symbols so that the problem reduces to classical communication. Finally, without $P_1\ll P_0$, Alice and Bob have an unfair advantage that allows them to exchange $\omega(\sqrt{n})$ bits covertly @Bloch2016a [Theorem 7].</span></span>

![Model of covert communications over noisy channels<span data-label="fig:model"></span>](model-ieee){width="0.6\linewidth"}

The objective is for the transmitter to communicate a uniformly distributed message $W\in{\ensuremath{\llbracket{1},{M}\rrbracket}}$ with a small probability of error while ensuring low probability of detection from the adversary. The communication may be assisted by a uniformly distributed shared secret key $S\in{\ensuremath{\llbracket{1},{K}\rrbracket}}$. A formal description of a code is as follows.

\[def:covert\_code\] A code of length $n$ consists of an encoder/decoder pair $$\begin{aligned}
f:{\ensuremath{\llbracket{1},{K}\rrbracket}}\times{\ensuremath{\llbracket{1},{M}\rrbracket}}\rightarrow{{\mathcal{X}}}^n\text{ and }\phi:{{\mathcal{Y}}}^n\times{\ensuremath{\llbracket{1},{K}\rrbracket}}\rightarrow{\ensuremath{\llbracket{1},{M}\rrbracket}},\end{aligned}$$ which induces the distribution $\widehat{P}_{\textbf{Z}}$ at the adversary's channel output, defined by $$\begin{aligned}
\forall \textbf{z},\quad\widehat{P}_{\textbf{Z}}(\textbf{z}){\ensuremath{\triangleq}}\sum_{s=1}^K\sum_{w=1}^M \frac{1}{MK}W_{Z|X}^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}(\mathbf{z}|f(s,w)).\end{aligned}$$ A code is $\epsilon$-reliable, if the pair $(f,\phi)$ is such that $$\begin{aligned}
P_{\text{err}}^*{\ensuremath{\triangleq}}\max_{s\in{\ensuremath{\llbracket{1},{K}\rrbracket}}}{{\mathbb{P}_{}}{\left(\phi(\mathbf{Y},s)\neq W|S=s\right)}}{\leqslant}\epsilon.\label{eq:prob_error}\end{aligned}$$ <span><span> A code has a "constant composition" if for all $(s,w), (s', w')\in{\ensuremath{\llbracket{1},{K}\rrbracket}} \times {\ensuremath{\llbracket{1},{M}\rrbracket}}$, we have ${\ensuremath{\mbox{wt}(f(s, w))}} = {\ensuremath{\mbox{wt}(f(s', w'))}}$.</span></span> Moreover, an $\epsilon$-reliable code defined by $(f,\phi)$ is

-   an $(M,K,n,\epsilon,\delta)_D$ code, if it satisfies $$\begin{aligned}
    {{{\mathbb{D}}\!\left({\widehat{P}_{\textbf{Z}}\VertQ_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
                 {\raisebox{1pt}{$\otimes$}}
                 {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
                 {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}}\right)}}{\leqslant}\delta;\label{eq:covert_with_D}\end{aligned}$$

-   an $(M,K,n,\epsilon,\delta)_V$ code, if it satisfies $$\begin{aligned}
    {{{\mathbb{V}}\!\left(\widehat{P}_{\textbf{Z}},Q_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
                 {\raisebox{1pt}{$\otimes$}}
                 {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
                 {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}\right)}}{\leqslant}\delta;\label{eq:covert_with_V}\end{aligned}$$

-   an $(M,K,n,\epsilon,\delta, \alpha)_\beta$ code, if if it satisfies $$\begin{aligned}
    \beta_\alpha(Q_0^{{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
                 {\raisebox{1pt}{$\otimes$}}
                 {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
                 {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}}, \widehat{P}_{\textbf{Z}}) {\geqslant}1 - \alpha - \delta.\label{eq:covert_with_beta}\end{aligned}$$

The maximum number of messages that can be transmitted by an $(M,K,n,\epsilon,\delta)_D$, $(M,K,n,\epsilon,\delta)_V$, and $(M,K,n,\epsilon,\delta, \alpha)_\beta$ code is denoted by $M^*_D(n, \epsilon, \delta)$, $M^*_V(n, \epsilon, \delta)$, and $M^*_\beta(n, \epsilon, \delta, \alpha)$, respectively. <span><span> The maximum number of messages that can be transmitted by an $(M,K,n,\epsilon,\delta)_D$, $(M,K,n,\epsilon,\delta)_V$, and $(M,K,n,\epsilon,\delta, \alpha)_\beta$ constant composition code is denoted by $M^\text{cc}_D(n, \epsilon, \delta)$, $M^\text{cc}_V(n, \epsilon, \delta)$, and $M^\text{cc}_\beta(n, \epsilon, \delta, \alpha)$, respectively</span></span>

We point out that the definition of the probability of error in (\[eq:prob\_error\]) differs from previous studies @Wang2016b [@Bloch2016a]; we ask that the average probability of error be small for *any* choice of the key $S$. This more stringent condition captures a more practical requirement, but our converse proof for constant composition codes carries over to the codes with average probability of error as defined in @Wang2016b [@Bloch2016a]. Also note that the three metrics for covertness in (\[eq:covert\_with\_D\])-(\[eq:covert\_with\_beta\]) have different operational meanings. When enforcing $\beta_\alpha(Q_0^{{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}}, \widehat{P}_{\textbf{Z}}) {\geqslant}1 - \alpha - \delta$ for a fixed probability of false alarm $\alpha$, one implicitly assumes that the adversary is known to optimize its detection at a specific point of its curve. In contrast, when enforcing ${{{\mathbb{V}}\!\left(\widehat{P}_{\textbf{Z}},Q_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}\right)}}{\leqslant}\delta$, since $\alpha+\beta_\alpha(Q_0^{{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}}, \widehat{P}_{\textbf{Z}}) {\geqslant}1-{{{\mathbb{V}}\!\left(\widehat{P}_{\textbf{Z}},Q_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}\right)}}$ for *any* probability of false alarm $\alpha$, one essentially wishes to enforce covertness irrespective of the exact operating point on the adversary's curve. Finally, since <span><span> ${{{\mathbb{V}}\!\left(\smash{\widehat{P}_{\textbf{Z}}},Q_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}\right)}}^2{\leqslant}\frac{1}{2}{{{{\mathbb{D}}\!\left({\widehat{P}_{\textbf{Z}}\VertQ_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}}\right)}}}$</span></span> by Pinsker's Inequality, the constraint ${{{\mathbb{D}}\!\left({\widehat{P}_{\textbf{Z}}\VertQ_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}}\right)}}{\leqslant}\delta$ is more stringent than when using variational distance, but otherwise has the same significance.[^2] The relations between the metrics for covertness immediately lead to the following ordering of the maximum number of covert bits.

<span><span> $$\begin{aligned}
  \label{eq:ordering}
  M^*_D(n, \epsilon, \delta) &{\leqslant}M^*_V(n, \epsilon, \sqrt{\frac{\delta}{2}}) {\leqslant}\min_{\alpha\in[0,1]}M^*_\beta(n, \epsilon, \sqrt{\frac{\delta}{2}}, \alpha),\\
 M^\text{cc}_D(n, \epsilon, \delta) &{\leqslant}M^\text{cc}_V(n, \epsilon, \sqrt{\frac{\delta}{2}}) {\leqslant}\min_{\alpha\in[0,1]}M^\text{cc}_\beta(n, \epsilon, \sqrt{\frac{\delta}{2}}, \alpha).\end{aligned}$$ </span></span>

Our main results in Theorem \[th:main\_result\_d\], Theorem \[th:main\_result\_tv\], and Theorem \[th:main\_result\_beta\] characterize the maximum number of reliable and covert bits defined above <span><span> for </span></span> as a function of the channel characteristics and the block length $n$. In all cases, the first and second terms behave as $\Theta\left(\smash{n^{\frac{1}{2}}}\right)$ and $\Theta\left(\smash{n^{\frac{1}{4}}}\right)$, respectively, as expected; nevertheless, the constant behind $\Theta(\cdot)$ is metric-specific.

\[th:main\_result\_d\] For $\epsilon \in ]0, 1[$ and $\delta>0$, we have $$\begin{aligned}
\log M^\text{cc}_D(n, \epsilon, \delta) = \sqrt{\frac{2\delta}{\chi_2(Q_1\|Q_0)}}D_Pn^{\frac{1}{2}}-\sqrt{\sqrt{\frac{2\delta}{\chi_2(Q_1\|Q_0)}}V_P}Q^{-1}(\epsilon)n^{\frac{1}{4}} + O(\log n),\end{aligned}$$ with $$\begin{aligned}
\label{eq:DVP_definition}
D_P {\ensuremath{\triangleq}}{{{\mathbb{D}}\!\left({P_1\VertP_0}\right)}}, &\quad
V_P {\ensuremath{\triangleq}}{{\text{\textnormal{Var}}{\left(\left.\log\frac{P_1(Y)}{P_0(Y)}\right|P_1\right)}}}.\end{aligned}$$ This optimal message length is obtained with a first-order optimal number of key bits $$\begin{aligned}
\log K = (1+\rho)\sqrt{\frac{2\delta}{\chi_2(Q_1\|Q_0)}}[D_Q-D_P]^+ n^{\frac{1}{2}},\end{aligned}$$ where $\rho>0$ can be arbitrarily small and $D_Q={{{\mathbb{D}}\!\left({Q_1\VertQ_0}\right)}}$. <span><span> In addition, $$\begin{aligned}
  \lim_{\epsilon\to 0}\lim_{n\rightarrow\infty}\frac{\log M_D^*(n,\epsilon,\delta)}{\sqrt{n}} =   \lim_{\epsilon\to 0}\lim_{n\rightarrow\infty}\frac{\log M_D^\text{cc}(n,\epsilon,\delta)}{\sqrt{n}} = \sqrt{\frac{2\delta}{\chi_2(Q_1\|Q_0)}}D_P.\end{aligned}$$ </span></span>

\[th:main\_result\_tv\] For $\epsilon \in ]0, 1[$ and $\delta\in ]0,1[$, let $\Gamma {\ensuremath{\triangleq}}Q{{\left(\frac{1-\delta}{2}\right)}}$. <span><span> If $Q_0 \ll Q_1$</span></span>, we have $$\begin{aligned}
\log M^\text{cc}_V(n, \epsilon, \delta) {\leqslant}\frac{2\Gamma D_P}{\sqrt{\chi_2(Q_1\|Q_0)}}n^{\frac{1}{2}}-\sqrt{\frac{2\Gamma V_P}{\sqrt{\chi_2(Q_1\|Q_0)}}}Q^{-1}(\epsilon)n^{\frac{1}{4}} + O(\log n),\end{aligned}$$ and $$\begin{aligned}
\log M^\text{cc}_V(n, \epsilon, \delta) {\geqslant}\frac{2\Gamma D_P}{\sqrt{\chi_2(Q_1\|Q_0)}}n^{\frac{1}{2}}-{{\left(\sqrt{\frac{2\Gamma V_P}{\sqrt{\chi_2(Q_1\|Q_0)}}}Q^{-1}(\epsilon) + \frac{2\sqrt{\pi} e^{\frac{\Gamma^2}{2}} D_P }{\sqrt{\Gamma}\chi_2(Q_1\|Q_0)^{\frac{1}{4}} }\right)}}n^{\frac{1}{4}} + O(\log n),\end{aligned}$$ where $D_P$ and $V_P$ are as in . This message length is obtained with a number of key bits $$\begin{aligned}
\log K = (1+\rho)\frac{2\Gamma D_P}{\sqrt{\chi_2(Q_1\|Q_0)}} [D_Q-D_P]^+ n^{\frac{1}{2}},\end{aligned}$$ where $\rho>0$ can be arbitrarily small. <span><span> In addition, $$\begin{aligned}
  \lim_{\epsilon\to 0}\lim_{n\rightarrow\infty}\frac{\log M_V^*(n,\epsilon,\delta)}{\sqrt{n}} =   \lim_{\epsilon\to 0}\lim_{n\rightarrow\infty}\frac{\log M_V^\text{cc}(n,\epsilon,\delta)}{\sqrt{n}} = \frac{2\Gamma D_P}{\sqrt{\chi_2(Q_1\|Q_0)}}.\end{aligned}$$ </span></span>

\[th:main\_result\_beta\] For $\epsilon \in ]0, 1[$, $\alpha\in]0,1[$, and $\delta\in ]0, 1-\alpha[$, let $\Lambda {\ensuremath{\triangleq}}Q^{-1}(1 - \alpha - \delta)$ and $\Upsilon {\ensuremath{\triangleq}}Q^{-1}(\alpha)$. <span><span> If $Q_0 \ll Q_1$</span></span>, we have $$\begin{aligned}
\log M^\text{cc}_\beta(n, \epsilon, \delta, \alpha) {\leqslant}\frac{(\Lambda + \Upsilon) D_P}{\sqrt{\chi_2(Q_1\|Q_0)}}n^{\frac{1}{2}}-\sqrt{\frac{(\Lambda + \Upsilon)V_P}{\sqrt{\chi_2(Q_1\|Q_0)}}}Q^{-1}(\epsilon)n^{\frac{1}{4}} + O(\log n),\end{aligned}$$ and $$\begin{aligned}
\log M^\text{cc}_\beta(n, \epsilon, \delta, \alpha) {\geqslant}\frac{(\Lambda + \Upsilon)D_P}{\sqrt{\chi_2(Q_1\|Q_0)}}n^{\frac{1}{2}}-{{\left(\sqrt{\frac{(\Lambda + \Upsilon) V_P}{\sqrt{\chi_2(Q_1\|Q_0)}}}Q^{-1}(\epsilon) + \frac{\sqrt{2\pi}{{\left(e^{\frac{\Gamma^2}{2}} + e^{\frac{\Upsilon^2}{2}}\right)}} D_P}{\sqrt{\Lambda +\Upsilon}\chi_2(Q_1\|Q_0)^{\frac{1}{4}}}\right)}} n^{\frac{1}{4}} + O(\log n).\end{aligned}$$ This message length is obtained with a number of key bits $$\begin{aligned}
\log K = (1+\rho)\frac{{{\left(\Lambda + \Upsilon\right)}} [D_Q-D_P]^+}{\sqrt{\chi_2(Q_1\|Q_0)}} n^{\frac{1}{2}},\end{aligned}$$ where $\rho>0$ can be arbitrarily small. <span><span> In addition, $$\begin{aligned}
  \lim_{\epsilon\to 0}\lim_{n\rightarrow\infty}\frac{\log M_\beta^*(n,\epsilon,\delta,\alpha)}{\sqrt{n}} =   \lim_{\epsilon\to 0}\lim_{n\rightarrow\infty}\frac{\log M_\beta^\text{cc}(n,\epsilon,\delta,\alpha)}{\sqrt{n}} = \frac{(\Lambda + \Upsilon)D_P}{\sqrt{\chi_2(Q_1\|Q_0)}}.\end{aligned}$$ </span></span>

<span><span> Note that Theorem \[th:main\_result\_tv\] and Theorem \[th:main\_result\_beta\] hold under the slightly stronger requirement $Q_0 \ll Q_1$. This is an artifact of our proof technique and can probably be removed. More importantly, the second order asymptotics in Theorem \[th:main\_result\_tv\] and Theorem \[th:main\_result\_beta\] are loose because the parameters $\Gamma$, $\Lambda$, and $\Upsilon$ may be very small. In particular, because of , Theorem \[th:main\_result\_d\] is often a tighter lower bound for lower values of $n$</span></span>

<span><span> We illustrate these different results with a simple numerical example. We consider the situation in which $({{\mathcal{X}}}, W_{Y|X}, {{\mathcal{Y}}})$ and $({{\mathcal{X}}}, W_{Z|X}, {{\mathcal{Z}}})$ are with cross-over probability $p_m=0.11$ and $p_w=0.45$, respectively, and $\epsilon=10^{-3}$, $\delta=10^{-2}$, and $\alpha=0.2$. Since the convergence to the asymptotic limit is slow ($\Theta(n^{-\frac{1}{4}}$), we use a log scale for the blocklength.</span></span> As shown in Fig. \[fig:illustration\], the choice of the covertness metric results in different number of bits, which of course raises the question of which number to settle on. We argue that $M^*_V(n, \epsilon, \delta)$ is the number to focus on since total variation distance satisfies two desirable properties: it is directly connected to the operation of the adversary, through the inequality $\alpha+\beta {\geqslant}1-{{{\mathbb{V}}\!\left(\widehat{P}_{\textbf{Z}},Q_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}\right)}}$, and it does not presume any knowledge about the exact operating point on the adversary's curve.

![Maximum number of covert and reliable bits as a function of blocklength. Both are with cross-over probability $p_m=0.11$ and $p_w=0.45$, respectively, and $\epsilon=10^{-3}$, $\delta=10^{-2}$, and $\alpha=0.2$. <span><span> The dotted horizontal lines indicate the optimal first-order asymptotics.</span></span><span data-label="fig:illustration"></span>](illustration-ieee){width="0.7\linewidth"}

Before we detail the achievability and converse proofs in the next sections, we provide here a high-level sketch of the proofs. Following @Bloch2016a, the coding scheme in the achievability proof consists of $MK$ randomly generated codewords $\mathbf{x}_{sw}$ with $s\in{\ensuremath{\llbracket{1},{K}\rrbracket}}$ and $w\in{\ensuremath{\llbracket{1},{M}\rrbracket}}$. The code is designed such that the following properties hold:

-   the codebook $\{\mathbf{x}_{sw}\}_{(s,w)\in{\ensuremath{\llbracket{1},{K}\rrbracket}}\times{\ensuremath{\llbracket{1},{M}\rrbracket}}}$ forms a resolvability code for the channel $({{\mathcal{X}}},W_{Z|X},{{\mathcal{Z}}})$ approximating $Q_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
                 {\raisebox{1pt}{$\otimes$}}
                 {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
                 {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}$;

-   for every $s\in{\ensuremath{\llbracket{1},{K}\rrbracket}}$, the sub-codebook $\{\mathbf{x}_{sw}\}_{w\in{\ensuremath{\llbracket{1},{M}\rrbracket}}}$ forms a reliability code for the channel $({{\mathcal{X}}},W_{Y|X},{{\mathcal{Y}}})$ with an average probability of error $\epsilon$.

The analysis does not follow from standard arguments for two reasons. First, if the codewords are generated according to an distribution, we do not obtain the optimal dispersion; instead, we resort to codes @Bloch2016b. Second, one cannot ensure (P2) by merely expurgating some of the sub-codebooks, since this expurgation may change the output distribution on ${{\mathcal{Z}}}^n$ induced by the code; we address this by carefully analyzing the probability of error and using concentration of measure results such as McDiarmid's Inequality. The converse proof adapts arguments from @Polyanskiy2010 to the case of covert communication.

Covert communications with generic covertness quasi-metric {#sec:covert-comm-results}
==========================================================

In this section, we develop results for a generic covertness metric, which will be specialized to the three metrics highlighted in Definition \[def:covert\_code\] in Section \[sec:covert-comm-with-kl\], Section \[sec:secon-order-covert-tv\], and Section \[sec:covert-comm-missed-detection\]. This organization allows us to handle separately the part of the analysis that depends solely on the code structure and not on the exact metric choice. Specifically, throughout this section, we consider an arbitrary *quasi-metric* $d$ measuring the distance between distributions. The quasi-metric $d$ does not necessarily possess the standard characteristics of a metric; however, we assume that it is non-negative and satisfies a modified triangle inequality, i.e.,

-   $\forall P, Q:\quad d(P, Q){\geqslant}0$

-   $\forall P, Q, R:\quad d(R, Q) {\leqslant}d(P, Q) + {{{\mathbb{D}}\!\left({R\VertP}\right)}}+\sqrt{{{{\mathbb{D}}\!\left({R\VertP}\right)}}}\max\left(1,\log \frac{1}{\min_x Q(x)}\right)$.

This modified version of the triangle inequality is intimately linked to the relative entropy, and is used mainly for convenience; this will avoid repetitions when we study different metrics and should not be given much operational significance. In brief, we will use the modified triangle inequality as follows: we will pick an appropriate distribution $P$ such that $d(R,Q)$ is essentially on the order of $d(P,Q)$, which depends on $d$, while the remaining terms that depend on relative entropy will be made negligible. We define an $(M, K, n, \epsilon, \delta)_d$ covert code and $M^*_d(n, \epsilon, \delta)$ for a covert communication channel $({{\mathcal{X}}}, W_{Y|X}, W_{Z|X}, {{\mathcal{Y}}}, {{\mathcal{Z}}})$ as in Definition \[def:covert\_code\].

<span><span> Our proof for generic covertness quasi-metrics is organized as follows. In Section \[lm:ch\_coding\], we start be developing one-shot results for random codes to bound the average probability of error (Lemma \[lm:ch\_coding\]) and the approximation of output statistics as measured with the quasi-metric (Lemma \[lm:ch\_resolve\_p\] and Lemma \[lm:ch\_resolve\_e\]). The expurgation of the code requires some care because of the interplay between reliability and channel resolvability (Lemma \[thm:one-shot-covert-cm\]). In Section \[sec:asympt-results-cover\], we specialize the one-shot results to obtain an achievability result for random codes with large-enough blocklength (Theorem \[thm:general\_achv\]). In Section \[sec:distributions\], we refine the statement of Theorem \[thm:general\_achv\] for the specific random code ensemble consisting of codes. This requires the study of the specific quantities involved in the statement of Theorem \[thm:general\_achv\] (Lemma \[lm:F\_XY\_bound\], Lemma \[lm:expected\_ration\_ppm\], Lemma \[lm:F\_XZ\_bound\]). We also pave the way for our final results by developing bounds between the output distribution induced by a ensemble and the innocent distribution for relative entropy, variational distance, and probability of missed-detection (Lemma \[lm:div\_ppm\]). These bounds are fairly technical and rely on moment bounds (Lemma \[lm:A-moments\]). Finally, in Section \[sec:generic-converse\], we develop a general converse (Theorem \[thm:converse-general\]).</span></span>

One-shot achievability analysis
-------------------------------

We now develop one-shot random coding results for codes simultaneously ensuring channel reliability and channel resolvability. Given a $(\mathcal{X}, W_{Y|X}, \mathcal{Y})$ and a codebook with $M$ codewords $x_1, \cdots, x_M\in \mathcal{X}$[^3], our analysis of reliability is based on a threshold decoder @Polyanskiy2010 operating as follows. Given $\gamma>0$ and a distribution $Q_Y$ on $\mathcal{Y}$, and upon observing $y$, the decoder forms the estimate $\widehat{W}=w$ of the transmitted message $W$ if there exists a unique $w\in{\ensuremath{\llbracket{1},{M}\rrbracket}}$ such that $$\begin{aligned}
\label{eq:th-decoder}
\log \frac{W_{Y|X}(y|x_w)}{Q_Y(y)} > \gamma.\end{aligned}$$ If there is no $w$ satisfying , the decoder declares an error. It is known that the conditional probability of error when $W=w$ is upper bounded by $\epsilon_w^{(1)} + \epsilon_w^{(2)}$ where $$\begin{aligned}
\epsilon_w^{(1)} &{\ensuremath{\triangleq}}\sum_y W_{Y|X}(y|x_w) {\ensuremath{\mathds{1}\!\left\{\log \frac{W_{Y|X}(y|x_w)}{Q_Y(y)} {\leqslant}\gamma\right\}}},\\
\epsilon_w^{(2)} &{\ensuremath{\triangleq}}\sum_y W_{Y|X}(y|x_w) {\ensuremath{\mathds{1}\!\left\{\exists w'\neq w:\log \frac{W_{Y|X}(y|x_{w'})}{Q_Y(y)} > \gamma\right\}}}.\end{aligned}$$ Under random coding, $\epsilon_1^{(1)}, \cdots, \epsilon_w^{(1)}$ are independent, and we can therefore bound their average using well-known concentration inequalities. The following lemma upper bounds the expectation of $\epsilon_w^{(1)}$ and $\epsilon_w^{(2)}$.

\[lm:ch\_coding\] Let $(\mathcal{X}, W_{Y|X}, \mathcal{Y})$ be a and $P_X$ and $Q_Y$ be two distributions on $\mathcal{X}$ and $\mathcal{Y}$. If we choose $X_1, \cdots, X_M$ independently according to $P_X$, for all $\gamma\in\mathbb{R}$ and $w\in{\ensuremath{\llbracket{1},{M}\rrbracket}}$, we have $$\begin{aligned}
{{\mathbb{E}_{}}{\left(\epsilon_w^{(1)}\right)}}&= F_{XY|Q_Y}(\gamma),\\
{{\mathbb{E}_{}}{\left(\epsilon_w^{(2)}\right)}}&{\leqslant}\frac{M}{\exp(\gamma)} {{\mathbb{E}_{P_Y}}{\left(\frac{P_Y(Y)}{Q_Y(Y)}\right)}}.\label{eq:epsilon2-bound}\end{aligned}$$

The proof is very similar to the proof of @Bloch2016a [Lemma 3] or @Polyanskiy2010 [Theorem 18], but for completeness we provide the proof. We know that $$\begin{aligned}
{{\mathbb{E}_{}}{\left(\epsilon_w^{(1)}\right)}} &= \sum_{x_1, \cdots, x_M}\prod_{k=1}^MP_X(x_k) \sum_y W_{Y|X}(y|x_w){\ensuremath{\mathds{1}\!\left\{\log \frac{W_{Y|X}(y|x_w)}{Q_Y(y)} {\leqslant}\gamma\right\}}}\\
&= \sum_{x_w, y} P_X(x_w) W_{Y|X}(y|x_w){\ensuremath{\mathds{1}\!\left\{\log \frac{W_{Y|X}(y|x_w)}{Q_Y(y)} {\leqslant}\gamma\right\}}}\displaybreak[0]\\
&= {{\mathbb{P}_{W_{Y|X}P_X}}{\left(\log \frac{W_{Y|X}(Y|X)}{Q_Y(Y)}{\leqslant}\gamma\right)}}\displaybreak[0]\\
&= F_{XY|Q_Y}(\gamma).\end{aligned}$$ Moreover, we have $$\begin{aligned}
{{\mathbb{E}_{}}{\left(\epsilon_w^{(2)}\right)}} &{\leqslant}\sum_{x_1, \cdots, x_M}\prod_{k=1}^MP_X(x_k) \sum_y W_{Y|X}(y|x_w) {\ensuremath{\mathds{1}\!\left\{\exists w' \neq w: \log \frac{W_{Y|X}(y|x_{{{\color{black} w'}}})}{Q_Y(y)} {\geqslant}\gamma\right\}}}\\
&{\leqslant}\sum_{x_1, \cdots, x_M}\prod_{k=1}^MP_X(x_k) \sum_y W_{Y|X}(y|x_w)\sum_{w'\neq w} {\ensuremath{\mathds{1}\!\left\{\log \frac{W_{Y|X}(y|x_{w'})}{Q_Y(y)} {\geqslant}\gamma\right\}}}\displaybreak[0]\\
&=\sum_{w'\neq w} \sum_{x_1, \cdots, x_M, y} W_{Y|X}(y|x_w)\prod_{k=1}^MP_X(x_k) {\ensuremath{\mathds{1}\!\left\{\log \frac{W_{Y|X}(y|x_{w'})}{Q_Y(y)} {\geqslant}\gamma\right\}}}\displaybreak[0]\\
&= \sum_{{w'}\neq w} \sum_{x_{w'}, y} P_Y(y) P_X(x_{w'}) {\ensuremath{\mathds{1}\!\left\{\log \frac{W_{Y|X}(y|x_{w'})}{Q_Y(y)} {\geqslant}\gamma\right\}}}\displaybreak[0]\\
&= \sum_{w'\neq w} \sum_{x_{w'}, y} Q_Y(y) \frac{P_Y(y)}{Q_Y(y)} P_X(x_{w'}) {\ensuremath{\mathds{1}\!\left\{\log \frac{W_{Y|X}(y|x_{{{\color{black} w'}}})}{Q_Y(y)} {\geqslant}\gamma\right\}}}\displaybreak[0]\\
&{\leqslant}\sum_{w'\neq w} \sum_{x_{w'}, y}\exp(-\gamma)W_{{{\color{black} Y|X}}}(y|x_{w'}) \frac{P_Y(y)}{Q_Y(y)}P_X(x_{w'}) {\ensuremath{\mathds{1}\!\left\{\log \frac{W_{Y|X}(y|x_{w'})}{{{\color{black} Q}}_Y(y)} {\geqslant}\gamma\right\}}}\\
&{\leqslant}\frac{M}{\exp(\gamma)} {{\mathbb{E}_{P_Y}}{\left(\frac{P_Y(Y)}{Q_Y(Y)}\right)}}.\end{aligned}$$

In a second-order analysis, $\gamma$ is generally chosen such that ${{\mathbb{E}_{}}{\left(\epsilon_w^{(1)}\right)}}$ dominates ${{\mathbb{E}_{}}{\left(\epsilon_w^{(2)}\right)}}$; we follow this approach as well, which is convenient since we have some flexibility in the bounding of the expected value of $\epsilon_w^{(1)}$.

<span><span> The extra factor ${{\mathbb{E}_{P_Y}}{\left(\frac{P_Y(Y)}{Q_Y(Y)}\right)}}$ in , which does not appear in @Polyanskiy2010 [Theorem 18], is the penalty of using $Q_Y$ instead of the "true" probability distribution of $Y$, $P_Y$, in the definition of $F_{XY|Q_Y}$. These sub-optimal bounds yield the same first- and second-order asymptotics for covert communications, although they can certainly be improved for a finite-length analysis; this choice of $Q_Y$, however, simplifies our calculations.</span></span>

Next, we develop one-shot channel resolvability results. In our proofs, we treat the distance between induced output distribution and the desired distribution as a function of independently generated codewords, which allows us to prove a super-exponential concentration inequality in Lemma \[lm:ch\_resolve\_p\] using <span><span> McDiarmid</span></span>'s Theorem. This may be viewed as an alternative approach to @Cuff2015 and we recall this concentration inequality below for convenience.

\[McDiarmid's Theorem\] \[thm:mcdiarmid\] Let $\textbf{X} {\ensuremath{\triangleq}}(X_1, \cdots, X_n)$ be a sequence of independent random variables defined on $\mathcal{X}$. Furthermore, suppose $g:\mathcal{X}^n\to \mathbb{R}$ is a function satisfying $$\begin{aligned}
\sup_{x_1, \cdots, x_n, x_i'}|g(x_1, \cdots, x_i, \cdots, x_n) - g(x_1, \cdots, x_i', \cdots, x_n)| {\leqslant}c_i,\quad \forall i \in {\ensuremath{\llbracket{1},{n}\rrbracket}}.\end{aligned}$$ Then, for all $\lambda>0$, we have $$\begin{aligned}
{{\mathbb{P}_{}}{\left(g(\textbf{X})-{{\mathbb{E}_{}}{\left(g(\textbf{X})\right)}} {\geqslant}\lambda\right)}} {\leqslant}\exp\left(\frac{-2\lambda^2}{\sum c_i^2}\right).\end{aligned}$$

See @Raginsky2014 [Theorem 2.2.2].

\[lm:ch\_resolve\_p\] Consider a $(\mathcal{X}, W_{Z|X}, \mathcal{Z})$ and a distribution $P_X$ on $\mathcal{X}$. If $\{x_w\}_{w=1}^M \in \mathcal{X}^M$ are <span><span> $M{\geqslant}2$</span></span> codewords[^4] and $\widehat{P}_Z {{\color{black} {\ensuremath{\triangleq}}\frac{1}{M}\sum_{w=1}^M W_{Z|X=x_w}}}$ is the corresponding induced distribution on $\mathcal{Z}$, we define the functions $g_1, g_2:\mathcal{X}^M\to \mathbb{R}$ as $$\begin{aligned}
g_1(x_1, \cdots, x_M) {\ensuremath{\triangleq}}{{{\mathbb{V}}\!\left(\widehat{P}_Z, P_Z\right)}},\end{aligned}$$ and $$\begin{aligned}
g_2(x_1, \cdots, x_M) {\ensuremath{\triangleq}}{{{\mathbb{D}}\!\left({\widehat{P}_Z\VertP_Z}\right)}},\end{aligned}$$ with $P_Z(z) = \sum_x P_X(x) W_{Z|X}(z|x)$. Then, for all $x_1, \cdots, x_M, x_i'\in \mathcal{X}$, we have $$\begin{aligned}
|g_1(x_1, \cdots, x_i, \cdots, x_M) - g_1(x_1, \cdots, x_i', \cdots, x_M)| {\leqslant}\frac{1}{M},\end{aligned}$$ and $$\begin{aligned}
|g_2(x_1, \cdots, x_i, \cdots, x_M) - g_2(x_1, \cdots, x_i', \cdots, x_M)| {\leqslant}\frac{1}{M}\log\left(\frac{M|\mathcal{Z}|}{\mu_{Z}^2}\right).\end{aligned}$$ Moreover, if $X_1, \cdots, X_M$ are with distribution $P_X$, then $$\begin{aligned}
\label{eq:v-concentration}
{{\mathbb{P}_{}}{\left({{{\mathbb{V}}\!\left(\widehat{P}_Z, P_Z\right)}}-{{\mathbb{E}_{}}{\left({{{\mathbb{V}}\!\left(\widehat{P}_Z,P_Z\right)}}\right)}}  {\geqslant}\lambda\right)}} {\leqslant}\exp\left(-2M\lambda^2\right),\end{aligned}$$ and $$\begin{aligned}
\label{eq:div-concentration}
{{\mathbb{P}_{}}{\left({{{\mathbb{D}}\!\left({\widehat{P}_Z\VertP_Z}\right)}}-{{\mathbb{E}_{}}{\left({{{\mathbb{D}}\!\left({\widehat{P}_Z\VertP_Z}\right)}}\right)}} {\geqslant}\lambda\right)}} {\leqslant}\exp\left(-\frac{2M\lambda^2}{\log^2\left(\frac{M|\mathcal{Z}|}{\mu_Z^2}\right)}\right).\end{aligned}$$

We assume that $\widehat{P}_Z^1$ and $\widehat{P}_Z^2$ are the distributions induced by the codebooks $\mathcal{C}_1{\ensuremath{\triangleq}}\{x_1, \cdots, x_i, \cdots, x_M\}$ and $\mathcal{C}_2{\ensuremath{\triangleq}}\{x_1, \cdots, x_i', \cdots, x_M\}$, respectively. First, note that $$\begin{aligned}
g_1(x_1, \cdots, x_i, \cdots, x_M) - g_1(x_1, \cdots, x_i', \cdots, x_M) &= {{{\mathbb{V}}\!\left(\widehat{P}_Z^1, P_Z\right)}} - {{{\mathbb{V}}\!\left(\widehat{P}_Z^2, P_Z\right)}}\\
&{\leqslant}{{{\mathbb{V}}\!\left(\widehat{P}_{Z}^1, \widehat{P}_{Z}^2\right)}}\\
&= \frac{1}{2}\sum_{z}\left|\widehat{P}_{Z}^1(z) - \widehat{P}_{Z}^2(z)\right|\\
&=\frac{1}{2}\sum_{z} \left| \frac{1}{M}\sum_{x\in \mathcal{C}_1}W_{Z|X}(z|x)- \frac{1}{M}\sum_{x\in \mathcal{C}_2}W_{Z|X}(z|x) \right|\\
&=\frac{1}{2M}\sum_{z}\left|W_{Z|X}(z|x_i) -W_{Z|X}(z|x_i')\right| \\
&=\frac{1}{M}{{{\mathbb{V}}\!\left(W_{Z|X}(.|x_i), W_{Z|X}(.|x_i')\right)}}\\
&{\leqslant}\frac{1}{M}.\end{aligned}$$ Next, for any two distributions $P$ and $Q$, by @CodingTheoremsDMC2 [Lemma 2.7], we have $$\begin{aligned}
|H(P)-H(Q)| {\leqslant}-{{{\mathbb{V}}\!\left(P, Q\right)}}\log \frac{{{{\mathbb{V}}\!\left(P, Q\right)}}}{|\mathcal{X}|}.\end{aligned}$$ Therefore, we have $$\begin{aligned}
\left|H(\widehat{P}_Z^1) - H(\widehat{P}_Z^2)\right| &{\leqslant}- {{{\mathbb{V}}\!\left(\widehat{P}_Z^1, \widehat{P}_Z^2\right)}}\log \frac{{{{\mathbb{V}}\!\left(\widehat{P}_Z^1, \widehat{P}_Z^2\right)}}}{|\mathcal{Z}|}\\
&\stackrel{(a)}{{\leqslant}} -\frac{1}{M} \log \frac{1}{M|\mathcal{Z}|}\\
&=\frac{1}{M}\log \left(M|\mathcal{Z}|\right),\end{aligned}$$ where $(a)$ follows from the fact that $x \log (x/|\mathcal{Z}|)$ is decreasing for $0 < x < |\mathcal{Z}|/2$. Accordingly, we obtain $$\begin{aligned}
\left|{{{\mathbb{D}}\!\left({\widehat{P}_Z^1\VertP_Z}\right)}}-{{{\mathbb{D}}\!\left({\widehat{P}_Z^2\VertP_Z}\right)}}\right| 
&= \left|-H(\widehat{P}_Z^1) + \sum_z\widehat{P}_Z^1(z)\log \frac{1}{P_Z(z)} + H(\widehat{P}_Z^2) - \sum_z\widehat{P}_Z^2(z)\log \frac{1}{P_Z(z)}  \right| \\
&{\leqslant}\frac{1}{M}\log\left(M|\mathcal{Z}|\right)+{{\color{black} \sum_z\left|\widehat{P}_Z^1(z) - \widehat{P}_Z^2(z)\right|\left|\log \frac{1}{P_Z(z)}\right|}}\\
&{\leqslant}\frac{1}{M}\log\left(M|\mathcal{Z}|\right) + \frac{2}{M}\log \frac{1}{\mu_Z}\\
&= \frac{1}{M}\log\left(\frac{M|\mathcal{Z}|}{\mu_Z^2}\right). \end{aligned}$$ Additionally, using Theorem \[thm:mcdiarmid\], we obtain  and .

\[lm:ch\_resolve\_e\] Let $(\mathcal{X}, W_{Z|X}, \mathcal{Z})$ be a and $P_X$ be a distribution on $\mathcal{X}$. If $X_1, \cdots, X_M$ are with distribution $P_X$, and $\widehat{P}_Z(z) {{\color{black} {\ensuremath{\triangleq}}\frac{1}{M} \sum_{w=1}^M W_{Z|X}(z,X_w)}}$ is the corresponding induced distribution on $\mathcal{Z}$, we have $$\begin{aligned}
{{\mathbb{E}_{}}{\left({{{\mathbb{D}}\!\left({\widehat{P}_Z\VertP_Z}\right)}}\right)}} {\leqslant}\log \left(\frac{1}{\mu_Z} +1\right)\overline{F}_{XZ}(\gamma)+ \frac{\exp(\gamma)}{M},\end{aligned}$$ for all $\gamma\in\mathbb{R}$ where $P_Z(z) = \sum_x P_X(x) W_{Z|X}(z|x)$.

From @Hou2013 [Equation 10], we know that $$\begin{aligned}
{{\mathbb{E}_{}}{\left({{{\mathbb{D}}\!\left({\widehat{P}_Z\VertP_Z}\right)}}\right)}} &{\leqslant}{{\mathbb{E}_{W_{Z|X}P_X}}{\left(\log\left(\frac{W_{Z|X}(Z|X)}{MP_Z(Z)} +1\right)\right)}}.\end{aligned}$$ If we define the event $\mathcal{E}{\ensuremath{\triangleq}}\{(x, z): \log \frac{W_{Z|X}(z|x))}{P_Z(z)} {\leqslant}\gamma\}$, then we get $$\begin{aligned}
{{\mathbb{E}_{}}{\left(\log\left(\frac{W_{Z|X}(Z|X)}{MP_Z(Z)} +1\right)\right)}} &= {{\mathbb{E}_{}}{\left(\log\left(\frac{W_{Z|X}(Z|X)}{MP_Z(Z)} +1\right)|\mathcal{E}\right)}}{{\mathbb{P}_{}}{\left(\mathcal{E}\right)}} + {{\mathbb{E}_{}}{\left(\log\left(\frac{W_{Z|X}(Z|X)}{MP_Z(Z)} +1\right)|\mathcal{E}^c\right)}} {{\mathbb{P}_{}}{\left(\mathcal{E}
^c\right)}}\\
&{\leqslant}\log\left(\frac{\exp(\gamma)}{M} +1\right) +\overline{F}_{XZ}(\gamma) \log \left(\frac{1}{\mu_Z} +1\right)\\
&{\leqslant}\frac{\exp(\gamma)}{M} +\overline{F}_{XZ}(\gamma) \log \left(\frac{1}{\mu_Z} +1\right).\end{aligned}$$

Consider now the $({{\mathcal{X}}}, W_{Y|X}, W_{Z|X}, {{\mathcal{Y}}}, {{\mathcal{Z}}})$ and a randomly generated code $\{X_{sw}:s\in {\ensuremath{\llbracket{1},{K}\rrbracket}},w\in {\ensuremath{\llbracket{1},{M}\rrbracket}}\}$. The next lemma leverages Lemma \[lm:ch\_coding\] and Lemma \[lm:ch\_resolve\_p\] to guarantee that, with high probability, the entire code is a channel resolvability code for the channel $W_{Z|X}$, and *simultaneously*, the subcode corresponding to every $s\in{\ensuremath{\llbracket{1},{K}\rrbracket}}$ is a channel reliability code for the channel $W_{Y|X}$. Note that a code with these properties is not necessarily a covert code, but we show in the next sections how a careful choice of the random coding distribution leads to covertness.

\[thm:one-shot-covert-cm\] Consider a $(\mathcal{X}, W_{Y|X}, W_{Z|X}, \mathcal{Y}, \mathcal{Z})$ and two probability distributions $P_X$ and $Q_Y$ on $\mathcal{X}$ and $\mathcal{Y}$. We sample codewords $\{X_{sw}:s\in {\ensuremath{\llbracket{1},{K}\rrbracket}},w\in {\ensuremath{\llbracket{1},{M}\rrbracket}}\}$ independently according to $P_X$. <span><span> For this random code, the quantities $P^{*}_{\text{err}}$ and ${{{\mathbb{D}}\!\left({\widehat{P}_Z\VertP_Z}\right)}}$ will be treated as random variables with respect to the randomness of the random code</span></span>. Moreover, for every $\lambda_1$, $\lambda_2$, $\lambda_3$, $\gamma_1$, and $\gamma_2>0$, we define events $$\begin{aligned}
\label{eq:one-shot-reliability}
\mathcal{E}_1 {\ensuremath{\triangleq}}\left\{P_{\text{err}}^* {\leqslant}F_{XY|Q_Y}(\gamma_1) + \lambda_1+\lambda_2 \frac{M}{ \exp(\gamma_1)}{{\mathbb{E}_{P_Y}}{\left(\frac{P_Y(Y)}{Q_Y(Y)}\right)}}\right\} \end{aligned}$$ and $$\begin{aligned}
\label{eq:one-shot-resolvability}
\mathcal{E}_2 {\ensuremath{\triangleq}}\left\{{{{\mathbb{D}}\!\left({\widehat{P}_Z\VertP_Z}\right)}} {\leqslant}\log \left(\frac{1}{\mu_Z} +1\right)\overline{F}_{XZ}(\gamma_2)+ \frac{\exp(\gamma_2)}{MK} + \lambda_3\right\}.\end{aligned}$$ Then ${{\mathbb{P}_{}}{\left(\mathcal{E}_1 \cap \mathcal{E}_2\right)}} > 0$, if $$\begin{aligned}
\label{eq:mc-criterion}
1 > \exp\left(-\frac{2M\lambda_3^2}{\log^2\left(\frac{MK|\mathcal{Z}|}{\mu_Z^2}\right)}\right)-\exp\left(-2M\lambda_1^2\right)-\frac{1}{\lambda_2}.\end{aligned}$$

We analyze the probability of each event separately. First, note that $$\begin{aligned}
{{\mathbb{P}_{}}{\left(\mathcal{E}_1\right)}} &= {{\mathbb{P}_{}}{\left(P_{\text{err}}^* {\leqslant}F_{XY|Q_Y}(\gamma_1) + \lambda_1+\lambda_2 \frac{M}{ \exp(\gamma_1)}{{\mathbb{E}_{P_Y}}{\left(\frac{P_Y(Y)}{Q_Y(Y)}\right)}}\right)}}\\
&{\geqslant}{{\mathbb{P}_{}}{\left(\max_{s\in{\ensuremath{\llbracket{1},{K}\rrbracket}}}\frac{1}{M}\sum_{w=1}^M \left(\epsilon_{sw}^{(1)}+\epsilon_{s w}^{(2)}\right) {\leqslant}F_{XY|Q_Y}(\gamma_1) + \lambda_1+\lambda_2 \frac{M}{ \exp(\gamma_1)}{{\mathbb{E}_{P_Y}}{\left(\frac{P_Y(Y)}{Q_Y(Y)}\right)}}\right)}}\displaybreak[0]\\
&=  {{\mathbb{P}_{}}{\left(\frac{1}{M}\sum_{w=1}^M \left(\epsilon_{1w}^{(1)}+\epsilon_{1w}^{(2)}\right) {\leqslant}F_{XY|Q_Y}(\gamma_1) + \lambda_1+\lambda_2 \frac{M}{ \exp(\gamma_1)}{{\mathbb{E}_{P_Y}}{\left(\frac{P_Y(Y)}{Q_Y(Y)}\right)}}\right)}}^K \displaybreak[0]\\
&{\geqslant}\left({{\mathbb{P}_{}}{\left(\frac{1}{M}\sum_{w=1}^M\epsilon_{1w}^{(1)} {\leqslant}F_{XY|Q_Y}(\gamma_1) + \lambda_1\right)}} - {{\mathbb{P}_{}}{\left(\frac{1}{M}\sum_{w=1}^M\epsilon_{1w}^{(2)} >\lambda_2 \frac{M}{ \exp(\gamma_1)}{{\mathbb{E}_{P_Y}}{\left(\frac{P_Y(Y)}{Q_Y(Y)}\right)}}\right)}}\right)^K \displaybreak[0]\\
&\stackrel{(a)}{{\geqslant}} \left(1-\exp\left(-2M\lambda_1^2\right)-{{\mathbb{P}_{}}{\left(\frac{1}{M}\sum_{w=1}^M\epsilon_{1w}^{(2)} >\lambda_2 \frac{M}{ \exp(\gamma_1)}{{\mathbb{E}_{P_Y}}{\left(\frac{P_Y(Y)}{Q_Y(Y)}\right)}}\right)}}\right)^K\\
&\stackrel{(b)}{{\geqslant}}\left(1-\exp\left(-2M\lambda_1^2\right) -\frac{1}{\lambda_2}\right)^K ,\end{aligned}$$ where $(a)$ follows from Hoeffding's Inequality and the fact that $\epsilon_{11}^{(1)}, \cdots, \epsilon_{1M}^{(1)}$ are independent random variables taking value in $[0, 1]$ with mean $ F_{XY}(\gamma_1)$, and $(b)$ follows from Markov's Inequality. Furthermore, we have $$\begin{aligned}
{{\mathbb{P}_{}}{\left(\mathcal{E}_2\right)}} &= {{\mathbb{P}_{}}{\left({{{\mathbb{D}}\!\left({\widehat{P}_Z\VertP_Z}\right)}} {\leqslant}\log \left(\frac{1}{\mu_Z} +1\right)\overline{F}_{XZ}(\gamma_2)+ \frac{\exp(\gamma_2)}{MK} + \lambda_3\right)}}  \\ 
&\stackrel{(a)}{{\geqslant}}  {{\mathbb{P}_{}}{\left({{{\mathbb{D}}\!\left({\widehat{P}_Z\VertP_Z}\right)}} {\leqslant}{{\mathbb{E}_{}}{\left({{{\mathbb{D}}\!\left({\widehat{P}_Z\VertP_Z}\right)}} \right)}} + \lambda_3\right)}}  \\ 
&\stackrel{(b)}{{\geqslant}} 1-  \exp\left(-\frac{2MK\lambda_3^2}{\log^2\left(\frac{MK|\mathcal{Z}|}{\mu_Z^2}\right)}\right),\end{aligned}$$ where $(a)$ follows from Lemma \[lm:ch\_resolve\_e\], and $(b)$ follows from Lemma \[lm:ch\_resolve\_p\]. Combining these inequalities, we get $$\begin{aligned}
\label{eq:mc-events}
{{\mathbb{P}_{}}{\left(\mathcal{E}_1\right)}} + {{\mathbb{P}_{}}{\left(\mathcal{E}_2\right)}} {\geqslant}\left(1-\exp\left(-2M\lambda_1^2\right) -\frac{1}{\lambda_2}\right)^K + 1 - \exp\left(-\frac{2MK\lambda_3^2}{\log^2\left(\frac{MK|\mathcal{Z}|}{\mu_Z^2}\right)}\right).\end{aligned}$$ Thus, we obtain $$\begin{aligned}
{{\mathbb{P}_{}}{\left(\mathcal{E}_1\cap \mathcal{E}_2\right)}} &= 1- {{\mathbb{P}_{}}{\left(\mathcal{E}_1^c\cup \mathcal{E}_2^c\right)}}\\
&{\geqslant}1-{{\mathbb{P}_{}}{\left(\mathcal{E}_1^c\right)}}-{{\mathbb{P}_{\mathbb{C}}}{\left(\mathcal{E}_2^c\right)}}\\
&={{\mathbb{P}_{}}{\left(\mathcal{E}_1\right)}}+{{\mathbb{P}_{}}{\left(\mathcal{E}_2\right)}}-1\\
&\stackrel{(a)}{{\geqslant}}\left(1-\exp\left(-2M\lambda_1^2\right) -\frac{1}{\lambda_2}\right)^K  - \exp\left(-\frac{2MK\lambda_3^2}{\log^2\left(\frac{MK|\mathcal{Z}|}{\mu_Z^2}\right)}\right),\end{aligned}$$ where $(a)$ follows from the . Finally, completes the proof.

Asymptotic results for covert communications {#sec:asympt-results-cover}
--------------------------------------------

We now specialize the one-shot result of Lemma \[thm:one-shot-covert-cm\] to show the existence of covert codes for large blocklength $n$.

\[thm:general\_achv\] Consider a sequence of distributions $\{P_\textbf{X}^n\}_{n{\geqslant}1}$ where $P_\textbf{X}^n$ is defined on ${{\mathcal{X}}}^n$ and two sequences of natural numbers $\{M_n\}_{n{\geqslant}1}$ and $\{K_n\}_{n{\geqslant}1}$. For a quasi-metric $d$ and $n$ large enough, if we have $$\begin{aligned}
\label{eq:positive_prob}
 1 - \exp\left(-\frac{2M_n}{n^8\log^2\left(\frac{M_nK_n|\mathcal{Z}|}{\mu_Z^2}\right)}\right)-\exp\left(-2\frac{M_n}{n^2}\right)-\frac{1}{n} > 0,\end{aligned}$$ $$\begin{aligned}
\label{eq:F_Y}
F_{\textbf{X}\textbf{Y}|P_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}}\left(\log \left(n^2M_n\right)\right) +\frac{1+{{\mathbb{E}_{P_\textbf{Y}}}{\left(\frac{P_\textbf{Y}(\textbf{Y})}{P_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}(\textbf{Y})}\right)}}}{n} {\leqslant}\epsilon ,\end{aligned}$$ $$\begin{aligned}
\label{eq:F_Z}
\overline{F}_{\textbf{X}\textbf{Z}}\left(\log \frac{M_n K_n}{n^4}\right) {\leqslant}\frac{1}{n^6},\end{aligned}$$ and $$\begin{aligned}
\label{eq:dist_P_Z}
d(P_{\textbf{Z}}, Q_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}) {\leqslant}\delta - \frac{1}{\sqrt{n}},\end{aligned}$$ then $M_d^*(n, \epsilon, \delta) {\geqslant}M_n$.

Theorem \[thm:general\_achv\] is useful in that it identifies sufficient conditions for the existence of codes. In particular, subsequent achievability proofs are reduced to choosing an appropriate sequence of random coding distributions $\{P_\textbf{X}^n\}_{n{\geqslant}1}$ and verifying inequalities (\[eq:positive\_prob\])-(\[eq:dist\_P\_Z\]). We use both and distributions, which we introduce and analyze precisely in Section \[sec:distributions\].

For a fixed $n$, we choose codewords $\textbf{X}_{sw}$ for $s\in{\ensuremath{\llbracket{1},{K_n}\rrbracket}}$ and $w\in {\ensuremath{\llbracket{1},{M_n}\rrbracket}}$ independently according to $P_\textbf{X}^n$. In Lemma \[thm:one-shot-covert-cm\], if we set $$\begin{aligned}
\lambda_1 = \frac{1}{n},\quad \lambda_2 = n, \quad, \lambda_3 = \frac{1}{n^4},\quad, \gamma_1 = \log \left(n^2 M_n\right), \quad \text{and } \gamma_2 = \log \frac{M_n K_n}{n^4},\end{aligned}$$ because of , we have with positive probability for $n$ large enough $$\begin{aligned}
 P_{\text{err}}^* &{\leqslant}F_{\textbf{X}\textbf{Y}|P_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}}(\gamma_1) + \lambda_1 + \lambda_2 \frac{M_n}{\exp(\gamma_1)} {{\mathbb{E}_{P_\textbf{Y}}}{\left(\frac{P_\textbf{Y}(\textbf{Y})}{P_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}(\textbf{Y})}\right)}}\\
 \label{eq:asym_reliable}
 &= F_{\textbf{X}\textbf{Y}|P_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}}\left(\log (n^2 M_n)\right) + \frac{1 + {{\mathbb{E}_{P_\textbf{Y}}}{\left(\frac{P_\textbf{Y}(\textbf{Y})}{P_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}(\textbf{Y})}\right)}}}{n} \stackrel{(a)}{{\leqslant}} \epsilon,
 \end{aligned}$$ and with $\mu_{\textbf{Z}} {\ensuremath{\triangleq}}\min_\textbf{z} P_{\textbf{Z}}(\textbf{z})$ $$\begin{aligned}
 {{{\mathbb{D}}\!\left({\widehat{P}_{\textbf{Z}}\VertP_{\textbf{Z}}}\right)}} &{\leqslant}\log\left(1 + \frac{1}{\mu_\textbf{Z}}\right)\overline{F}_{\textbf{X}\textbf{Z}}(\gamma_2)+ \frac{\exp(\gamma_2)}{M_nK_n} + \lambda_3\\
 \label{eq:asym_resolve}
 &\stackrel{(b)}{{\leqslant}} n \log\left(1 + \frac{1}{\mu_Z}\right) \frac{1}{n^6} + \frac{1}{n^4} + \frac{1}{n^4}{\leqslant}\frac{3}{n^4},
 \end{aligned}$$ where $(a)$ follows from and $(b)$ follows from . Finally, to prove the covertness of the code, note that for $n$ large enough $$\begin{aligned}
d(\widehat{P}_{\textbf{Z}}, Q_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}) &\stackrel{(a)}{{\leqslant}} d(P_\textbf{Z}^n, Q_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}) + {{{\mathbb{D}}\!\left({\widehat{P}_{\textbf{Z}}\VertP_\textbf{Z}^n}\right)}} + \sqrt{ {{{\mathbb{D}}\!\left({\widehat{P}_{\textbf{Z}}\VertP_\textbf{Z}^n}\right)}}}\max\left(1,\log \frac{1}{\min_\textbf{z} Q_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}(\textbf{z)}}\right)\\
&\stackrel{(b)}{{\leqslant}} \delta - \frac{1}{\sqrt{n}}+ {{{\mathbb{D}}\!\left({\widehat{P}_{\textbf{Z}}\VertP_\textbf{Z}^n}\right)}} + \sqrt{ {{{\mathbb{D}}\!\left({\widehat{P}_{\textbf{Z}}\VertP_\textbf{Z}^n}\right)}}}\max\left(1,\log \frac{1}{\min_\textbf{z} Q_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}(\textbf{z)}}\right)\\
&\stackrel{(c)}{{\leqslant}}  \delta - \frac{1}{\sqrt{n}}+\frac{3}{n^4} + \sqrt{ \frac{3}{n^4}}\max\left(1,\log \frac{1}{\min_\textbf{z} Q_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}(\textbf{z)}}\right)\\
&{\leqslant}\delta - \frac{1}{\sqrt{n}}+\frac{3}{n^4} + \sqrt{ \frac{3}{n^4}}\max\left(1, n\log \frac{1}{\mu_Z}\right)\\
 &{\leqslant}\delta,\end{aligned}$$ where $(a)$ follows because $d$ is a quasi-metric, $(b)$ follows from , and $(c)$ follows from .

PPM distribution {#sec:distributions}
----------------

In this section, we study specific " distribution," which was used in @Bloch2016b for covert communication; we subsequently use this distribution to generate random codes and combine with Theorem \[thm:general\_achv\].

\[$(n, \ell)$- covert distribution\] \[def:ppm\_distribution\] Given $\mathcal{X} = \{0, 1\}$ and $n{\geqslant}\ell {\geqslant}1$, we will define distribution ${P_{\textbf{X}, \text{PPM}}^{n, \ell}}$ on $\mathcal{X}^n$. If $n = m\ell + r$ for $0{\leqslant}r < \ell$, we partition the set ${\ensuremath{\llbracket{1},{n}\rrbracket}}$ into $\ell$ sets of size $m$ and one set of size $r$. For simplicity, we consider the following partition: $\mathcal{B}_i = \{(i-1)m+1, \cdots, im\}$ for $i\in{\ensuremath{\llbracket{1},{\ell}\rrbracket}}$ and $\mathcal{B}_{\ell+1} = \{\ell m+1, \cdots, n\}$. Then, $P_{\textbf{X},\text{PPM}}^{n, \ell}$ is the uniform distribution on the sequences with exactly one "1" in all $\mathcal{B}_i$ for $i\in{\ensuremath{\llbracket{1},{\ell}\rrbracket}}$ and no "1" in $\mathcal{B}_{\ell+1}$, i.e., $$\begin{aligned}
\left\{\mathbf{x}\in\mathcal{X}^n: \forall i \in {\ensuremath{\llbracket{1},{\ell}\rrbracket}}: \sum_{j\in\mathcal{B}_i}x_j = 1~ \mathrm{ and } \sum_{j\in \mathcal{B}_{\ell+1}} x_j= 0\right\}.\end{aligned}$$ We denote the output distribution of $P_{\textbf{X}, \text{PPM}}^{n,\ell}$ for s $(\mathcal{X}, W_{Y|X}, \mathcal{Y})$ and $(\mathcal{X}, W_{Z|X}, \mathcal{Z})$ by $P_{\textbf{Y}, \text{PPM}}^{n, \ell}$ and $P_{\textbf{Z}, \text{PPM}}^{n, \ell}$.

The covert distribution ${P_{\textbf{X}, \text{PPM}}^{n, \ell}}$ may be viewed as a way to generate structured constant composition codewords; specifically, every codeword generated according to ${P_{\textbf{X}, \text{PPM}}^{n, \ell}}$ contains exactly $\ell$ 1-symbols, each located in a window of size $m$, the quotient of the Euclidean division of $n$ by $\ell$. The structure of the covert distribution plays a pivotal role in our analysis.

We devote the remainder of this section to the development of properties of PPM distribution, which are geared towards the use of Theorem \[thm:general\_achv\]. We make repeated use of the Berry-Esseen Theorem, which we recall here for convenience.

\[Berry-Esseen Theorem\] \[Berry-Esseen\] Let $X_1, \cdots, X_n$ be independent random variables s.t. for $k\in{\ensuremath{\llbracket{1},{n}\rrbracket}}$ we have $ {{\mathbb{E}_{}}{\left(X_k\right)}} = \mu_k$, $\sigma_k^2={{\text{\textnormal{Var}}{\left(X_k\right)}}}$, and $t_k={{\mathbb{E}_{}}{\left(|X_k-\mu_k|^3\right)}}$. If we define $\sigma^2 = \sum_{{{\color{black} k}}=1}^{{\color{black} n}} \sigma_k^2$ and $T=\sum_{k=1}^n t_{{\color{black} k}}$, then we have $$\begin{aligned}
 \left|{{\mathbb{P}_{}}{\left(\sum_{k=1}^n(X_k-\mu_k) {\geqslant}\lambda \sigma\right)}}-Q(\lambda)\right| {\leqslant}\frac{6T}{\sigma^3}.\end{aligned}$$

We start with the specialization of  with Lemma \[lm:F\_XY\_bound\] and Lemma \[lm:expected\_ration\_ppm\].

\[lm:F\_XY\_bound\] Let $(\mathcal{X}, W_{Y|X}, \mathcal{Y})$ be a binary-input . If $(\textbf{X}, \textbf{Y})$ is distributed according to ${P_{\textbf{X}, \text{PPM}}^{n, \ell}}W_{Y|X}^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}$, we have $$\begin{aligned}
F_{\textbf{X}\textbf{Y}|P_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}}(\gamma) {\leqslant}Q\left(\frac{\ell D_P - \gamma}{\sqrt{\ell V_P}}\right) + \frac{6T_P}{\sqrt{\ell}V_P^{\frac{3}{2}}},\end{aligned}$$ with $$\begin{aligned}
T_P {\ensuremath{\triangleq}}{{\mathbb{E}_{P_1}}{\left(\left|\log\frac{P_1(Y)}{P_0(Y)} - {{{\mathbb{D}}\!\left({P_1\VertP_0}\right)}} \right|^3\right)}}.\end{aligned}$$

When $(\textbf{X}, \textbf{Y})$ is distributed according to ${P_{\textbf{X}, \text{PPM}}^{n, \ell}}W_{Y|X}^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}$, for a sequence $\mathbf{x}_0$ with ${P_{\textbf{X}, \text{PPM}}^{n, \ell}}(\textbf{x}_0) > 0$ , we know that $$\begin{aligned}
F_{\textbf{X}\textbf{Y}|P_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}}(\gamma) &= {{\mathbb{P}_{P^{n, \ell}_{\textbf{X}, \text{PPM}} W_{Y|X}^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}}}{\left(\log \frac{W_{Y|X}^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}(\textbf{Y}|\textbf{X})}{P_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}(\textbf{Y})}{\leqslant}\gamma\right)}}\displaybreak[0]\\
&= \sum_{\textbf{x}\in \mathcal{X}^n}{P_{\textbf{X}, \text{PPM}}^{n, \ell}}(\textbf{x}) {{\mathbb{P}_{{P_{\textbf{X}, \text{PPM}}^{n, \ell}} W_{Y|X}^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}}}{\left(\log \frac{W_{Y|X}^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}(\textbf{Y}|\textbf{X})}{P_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}(\textbf{Y})}{\leqslant}\gamma \big| \mathbf{X}=\mathbf{x}\right)}}\displaybreak[0]\\
&\stackrel{(a)}{=} {{\mathbb{P}_{{P_{\textbf{X}, \text{PPM}}^{n, \ell}} W_{Y|X}^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}}}{\left(\log \frac{W_{Y|X}^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}(\textbf{Y}|\textbf{x}_0)}{P_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}(\textbf{Y})}{\leqslant}\gamma \big| \mathbf{X}=\mathbf{x}_0\right)}},\end{aligned}$$ <span><span> where $(a)$ follows since ${{\mathbb{P}_{{P_{\textbf{X}, \text{PPM}}^{n, \ell}} W_{Y|X}^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}}}{\left(\log \frac{W_{Y|X}^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}(\textbf{Y}|\textbf{X})}{P_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}(\textbf{Y})}{\leqslant}\gamma \big| \mathbf{X}=\mathbf{x}\right)}} = {{\mathbb{P}_{{P_{\textbf{X}, \text{PPM}}^{n, \ell}} W_{Y|X}^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}}}{\left(\sum_{i=1}^n\log \frac{W_{Y|X}(Y_i|x_i)}{P_0(Y_i)}{\leqslant}\gamma\big|\mathbf{X} = \mathbf{x} \right)}}$, which only depends on ${\ensuremath{\mbox{wt}(\mathbf{x})}}$</span></span>. Since channel is memoryless, by relabeling, we can assume without loss of generality that the support of $\mathbf{x}_0$ is ${\ensuremath{\llbracket{1},{\ell}\rrbracket}}$. Hence, we have $$\begin{aligned}
{{\mathbb{P}_{{P_{\textbf{X}, \text{PPM}}^{n, \ell}} W_{Y|X}^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}}}{\left(\log \frac{W_{Y|X}^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}(\textbf{Y}|\textbf{x}_0)}{P_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}(\textbf{Y})}{\leqslant}\gamma | \mathbf{X}=\mathbf{x}_0\right)}}  &= {{\mathbb{P}_{P_1^{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}\ell}}}{\left(\sum_{i=1}^\ell\log \frac{P_1(Y_i)}{P_0(Y_i)}{\leqslant}\gamma\right)}}\\
&\stackrel{(a)}{{\leqslant}}  Q\left(\frac{\ell D_P - \gamma}{\sqrt{\ell V_P}}\right) + \frac{6T_P}{\sqrt{\ell}V_P^{\frac{3}{2}}},\end{aligned}$$ where $(a)$ follows from Theorem \[Berry-Esseen\].

\[lm:expected\_ration\_ppm\] For a binary-input $(\mathcal{X}, W_{Y|X}, \mathcal{Y})$, we have $$\begin{aligned}
\label{eq:ratio_ppm}
{{\mathbb{E}_{{P_{\textbf{Y}, \text{PPM}}^{n, \ell}}}}{\left(\frac{{P_{\textbf{Y}, \text{PPM}}^{n, \ell}}(\textbf{Y})}{P_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}(\textbf{Y})}\right)}} &= \left(1 + \frac{\chi_2(P_1\|P_0)}{\lfloor n /\ell \rfloor}\right)^{\ell}\\
&{\leqslant}\exp\left(\frac{\ell(\ell+1)}{n}\chi_2(P_1\|P_0)\right).\end{aligned}$$

To prove , we define $m{\ensuremath{\triangleq}}\lfloor n /\ell \rfloor$. We first consider <span><span> ${P_{\textbf{X}, \text{PPM}}^{m, 1}}$</span></span> for which we have $$\begin{aligned}
{{\mathbb{E}_{{{\color{black} {P_{\textbf{Y}, \text{PPM}}^{m, 1}}}}}}{\left(\frac{{{\color{black} {P_{\textbf{Y}, \text{PPM}}^{m, 1}}}}(\textbf{Y})}{P_0^{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}m}(\textbf{Y})}\right)}} 
&= \sum_\textbf{y} {{\color{black} {P_{\textbf{Y}, \text{PPM}}^{m, 1}}}}(\textbf{y})\frac{{{\color{black} {P_{\textbf{Y}, \text{PPM}}^{m, 1}}}}(\textbf{y})}{P_0^{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}m}(\textbf{y})}\\
&= \sum_\textbf{y} P_0^{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}m}(\textbf{y})\left(\frac{{{\color{black} {P_{\textbf{Y}, \text{PPM}}^{m, 1}}}}(\textbf{y})}{P_0^{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}m}(\textbf{y})}\right)^2\\
&= \sum_\textbf{y} P_0^{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}m}(\textbf{y}) \left(\frac{1}{m}\sum_{i=1}^m \frac{P_1(y_i)}{P_0(y_i)}\right)^2\\
&= \frac{1}{m^2}\left(m(m-1)+m(\chi_2(P_1\|P_0) +1)\right)\\
&= 1 + \frac{\chi_2(P_1\|P_0)}{m}.\end{aligned}$$ Since ${P_{\textbf{Y}, \text{PPM}}^{n, \ell}}$ is the product of the distributions over different blocks, i.e. ${P_{\textbf{Y}, \text{PPM}}^{n, \ell}} = \left({P_{\textbf{Y}, \text{PPM}}^{m, 1}}\right) ^ {{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}\ell} {  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}{{\color{black} P}}_0^{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n \text{ mod } \ell}$, upon defining $\textbf{Y}_i = (Y_{(i-1)m+1}, \cdots, Y_{im})$ for $i\in{\ensuremath{\llbracket{1},{\ell}\rrbracket}}$, we obtain $$\begin{aligned}
{{\mathbb{E}_{{P_{\textbf{Y}, \text{PPM}}^{n, \ell}}}}{\left(\frac{{P_{\textbf{Y}, \text{PPM}}^{n, \ell}}(\textbf{Y})}{P_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}(\textbf{Y})}\right)}} &= {{\mathbb{E}_{\left({P_{\textbf{Y}, \text{PPM}}^{m, 1}}\right) ^ {{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}\ell}}}{\left(\prod_{i=1}^\ell \frac{{P_{\textbf{Y}, \text{PPM}}^{m, 1}}(\textbf{Y}_i)}{P_0^{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}m}(\textbf{Y}_i)}\right)}}\\
&= \prod_{i=1}^\ell{{\mathbb{E}_{{P_{\textbf{Y}, \text{PPM}}^{m, 1}}}}{\left(\frac{{P_{\textbf{Y}, \text{PPM}}^{m, 1}}(\textbf{Y}_i)}{P_0^{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}m}(\textbf{Y}_i)}\right)}}\\
&= \left(1 + \frac{\chi_2(P_1\|P_0)}{m}\right)^{\ell}\\
&{\leqslant}\exp\left(\frac{\ell(\ell+1)}{n}\chi_2(P_1\|P_0)\right).\end{aligned}$$

We now specialize  with Lemma \[lm:F\_XZ\_bound\].

\[lm:F\_XZ\_bound\] Given a binary-input $(\mathcal{X}, W_{Z|X}, \mathcal{Z})$, if $(\textbf{X}, \textbf{Z})$ is distributed according to ${P_{\textbf{X}, \text{PPM}}^{n, \ell}}W_{Z|X}^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}$, then, for $\gamma {\geqslant}\ell D_Q$, we have $$\begin{aligned}
\overline{F}_{\textbf{X}\textbf{Z}}(\gamma) {\leqslant}\exp\left(-\frac{\left(\gamma-\ell D_Q\right)^2}{2\ell \log^2\mu_Z}\right).\end{aligned}$$

When $(\textbf{X}, \textbf{Z})$ is distributed according to ${P_{\textbf{X}, \text{PPM}}^{n, \ell}}W_{Z|X}^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}$, for the random vector $\mathbf{Z}\in \mathcal{Z}^n$, the first $\ell$ blocks of length $m{\ensuremath{\triangleq}}\lfloor n/\ell \rfloor$ are denoted by $\textbf{Z}_1, \cdots, \textbf{Z}_{\ell}$ with $\textbf{Z}_i = (Z_{(i-1)m+1}, \cdots, Z_{im})$. Moreover, $P_{\textbf{Z}_i}$ denotes the distribution of block $\mathbf{Z}_i$. Therefore, we have $$\begin{aligned}
\overline{F}_{\textbf{X}\textbf{Z}}(\gamma)&= {{\mathbb{P}_{{P_{\textbf{X}, \text{PPM}}^{n, \ell}}W_{Z|X}^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}}}{\left(\log \frac{W_{Z|X}^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}(\textbf{Z}|\textbf{X})}{{P_{\textbf{Z}, \text{PPM}}^{n, \ell}}(\textbf{Z})}{\geqslant}\gamma\right)}}\\
&= {{\mathbb{P}_{{P_{\textbf{X}, \text{PPM}}^{n, \ell}}W_{Z|X}^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}}}{\left(\sum_{i=1}^\ell \log \frac{W_{Z|X}^{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}m}(\textbf{Z}_i|\textbf{X}_i)}{P_{\textbf{Z}_i}(\textbf{Z}_i)}{\geqslant}\gamma\right)}}\\
&\stackrel{(a)}{{\leqslant}} \exp\left(-\frac{2\left(\gamma-\ell I({P_{\textbf{X}, \text{PPM}}^{m, 1}}, W_{Z|X}^{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}m})\right)^2}{\ell B^2}\right),\end{aligned}$$ where $(a)$ follows from Hoeffding's Inequality with $$\begin{aligned}
B{\ensuremath{\triangleq}}\sup_{\textbf{x}_i, \textbf{z}_i}\left| \log \frac{W_{Z|X}^{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}m}(\textbf{z}_i|\textbf{x}_i)}{P_{\textbf{Z}_i}(\textbf{z}_i)}\right| > 0\end{aligned}$$ and $I({P_{\textbf{X}, \text{PPM}}^{m, 1}}, W_{Z|X}^{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}m})$ is defined as in . By @Bloch2016b [Lemma 1.5], we know that $I({P_{\textbf{X}, \text{PPM}}^{m, 1}}, W_{Z|X}^{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}m}) {\leqslant}D_Q$ and $B {\leqslant}2 \log \frac{1}{\mu_Z}$. Hence, we obtain $$\begin{aligned}
\exp\left(-\frac{2\left(\gamma-\ell I({P_{\textbf{X}, \text{PPM}}^{m, 1}}, W_{Z|X}^{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}m})\right)^2}{\ell B^2}\right) {\leqslant}\exp\left(-\frac{\left(\gamma-\ell D_Q\right)^2}{2\ell\log^2\mu_Z}\right).\end{aligned}$$

<span><span> Finally, we specialize  using Lemma \[lm:div\_ppm\].</span></span>

\[lm:div\_ppm\] Let $({{\mathcal{X}}}, W_{Z|X}, {{\mathcal{Z}}})$ be a , and $n$ and $\ell$ be positive integers with $m {\ensuremath{\triangleq}}\left \lfloor n/\ell \right \rfloor$ large enough and $\ell = \Theta(m)$. Then, we have $$\begin{aligned}
{{{\mathbb{D}}\!\left({{P_{\textbf{Z}, \text{PPM}}^{n, \ell}}\VertQ_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}}\right)}} &{\leqslant}\frac{\ell^2}{2n}\chi_2(Q_1\|Q_0) + O{{\left(\frac{1}{\sqrt{n}}\right)}}\label{eq:d_ppm}.\end{aligned}$$ <span><span> Furthermore, if $Q_0\ll Q_1$, we have $$\begin{aligned}
{{{\mathbb{V}}\!\left({P_{\textbf{Z}, \text{PPM}}^{n, \ell}},Q_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}\right)}} &{\leqslant}1- 2Q{{\left(\frac{\ell}{2}\sqrt{\frac{\chi_2(Q_1\|Q_0)}{n}}\right)}} + \frac{2}{\sqrt{\ell}} + O{{\left(\frac{1}{\sqrt{n}}\right)}}\label{eq:v_ppm},\\
\beta_\alpha\left(Q_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}, {P_{\textbf{Z}, \text{PPM}}^{n, \ell}}\right) &{\geqslant}Q{{\left(\ell \sqrt{\frac{\chi_2(Q_1\|Q_0)}{n}} - Q^{-1}{{\left(\alpha + \frac{1}{\sqrt{\ell}}\right)}}\right)}} - \frac{1}{\sqrt{\ell}} + O{{\left(\frac{1}{\sqrt{n}}\right)}}.\label{eq:beta_ppm}\end{aligned}$$</span></span>

By @Bloch2016b [Lemma 1], we have for some constant $C_1$, $C_2$, and $C_3$ $$\begin{aligned}
 {{{\mathbb{D}}\!\left({{P_{\textbf{Z}, \text{PPM}}^{n, \ell}}\VertQ_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}}\right)}} &{\leqslant}\frac{\ell}{2m} \chi_2(Q_1\|Q_0) + \frac{\ell C_1}{m^2} + \frac{\ell C_2}{m^3}\\
 &{\leqslant}\frac{\ell}{2m} \chi_2(Q_1\|Q_0) + \frac{\ell C_3}{m^2}\\
 &{\leqslant}\frac{\ell}{2(n/\ell - 1)} \chi_2(Q_1\|Q_0) + \frac{\ell C_3}{(n/\ell - 1)^2}\\
 &{\leqslant}\frac{\ell^2}{2n}\chi_2(Q_1\|Q_0) + \frac{\ell^3C_4}{n^2}.\end{aligned}$$

To prove , note that for any two distributions $P$ and $Q$, one can write ${{{\mathbb{V}}\!\left(P, Q\right)}} = {{\mathbb{P}_{P}}{\left(P(X) {\geqslant}Q(X)\right)}} - {{\mathbb{P}_{Q}}{\left(P(X) {\geqslant}Q(X)\right)}}$. Therefore, if $\mathbf{Z} = (Z_1, \cdots, Z_n)$ and $\widetilde{\mathbf{Z}} = (\widetilde{Z}_1, \cdots, \widetilde{Z}_n)$ are distributed according to $Q_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}$ and ${P_{\textbf{Z}, \text{PPM}}^{n, \ell}}$, respectively, then $$\begin{aligned}
{{{\mathbb{V}}\!\left({P_{\textbf{Z}, \text{PPM}}^{n, \ell}}, Q_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}\right)}} 
&= {{\mathbb{P}_{}}{\left({P_{\textbf{Z}, \text{PPM}}^{n, \ell}}(\widetilde{\mathbf{Z}}) {\geqslant}Q_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}(\widetilde{\mathbf{Z}})\right)}} - {{\mathbb{P}_{}}{\left({P_{\textbf{Z}, \text{PPM}}^{n, \ell}}({\mathbf{Z}}) {\geqslant}Q_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}({\mathbf{Z}})\right)}}\\
&= {{\mathbb{P}_{}}{\left(\log \frac{{P_{\textbf{Z}, \text{PPM}}^{n, \ell}}(\widetilde{\mathbf{Z}})}{Q_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}(\widetilde{\mathbf{Z}})} {\geqslant}0\right)}} - {{\mathbb{P}_{}}{\left(\log \frac{{P_{\textbf{Z}, \text{PPM}}^{n, \ell}}({\mathbf{Z}}) }{ Q_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}({\mathbf{Z}})} {\geqslant}0\right)}}.\end{aligned}$$ However, note that ${P_{\textbf{Z}, \text{PPM}}^{n, {  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}\ell}} = ({P_{\textbf{Z}, \text{PPM}}^{m, 1}})^\ell \otimes Q_0^{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}r}$, and for any $\mathbf{z} = (z_1, \cdots, z_n)$ with $\mathbf{z}_i = (z_{(i-1)m + 1},\cdots, z_{im})$, we have $$\begin{aligned}
\log{{\left( \frac{{P_{\textbf{Z}, \text{PPM}}^{n, \ell}}({\mathbf{z}})}{Q_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}({\mathbf{z}})} \right)}}
&= \sum_{i=1}^\ell \log{{\left( \frac{{P_{\textbf{Z}, \text{PPM}}^{m, 1}}(\mathbf{z}_i)}{Q_0^{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}m}(\mathbf{z}_i)}\right)}}\\
&= \sum_{i=1}^\ell \log{{\left( \frac{\sum_{j=1}^m \frac{1}{m} Q_1(z_{(i-1)m + j}) \prod_{k\neq j} Q_0(z_{(i-1)m + k})}{Q_0^{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}m}(\mathbf{z}_i)}\right)}}\\
&= \sum_{i=1}^\ell \log {{\left(\frac{1}{m}\sum_{j=1}^m\frac{  Q_1(z_{(i-1)m + j})}{ Q_0(z_{(i-1)m + j})}\right)}}\\
&= \sum_{i=1}^\ell \log {{\left(1 + \frac{1}{m}\sum_{j=1}^m\frac{  Q_1(z_{(i-1)m + j})-Q_0(z_{(i-1)m + j})}{ Q_0(z_{(i-1)m + j})}\right)}}\\
&= \sum_{i=1}^\ell \log {{\left(1 + \frac{1}{m}\sum_{j=1}^mA(z_{(i-1)m+j})\right)}},\end{aligned}$$ for $A(z) {\ensuremath{\triangleq}}\frac{Q_1(z) - Q_0(z)}{Q_0(z)}$. Thus, if we define $B_i {\ensuremath{\triangleq}}\log {{\left(1 + \frac{1}{m} \sum_{j=1}^m A(Z_{(i-1)m + j})\right)}}$ and $\widetilde{B}_i {\ensuremath{\triangleq}}\log {{\left(1 + \frac{1}{m} \sum_{j=1}^m A(\widetilde{Z}_{(i-1)m + j})\right)}}$, then $$\begin{aligned}
{{\mathbb{P}_{}}{\left(\log \frac{{P_{\textbf{Z}, \text{PPM}}^{n, \ell}}(\widetilde{\mathbf{Z}})}{Q_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}(\widetilde{\mathbf{Z}})} {\geqslant}0\right)}} - {{\mathbb{P}_{}}{\left(\log \frac{{P_{\textbf{Z}, \text{PPM}}^{n, \ell}}({\mathbf{Z}}) }{ Q_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}({\mathbf{Z}})} {\geqslant}0\right)}}
&= {{\mathbb{P}_{}}{\left(\sum_{i=1}^\ell \widetilde{B}_i {\geqslant}0\right)}} - {{\mathbb{P}_{}}{\left(\sum_{i=1}^\ell B_i {\geqslant}0\right)}}.\end{aligned}$$ Since $B_1, \cdots  B_{\ell}$ are , we apply Theorem \[Berry-Esseen\] and obtain $$\begin{aligned}
 {{\mathbb{P}_{}}{\left(\sum_{i=1}^\ell \widetilde{B}_i {\geqslant}0\right)}} 
 &{\leqslant}Q{{\left(\frac{- \sum_{i=1}^\ell {{\mathbb{E}_{}}{\left(\widetilde{B}_i\right)}}}{\sqrt{\ell \sum_{i=1}^\ell {{\text{\textnormal{Var}}{\left(\widetilde{B}_i\right)}}}}}\right)}}  + \frac{\sum_{i=1}^\ell {{\mathbb{E}_{}}{\left(\left|\widetilde{B}_i - {{\mathbb{E}_{}}{\left(\widetilde{B}_i\right)}}\right|^3\right)}}}{{{\left(\sum_{i=1}^\ell {{\text{\textnormal{Var}}{\left(\widetilde{B}_i\right)}}}\right)}}^{\frac{3}{2}}}\displaybreak[0]\\
 &\stackrel{(a)}{{\leqslant}} Q{{\left(-\frac{\ell {{\left( \frac{\chi_2(Q_1\|Q_0)}{2m} + O{{\left(\frac{1}{m^2}\right)}}\right)}}}{\sqrt{\ell{{\left(\frac{\chi_2(Q_1\|Q_0)}{m} + O{{\left(\frac{1}{m^2}\right)}}\right)}} }}\right)}} + \frac{\ell{{\left(\frac{\chi_2(Q_1\|Q_0)^{\frac{3}{2}}}{m^{\frac{3}{2}}} + O{{\left(\frac{1}{m^{\frac{9}{4}}}\right)}}\right)}}}{{{\left(\ell{{\left(\frac{\chi_2(Q_1\|Q_0)}{m} + O{{\left(\frac{1}{m^2}\right)}}\right)}}\right)}}^{\frac{3}{2}}}\displaybreak[0]\\
 &= Q{{\left(-\frac{1}{2} \sqrt{\frac{\ell \chi_2(Q_1\|Q_0)}{m} }\right)}} + \frac{1}{\sqrt{\ell}} + O{{\left(\frac{1}{\sqrt{n}}\right)}},\end{aligned}$$ where $(a)$ follows from Lemma \[lm:A-moments\] in the Appendix. Analogously, we can obtain $$\begin{aligned}
{{\mathbb{P}_{}}{\left(\sum_{i=1}^\ell {B}_i {\geqslant}0\right)}}  {\geqslant}Q{{\left(\frac{1}{2} \sqrt{\frac{\ell \chi_2(Q_1\|Q_0)}{m} }\right)}} - \frac{1}{\sqrt{\ell}} + O{{\left(\frac{1}{\sqrt{n}}\right)}},\label{eq:q0-log-ratio}\end{aligned}$$ and therefore, we have .

To lower-bound $\beta_{\alpha}( Q_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}, {P_{\textbf{Z}, \text{PPM}}^{n, \ell}})$, we use the Neyman-Pearson lemma, which states that if $\alpha {\leqslant}{{\mathbb{P}_{}}{\left(\log \frac{{P_{\textbf{Z}, \text{PPM}}^{n, \ell}}({\mathbf{Z}})}{Q_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}({\mathbf{Z}})} {\geqslant}\gamma\right)}}$ for some $\gamma$, then we have $\beta_{\alpha}( Q_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}, {P_{\textbf{Z}, \text{PPM}}^{n, \ell}}) {\geqslant}{{\mathbb{P}_{}}{\left(\log \frac{{P_{\textbf{Z}, \text{PPM}}^{n, \ell}}(\widetilde{\mathbf{Z}})}{Q_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}(\widetilde{\mathbf{Z}})} {\leqslant}\gamma\right)}}$ where $\mathbf{Z}$ and $\widetilde{\mathbf{Z}}$ are defined as before. Using Theorem \[Berry-Esseen\] again, similar to , we obtain $$\begin{aligned}
{{\mathbb{P}_{}}{\left(\log \frac{{P_{\textbf{Z}, \text{PPM}}^{n, \ell}}({\mathbf{Z}})}{Q_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}({\mathbf{Z}})} {\geqslant}\gamma\right)}} {\geqslant}Q{{\left(\frac{\gamma + \frac{\ell \chi_2(Q_1\|Q_0)}{2m}}{\sqrt{\frac{\ell \chi_2(Q_1\|Q_0)}{m}}}\right)}} - \frac{1}{\sqrt{\ell}} + O{{\left(\frac{1}{\sqrt{n}}\right)}}.\end{aligned}$$ Accordingly, to ensure that ${{\mathbb{P}_{}}{\left(\log \frac{{P_{\textbf{Z}, \text{PPM}}^{n, \ell}}({\mathbf{Z}})}{Q_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}({\mathbf{Z}})} {\leqslant}\gamma\right)}} {\geqslant}\alpha$, we choose $\gamma = \sqrt{\frac{\ell \chi_2(Q_1\|Q_0)}{m}} Q^{-1}{{\left(\alpha + \frac{1}{\sqrt{\ell}}\right)}} -\frac{\ell\chi_2(Q_1\|Q_0)}{2m} + O{{\left(\frac{1}{\sqrt{n}}\right)}}$. Thus, we have $$\begin{aligned}
\beta_{\alpha}( Q_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}, {P_{\textbf{Z}, \text{PPM}}^{n, \ell}}) 
&{\geqslant}{{\mathbb{P}_{}}{\left(\log \frac{{P_{\textbf{Z}, \text{PPM}}^{n, \ell}}(\widetilde{\mathbf{Z}})}{Q_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}(\widetilde{\mathbf{Z}})} {\leqslant}\sqrt{\frac{\ell \chi_2(Q_1\|Q_0)}{m}} Q^{-1}{{\left(\alpha + \frac{1}{\sqrt{\ell}}\right)}} -\frac{\ell\chi_2(Q_1\|Q_0)}{2m} + O{{\left(\frac{1}{\sqrt{n}}\right)}}\right)}}\\
&{\geqslant}Q{{\left(\frac{-\sqrt{\frac{\ell \chi_2(Q_1\|Q_0)}{m}} Q^{-1}{{\left(\alpha + \frac{1}{\sqrt{\ell}}\right)}} +\frac{\ell\chi_2(Q_1\|Q_0)}{2m} + \frac{\ell \chi_2(Q_1\|Q_0)}{2m}}{\sqrt{\frac{\ell \chi_2(Q_1\|Q_0)}{m}}}\right)}} - \frac{1}{\sqrt{\ell}} + O{{\left(\frac{1}{\sqrt{n}}\right)}}\\
&= Q{{\left(\sqrt{\frac{\ell \chi_2(Q_1\|Q_0)}{m}} - Q^{-1}{{\left(\alpha + \frac{1}{\sqrt{\ell}}\right)}}\right)}} - \frac{1}{\sqrt{\ell}} + O{{\left(\frac{1}{\sqrt{n}}\right)}}.\end{aligned}$$

Converse {#sec:generic-converse}
--------

We now develop a generic converse for a quasi-metric $d$. The following result states that the number of covert and reliable bits that one can transmit may be characterized by establishing an upper bound on the weight of codewords. Such upper bounds are metric-specific, and we develop them in subsequent sections.

\[thm:converse-general\] Let $d$ be a quasi-metric and $({{\mathcal{X}}}, W_{Y|X}, W_{Z|X}, {{\mathcal{Y}}}, {{\mathcal{Z}}})$ be a . If there exists <span><span> a function $g:\mathbb{R} \to \mathbb{R}$</span></span> such that for every $(M, K, n, \epsilon, \delta)_d$ constant composition code $\mathcal{C}$ with weight $w_n$ we have $$\begin{aligned}
\label{eq:wt-condition-metric}
w_n {\leqslant}g(\delta) + \frac{C}{\sqrt{n}},\end{aligned}$$ then $$\begin{aligned}
\log M^{\text{cc}}_d(n, \epsilon, \delta) {\leqslant}g(\delta)D_P n^{\frac{1}{2}} - \sqrt{g(\delta)V_P} Q^{-1}(\epsilon)n^{\frac{1}{4}} + \log (\sqrt{n}g(\delta)+C)  + O(1).\end{aligned}$$ <span><span> In addition, if for every $(M_n, K_n, n, \epsilon, \delta)_d$ code in a sequence $\{{{\mathcal{C}}}_n\}$ of increasing length $n$ such that $\lim_{n\rightarrow\infty}\epsilon_n=0$, there exists a non-empty subset of codewords $\mathcal{D}_n\subset{{\mathcal{C}}}_n$ with $$\begin{aligned}
\label{eq:wt-condition-metric-first-order}
\frac{\max_{\textbf{x} \in\mathcal{D}_n} {\ensuremath{\mbox{wt}(\textbf{x})}}}{\sqrt{n}} {\leqslant}g(\delta) + o(1),\quad \frac{M_nK_n}{{\ensuremath{\left|{{{\mathcal{D}}}_n}\right|}}}=o\left(\frac{1}{\epsilon_n}\right),\quad \text{ and } \log\frac{M_nK_n}{{\ensuremath{\left|{{{\mathcal{D}}}_n}\right|}}}=o\left(\sqrt{n}\right).\end{aligned}$$ Then, $$\begin{aligned}
  \lim_{\epsilon\rightarrow 0}\lim_{n\rightarrow\infty} \frac{\log M^*_d(n,\epsilon,\delta)}{\sqrt{n}}=g(\delta).\end{aligned}$$</span></span>

Let $\mathcal{C}$ be an $(M, K, n, \epsilon, \delta)_d$ constant composition code whose codewords are of weight $w_n$. Since ${{\mathcal{C}}}$ is a constant composition code, for any $\mathbf{x}\in{{\mathcal{X}}}^n$ with ${\ensuremath{\mbox{wt}(\mathbf{x})}} = w_n$, @Polyanskiy2010 [Theorem 28] yields that $$\begin{aligned}
\log M &{\leqslant}-\log \beta_{\epsilon}\left(W_{\mathbf{Y}|\textbf{X} = \textbf{x}}, P_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}\right).\end{aligned}$$ Furthermore, similar to @Yang2016, by @Polyanskiy2010 [Equation 102], we obtain for any $\gamma$ $$\begin{aligned}
-{{\color{black} \log}}\beta_{\epsilon}\left(W_{\mathbf{Y}|\textbf{X} = \textbf{x}}, P_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}\right) {\leqslant}\gamma - \log \left(1-\epsilon - {{\mathbb{P}_{W_{\textbf{Y}|\textbf{X} = \textbf{x}}}}{\left(\log \frac{W_{\textbf{Y}|\textbf{X}}(\textbf{Y}|\textbf{x})}{P_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}(\textbf{Y})} {\geqslant}\gamma\right)}}\right).\end{aligned}$$ However, we know that $W_{\textbf{Y}|\textbf{X}}(\textbf{Y}|\textbf{x}) = \prod_{k: x_k = 1} P_1(Y_k) \prod_{j:x_j = 0} P_0(Y_j)$, which implies that if $\tilde{Y}_1, \cdots, \tilde{Y}_{w_n}$ are according to $P_1$, then $$\begin{aligned}
 {{\mathbb{P}_{W_{\textbf{Y}|\textbf{X} = \textbf{x}}}}{\left(\log \frac{W_{\textbf{Y}|\textbf{X}}(\textbf{Y}|\textbf{x})}{P_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}(\textbf{Y})} {\geqslant}\gamma\right)}} = {{\mathbb{P}_{P_{{{\color{black} 1}}}^{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}w}}}{\left(\sum_{k=1}^{w_n} \log \frac{P_1(\tilde{Y}_k)}{P_0(\tilde{Y}_k)} {\geqslant}\gamma\right)}}.\end{aligned}$$ By Theorem \[Berry-Esseen\], we have $$\begin{aligned}
{{\mathbb{P}_{}}{\left(\sum_{k=1}^{w_n} \log \frac{P_1(\tilde{Y}_k)}{P_0(\tilde{Y}_k)} {\geqslant}\gamma\right)}} {\leqslant}Q\left(\frac{\gamma - w_n D_P}{\sqrt{{w_n}V_P}}\right) + \frac{B}{\sqrt{w_n}},\end{aligned}$$ where $B$ just depends on the channel. Setting $\gamma = w_nD_P + \sqrt{w_nV_P} Q^{-1}(1 - \epsilon - \frac{2B}{\sqrt{w_n}})$ and combining all above equations, we have $$\begin{aligned}
\log M
&{\leqslant}w_n D_P + \sqrt{w_nV_P}Q^{-1}\left(1-\epsilon - \frac{2B}{\sqrt{w_n}}\right ) -\log \left(\frac{B}{\sqrt{w_n}}\right)\\
&=  w_n D_P + \sqrt{w_nV_P}Q^{-1}\left(1-\epsilon\right ) -\log \left(\frac{B}{\sqrt{w_n}}\right) + O(1). \label{eq:logM_w}\end{aligned}$$

Since $w_n{\leqslant}\sqrt{n}g(\delta) + C$, this completes the converse proof. Note that we need not worry about exotic channels for $\epsilon\in(\frac{1}{2},1)$ since the constants $D_P$ and $V_P$ are known and fixed.

Consider now a sequence of $(M_n,K_n,n,\epsilon_n,\delta)$ code for which subsets ${{\mathcal{D}}}_n\subset {{\mathcal{C}}}_n$ exist and  holds. Recall that $\epsilon_n$ is defined as per . By the pigeon hole principle, for every $n$, there exists a sub-codebook ${{\mathcal{C}}}_n(s)$ consisting of all codewords indexed by the same key $s\in{\ensuremath{\llbracket{1},{K_n}\rrbracket}}$, such that ${\ensuremath{\left|{{{\mathcal{C}}}_n(s)\cap{{\mathcal{D}}}_n}\right|}}{\geqslant}\frac{{\ensuremath{\left|{{{\mathcal{D}}}_n}\right|}}}{K_n}$. For the sub-codebook ${{\mathcal{C}}}_n(s)\cap{{\mathcal{D}}}_n$, the average probability of error $\eta_{_n}$ satisfies $$\begin{aligned}
    \eta_{n}{\leqslant}\frac{M_nK_n}{{\ensuremath{\left|{{{\mathcal{D}}}_n}\right|}}}\epsilon_n
  \end{aligned}$$ Following the exact same converse steps as in @Bloch2016a [Section VI], we obtain for $n$ large enough that $$\begin{aligned}
  \log {\ensuremath{\left|{{{\mathcal{C}}}_n(s)\cap{{\mathcal{D}}}_n}\right|}} {\leqslant}\frac{1}{1-\eta_n}\left(\sqrt{n}\left(g(\delta)+o(1)\right) + {{\mathbb{H}_b}\left(\eta_n\right)}\right). \end{aligned}$$ Consequently, $$\begin{aligned}
  \log M_n &= \log {\ensuremath{\left|{{{\mathcal{C}}}_n(s)\cap{{\mathcal{D}}}_n}\right|}} + \log\frac{M_nK_n}{{\ensuremath{\left|{{{\mathcal{D}}}_n}\right|}}}\\
           &{\leqslant}\frac{1}{1-\frac{M_nK_n}{{\ensuremath{\left|{{{\mathcal{D}}}_n}\right|}}}\epsilon_n}\left(\sqrt{n}\left(g(\delta)+o(1)\right) + {{\mathbb{H}_b}\left(\frac{M_nK_n}{{\ensuremath{\left|{{{\mathcal{D}}}_n}\right|}}}\epsilon_n\right)}\right)+\log\frac{M_nK_n}{{\ensuremath{\left|{{{\mathcal{D}}}_n}\right|}}}\end{aligned}$$ and $$\begin{aligned}
  \lim_{n\rightarrow\infty} \frac{\log M_n}{\sqrt{n}} = g(\delta). \end{aligned}$$

Covert Communication with specific covertness metrics {#sec:covert-comm-with}
=====================================================

We now leverage the general results established in Section \[sec:covert-comm-results\] and specialize them to study three covertness metrics: relative entropy (Subsection \[sec:covert-comm-with-kl\]), variational distance (Subsection \[sec:secon-order-covert-tv\]), and probability of missed detection (Subsection \[sec:covert-comm-missed-detection\]). As alluded to earlier, all that needs to be done is: (i) establish that the metric under consideration is a quasi metric, as defined at the beginning of Section \[sec:covert-comm-results\]; (ii) verify that the conditions of Theorem \[thm:general\_achv\] and Theorem \[thm:converse-general\] are satisfied.

Covertness in relative entropy {#sec:covert-comm-with-kl}
------------------------------

In this subsection, we prove Theorem \[th:main\_result\_d\].

Relative entropy is a quasi-metric, i.e., $$\begin{aligned}
\forall P, Q, R:\quad {{{\mathbb{D}}\!\left({R\Vert Q}\right)}} {\leqslant}{{{\mathbb{D}}\!\left({P\Vert Q}\right)}} + {{{\mathbb{D}}\!\left({R\VertP}\right)}}+\sqrt{{{{\mathbb{D}}\!\left({R\VertP}\right)}}}\max\left(1,\log \frac{1}{\min_z Q(z)}\right).\end{aligned}$$

Note that $$\begin{aligned}
{{{\mathbb{D}}\!\left({R\Vert Q}\right)}} &= \sum_z R(z) \log \frac{R(z)}{Q(z)}\displaybreak[0]\\
&=  \sum_z R(z) \log \frac{R(z)}{P(z)}+ \sum_z R(z) \log \frac{P(z)}{Q(z)}\displaybreak[0]\\
&= {{{\mathbb{D}}\!\left({R\VertP}\right)}} + \sum_z R(z) \log \frac{P(z)}{Q(z)}\displaybreak[0]\\
&= {{{\mathbb{D}}\!\left({R\VertP}\right)}} + {{{\mathbb{D}}\!\left({P\VertQ}\right)}} + \sum_z (R(z) - P(z))\log \frac{P(z)}{Q(z)}\displaybreak[0]\\
&{\leqslant}{{{\mathbb{D}}\!\left({R\VertP}\right)}} + {{{\mathbb{D}}\!\left({P\VertQ}\right)}} + \log \frac{1}{\min_z Q(z)} {{{\mathbb{V}}\!\left(R, P\right)}}\displaybreak[0]\\
&{\leqslant}{{{\mathbb{D}}\!\left({R\VertP}\right)}} + {{{\mathbb{D}}\!\left({P\VertQ}\right)}} + \sqrt{{{{\mathbb{D}}\!\left({R\Vert P}\right)}}}\log \frac{1}{\min_z Q(z)}\displaybreak[0]\\
&{\leqslant}{{{\mathbb{D}}\!\left({P\Vert Q}\right)}} + {{{\mathbb{D}}\!\left({R\VertP}\right)}}+\sqrt{{{{\mathbb{D}}\!\left({R\VertP}\right)}}}\max\left(1,\log \frac{1}{\min_z Q(z)}\right).\end{aligned}$$

\[<span><span> Achievability of Theorem \[th:main\_result\_d\]</span></span>\] Fix $\epsilon \in ]0, 1[$ and $\delta > 0$, and define $\omega {\ensuremath{\triangleq}}\sqrt{\frac{2\delta}{\chi_2(Q_1\|Q_0)}}$ and $\ell_n {\ensuremath{\triangleq}}\lfloor \omega \sqrt{n} -t \rfloor$ where the value of $t$ will be determined later. To use Theorem \[thm:general\_achv\], we choose $P_\textbf{X}^n {\ensuremath{\triangleq}}{P_{\textbf{X}, \text{PPM}}^{n, \ell_n}}$, and we set $$\begin{aligned}
\log M_ n &{\ensuremath{\triangleq}}\ell_n D_P - \sqrt{\ell_n V_P}Q^{-1}\left(\epsilon - \frac{1+6T_P/V_P^{\frac{3}{2}}}{\sqrt{\ell_n} }\right) - 2\log n\\
&= \omega D_P n ^{\frac{1}{2}} - \sqrt{\omega V_P}Q^{-1}\left(\epsilon\right)n^{\frac{1}{4}} - 2\log n + O(1),\end{aligned}$$ and $$\begin{aligned}
\log M_n + \log K_n &{\ensuremath{\triangleq}}\max(\log M_n, (1+\rho) \ell_n D_Q)\\
&= \max(\log M_n, (1+\rho) \omega D_Q n^{\frac{1}{2}} + O(1)).\end{aligned}$$ By Lemma \[lm:div\_ppm\], we know that $$\begin{aligned}
{{{\mathbb{D}}\!\left({{P_{\textbf{Z}, \text{PPM}}^{n, \ell_n}}\VertQ_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}}\right)}} &{\leqslant}\frac{\ell_n^2}{2n}\chi_2(Q_1\|Q_0) + \frac{\ell_n^3C}{n^2}\\
&{\leqslant}\frac{(\omega\sqrt{n} - t)^2}{2n}\chi_2(Q_1\|Q_0) + \frac{(\omega\sqrt{n} - t)^3C}{n^2}\\
&{\leqslant}\frac{1}{2}\omega^2\chi_2(Q_1\|Q_0) - \frac{t\omega \chi_2(Q_1\|Q_0)}{\sqrt{n}} + \frac{t^2\chi_2(Q_1\|Q_0)}{2n} + \frac{\omega^3C}{\sqrt{n}}\\
&\stackrel{(a)}{{\leqslant}} \frac{1}{2}\omega^2\chi_2(Q_1\|Q_0) - \frac{1}{\sqrt{n}}, \end{aligned}$$ where $(a)$ is true for $t$ and $n$ large enough. Furthermore, by Lemma \[lm:expected\_ration\_ppm\], we have $$\begin{aligned}
{{\mathbb{E}_{{P_{\textbf{Y}, \text{PPM}}^{n, \ell_n}}}}{\left(\frac{{P_{\textbf{Y}, \text{PPM}}^{n, \ell_n}}(\textbf{Y})}{P_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}(\textbf{Y})}\right)}}&{\leqslant}\exp\left(\frac{\ell_n(\ell_n+1)}{n}\chi_2(P_1\|P_0)\right) = O(1).\end{aligned}$$ Hence, for large enough $n$, we have $$\begin{gathered}
F_{\textbf{X}\textbf{Y}|P_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}}\left(\log \left(n^2M_n\right)\right) +\frac{1+{{\mathbb{E}_{{P_{\textbf{Y}, \text{PPM}}^{n, \ell_n}}}}{\left(\frac{{P_{\textbf{Y}, \text{PPM}}^{n, \ell_n}}(\textbf{Y})}{P_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}(\textbf{Y})}\right)}}}{n}\\
\begin{split}
 &= F_{\textbf{X}\textbf{Y}|P_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}}\left( \ell_n D_P - \sqrt{\ell_n V_P}Q^{-1}\left(\epsilon - \frac{1+6T_P/V_P^{\frac{3}{2}}}{\sqrt{\ell_n} }\right) \right)  + O\left(\frac{1}{n}\right)\\
&\stackrel{(a)}{{\leqslant}}Q\left(\frac{\ell_n D_P -  \ell_n D_P + \sqrt{\ell_n V_P}Q^{-1}\left(\epsilon - \frac{1+6T_P/V_P^{\frac{3}{2}}}{\sqrt{\ell_n} }\right) }{\sqrt{\ell_nV_P}}\right) + \frac{6T_P}{\sqrt{\ell_n V_P^3}} + O\left(\frac{1}{n}\right)\\
&{\leqslant}\epsilon,
\end{split}\label{eq:bound_f_xy_div}\end{gathered}$$ where $(a)$ follows from Lemma \[lm:F\_XY\_bound\]. By Lemma \[lm:F\_XZ\_bound\], we have $$\begin{aligned}
\overline{F}_{\textbf{X}\textbf{Z}}\left(\log \frac{M_nK_n}{n^4}\right) &{\leqslant}\exp\left(-\frac{\left(\log \frac{M_nK_n}{n^4}-\ell_n D_Q\right)^2}{2\ell_n\log^2\mu_Z}\right)\displaybreak[0]\\
&{\leqslant}\exp\left(-\frac{\left( (1+\rho) \ell _n D_Q - 4\log n-\ell_n D_Q\right)^2}{2\ell_n\log^2\mu_Z}\right)\displaybreak[0]\\
&{\leqslant}\exp\left(-\frac{\ell_n\left( \rho D_Q - 4\log n / \ell_n \right)^2}{2\log^2\mu_Z}\right)\\
&\stackrel{(a)}{{\leqslant}} \frac{1}{n^6},\end{aligned}$$ where $(a)$ is true for large enough $n$. Thus, all the conditions in Theorem \[thm:general\_achv\] hold, and we obtain $$\begin{aligned}
\log M^*_D(n, \epsilon, \delta) {\geqslant}\log M^\text{cc}_D(n, \epsilon, \delta) {\geqslant}\omega D_P n ^{\frac{1}{2}} - \sqrt{\omega V_P}Q^{-1}\left(\epsilon\right)n^{\frac{1}{4}} - 2\log n + O(1).\end{aligned}$$

\[<span><span> Converse of Theorem \[th:main\_result\_d\]</span></span>\] <span><span> For an $(M, K, n, \epsilon, \delta)_D$ code, we reproduce for completeness the argument of @Bloch2016a to obtain an upper-bound on the average weight of the codewords. Note that, by @Bloch2016a [Equation (96)], $$\begin{aligned}
\delta {\geqslant}{{{\mathbb{D}}\!\left({\widehat{P}_{\mathbf{Z}}\VertQ_0^n}\right)}}
\stackrel{(a)}{{\geqslant}} n{{{\mathbb{D}}\!\left({\overline{P}_Z\VertQ_0}\right)}},\end{aligned}$$ where $\overline{P}_Z(z) {\ensuremath{\triangleq}}\frac{1}{n} \widehat{P}_{Z_i}(z)$. We know that $\overline{P}_Z = Q_{\mu}$ for $\mu {\ensuremath{\triangleq}}\frac{1}{MK} \sum_{w\in{\ensuremath{\llbracket{1},{M}\rrbracket}}, s\in {\ensuremath{\llbracket{1},{K}\rrbracket}}} \frac{{\ensuremath{\mbox{wt}(\mathbf{x}_{s, w})}}}{n}$. Therefore, by @Bloch2016a [Equation (11)], we have $$\begin{aligned}
{{{\mathbb{D}}\!\left({\overline{P}_Z\VertQ_0}\right)}} {\geqslant}\frac{\mu^2}{2}\chi_2(Q_1\|Q_0) - O(\mu^3).\end{aligned}$$ Combining these two bounds, we obtain $$\begin{aligned}
\frac{1}{MK}\sum_{s=1}^K\sum_{w=1}^M {\ensuremath{\mbox{wt}(\textbf{x}_{sw})}}{\leqslant}(B+\sqrt{n})\sqrt{\frac{2\delta}{\chi_2(Q_1\|Q_0)}},\end{aligned}$$ for some $B>0$ depending on the channel. If the code has constant composition then for every $(s,w)$ ${\ensuremath{\mbox{wt}(\textbf{x}_{sw})}}=w_n$ so that we obtain $$\begin{aligned}
\frac{w_n}{\sqrt{n}} {\leqslant}\left(\frac{B}{\sqrt{n}}+1\right)\sqrt{\frac{2\delta}{\chi_2(Q_1\|Q_0)}}.\end{aligned}$$ Applying Theorem \[thm:converse-general\] completes the converse proof for constant composition codes. The first-order converse for all codes was already established in @Bloch2016a [@Wang2016b] and is not duplicated here.</span></span>

Covertness with variational distance {#sec:secon-order-covert-tv}
------------------------------------

In this subsection, we prove Theorem \[th:main\_result\_tv\].

Total variation is a quasi-metric for distributions, i.e., for all distributions $P$, $Q$, and $R$ defined over <span><span> ${{\mathcal{Z}}}$</span></span>, we have $$\begin{aligned}
{{{\mathbb{V}}\!\left(R, Q\right)}} {\leqslant}{{{\mathbb{V}}\!\left(P, Q\right)}} + {{{\mathbb{D}}\!\left({R\VertQ}\right)}} + \sqrt{{{{\mathbb{D}}\!\left({R\VertP}\right)}}}\max\left(1,\log \frac{1}{\min_{{{\color{black} z}}} Q({{\color{black} z}})}\right).\end{aligned}$$

Total variation is a metric, and therefore we have $$\begin{aligned}
{{{\mathbb{V}}\!\left(R, Q\right)}} & {\leqslant}{{{\mathbb{V}}\!\left(P, Q\right)}} + {{{\mathbb{V}}\!\left(R, P\right)}}\\
&\stackrel{(a)}{{\leqslant}} {{{\mathbb{V}}\!\left(P, Q\right)}} + \sqrt{{{{\mathbb{D}}\!\left({R\VertP}\right)}}}\\
&{\leqslant}{{{\mathbb{V}}\!\left(P, Q\right)}} + {{{\mathbb{D}}\!\left({R\VertQ}\right)}} + \sqrt{{{{\mathbb{D}}\!\left({R\VertP}\right)}}}\max\left(1,\log \frac{1}{\min_{{{\color{black} z}}} Q({{\color{black} z}})}\right),\end{aligned}$$ where $(a)$ follows from Pinsker Inequality.

\[<span><span> Achievability of Theorem \[th:main\_result\_tv\]</span></span>\]

Fix $\epsilon, \delta \in ]0, 1[$ and $n$. Similar to the analysis for relative entropy, we use Theorem \[thm:general\_achv\] with $P_\textbf{X}^n {\ensuremath{\triangleq}}{P_{\textbf{X}, \text{PPM}}^{n, \ell_n}}$ where $\ell_n$ is chosen to ensure ${{{\mathbb{V}}\!\left({P_{\textbf{Z}, \text{PPM}}^{n, \ell_n}}, Q_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}\right)}}{\leqslant}\delta - \frac{1}{\sqrt{n}}$. Specifically, upon setting $\Gamma {\ensuremath{\triangleq}}Q^{-1}{{\left(\frac{1-\delta}{2}\right)}}$, we wish to choose $\ell_n$ such that $$\begin{aligned}
\label{eq:ell_bound1}
\frac{\ell_n}{2} \sqrt{\frac{\chi_2(Q_1\|Q_0)}{n}} {\geqslant}\Gamma -\frac{e^{\frac{\Gamma^2}{2}} \sqrt{2\pi}}{\sqrt{\ell_n}} + O{{\left(\frac{1}{\sqrt{n}}\right)}}.\end{aligned}$$ The term $\Gamma$ is what we would expect by inspection of (\[eq:v\_ppm\]) to obtain a variational distance with first order approximately $\delta$. As we shall see next, the penalty term $\frac{e^{\frac{\Gamma^2}{2}} \sqrt{2\pi}}{\sqrt{\ell_n}}$ is the result of a Taylor series of the $Q$ function around $\Gamma$. Formally, we choose $\sqrt{\ell_n}$ as a solution of the cubic equation $$\begin{aligned}
x^3 - 2{{\left(\Gamma + O{{\left(\frac{1}{\sqrt{n}}\right)}}\right)}}\sqrt{\frac{n}{\chi_2(Q_1\|Q_0)}} x + 2\sqrt{2\pi} e^{\frac{\Gamma^2}{2}} \sqrt{\frac{n}{\chi_2(Q_1\|Q_0)}} = 0,\end{aligned}$$ which will be sufficient to ensure . For a cubic equation of the form $x^3 - px + q = 0$, the roots are known in closed algebraic form and one of them is $2\sqrt{\frac{-p}{3}}\cos{{\left(\frac{1}{3}\arccos{{\left(\frac{3q}{2p} \sqrt{\frac{-3}{p}}\right)}}\right)}}$. Thus, $$\begin{aligned}
\sqrt{\ell_n} 
&= 2\sqrt{\frac{2{{\left(\Gamma + O{{\left(\frac{1}{\sqrt{n}}\right)}}\right)}}\sqrt{n}}{3\sqrt{\chi_2(Q_1\|Q_0)}}}\cos{{\left(\frac{1}{3}\arccos{{\left(-\frac{3\sqrt{2\pi} e^{\frac{\Gamma^2}{2}}}{2{{\left(\Gamma + O{{\left(\frac{1}{\sqrt{n}}\right)}}\right)}}} \sqrt{\frac{3\sqrt{\chi_2(Q_1\|Q_0)}}{2{{\left(\Gamma+O{{\left(\frac{1}{\sqrt{n}}\right)}}\right)}}\sqrt{n}}}\right)}}\right)}}\displaybreak[0]\\
&\stackrel{(a)}{=}2\sqrt{\frac{2{{\left(\Gamma + O{{\left(\frac{1}{\sqrt{n}}\right)}}\right)}}\sqrt{n}}{3\sqrt{\chi_2(Q_1\|Q_0)}}}\cos{{\left(\frac{1}{3}{{\left(\frac{\pi}{2} + \frac{3\sqrt{2\pi} e^{\frac{\Gamma^2}{2}}}{2\Gamma } \sqrt{\frac{3\sqrt{\chi_2(Q_1\|Q_0)}}{2\Gamma\sqrt{n}}} + O{{\left(\frac{1}{\sqrt{n}}\right)}}\right)}}\right)}}\displaybreak[0]\\
&\stackrel{(b)}{=}  2\sqrt{\frac{2{{\left(\Gamma + O{{\left(\frac{1}{\sqrt{n}}\right)}}\right)}}\sqrt{n}}{3\sqrt{\chi_2(Q_1\|Q_0)}}} {{\left(\frac{\sqrt{3}}{2} -\frac{1}{2}\frac{\sqrt{2\pi} e^{\frac{\Gamma^2}{2}}}{2\Gamma } \sqrt{\frac{3\sqrt{\chi_2(Q_1\|Q_0)}}{2\Gamma\sqrt{n}}} + O{{\left(\frac{1}{\sqrt{n}}\right)}}\right)}}\\
&= \sqrt{\frac{2\Gamma\sqrt{n}}{\sqrt{\chi_2(Q_1\|Q_0)}}} - \sqrt{\frac{\pi}{2}}\frac{ e^{\frac{\Gamma^2}{2}}}{\Gamma} + O{{\left(\frac{1}{n^{\frac{1}{4}}}\right)}},\label{eq:sq_ell_v}\end{aligned}$$ where $(a)$ and $(b)$ follow since, for $x$ close to zero, $\arccos(x) = \frac{\pi}{2} - x + O(x^2)$ and $\cos{{\left(\frac{\pi}{6} + x\right)}} = \frac{\sqrt{3}}{2} - \frac{1}{2}x + O(x^2)$, respectively. Consequently, upon choosing $$\begin{aligned}
\ell_n = 2 \Gamma \sqrt{\frac{n}{\chi_2(Q_1\|Q_0)}} - \frac{2\sqrt{\pi} e^{\frac{\Gamma^2}{2}} n^{\frac{1}{4}}}{\sqrt{\Gamma} \chi_2(Q_1\|Q_0)^{\frac{1}{4}}}  + O{{\left(1\right)}},\end{aligned}$$ we satisfy . Combining with , we have $$\begin{aligned}
{{{\mathbb{V}}\!\left({P_{\textbf{Z}, \text{PPM}}^{n, \ell_n}}, Q_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}\right)}} 
&{\leqslant}1-2Q{{\left(\frac{\ell_n}{2} \sqrt{\frac{\chi_2(Q_1\|Q_0)}{n}}\right)}} + \frac{2}{\sqrt{\ell_n}} + O{{\left(\frac{1}{\sqrt{n}}\right)}}\\
&{\leqslant}1-2Q{{\left(\Gamma -\frac{e^{\frac{\Gamma^2}{2}} \sqrt{2\pi}}{\sqrt{\ell_n}} + O{{\left(\frac{1}{\sqrt{n}}\right)}}\right)}} + \frac{2}{\sqrt{\ell_n}}+ O{{\left(\frac{1}{\sqrt{n}}\right)}}\\
&\stackrel{(a)}{{\leqslant}} 1 - 2Q(\Gamma) - \frac{2}{\sqrt{\ell_n}} + \frac{2}{\sqrt{\ell_n}} + O{{\left(\frac{1}{\sqrt{n}}\right)}}\\
&= \delta + O{{\left(\frac{1}{\sqrt{n}}\right)}},  \label{eq:v_bound_ppm}\end{aligned}$$ where $(a)$ follows from $Q(x - y) {\geqslant}Q(x) + \frac{e^{-\frac{x^2}{2}}y}{\sqrt{2\pi}}$ for $x {\geqslant}y {\geqslant}0$. Finally, we can control the term $O{{\left(\frac{1}{\sqrt{n}}\right)}}$ in to guarantee that is less than $\delta - \frac{1}{\sqrt{n}}$.

Finally, let $$\begin{aligned}
\log M_ n &{\ensuremath{\triangleq}}\ell_n D_P - \sqrt{\ell_n V_P}Q^{-1}\left(\epsilon - \frac{1+6T_P/V_P^{\frac{3}{2}}}{\sqrt{\ell_n} }\right) - 2\log n\end{aligned}$$ and for some $\rho > 0$, $$\begin{aligned}
\log M_n + \log K_n &{\ensuremath{\triangleq}}\max(\log M_n, (1+\rho) \ell_n D_Q).\end{aligned}$$ Similar to , we can show that, for large enough $n$, $$\begin{aligned}
F_{\textbf{X}\textbf{Y}|P_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}}\left(\log \left(n^2M_n\right)\right) +\frac{1+{{\mathbb{E}_{{P_{\textbf{Y}, \text{PPM}}^{n, \ell_n}}}}{\left(\frac{{P_{\textbf{Y}, \text{PPM}}^{n, \ell_n}}(\textbf{Y})}{P_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}(\textbf{Y})}\right)}}}{n} {\leqslant}\epsilon,\end{aligned}$$ and $$\begin{aligned}
\overline{F}_{\textbf{X}\textbf{Z}}\left(\log \frac{M_nK_n}{n^4}\right)  {\leqslant}\frac{1}{n^6}.\end{aligned}$$ Thus, all the conditions in Theorem \[thm:general\_achv\] hold, and we obtain $$\begin{aligned}
  \log M^*_V(n, \epsilon, \delta) &{\geqslant}\log M^\text{cc}_V(n, \epsilon, \delta)\\
  &{\geqslant}\ell_n D_P - \sqrt{\ell_n V_P}Q^{-1}\left(\epsilon\right) - 2\log n + O(1)\\
&=  \frac{2\Gamma D_Pn^{\frac{1}{2}}}{\sqrt{\chi_2(Q_1\|Q_0)}} - {{\left(\sqrt{ \frac{2\Gamma  V_P}{\sqrt{\chi_2(Q_1\|Q_0)}}}Q^{-1}\left(\epsilon\right) +\frac{2\sqrt{\pi}e^{\frac{\Gamma^2}{2}}D_P}{\sqrt{\Gamma} \chi_2(Q_1\|Q_0)^{\frac{1}{4}}} \right)}}n^{\frac{1}{4}}- 2\log n + O(1).\end{aligned}$$

To develop the converse for variational distance, we start by relating the variational distance ${{{\mathbb{V}}\!\left(\widehat{P}_\textbf{Z}, Q_0^{{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}}\right)}} $ to the minimum weight of the codewords.

\[lm:converse-wmin\] Consider a binary-input $({{\mathcal{X}}}, W_{Z|X}, {{\mathcal{Z}}})$ and $M$ codewords $\textbf{x}_1, \cdots, \textbf{x}_M\in\mathcal{X}^n$ with induced distribution $\widehat{P}_\textbf{Z}$ on $\mathcal{Z}^n$. If $w_{\min} {\ensuremath{\triangleq}}\min_{m\in {\ensuremath{\llbracket{1},{M}\rrbracket}}}{\ensuremath{\mbox{wt}(\textbf{x}_m)}}$, then we have $$\begin{aligned}
{{{\mathbb{V}}\!\left(\widehat{P}_\textbf{Z}, Q_0^{{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}}\right)}} {\geqslant}1 - 2Q\left(\frac{w_{\min}\sqrt{\chi_2(Q_1\|Q_0)}}{2\sqrt{n} }\right)- \frac{B}{\sqrt{n}} - \frac{w_{\min}^2B}{n^{\frac{3}{2}}},\end{aligned}$$ where $B$ is a constant that only depends on the channel.

To lower bound ${{{\mathbb{V}}\!\left(\widehat{P}_\textbf{Z}, Q_0^{{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}}\right)}}$, we introduce hypothesis testing problem with two hypotheses $H_0$ and $H_1$ corresponding to distributions $Q_0^{{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}}$ and $\widehat{P}_\textbf{Z}$, respectively. We know that for any test with probability of false alarm and missed detection $\alpha$ and $\beta$, respectively, we have $$\begin{aligned}
\label{eq:tv_ht}
{{{\mathbb{V}}\!\left(\widehat{P}_{\textbf{Z}}, Q_0^{{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}}\right)}} {\geqslant}1 - \alpha - \beta.\end{aligned}$$ Hence, to link the variational distance to the weight of codewords, it suffices to introduce a test for which $\alpha$ and $\beta$ conveniently relate to the weight of codewords. We consider here the sub-optimal test $$\begin{aligned}
T(\textbf{z}) {\ensuremath{\triangleq}}{\ensuremath{\mathds{1}\!\left\{\sum_{i=1}^n A(z_i) > \tau\right\}}},\end{aligned}$$ where $A(z) {\ensuremath{\triangleq}}\frac{Q_1(z) - Q_0(z)}{Q_0(z)}$ and $\tau$ is an arbitrary constant that is determined later. Intuitively, this test plays the same role for as the radiometer played for Gaussian channels @Bash2013 in that it only depends on the codeword weight. To bound the probability of false alarm, we use Theorem \[Berry-Esseen\] to obtain $$\begin{aligned}
\label{eq:fa_first}
{{\mathbb{P}_{H_0}}{\left(\sum_{i=1}^n A(Z_i) {\geqslant}\tau\right)}} & {\leqslant}Q\left(\frac{\tau - n \mu_0}{\sqrt{n}\sigma_0}\right) +\frac{6t_0}{\sigma_0^{{{\color{black} 3}}}\sqrt{n}},\end{aligned}$$ with $$\begin{aligned}
\label{eq:def_moments}
\mu_0 {\ensuremath{\triangleq}}{{\mathbb{E}_{Q_0}}{\left(A(Z)\right)}}, \quad\sigma_0^2 {\ensuremath{\triangleq}}\text{Var}_{Q_0}\left(A(Z)\right), \quad t_0 {\ensuremath{\triangleq}}{{\mathbb{E}_{Q_0}}{\left(|A(Z )-\mu_0|^3\right)}}.\end{aligned}$$ Note that all above quantities are finite. For the probability of missed detection, we condition on the codeword transmitted by the channel to obtain $$\begin{aligned}
{{\mathbb{P}_{H_1}}{\left(\sum_{i=1}^n A(Z_i) {\leqslant}\tau\right)}}&= \sum_{m=1}^M\frac{1}{M}{{\mathbb{P}_{}}{\left(\sum_{i=1}^n A(Z_i) {\leqslant}\tau |\textbf{X}=\textbf{x}_m\right)}} \\
& {\leqslant}\sum_{m=1}^M \frac{1}{M}\left( Q\left(\frac{-\tau + n \mu_0 + {\ensuremath{\mbox{wt}(\textbf{x}_m)}}(\mu_1-\mu_0)}{\sqrt{n\sigma_0^2 + {\ensuremath{\mbox{wt}(\textbf{x}_m)}}\left(\sigma_1^2-\sigma_0^2\right)}}\right)+\frac{6\left(t_0+{\ensuremath{\mbox{wt}(\textbf{x}_m)}}/n(t_1-t_0)\right)}{\left(\sigma_0^2+{\ensuremath{\mbox{wt}(\textbf{x}_m)}}/n(\sigma_1^2-\sigma_0^2)\right)^{3/2}\sqrt{n}}\right)\\
& {\leqslant}\sum_{m=1}^M \frac{1}{M}\left( Q\left(\frac{-\tau + n \mu_0 + {\ensuremath{\mbox{wt}(\textbf{x}_m)}}(\mu_1-\mu_0)}{\sqrt{n\sigma_0^2 + {\ensuremath{\mbox{wt}(\textbf{x}_m)}}\left(\sigma_1^2-\sigma_0^2\right)}}\right)\right) + \frac{B_1}{\sqrt{n}},\end{aligned}$$ with $$\begin{aligned}
\mu_1 {\ensuremath{\triangleq}}{{\mathbb{E}_{Q_1}}{\left(A(Z)\right)}}, \quad\sigma_1^2 {\ensuremath{\triangleq}}\text{Var}_{Q_1}\left(A(Z)\right), \quad t_1 {\ensuremath{\triangleq}}{{\mathbb{E}_{Q_1}}{\left(|A(Z )-\mu_1|^3\right)}}.\end{aligned}$$ If we choose $\tau = n\mu_0 + \frac{w_{\min}}{2}(\mu_1-\mu_0)$, we have $$\begin{aligned}
\label{eq:md_summation_cw}
{{\mathbb{P}_{H_1}}{\left(\sum_{i=1}^n A(Z_i) {\leqslant}\tau\right)}} {\leqslant}\sum_{m=1}^M \frac{1}{M}\left( Q\left(\frac{{\ensuremath{\mbox{wt}(\textbf{x}_m)}}(\mu_1-\mu_0)}{2\sqrt{n\sigma_0^2 + {\ensuremath{\mbox{wt}(\textbf{x}_m)}}\left(\sigma_1^2-\sigma_0^2\right)}}\right)\right) + \frac{B_1}{\sqrt{n}}.\end{aligned}$$ Note that if we have $\sigma_1 < \sigma_0$, then we get $$\begin{aligned}
\beta {\ensuremath{\triangleq}}{{\mathbb{P}_{H_1}}{\left(\sum_{i=1}^n A(Z_i) {\leqslant}\tau\right)}} {\leqslant}Q\left(\frac{w_{\min} (\mu_1 - \mu_0)}{2\sqrt{n} \sigma_0}\right)\end{aligned}$$ Otherwise, we split the summation in into two parts: if ${\ensuremath{\mbox{wt}(\textbf{x}_m)}} > \frac{\sigma_1}{\sigma_0} w_{\min}$, then we have $$\begin{aligned}
Q\left(\frac{{\ensuremath{\mbox{wt}(\textbf{x}_m)}}(\mu_1-\mu_0)}{2\sqrt{n\sigma_0^2 + {\ensuremath{\mbox{wt}(\textbf{x}_m)}}\left(\sigma_1^2-\sigma_0^2\right)}}\right) &\stackrel{(a)}{{\leqslant}} Q\left(\frac{\frac{\sigma_1}{\sigma_0}w_{\min}(\mu_1 - \mu_0)}{2\sqrt{n}\sigma_1}\right)\\
&= Q\left(\frac{w_{\min} (\mu_1 - \mu_0)}{2\sqrt{n} \sigma_0}\right),\end{aligned}$$ where $(a)$ follows from $\sigma_1 > \sigma_0$. If $w_{\min} {\leqslant}{\ensuremath{\mbox{wt}(\textbf{x}_m)}} {\leqslant}\frac{\sigma_1}{\sigma_0} w_{\min}$, then we obtain $$\begin{aligned}
Q\left(\frac{{\ensuremath{\mbox{wt}(\textbf{x}_m)}}(\mu_1-\mu_0)}{2\sqrt{n\sigma_0^2 + {\ensuremath{\mbox{wt}(\textbf{x}_m)}}\left(\sigma_1^2-\sigma_0^2\right)}}\right) &{\leqslant}Q\left(\frac{w_{\min}(\mu_1-\mu_0)}{2\sqrt{n\sigma_0^2 +\frac{\sigma_1}{\sigma_0} w_{\min}\left(\sigma_1^2-\sigma_0^2\right)}}\right)\\
&=  Q\left(\frac{w_{\min}(\mu_1-\mu_0)}{2\sqrt{n}\sigma_0}\left(\frac{1}{ \sqrt{1+\frac{\sigma_1}{\sigma_0^3}\frac{ w_{\min}}{n}\left(\sigma_1^2-\sigma_0^2\right)}}\right)\right)\\
&\stackrel{(a)}{{\leqslant}} Q\left(\frac{w_{\min}(\mu_1-\mu_0)}{2\sqrt{n}\sigma_0}\left(1 - \frac{w_{\min}B_2}{n}\right)\right)\\
&\stackrel{(b)}{{\leqslant}} Q\left(\frac{w_{\min}(\mu_1-\mu_0)}{2\sqrt{n}\sigma_0}\right) + \frac{w_{\min}^2 B_3}{n^{\frac{3}{2}}},\end{aligned}$$ for $B_2 =\frac{\sigma_1(\sigma_1^2-\sigma_0^2)}{2\sigma_0^3} > 0$ and $B_3 = \frac{(\mu_1-\mu_0)B_2}{2\sqrt{2\pi}\sigma_0} > 0$ where $(a)$ follows from $\frac{1}{\sqrt{1 + x}} {\geqslant}-\frac{x}{2}+1$ for all $x>0$, and $(b)$ follow from $Q(x-y) {\leqslant}Q(x) + \frac{y}{\sqrt{2\pi}}$ for all $0<y<x$. Therefore, we always have $$\begin{aligned}
\label{eq:md_prob}
\beta {\leqslant}Q\left(\frac{w_{\min}(\mu_1-\mu_0)}{2\sqrt{n}\sigma_0}\right) + \frac{w_{\min}^2 B_3}{n^{\frac{3}{2}}} + \frac{B_1}{\sqrt{n}}.\end{aligned}$$ Moreover, plugging in the value $\tau$ in , we obtain $$\begin{aligned}
\label{eq:fa_boudn}
\alpha{\ensuremath{\triangleq}}{{\mathbb{P}_{H_0}}{\left(\sum_{i=1}^n A(Z_i) {\geqslant}\tau\right)}} {\leqslant}Q\left(\frac{w_{\min}(\mu_1 - \mu_0)}{2\sqrt{n} \sigma_0}\right)+\frac{B_0}{\sqrt{n}},\end{aligned}$$ for some positive constant $B_0$. Using , , and , we obtain $$\begin{aligned}
{{{\mathbb{V}}\!\left(\widehat{P}_{\textbf{Z}}, Q_0^{{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}}\right)}} {\geqslant}1 - 2Q\left(\frac{w_{\min}(\mu_1 - \mu_0)}{2\sqrt{n} \sigma_0}\right) - \frac{B_0+B_1}{\sqrt{n}}- \frac{w_{\min}^2B_3}{n^{\frac{3}{2}}}.\end{aligned}$$ Finally, since $\mu_0 = 0$ and $\sigma_0^2  = \mu_1=\chi_2(Q_1\|Q_0)$, we have $$\begin{aligned}
{{{\mathbb{V}}\!\left(\widehat{P}_\textbf{Z}, Q_0^{{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}}\right)}} {\geqslant}1 - 2Q\left(\frac{w_{\min}\sqrt{\chi_2(Q_1\|Q_0)}}{2\sqrt{n} }\right)- \frac{B_0 + B_1}{\sqrt{n}} - \frac{w_{\min}^2B_3}{n^{\frac{3}{2}}}.\end{aligned}$$

We can now establish the converse for constant composition codes.

\[<span><span> Converse for constant composition codes of Theorem \[th:main\_result\_tv\]</span></span>\] <span><span> Letting $w_n$ be the codeword weight of the constant composition code $(M, K, n, \epsilon, \delta)_V$, we have by Lemma \[lm:converse-wmin\] that $$\begin{aligned}
\frac{w_n}{\sqrt{n}} &{\leqslant}\frac{2}{\sqrt{\chi_2(Q_1\|Q_0)}}Q^{-1}\left(\frac{1-\delta}{2}-\frac{C}{\sqrt{n}}\right)\\
&= \frac{2}{\sqrt{\chi_2(Q_1\|Q_0)}}Q^{-1}\left(\frac{1-\delta}{2}\right)+O\left(\frac{1}{\sqrt{n}}\right).\end{aligned}$$ Therefore, by Theorem \[thm:converse-general\], we have $$\begin{aligned}
\log M^\text{cc}_V(n, \epsilon, \delta) {\leqslant}\frac{2}{\sqrt{\chi_2(Q_1\|Q_0)}}Q^{-1}\left(\frac{1-\delta}{2}\right)D_Pn^{\frac{1}{2}}-\sqrt{\frac{2}{\sqrt{\chi_2(Q_1\|Q_0)}}Q^{-1}\left(\frac{1-\delta}{2}\right)V_P}Q^{-1}(\epsilon)n^{\frac{1}{4}} + O(\log n).\end{aligned}$$</span></span>

Next, we develop a bound for the maximum weight of a sub-codebook.

\[lm:wt-total-variation\] Let $\mathcal{C}$ be an $(M, K, n, \epsilon, \delta)_V$ code for a binary-input covert communication channel $({{\mathcal{X}}}, W_{Y|X}, W_{Z|X}, {{\mathcal{Y}}}, {{\mathcal{Z}}})$. For all $\gamma\in[0,1]$, there exists a subset of codewords $\mathcal{D}$ such that $|\mathcal{D}|{\geqslant}\gamma MK$ and $$\begin{aligned}
\label{eq:weight-condition}
\frac{1}{\sqrt{n}} \max\{{\ensuremath{\mbox{wt}(\textbf{x})}}: \textbf{x}\in \mathcal{D}\} {\leqslant}\frac{2}{\sqrt{\chi_2(Q_1\|Q_0)}}Q^{-1}\left(\frac{1-\delta}{2}-\frac{C}{\sqrt{n}}-\gamma\right),\end{aligned}$$ where $C$ is a constant that depends only on the channel.

We define $$\begin{aligned}
A {\ensuremath{\triangleq}}\frac{2}{\sqrt{\chi_2(Q_1\|Q_0)}}Q^{-1}\left(\frac{1-\delta}{2}-\frac{C_2}{\sqrt{n}}-\gamma\right)\end{aligned}$$ where $C_2 > 0$ is specified later and $\mathcal{D} {\ensuremath{\triangleq}}\{\textbf{x}\in \mathcal{C}: {\ensuremath{\mbox{wt}(\textbf{x})}} {\leqslant}A\sqrt{n}\}$. Clearly, $\mathcal{D}$ satisfies , and we just need to check $|\mathcal{D}|{\geqslant}\gamma MK$. To this end, let $\widehat{P}_1$ and $\widehat{P}_2$ be the induced output distributions for codes $\mathcal{D}$ and $\mathcal{C}\setminus \mathcal{D}$, respectively. Then, we have $$\begin{aligned}
\delta &\stackrel{(a)}{{\geqslant}} {{{\mathbb{V}}\!\left(\widehat{P}_\textbf{Z}, Q_0^{{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}}\right)}}\\
&\stackrel{(b)}{{\geqslant}} (1-\frac{|\mathcal{D}|}{MK}) {{{\mathbb{V}}\!\left(\widehat{P}_2, Q_0^{{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}}\right)}} - \frac{|\mathcal{D}|}{MK}  {{{\mathbb{V}}\!\left(\widehat{P}_1, Q_0^{{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}}\right)}}\\
&\stackrel{(c)}{{\geqslant}}(1-\frac{|\mathcal{D}|}{MK})\left(1- \frac{B(1+A^2)}{\sqrt{n}} -2 Q\left(\frac{A\sqrt{n}\sqrt{\chi_2(Q_1\|Q_0)}}{2\sqrt{n} }\right)\right)-\frac{|\mathcal{D}|}{MK}\\
&{\geqslant}\left(1- 2Q\left(\frac{A\sqrt{\chi_2(Q_1\|Q_0)}}{2}\right)\right) - \frac{B(1+A^2)}{\sqrt{n}}  - 2\frac{|\mathcal{D}|}{MK}\\
&\stackrel{(d)}{=}\left(1-2\left(\frac{1-\delta}{2}-\frac{C_2}{\sqrt{n}}-\gamma\right)\right)-\frac{B(1+A^2)}{\sqrt{n}}  - 2\frac{|\mathcal{D}|}{MK}\\
&\stackrel{(e)}{{\geqslant}}\delta + 2\gamma-2\frac{|\mathcal{D}|}{MK},\end{aligned}$$ where $(a)$ follows from the definition of an $(M, K, n, \epsilon, \delta)_V$ code, $(b)$ follows from the triangle inequality and $\widehat{P}_\textbf{Z} = \frac{|\mathcal{D}|}{MK} \widehat{P}_1 + (1-\frac{|\mathcal{D}|}{MK})\widehat{P}_2$, $(c)$ follows from Lemma \[lm:converse-wmin\], $(d)$ follows from the definition of $A$, and $(e)$ follows by choosing $$\begin{aligned}
C_2 >\frac{1}{2}B\left(1+\left(\frac{2}{\sqrt{\chi_2(Q_1\|Q_0)}}Q^{-1}\left(\frac{1-\delta}{2}-\gamma\right)\right)^2\right).\end{aligned}$$ Therefore, we get $|\mathcal{D}|{\geqslant}\gamma MK$.

\[Converse proof for all codes of Theorem \[th:main\_result\_tv\]\] <span><span> Lemma \[lm:wt-total-variation\] already ensures the upper bound needed to apply Theorem \[thm:converse-general\], and we only need to make sure that we can choose $\gamma$ in Lemma \[lm:wt-total-variation\] such that we can satisfy the other conditions in . For every $(M_n,K_n,n,\epsilon_n,\delta)_V$ code in a sequence of codes such that $\lim_{n\to\infty}\epsilon_n=0$, we choose $\gamma_n=\max(\sqrt{\epsilon_n},\frac{1}{n})$. Then, $$\begin{aligned}
      \lim_{n\to \infty}\gamma_n^{-1}\epsilon_n=0\text{ and }\lim_{n\to\infty}-\frac{\log \gamma_n}{\sqrt{n}}=0.  
    \end{aligned}$$ Hence, the results follows by Theorem \[thm:converse-general\].</span></span>

Covertness with probability of missed detection at fixed significance level {#sec:covert-comm-missed-detection}
---------------------------------------------------------------------------

In this subsection, we prove Theorem \[th:main\_result\_beta\].

For a fixed $\alpha\in]0,1[$ and two distributions $P$ and $Q$ over same set $\mathcal{Z}$, we define $d(P, Q) {\ensuremath{\triangleq}}1 - \alpha - \beta_\alpha(Q, P)$; then $d$ is a quasi-metric, and we have $$\begin{aligned}
d(R, Q) {\leqslant}d(P, Q) + {{{\mathbb{D}}\!\left({R\VertP}\right)}}+\sqrt{{{{\mathbb{D}}\!\left({R\VertP}\right)}}}\max\left(1,\log \frac{1}{\min_z Q(z)}\right).\end{aligned}$$

By definition of $\beta_\alpha(Q,R)$, there exists a set $\mathcal{T}$ with $Q(\mathcal{T}) {\leqslant}\alpha$ and $R(\mathcal{T}) = \beta_\alpha(Q, R)$; therefore we have $$\begin{aligned}
\beta_\alpha(Q, P) &{\leqslant}P(\mathcal{T})\\
&=R(\mathcal{T}) + (P(\mathcal{T}) - R(\mathcal{T})) \displaybreak[0]\\
&{\leqslant}R(\mathcal{T}) + {{{\mathbb{V}}\!\left(R, P\right)}}\\
&= \beta_\alpha(Q, R) + {{{\mathbb{V}}\!\left(R, P\right)}}.\end{aligned}$$ By Pinsker's Inequality, we obtain $$\begin{aligned}
\beta_\alpha(Q, R) + {{{\mathbb{V}}\!\left(R, P\right)}} &{\leqslant}\beta_\alpha(Q, R) + \sqrt{{{{\mathbb{D}}\!\left({R\VertP}\right)}}}.\end{aligned}$$ Finally, using the definition of $d(P, Q)$, we get the result.

\[<span><span> Achievability of Theorem \[th:main\_result\_beta\]</span></span>\] <span><span> Fix $\epsilon\in]0, 1[$, $\delta \in ]0, 1- \alpha$, and $n$; we just show how we can choose $\ell_n$ such that $\beta_{\alpha}(Q_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}, {P_{\textbf{Z}, \text{PPM}}^{n, \ell_n}}) {\geqslant}1 - \alpha - \delta + \frac{1}{\sqrt{n}}$ and the rest of the proof is similar to the proof for variational distance. Let $\Lambda {\ensuremath{\triangleq}}Q^{-1}(1-\alpha-\delta)$ and $\Upsilon {\ensuremath{\triangleq}}Q^{-1}(\alpha)$; we choose $\ell_n$ to satisfy $$\begin{aligned}
\label{eq:ell_beta}
\ell_n \sqrt{\frac{\chi_2(Q_1\|Q_0)}{n} } - Q^{-1}{{\left(\alpha + \frac{1}{\sqrt{\ell_n}}\right)}} {\leqslant}\Lambda - \frac{\sqrt{2\pi} e^{\frac{\Lambda^2}{2}}}{\sqrt{\ell_n}}  + O{{\left(\frac{1}{\sqrt{n}}\right)}}\end{aligned}$$ Using $Q^{-1}{{\left(\alpha + x\right)}} = Q^{-1}(\alpha)  - \sqrt{2\pi} e^{\frac{{{\left(Q^{-1}(\alpha)\right)}}^2}{2}}x + O(x^2) = \Upsilon +\sqrt{2\pi} e^{\frac{\Upsilon^2}{2}}x + O(x^2)$ for $x$ close to zero, the above inequality is equivalent to $$\begin{aligned}
\ell_n \sqrt{\frac{\chi_2(Q_1\|Q_0)}{n} } - \Upsilon + \frac{\sqrt{2\pi} e^{\frac{\Upsilon^2}{2}}}{\sqrt{\ell_n}} {\leqslant}\Lambda - \frac{\sqrt{2\pi} e^{\frac{\Lambda^2}{2}}}{\sqrt{\ell_n}}  + O{{\left(\frac{1}{\sqrt{n}}\right)}}.\end{aligned}$$ We form cubic equation $$\begin{aligned}
x^3  -{{\left(\Lambda + \Upsilon + O{{\left(\frac{1}{\sqrt{n}}\right)}}\right)}}\sqrt{\frac{n}{\chi_2(Q_1\|Q_0)}}x + \sqrt{2\pi}{{\left(e^{\frac{\Lambda^2}{2}} + e^{\frac{\Upsilon^2}{2}}\right)}}\sqrt{\frac{n}{\chi_2(Q_1\|Q_0)}}=0,\end{aligned}$$ and set $\sqrt{\ell_n}$ to be its solution; Thus, analogous to and, we obtain $$\begin{aligned}
\sqrt{\ell_n} 
&= 2\sqrt{\frac{{{\left(\Lambda + \Upsilon + O{{\left(\frac{1}{\sqrt{n}}\right)}}\right)}} \sqrt{n}}{3\sqrt{\chi_2(Q_1\|Q_0)}}}\cos{{\left(\frac{1}{3}\arccos{{\left(\frac{3\sqrt{2\pi} {{\left(e^{\frac{\Lambda^2}{2}}+ e^{\frac{\Upsilon^2}{2}}\right)}}}{-2{{\left(\Lambda + \Upsilon + O{{\left(\frac{1}{\sqrt{n}}\right)}}\right)}}}\sqrt{\frac{3\sqrt{\chi_2(Q_1\|Q_0)}}{{{\left(\Lambda + \Upsilon + O{{\left(\frac{1}{\sqrt{n}}\right)}}\right)}} \sqrt{n}}} \right)}}\right)}}\\
&= 2\sqrt{\frac{{{\left(\Lambda + \Upsilon + O{{\left(\frac{1}{\sqrt{n}}\right)}}\right)}} \sqrt{n}}{3\sqrt{\chi_2(Q_1\|Q_0)}}}\cos{{\left(\frac{1}{3}{{\left(\frac{\pi}{2}+\frac{3\sqrt{2\pi} {{\left(e^{\frac{\Lambda^2}{2}}+ e^{\frac{\Upsilon^2}{2}}\right)}}}{2{{\left(\Lambda + \Upsilon \right)}}}\sqrt{\frac{3\sqrt{\chi_2(Q_1\|Q_0)}}{{{\left(\Lambda + \Upsilon \right)}} \sqrt{n}}} + O{{\left(\frac{1}{\sqrt{n}}\right)}} \right)}}\right)}}\\
&= 2\sqrt{\frac{{{\left(\Lambda + \Upsilon + O{{\left(\frac{1}{\sqrt{n}}\right)}}\right)}} \sqrt{n}}{3\sqrt{\chi_2(Q_1\|Q_0)}}}{{\left(\cos{{\left(\frac{\pi}{6}\right)}}-\sin{{\left(\frac{\pi}{6}\right)}}\frac{\sqrt{2\pi} {{\left(e^{\frac{\Lambda^2}{2}}+ e^{\frac{\Upsilon^2}{2}}\right)}}}{2{{\left(\Lambda + \Upsilon \right)}}}\sqrt{\frac{3\sqrt{\chi_2(Q_1\|Q_0)}}{{{\left(\Lambda + \Upsilon \right)}} \sqrt{n}}} + O{{\left(\frac{1}{\sqrt{n}}\right)}} \right)}}\\
&= \sqrt{\frac{(\Lambda + \Upsilon) \sqrt{n}}{\sqrt{\chi_2(Q_1\|Q_0)}}} - \sqrt{\frac{\pi}{2}} \frac{e^{\frac{\Lambda^2}{2}} + e^{\frac{\Upsilon^2}{2}}}{\Lambda + \Upsilon} + O{{\left(\frac{1}{\sqrt{n}}\right)}}.\end{aligned}$$ Hence, if we choose $$\begin{aligned}
\ell_n = \frac{(\Lambda + \Upsilon)}{\sqrt{\chi_2(Q_1\|Q_0)}}n^{\frac{1}{2}} - \frac{\sqrt{2\pi}{{\left(e^{\frac{\Lambda^2}{2}} + e^{\frac{\Upsilon^2}{2}}\right)}}}{\sqrt{\Lambda + \Upsilon} \chi_2(Q_1\|Q_0) ^{\frac{1}{4}}} n^{\frac{1}{4}}  +O(1),\end{aligned}$$ then we have $$\begin{aligned}
\beta_{\alpha}(Q_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}, {P_{\textbf{Z}, \text{PPM}}^{n, \ell_n}}) 
&\stackrel{(a)}{{\geqslant}} Q{{\left(\ell_n\sqrt{\frac{\chi_2(Q_1\|Q_0)}{n}} - Q^{-1}{{\left(\alpha + \frac{1}{\ell_n}\right)}}\right)}} - \frac{1}{\sqrt{\ell_n}} + O{{\left(\frac{1}{\sqrt{n}}\right)}}\\
&\stackrel{(b)}{{\geqslant}} Q{{\left(\Lambda - \frac{\sqrt{2\pi} e^{\frac{\Lambda^2}{2}}}{\sqrt{\ell_n}}  + O{{\left(\frac{1}{\sqrt{n}}\right)}}\right)}} - \frac{1}{\sqrt{\ell_n}} + O{{\left(\frac{1}{\sqrt{n}}\right)}}\\
&\stackrel{(c)}{{\geqslant}} Q{{\left(\Lambda\right)}} + \frac{1}{\sqrt{\ell_n}} - \frac{1}{\sqrt{\ell_n}} + O{{\left(\frac{1}{\sqrt{n}}\right)}}\\
&= 1 - \alpha - \delta + O{{\left(\frac{1}{\sqrt{n}}\right)}},\end{aligned}$$ where $(a)$ follows from , $(b)$ follows from , and $(c)$ follows from $Q(\Lambda + x) = Q(\Lambda) + \frac{x}{\sqrt{2\pi} e^{\frac{\Lambda^2}{2}}} + O(x^2)$ for $x$ close to zero. </span></span>

The proof of the converse of Theorem \[th:main\_result\_beta\] requires the following steps similar to those of covertness with variational distance. We first relate the probability of missed detection $\beta_\alpha\left(Q_0^{{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}}, \widehat{P}_\textbf{Z}\right)$ at significance level $\alpha$ to the minimum weight of codewords.

\[lm:converse-wmin-beta\] Consider a binary-input $({{\mathcal{X}}}, W_{Z|X}, {{\mathcal{Z}}})$ and $M$ codewords $\textbf{x}_1, \cdots, \textbf{x}_M\in\mathcal{X}^n$ with induced distribution $\widehat{P}_\textbf{Z}$ on $\mathcal{Z}^n$. If $\frac{\sqrt{n}Q^{-1}(\alpha)}{\sqrt{\chi_2(Q_1\|Q_0)}}<w_{\min} {\ensuremath{\triangleq}}\min_{m\in {\ensuremath{\llbracket{1},{M}\rrbracket}}}{\ensuremath{\mbox{wt}(\textbf{x}_m)}}$, we have $$\begin{aligned}
\beta_\alpha\left(Q_0^{{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}}, \widehat{P}_\textbf{Z}\right) {\leqslant}Q\left(\frac{w_{\min}\sqrt{\chi_2(Q_1\|Q_0)}}{\sqrt{n}}-Q^{-1}(\alpha)\right)+ \frac{B}{\sqrt{n}} + \frac{w_{\min}^2B}{n^{\frac{3}{2}}},\end{aligned}$$ where $B$ is a constant that depends just on the channel.

For the hypothesis testing problem consisting of two hypotheses $H_0$ with distribution $Q_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}$ and $H_1$ with distribution $\widehat{P}_\textbf{Z}$, we introduce again the test $$\begin{aligned}
T(\textbf{z}) {\ensuremath{\triangleq}}{\ensuremath{\mathds{1}\!\left\{\sum_{i=1}^n A(z_i) >\tau\right\}}},\end{aligned}$$ where $A(z)$ is defined as $A(z) = \frac{Q_1(z)-Q_0(z)}{Q_0(z)}$. Using Theorem \[Berry-Esseen\] and the calculations in the proof of Lemma \[lm:converse-wmin\], we have $$\begin{aligned}
{{\mathbb{P}_{H_0}}{\left(\sum_{i=1}^n A(Z_i) {\geqslant}\tau\right)}} &= Q\left(\frac{\tau}{\sqrt{n\chi_2(Q_1\|Q_0)}}\right)+ O\left(\frac{1}{\sqrt{n}}\right).\end{aligned}$$ Thus, if we choose $\tau = \sqrt{n\chi_2(Q_1\|Q_0)}Q^{-1}\left(\alpha+O\left(n^{-\frac{1}{2}}\right)\right)$, the false alarm probability would be less than or equal to $\alpha$. Hence, by definition of $\beta_\alpha\left(Q_0^{{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}}, \widehat{P}_\textbf{Z}\right)$, we get $$\begin{aligned}
\beta_\alpha\left(Q_0^{{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}}, \widehat{P}_\textbf{Z}\right) &{\leqslant}{{\mathbb{P}_{H_1}}{\left(\sum_{i=1}^n A(Z_i) {\leqslant}\tau \right)}}\\
&= \sum_{i=1}^M\frac{1}{M}{{\mathbb{P}_{}}{\left(\sum_{i=1}^n A(Z_i) {\leqslant}\tau |\textbf{X}=\textbf{x}_i\right)}}\\
&= \sum_{i=1}^M \frac{1}{M}\left( Q\left(\frac{-\tau + \chi_2(Q_1\|Q_0){\ensuremath{\mbox{wt}(\textbf{x}_i)}}}{\sqrt{n\chi_2(Q_1\|Q_0)+ {\ensuremath{\mbox{wt}(\textbf{x}_i)}}(\sigma_1^1 - \sigma_0^2)}} \right)+O\left(n^{-\frac{1}{2}}\right)\right),\end{aligned}$$ with $$\begin{aligned}
\sigma_0^2 {\ensuremath{\triangleq}}\text{Var}_{Q_0}(A(Z)) \text{ and } \sigma_1^2{\ensuremath{\triangleq}}\text{Var}_{Q_1}(A(Z)).\end{aligned}$$ Plugging in the value of $\tau$, we obtain $$\begin{aligned}
\beta_\alpha\left(Q_0^{{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}}, \widehat{P}_\textbf{Z}\right) &{\leqslant}\sum_{i=1}^M \frac{1}{M}\left( Q\left(\frac{-\sqrt{n\chi_2(Q_1\|Q_0)}Q^{-1}\left(\alpha+O\left(n^{-\frac{1}{2}}\right)\right) + \chi_2(Q_1\|Q_0){\ensuremath{\mbox{wt}(\textbf{x}_i)}}}{\sqrt{n\chi_2(Q_1\|Q_0)+ {\ensuremath{\mbox{wt}(\textbf{x}_i)}}(\sigma_1^1 - \sigma_0^2)}} \right)+O\left(n^{-\frac{1}{2}}\right)\right)\\
&= \sum_{i=1}^M \frac{1}{M}\left( Q\left(\frac{-Q^{-1}\left(\alpha\right)}{\sqrt{1+ \frac{{\ensuremath{\mbox{wt}(\textbf{x}_i)}}}{n}\frac{\sigma_1^2- \sigma_0^2}{\chi_2(Q_1\|Q_0)}}} + \frac{\chi_2(Q_1\|Q_0){\ensuremath{\mbox{wt}(\textbf{x}_i)}}}{\sqrt{n\chi_2(Q_1\|Q_0)+ {\ensuremath{\mbox{wt}(\textbf{x}_i)}}(\sigma_1^1 - \sigma_0^2)}} \right)+O\left(n^{-\frac{1}{2}}\right)\right).\end{aligned}$$ Analogous to the proof of Lemma \[lm:converse-wmin\], we obtain $$\begin{aligned}
\beta_\alpha\left(Q_0^{{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}}, \widehat{P}_\textbf{Z}\right) &{\leqslant}Q\left(\frac{w_{\min}\sqrt{\chi_2(Q_1\|Q_0)}}{\sqrt{n}}-Q^{-1}(\alpha)\right)+O\left(n^{-\frac{1}{2}}\right) + O\left(\frac{w_{\min}^2}{n^{\frac{3}{2}}}\right).\end{aligned}$$

Next, we develop an upper bound on the weight of codewords as a function of channel characteristics and covertness measured in terms of probability of missed detection.

\[lm:converse\_beta\_max\_wt\] Let $({{\mathcal{X}}}, W_{Y|X}, W_{Z|X}, {{\mathcal{Y}}}, {{\mathcal{Z}}})$ be a binary-input covert communication channel and $\mathcal{C}$ be an $(M, K, n, \epsilon, \delta, \alpha)_{\beta}$ code. For all $\gamma\in[0,1]$, we can choose a subset of codewords $\mathcal{D}$ such that $|\mathcal{D}|{\geqslant}\gamma MK$ and $$\begin{aligned}
\label{eq:weight-condition-beta}
\frac{1}{\sqrt{n}} \max\{{\ensuremath{\mbox{wt}(\textbf{x})}}: \textbf{x}\in \mathcal{D}\} {\leqslant}\frac{1}{\sqrt{\chi_2(Q_1\|Q_0)}}\left(Q^{-1}\left(1-\alpha-\delta-\frac{C}{\sqrt{n}}-\gamma\right) + Q^{-1}(\alpha)\right),\end{aligned}$$ where $C$ is a constant that depends just on the channel.

If $A {\ensuremath{\triangleq}}\frac{1}{\sqrt{\chi_2(Q_1\|Q_0)}}\left(Q^{-1}\left(1-\alpha-\delta-\frac{C_2}{\sqrt{n}}-\gamma\right) + Q^{-1}(\alpha)\right)$ for $C_2>0$ specified later, we define $$\begin{aligned}
\mathcal{D} {\ensuremath{\triangleq}}\{\textbf{x}\in \mathcal{C}: {\ensuremath{\mbox{wt}(\textbf{x})}} {\leqslant}A\sqrt{n}\}.\end{aligned}$$ Obviously, $\mathcal{D}$ satisfies , and we just need to check $|\mathcal{D}|{\geqslant}\gamma MK$. To do so, let $\widehat{P}_1$ and $\widehat{P}_2$ be the induced output distributions for codes $\mathcal{D}$ and $\mathcal{C}\setminus \mathcal{D}$, respectively. Using Lemma \[lm:converse-wmin-beta\] for $\mathcal{C}\setminus\mathcal{D}$, we get $$\begin{aligned}
\beta_\alpha\left(Q_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}, \widehat{P}_2\right) &{\leqslant}Q\left(A\sqrt{\chi_2(Q_1\|Q_0)}-Q^{-1}(\alpha)\right)+\frac{B(1+A^2)}{\sqrt{n}}\\
&\stackrel{(a)}{{\leqslant}} 1-\alpha-\delta -\gamma,\end{aligned}$$ where $(a)$ follows from the definition of $A$ and by choosing $$\begin{aligned}
C_2 > \frac{1}{2}B\left(1+\left(\frac{1}{\sqrt{\chi_2(Q_1\|Q_0)}}Q^{-1}\left(1-\alpha-\delta-\gamma\right)\right)^2\right).\end{aligned}$$ This means that there exists $\mathcal{T} \subset \mathcal{Z}^n$ such that $Q_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}(\mathcal{T}) {\leqslant}\alpha$ and $\widehat{P}_2(\mathcal{T}) {\leqslant}1-\alpha-\delta-\gamma$. Accordingly, we have $$\begin{aligned}
1-\alpha-\delta&\stackrel{(a)}{{\leqslant}} \beta_\alpha\left(Q_0^{{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}n}}, \widehat{P}_\textbf{Z}\right) \\
&{\leqslant}\widehat{P}_\textbf{Z}(\mathcal{T}) \\
&\stackrel{(b)}{=}\frac{|\mathcal{D}|}{MK} \widehat{P}_1(\mathcal{T}) + (1-\frac{|\mathcal{D}|}{MK})\widehat{P}_2(\mathcal{T})\\
&{\leqslant}\frac{|\mathcal{D}|}{MK} +  1-\alpha-\delta-\gamma,\end{aligned}$$ where $(a)$ follows from the definition of an $(M, K, n, \epsilon, \delta, \alpha)_{\beta}$ code, and $(b)$ follows from $\widehat{P}_{\textbf{Z}} = \frac{|\mathcal{D}|}{MK} \widehat{P}_1 + (1-\frac{|\mathcal{D}|}{MK})\widehat{P}_2$. Simplifying the above inequality, we get $|\mathcal{D}|{\geqslant}\gamma MK$.

Conclusion {#sec:conclusion}
==========

We have developed the tools to study covert communication when covertness is measured with several "quasi-metrics," as defined in Section \[sec:covert-comm-results\]. It is legitimate to ask which metric would make most sense from an operational perspective. While relative entropy is amenable to a fairly extensive information-theoretic analysis, as illustrated by our complete characterization of second-order asymptotics in Theorem \[th:main\_result\_d\], variational distance and probability of false alarm are probably more adequate since they directly relate to the operation of an adversary attempting to detect communication. Since measuring covertness in terms of variational distance does not impose any constraint on where the adversary operates on its curve, we believe that variational distance is perhaps the metric of choice for covertness.

Our results are presently limited to binary-input , but extensions to arbitrary finite input alphabets are certainly possible following the approach of @Wang2016b; however several research questions remain open. We have not characterized the exact second-order asymptotics of covert communication with variational distance and probability of missed detection metrics. We have also not characterized the second-order asymptotics for the number of key bits required. A close inspection of our current proof technique shows that we explicitly rely on a law of large numbers to analyze the number of key bits, which one would have to circumvent.

<span>10</span>

Keerthi Suria Kumar Arumugam and Matthieu R. Bloch. Keyless covert communication over multiple-access channels. In <span>*Proc. of IEEE International Symposium on Information Theory*</span>, pages 2229–2233, Barcelona, Spain, July 2016.

B.A Bash, D. Goeckel, and D. Towsley. Limits of reliable communication with low probability of detection on <span>AWGN</span> channels. , 31(9):1921–1930, September 2013.

Matthieu Bloch and Joao Barros. . Cambridge University Press, October 2011.

Matthieu Bloch and Saikat Guha. . submitted to *IEEE International Symposium on Information Theory*, February 2017.

Matthieu R. Bloch. Covert communication over noisy channels: A resolvability perspective. , 62(5):2334–2354, May 2016.

Christian Cachin. An information-theoretic model for steganography. , 192(1):41–56, July 2004.

Pak Hou Che, M. Bakshi, and S. Jaggi. Reliable deniable communication: Hiding messages in noise. In <span>*Proc. of IEEE International Symposium on Information Theory*</span>, pages 2945–2949, Istanbul, Turkey, July 2013.

Imre Csiszár and Janos Körner. . Cambridge University Press, 2nd edition, 2011.

P. Cuff. A stronger soft-covering lemma and applications. arXiv preprint 1508.01602, August 2015.

Masahito Hayashi, Himanshu Tyagi, and Shun Watanabe. Strong converse for a degraded wiretap channel via active hypothesis testing. In <span>*Proc. of 52nd Annual Allerton Conference on Communication, Control, and Computing (Allerton)*</span>, pages 148–151, 2014.

Alfred O. Hero. Secure space-time communication. , 49(12):3235–3249, December 2003.

J. Hou and G. Kramer. Effective secrecy: Reliability, confusion and stealth. In <span>*Proc. of IEEE International Symposium on Information Theory*</span>, pages 601–605, Honolulu, HI, July 2014.

Jie Hou and G. Kramer. Informational divergence approximations to product distributions. In <span>*Proc. of 13th Canadian Workshop on Information Theory*</span>, pages 76–81, Toronto, ON, Canada, June 2013.

E. Jorswieck, S. Tomasin, and A. Sezgin. Broadcasting into the uncertainty: Authentication and confidentiality by physical-layer processing. , 103(10):1702–1724, October 2015.

Valery Korzhik, Guillermo Morales-Luna, and MoonHo Lee. On the existence of perfect stegosystems. In Mauro Barni, Ingemar Cox, Ton Kalker, and Hyoung-Joong Kim, editors, <span>*Digital Watermarking*</span>, volume 3710 of <span>*Lecture Notes in Computer Science*</span>, pages 30–38. Springer Berlin Heidelberg, 2005.

Yingbin Liang, H Vincent Poor, Shlomo Shamai, et al. Information theoretic security. , 5(4–5):355–580, 2009.

Yury Polyanskiy, H Vincent Poor, and Sergio Verd<span>ú</span>. Channel coding rate in the finite blocklength regime. , 56(5):2307–2359, 2010.

Maxim Raginsky, Igal Sason, et al. Concentration of measure inequalities in information theory, communications, and coding. , 10(1-2):1–246, 2013.

A. Sheikholeslami, B. A. Bash, D. Towsley, D. Goeckel, and S. Guha. Covert communication over classical-quantum channels. In <span>*Proc. of IEEE International Symposium on Information Theory*</span>, pages 2064–2068, Barcelona, Spain, July 2016.

Mehrdad Tahmasbi and Matthieu R. Bloch. Second order asymptotics for covert communication over noisy channels. In <span>*Proc. of IEEE International Symposium on Information Theory*</span>, Barcelona, Spain, 2016.

Vincent YF Tan and Matthieu R Bloch. Information spectrum approach to strong converse theorems for degraded wiretap channels. , 10(9):1891–1904, 2015.

L. Wang. Optimal throughput for covert communication over a classical-quantum channel. In <span>*Proc. of IEEE Information Theory Workshop*</span>, pages 364–368, Cambridge, UK, September 2016.

L. Wang, G. W. Wornell, and L. Zheng. Fundamental limits of communication with low probability of detection. , 62(6):3493–3503, June 2016.

W. Yang, R. F. Schaefer, and H. V. Poor. Finite-blocklength bounds for wiretap channels. In <span>*Proc. IEEE International Symposium on Information Theory*</span>, pages 3087–3091, Barcelona, Spain, July 2016.

The Effect of Average Probability of Error on First Order Asymptotics {#sec:effect-aver-prob}
=====================================================================

<span><span> Assume that the optimal second order asymptotics are of the form $$\begin{aligned}
  \label{eq:assumption_scaling}
    \log M^*(\epsilon,\delta) = f(\delta)\sqrt{n} + o(\sqrt{n})
  \end{aligned}$$ for some function $f$ that is *strictly* increasing in $\delta$ and does not depend on $\epsilon$, which is what we are hoping to establish. Now for $1>\epsilon>0$ and $\delta>0$, pick $\frac{\epsilon}{1-\epsilon}>\alpha>0$ and set $\epsilon'=(1+\alpha)\epsilon-\alpha$, and $\delta'=(1+\alpha)\delta$. Since $\delta'>\delta$ and because of , we expect for all blocklengths large enough that $$\begin{aligned}
\log M^*(\epsilon',\delta') >     \log M^*(\epsilon,\delta).
  \end{aligned}$$ Consider now a code with $M^*(\epsilon',\delta')$ codewords, and let $\widehat{Q'}^n$ be the distribution induced at the eavesdropper's output when randomizing uniformly over all codewords. We construct a new code by adding at set $\mathcal{S}$ of $N{\ensuremath{\triangleq}}\alpha M^*(\epsilon',\delta')$ all-zero codewords. The resulting code has average probability of error $$\begin{aligned}
P_{\text{avg}} &= {{\mathbb{P}_{}}{\left(\widehat{W}\neq W|W\in\mathcal{S}\right)}} {{\mathbb{P}_{}}{\left(W\in\mathcal{S}\right)}}+ {{\mathbb{P}_{}}{\left(\widehat{W}\neq W|W\notin\mathcal{S}\right)}} {{\mathbb{P}_{}}{\left(W\notin\mathcal{S}\right)}}\\
    &{\leqslant}\frac{M^*(\epsilon',\delta')}{M^*(\epsilon',\delta')+N}\epsilon' +\frac{N}{M^*(\epsilon',\delta')+N}=\frac{1}{1+\alpha}\epsilon'+\frac{\alpha}{1+\alpha}=\epsilon.
  \end{aligned}$$ It also induces a new distribution $\widehat{Q}^n$ at the eavesdropper's output when randomizing uniformly over all codewords, such that $$\begin{aligned}
{{{\mathbb{D}}\!\left({\widehat{Q'}^n\VertQ_0^{\otimes n}}\right)}} &= {{{\mathbb{D}}\!\left({\frac{M^*(\epsilon',\delta')}{M^*(\epsilon',\delta')+N}\widehat{Q}^n+\frac{N}{M^*(\epsilon',\delta')+N}Q_0^{\otimes n}\VertQ_0^{\otimes n}}\right)}}\\
      &{\leqslant}\frac{M^*(\epsilon',\delta')}{M^*(\epsilon',\delta')+N}\delta' = \frac{1}{1+\alpha}\delta'=\delta.
  \end{aligned}$$ We therefore obtain a new code with probability of error less than $\epsilon$ and relative entropy less than $\delta$, but with a number of codewords $M^*(\epsilon',\delta')$ that *exceeds* $ M^*(\epsilon,\delta)$. This contradiction shows that  does not hold, so that either $f(\delta)$ is non-increasing or $\delta$ or depends on $\epsilon$. In both cases, this suggests a result significantly more complex that what we were trying to establish. Note that this does not contradict existing results on covert capacity @Wang2016b [@Bloch2016a] because these works have all been in the regime $\lim_{n\rightarrow\infty}\epsilon=0$.</span></span>

A technical lemma {#sec:technical-lemma}
=================

\[lm:A-moments\] <span><span> Suppose $Q_0\ll Q_1$, $\mathbf{Z} {\ensuremath{\triangleq}}(Z_1, \cdots, Z_m)$ is distributed according to $Q_0^{{  \mathchoice{\raisebox{1pt}{$\displaystyle\otimes$}}
             {\raisebox{1pt}{$\otimes$}}
             {\raisebox{0.5pt}{\scalebox{0.7}{$\scriptstyle\otimes$}}}
             {\raisebox{0.4pt}{\scalebox{0.6}{$\scriptscriptstyle\otimes$}}}}m}$, and $A(z) {\ensuremath{\triangleq}}\frac{Q_1(z) - Q_0(z)}{Q_0(z)}$, and let $B{\ensuremath{\triangleq}}\frac{1}{m}\sum_{i=1}^m A(Z_i)$ and $C {\ensuremath{\triangleq}}\log (1+B)$. Then, we have $$\begin{aligned}
{{\mathbb{E}_{}}{\left(B\right)}} &= 0,\\
{{\mathbb{E}_{}}{\left(B^2\right)}} &= \frac{\chi_2(Q_1\|Q_0)}{m},\\
{{\mathbb{E}_{}}{\left(B^3\right)}} &= O{{\left(\frac{1}{m^2}\right)}},\\
{{\mathbb{E}_{}}{\left(B^4\right)}} &= \frac{\chi_2(Q_1\|Q_0)^2}{m^2} + O{{\left(\frac{1}{m^3}\right)}},\end{aligned}$$ and $$\begin{aligned}
{{\mathbb{E}_{}}{\left(C\right)}} &= \frac{\chi_2(Q_1\|Q_0)}{2m} + O{{\left(\frac{1}{m^2}\right)}}\\
{{\text{\textnormal{Var}}{\left(C\right)}}} &= \frac{\chi_2(Q_1\|Q_0)}{m}+ O{{\left(\frac{1}{m^2}\right)}}\\ 
{{\mathbb{E}_{}}{\left(|C-{{\mathbb{E}_{}}{\left(C\right)}}|^3\right)}} &{\leqslant}\frac{\chi_2(Q_1\|Q_0)^{\frac{3}{2}}}{m^{\frac{3}{2}}} + O{{\left(\frac{1}{m^{\frac{9}{4}}}\right)}}.\end{aligned}$$ Moreover, if $\widetilde{\mathbf{Z}} {\ensuremath{\triangleq}}(\widetilde{Z}_1, \cdots, \widetilde{Z}_m)$ is distributed according to ${P_{\textbf{Z}, \text{PPM}}^{m, 1}}$, $\widetilde{B} {\ensuremath{\triangleq}}\frac{1}{m} \sum_{i=1}^m A(\widetilde{Z})$, and $\widetilde{C} {\ensuremath{\triangleq}}\log(1+\widetilde{B})$, then $$\begin{aligned}
{{\mathbb{E}_{}}{\left(\widetilde{B}\right)}} &= \frac{\chi_2(Q_1\|Q_0)}{m}, \\
{{\mathbb{E}_{}}{\left(\widetilde{B}^2\right)}} &= \frac{\chi_2(Q_1\|Q_0)}{m }+ O{{\left(\frac{1}{m^2}\right)}},\\
{{\mathbb{E}_{}}{\left(\widetilde{B}^3\right)}} &= O{{\left(\frac{1}{m^2}\right)}},\\
{{\mathbb{E}_{}}{\left(\widetilde{B}^4\right)}} &= \frac{\chi_2(Q_1\|Q_0)^2}{m^2} + O{{\left(\frac{1}{m^3}\right)}},\end{aligned}$$ and $$\begin{aligned}
{{\mathbb{E}_{}}{\left(\widetilde{C}\right)}} &= \frac{\chi_2(Q_1\|Q_0)}{2m} + O{{\left(\frac{1}{m^2}\right)}}\\
{{\text{\textnormal{Var}}{\left(\widetilde{C}\right)}}} &= \frac{\chi_2(Q_1\|Q_0)}{m}+ O{{\left(\frac{1}{m^2}\right)}}\\ 
{{\mathbb{E}_{}}{\left(|\widetilde{C}-{{\mathbb{E}_{}}{\left(\widetilde{C}\right)}}|^3\right)}} &{\leqslant}\frac{\chi_2(Q_1\|Q_0)^{\frac{3}{2}}}{m^{\frac{3}{2}}} + O{{\left(\frac{1}{m^{\frac{9}{4}}}\right)}}.\end{aligned}$$</span></span>

Note that $$\begin{aligned}
{{\mathbb{E}_{Q_0}}{\left(A(Z)\right)}} &= 0\\
{{\mathbb{E}_{Q_1}}{\left( A(Z)\right)}} &= \chi_2(Q_1\|Q_0)\\
\text{Var}_{Q_0} (A(Z)) &= \chi_2(Q_1\|Q_0).\end{aligned}$$ Therefore, we obtain $$\begin{aligned}
{{\mathbb{E}_{}}{\left(B\right)}} &= {{\mathbb{E}_{}}{\left(\frac{1}{m} \sum_{i=1}^m A(Z_i)\right)}} = 0,\displaybreak[0]\\
{{\mathbb{E}_{}}{\left(B^2\right)}} &= \frac{1}{m^2}{{\mathbb{E}_{}}{\left({{\left(\sum_{i=1}^m A(Z_i)\right)}}^2\right)}} = \frac{1}{m^2} \sum_{i=1}^m\sum_{j=1}^m {{\mathbb{E}_{}}{\left(A(Z_i) A(Z_j)\right)}} = \frac{\chi_2(Q_1\|Q_0)}{m}\displaybreak[0]\\
{{\mathbb{E}_{}}{\left(B^3\right)}} &= \frac{1}{m^3}{{\mathbb{E}_{}}{\left(\sum_{i=1}^m\sum_{j=1}^m \sum_{k=1}^m A(Z_i)A(Z_k) A(Z_j)\right)}} = \frac{\sum_{i=1}^m{{\mathbb{E}_{}}{\left(A(Z_i)^3\right)}}}{m^3} = O{{\left(\frac{1}{m^2}\right)}}\displaybreak[0]\\
{{\mathbb{E}_{}}{\left(B^4\right)}} &= \frac{1}{m^4}{{\mathbb{E}_{}}{\left(\sum_{i=1}^m\sum_{j=1}^m\sum_{k=1}^m\sum_{t=1}^m A(Z_i)A(Z_j)A(Z_k)A(Z_t)\right)}}=\frac{\sum_{i=1}^m A(Z_i)^4 + 2\sum_{i=1}^m \sum_{j=i+1}^m {{\mathbb{E}_{}}{\left(A(Z_i)^2\right)}}{{\mathbb{E}_{}}{\left(A(Z_j)^2\right)}}}{m^4}\displaybreak[0]\\
&=\frac{\chi_2(Q_1\|Q_0)^2}{m^2} +\frac{-\chi_2(Q_1\|Q_0) + {{\mathbb{E}_{Q_0}}{\left(A(Z)^4\right)}}}{m^3} = \frac{\chi_2(Q_1\|Q_0)^2}{m^2} + O{{\left(\frac{1}{m^3}\right)}}.\end{aligned}$$ To find the expected value of $C$, note that $ \ln(1+x) {\leqslant}x - \frac{x^2}{2} + \frac{x^3}{3}$, and therefore, we have $$\begin{aligned}
{{\mathbb{E}_{}}{\left(C\right)}} 
&= {{\mathbb{E}_{}}{\left(\log (1+B)\right)}} {\leqslant}{{\mathbb{E}_{}}{\left(B\right)}}- {{\mathbb{E}_{}}{\left(\frac{B^2}{2}\right)}} + {{\mathbb{E}_{}}{\left(\frac{B^3}{3}\right)}} = -\frac{\chi_2(Q_1\|Q_0)}{2m} + O{{\left(\frac{1}{m^2}\right)}}.\end{aligned}$$ For any $0<a<1$ and $x > -a$, we also have $x - \frac{x^2}{2} +\frac{x^3}{3} -\frac{x^4}{4(1-a)^4} {\leqslant}\ln(1+x)$; thus, $$\begin{aligned}
{{\mathbb{E}_{}}{\left(C\right)}} 
&{\geqslant}{{\mathbb{E}_{}}{\left(B\right)}} - {{\mathbb{E}_{}}{\left(\frac{B^2}{2}\right)}} + {{\mathbb{E}_{}}{\left(\frac{B^3}{3}\right)}} - {{\mathbb{E}_{}}{\left(\frac{B^4}{4(1-\min_{b:{{\mathbb{P}_{}}{\left(B=b\right)}}}b)^4}\right)}}\\
&= -\frac{\chi_2(Q_1\|Q_0)}{2m} + O{{\left(\frac{1}{m^2}\right)}}  +   \frac{\frac{\chi_2(Q_1\|Q_0)^2}{m^2} + O{{\left(\frac{1}{m^3}\right)}}}{4(1-\min_{b:{{\mathbb{P}_{}}{\left(B=b\right)}}}b)^4}\\
&= -\frac{\chi_2(Q_1\|Q_0)}{2m} + O{{\left(\frac{1}{m^2}\right)}}  +   \frac{\frac{\chi_2(Q_1\|Q_0)^2}{m^2} + O{{\left(\frac{1}{m^3}\right)}}}{4(1-\min_{z:Q_0(z) > 0}A(z))^4}\\
&\stackrel{(a)}{=}  -\frac{\chi_2(Q_1\|Q_0)}{2m}  + O{{\left(\frac{1}{m^2}\right)}},\end{aligned}$$ where $(a)$ follows since $Q_0 \ll Q_1$. Furthermore, for the variance of $C$, by $\log^2(1+x) {\geqslant}{{\left(x - \frac{x^2}{2}\right)}}^2 - x^4$, we have $$\begin{aligned}
{{\text{\textnormal{Var}}{\left(C\right)}}} 
&= {{\mathbb{E}_{}}{\left(C^2\right)}} - {{\mathbb{E}_{}}{\left(C\right)}}^2 \\
&{\geqslant}{{\mathbb{E}_{}}{\left({{\left(B - \frac{B^2}{2}\right)}}^2\right)}} - {{\mathbb{E}_{}}{\left(B^4\right)}} + O{{\left(\frac{1}{m^2}\right)}}\\
&= {{\mathbb{E}_{}}{\left(B^2\right)}} -{{\mathbb{E}_{}}{\left(B^3\right)}} - {{\mathbb{E}_{}}{\left(\frac{3}{4}B^4\right)}} + O{{\left(\frac{1}{m^2}\right)}}\\
&= \frac{\chi_2(Q_1\|Q_0)}{m} + O{{\left(\frac{1}{m^2}\right)}}\end{aligned}$$ Moreover, for $-1 < a < 0$ and $x > -a$, we have $\log^2(1+x) {\leqslant}{{\left(x-\frac{x^2}{2} + \frac{x^3}{3(1-a)^3}\right)}}^2$. Therefore, $$\begin{aligned}
{{\text{\textnormal{Var}}{\left(C\right)}}} 
&= {{\mathbb{E}_{}}{\left(C^2\right)}} - {{\mathbb{E}_{}}{\left(C\right)}}^2 \\
&{\geqslant}{{\mathbb{E}_{}}{\left({{\left(B-\frac{B^2}{2} - \frac{B^3}{3(1-\min_{z:Q_0(z) > 0}A(z))^3}\right)}}\right)}} + O{{\left(\frac{1}{m^2}\right)}}\\
&= \frac{\chi_2(Q_1\|Q_0)}{m} + O{{\left(\frac{1}{m^2}\right)}}.\end{aligned}$$ Finally, for the third moment of $C$, note that $$\begin{aligned}
{{\mathbb{E}_{}}{\left(|C - {{\mathbb{E}_{}}{\left(C\right)}}|^3\right)}}
&= {{\mathbb{E}_{}}{\left({{\left({{\left(C-{{\mathbb{E}_{}}{\left(C\right)}}\right)}}^4\right)}}^{\frac{3}{4}}\right)}}\\
&\stackrel{(a)}{{\leqslant}} {{\left({{\mathbb{E}_{}}{\left({{\left(C-{{\mathbb{E}_{}}{\left(C\right)}}\right)}}^4\right)}}\right)}}^{\frac{3}{4}}\\
&=  {{\left({{\mathbb{E}_{}}{\left(C^4 - 4C^3 {{\mathbb{E}_{}}{\left(C\right)}} + 6C^2 ({{\mathbb{E}_{}}{\left(C\right)}})^2 - 4 C ({{\mathbb{E}_{}}{\left(C\right)}})^3 + ({{\mathbb{E}_{}}{\left(C\right)}})^4 \right)}}\right)}}^{\frac{3}{4}}\\
&= \frac{\chi_2(Q_1\|Q_0)^{\frac{3}{2}}}{m^{\frac{3}{2}}} + O{{\left(\frac{1}{m^{\frac{9}{4}}}\right)}},\end{aligned}$$ where $(a)$ follows from Jensen's inequality.

We now calculate the moments with respect to distribution. First note that if we define $P_{\mathbf{Z}}^i(\mathbf{z}) {\ensuremath{\triangleq}}Q_1(z_i) \prod_{j\neq i} Q_0(z_j)$, then we can write ${P_{\textbf{Z}, \text{PPM}}^{m, 1}} = \frac{1}{m}P_{\mathbf{Z}}^i$; therefore, for any function of $\widetilde{\mathbf{Z}}$ such as $f(\widetilde{\mathbf{Z}})$, we have ${{\mathbb{E}_{{P_{\textbf{Z}, \text{PPM}}^{m, 1}}}}{\left(f(\widetilde{\mathbf{Z}})\right)}} = \frac{1}{m}\sum_{i=1}^m {{\mathbb{E}_{P_{\mathbf{Z}}^i}}{\left(f(\widetilde{\mathbf{Z}})\right)}}$. Moreover, if $f$ is invariant with respect to all permutation of elements of $\mathbf{z}$, then ${{\mathbb{E}_{{P_{\textbf{Z}, \text{PPM}}^{m, 1}}}}{\left(f(\widetilde{\mathbf{Z}})\right)}} =  {{\mathbb{E}_{P_{\mathbf{Z}}^1}}{\left(f(\widetilde{\mathbf{Z}})\right)}}$. It is easy to check that this property holds for all moments of $\widetilde{B}$ and $\widetilde{C}$. So, in the sequel, we assume that $\widetilde{\mathbf{Z}}$ is distributed according to $P_{\mathbf{Z}}^1$. Hence, we have $$\begin{aligned}
{{\mathbb{E}_{}}{\left(\widetilde{B}\right)}} &= {{\mathbb{E}_{}}{\left(\frac{1}{m} \sum_{i=1}^m A(\widetilde{Z}_i)\right)}} = \frac{\chi_2(Q_1\|Q_0)}{m},\\
{{\mathbb{E}_{}}{\left(\widetilde{B}^2\right)}} &= \frac{1}{m^2}{{\mathbb{E}_{}}{\left({{\left(\sum_{i=1}^m A(\widetilde{Z}_i)\right)}}^2\right)}} = \frac{1}{m^2} \sum_{i=1}^m\sum_{j=1}^m {{\mathbb{E}_{}}{\left(A(\widetilde{Z}_i) A(\widetilde{Z}_j)\right)}} = \frac{(m-1)\chi_2(Q_1\|Q_0) + {{\mathbb{E}_{Q_1}}{\left(A(Z)^2\right)}}}{m^2}\\
&= \frac{\chi_2(Q_1\|Q_0)}{m} + O{{\left(\frac{1}{m^2}\right)}}\\
{{\mathbb{E}_{}}{\left(\widetilde{B}^3\right)}} &= \frac{1}{m^3}{{\mathbb{E}_{}}{\left(\sum_{i=1}^m\sum_{j=1}^m \sum_{k=1}^m A(\widetilde{Z}_i)A(\widetilde{Z}_k) A(\widetilde{Z}_j)\right)}} = \frac{\sum_{i=1}^m{{\mathbb{E}_{}}{\left(A(\widetilde{Z}_i)^3\right)}} +\sum_{i=2}^m {{\mathbb{E}_{}}{\left(A(\widetilde{Z}_1)A(\widetilde{Z}_i)^2\right)}}}{m^3} = O{{\left(\frac{1}{m^2}\right)}}\\
{{\mathbb{E}_{}}{\left(\widetilde{B}^4\right)}} &= \frac{1}{m^4}{{\mathbb{E}_{}}{\left(\sum_{i=1}^m\sum_{j=1}^m\sum_{k=1}^m\sum_{t=1}^m A(\widetilde{Z}_i)A(\widetilde{Z}_j)A(\widetilde{Z}_k)A(\widetilde{Z}_t)\right)}}\\
&=\frac{\sum_{i=1}^m A(\widetilde{Z}_i)^4 + 2\sum_{i=1}^m \sum_{j=i+1}^m {{\mathbb{E}_{}}{\left(A(\widetilde{Z}_i)^2\right)}}{{\mathbb{E}_{}}{\left(A(\widetilde{Z}_j)^2\right)}} + \sum_{i=2}^m {{\mathbb{E}_{}}{\left(A(\widetilde{Z}_1)A(\widetilde{Z}_i)^3\right)}}}{m^4}\\
&= \frac{\chi_2(Q_1\|Q_0)^2}{m^2} + O{{\left(\frac{1}{m^3}\right)}}.\end{aligned}$$ Then, using same bounds for $\log(1+x)$ as before and the above calculation, we can derive the moments of $\widetilde{C}$.

[^1]: This work was presented in part at the 2016 IEEE International Symposium on Information Theory @Bloch2016. This work was supported by NSF under award TWC 1527387.

[^2]: See also the discussion in @Bloch2016a [Appendix A].

[^3]: <span><span> Since we are deriving one-shot bounds, ${{\mathcal{X}}}$ can be arbitrary in this section.</span></span>

[^4]: <span><span> Unlike the main problem in which we have $MK$ codewords, we denote here the total number of codewords by $M$for simplicity.</span></span>

{'source': 'arXiv_out/1703'}