See Appendix 7.

The proof follows the same lines as that of [13], but in the particular case of additive channels; details are omitted.

See Appendix 9

Direct application of 11 to Theorem 1.

An arbitrary deterministic guessing strategy can be described by a ranking function \(G \colon \mathcal{A}^n \to \{1, \dots, |\mathcal{A}|^n\}\) in such a way that the \(t\)-th guess is \(G^{-1}(t)\). Denote \(\mathcal{U}_t \mathrel{\vcenter{:}}= \left\{ G^{-1}(1), \dots, G^{-1}(t) \right\}\) the first \(t\) guesses, with the convention that \(\mathcal{U}_0 = \varnothing\).

Fix \(M\) sequences \(\pmb{z}_1, \dots, \pmb{z}_M\) and denote \(\mathcal{S}\mathrel{\vcenter{:}}= \left\{ \pmb{z}_1, \dots, \pmb{z}_M \right\}\) the set containing them. Note that the number of guesses needed to find a sequence in \(\mathcal{S}\) with the strategy \(G\) can be written as \[\sum_{t=0}^{|\mathcal{A}|^n} \mathbb{1} \left\{ \mathcal{U}_t \cap \mathcal{S}= \varnothing\right\}.\]

Taking the average over random realisations of \(\mathsf{S}= \left\{ \pmb{Z}_1, \dots, \pmb{Z}_M \right\}\), we have that the average complexity is \[\begin{align} \overline{q}_{d}(n,M) &= \mathbb{E}\left[ \sum_{t=0}^{|\mathcal{A}|^n} \mathbb{1} \left\{ \mathcal{U}_t \cap \mathsf{S}= \varnothing\right\} \right] \nonumber \\ &= \sum_{t=0}^{|\mathcal{A}|^n} \mathbb{P}\left( \mathcal{U}_t \cap \mathsf{S}= \varnothing\right) \nonumber \\ &= \sum_{t=0}^{|\mathcal{A}|^n} \mathbb{P}\left( \bigcap_{m=1}^{M} \left\{ \pmb{Z}_{m} \notin \mathcal{U}_t \right\} \right) \nonumber \\ &= \sum_{t=0}^{|\mathcal{A}|^n} \mathbb{P}\left( \pmb{Z}_{1} \notin \mathcal{U}_t \right) \prod_{m=2}^{M} \mathbb{P}\left( \pmb{Z}_{m} \notin \mathcal{U}_t \right) \nonumber \\ &= \sum_{t=0}^{|\mathcal{A}|^n} \left( 1 - \sum_{s=1}^{t} P_{\pmb{Z}}\left(G^{-1}(s)\right) \right) \left( 1 - \frac{t}{|\mathcal{A}|^n} \right)^{M-1}. \label{eq:ch3-expression-average-complexity} \end{align}\tag{19}\]

Denote \(G_{\star}\) a strategy that orders sequences in decreasing order of probability. Since \[\sum_{s=1}^{t} P_{\pmb{Z}}\left(G^{-1}(s)\right) \le \sum_{s=1}^{t} P_{\pmb{Z}}\left(G^{-1}_{\star}(s)\right),\] we conclude that \(G_{\star}\) is indeed an optimal strategy.

We can use 19 to write the average complexity as \[\begin{align} \overline{q}_d(n,M) &= \sum_{t=0}^{|\mathcal{A}|^n} \mathbb{P}\left( G(\pmb{Z}_1) > t \right) \left( 1-\frac{t}{|\mathcal{A}|^n} \right)^{M-1} \nonumber\\ &= \sum_{t=0}^{|\mathcal{A}|^n} \sum_{k=t+1}^{|\mathcal{A}|^n} \mathbb{P}\left( G(\pmb{Z}_1) = k \right) \left( 1-\frac{t}{|\mathcal{A}|^n} \right)^{M-1} \nonumber\\ &= \sum_{k=1}^{|\mathcal{A}|^n} \mathbb{P}\left( G(\pmb{Z}_1) = k \right) \sum_{t=0}^{k-1} \left( 1-\frac{t}{|\mathcal{A}|^n} \right)^{M-1} \nonumber\\ &= \mathbb{E}\left[ \sum_{t=0}^{G(\pmb{Z}_1)-1} \left( 1-\frac{t}{|\mathcal{A}|^n} \right)^{M-1} \right]. \label{eq:proof-aux-1} \end{align}\tag{20}\]

The function \(f \colon \left[0,1\right]\to \mathbb{R}\) given by \(f(x) = (1-x)^{M-1}\) is non-increasing, so its integral is upper bounded by right Riemann sums, and lower bounded by left Riemann sums. This yields \[\begin{align} \frac{|\mathcal{A}|^n}{M} \left[ 1 - \left( 1-\frac{G(\pmb{Z}_1)}{|\mathcal{A}|^n} \right)^{M} \right] &\le \sum_{t=0}^{G(\pmb{Z}_1)-1} \left( 1 - \frac{t}{|\mathcal{A}|^n} \right)^{M-1}\\ &\le \frac{|\mathcal{A}|^n}{M} \left[ 1 - \left( 1-\frac{G(\pmb{Z}_1)}{|\mathcal{A}|^n} \right)^{M} \right] + 1. \end{align}\] Using that \(\frac{1}{2}\min\left\{1,\, Mx\right\} \le 1-(1-x)^{M} \le \min\left\{1,\;Mx \right\}\), for \(x\in\left[0,1\right]\), we then get \[\begin{align} \frac{1}{2} \min\left\{ G(\pmb{Z}_1),\;\frac{|\mathcal{A}|^n}{M} \right\} &\le \sum_{t=0}^{G(\pmb{Z}_1)-1} \left( 1 - \frac{t}{|\mathcal{A}|^n} \right)^{M-1} \nonumber\\ &\le \min\left\{ G(\pmb{Z}_1),\;\frac{|\mathcal{A}|^n}{M} \right\} + 1 \nonumber\\ &\le 2 \min\left\{ G(\pmb{Z}_1),\;\frac{|\mathcal{A}|^n}{M} \right\}. \label{eq:proof-aux-2} \end{align}\tag{21}\] The proof is concluded by replacing 21 in 20 .

See Appendix 10.

See Appendix 11.

Direct application of 11 to Theorem 4.

This result is mostly analogous to [13] and [14], but in the particular case of additive channels (see also [39] for a detailed proof following the ideas of [14]). Details are omitted⁶.

Direct application of 9 to Theorem 7.

See Appendix 12.

Direct application of 11 to Theorem 7.

See Appendix 13.

See Appendix 14.

See Appendix 15.

Direct application of 11 to Theorem 11.

See Appendix 16.

Since \(E_d(R)\) and \(F_d(R)\) are respectively random-coding error and complexity exponents, there exist sequences \(\epsilon(n) \to 0\) and \(\delta(n) \to 0\) such that \[\mathbb{E}\left[p_{e,d}(\mathsf{C}_n;u_n) \right] \le e^{-n\left( E_d(R) - \epsilon(n) \right)}\] and \[\mathbb{E}\left[ q_d(\mathsf{C}_n;u_n) \right] \le e^{n\left( F_d(R) + \delta(n) \right)},\] with \(|\mathsf{C}_n| \le e^{nR}\), for every \(n\in\mathbb{N}\). Consider the sequence given by \(\eta(n) \mathrel{\vcenter{:}}= \max\left\{ \epsilon(n),\;\delta(n) \right\}\), which satisfies \(\eta(n) \to 0\). Then, for each \(n\in\mathbb{N}\), we have \[\begin{align} &\mathbb{P}\Bigg( \left\{ p_{e,d}(\mathsf{C}_n;u_n) \le 4e^{-n\left( E_d(R) - \eta(n) \right)} \right\}\\ &\cap \left\{ q_d(\mathsf{C}_n;u_n) \le 4e^{n\left( F_d(R) + \eta(n) \right)} \right\} \Bigg)\\ &= 1 - \mathbb{P}\Bigg( \left\{ p_{e,d}(\mathsf{C}_n;u_n) > 4e^{-n\left( E_d(R) - \eta(n) \right)} \right\}\\ &\cup \left\{ q_d(\mathsf{C}_n;u_n) > 4e^{-n\left( F_d(R) + \eta(n) \right)} \right\} \Bigg)\\ &\ge 1 - \Bigg[ \mathbb{P}\left( p_{e,d}(\mathsf{C}_n;u_n) > 4e^{-n\left( E_d(R) - \eta(n) \right)} \right)\\ &+ \mathbb{P}\left( q_d(\mathsf{C}_n;u_n) > 4e^{n\left( F_d(R) + \eta(n) \right)} \right) \Bigg]\\ &\ge 1 - \left[ \frac{\mathbb{E}\left[ p_{e,d}(\mathsf{C}_n;u_n) \right]}{4e^{-n\left( E_d(R)-\eta(n) \right)}} + \frac{\mathbb{E}\left[ q_{d}(\mathsf{C}_n;u_n) \right]}{4e^{n\left( F_d(R)+\eta(n) \right)}} \right]\\ &\ge \frac{1}{2}, \end{align}\] where the first inequality is due to the union bound; the second, to Markov’s inequality; and the third, to the definition of \(\eta(n)\). This means that we can find (with quite high probability) a sequence of codes \((\mathcal{C}_n)_{n\in\mathbb{N}}\) simultaneously satisfying \[p_{e,d}(\mathcal{C}_n;u_n) \le 4e^{-n\left( E_d(R) - \eta(n) \right)}\] and \[q_d(\mathcal{C}_n;u_n) \le 4e^{n\left( F_d(R) + \eta(n) \right)}.\] Taking the limit superior of the normalised logarithm of each quantity yields ?? and ?? .

1. Obtained by direct calculation of \(\frac{\mathrm{d}}{\mathrm{d}\alpha} \log \sum_{z\in\mathcal{A}} P_Z(z)^{\alpha}\).

2. Straightforward computations show that \[\begin{align} \psi_P''(\alpha) &= \frac{\mathrm{d}}{\mathrm{d}\alpha} \sum_{z \colon P_Z(z)>0} \widetilde{P}_{\alpha}(z) \log P_Z(z)\\ &= \mathsf{Var}_{\widetilde{P}_{\alpha}}\left( \log P_Z(Z) \right) \ge 0, \end{align}\] where \(\mathsf{Var}_P(X)\) denotes the variance of the random variable \(X \sim P\). The inequality is strict if \(\min_{z\in\mathcal{A}}{P_Z(z)>0}\) and \(P_Z\) is non-uniform.

3. We can directly compute \[\begin{align} D({\widetilde{P}_\alpha} \| \widetilde{P}_{\beta}) &= \sum_{z\in\mathcal{A}} \widetilde{P}_\alpha(z)\log \frac{\widetilde{P}_\alpha(z)}{\widetilde{P}_{\beta}(z)} \\ &= \sum_{z\in\mathcal{A}} \widetilde{P}_\alpha(z) \log P_Z(z)^{\alpha-\beta} + \psi_P(\beta) - \psi_P(\alpha) \\ &= (\alpha-\beta)\psi_P'(\alpha) + \psi_P(\beta) - \psi_P(\alpha). \end{align}\]

4. Similarly, \[\begin{align} H({\widetilde{P}_\alpha}) &= \sum_{z\in\mathcal{A}} \widetilde{P}_\alpha(z)\log\frac{1}{\widetilde{P}_\alpha(z)}\\ &= \sum_{z\in\mathcal{A}} \widetilde{P}_{\alpha}(z) \log \left( \frac{\sum_{z'\in\mathcal{A}} P_Z(z')^{\alpha}}{P_Z(z)^{\alpha}}\right)\\ &= \psi_P(\alpha) - \alpha\psi_P'(\alpha). \end{align}\]

For item 1, since both \(P'\) and \(\Pi_{\mathfrak{T}(Q)}(P)\) belong to \(\mathfrak{T}(Q)\), denote them \(\widetilde{Q}_{\alpha} \mathrel{\vcenter{:}}= P'\) and \(\widetilde{Q}_{\beta} \mathrel{\vcenter{:}}= \Pi_{\mathfrak{T}(Q)}(P)\), and note that \(H( \widetilde{Q}_{\beta} \| Q ) = H(P \| Q)\), by definition. Expanding the divergences and using 23 , we have \[\begin{align} D(P \| \widetilde{Q}_{\alpha}) &= -H(P) +\alpha H(P \| Q) + \psi_Q(\alpha),\\ D(P \| \widetilde{Q}_{\beta}) &= -H(P) +\beta H(P \| Q) + \psi_Q(\beta). \end{align}\] Together with items 1 and 3 of Proposition 16, we have \[\begin{align} &~D(P\| \widetilde{Q}_{\beta}) + D(\widetilde{Q}_{\beta} \| \widetilde{Q}_{\alpha})\\ &= \left[ -H(P) +\beta H(P \| Q) + \psi_Q(\beta) \right]\\ &\quad+ \left[(\alpha-\beta)H(\widetilde{Q}_{\beta}\|Q) + \psi_Q(\alpha) - \psi_Q(\beta) \right]\\ &= -H(P) +\beta H(P \| Q) + (\alpha-\beta)H(P\|Q) + \psi_Q(\alpha)\\ &= D(P \| \widetilde{Q}_{\alpha}). \end{align}\]

For item 2 , see [29]; for item 3, see [29].

One the one hand, restricting the minimisation domain to \(\mathfrak{T}(P_Z) \subseteq \mathcal{P}(\mathcal{A})\) can only increase the minimum: \[\begin{align} &\min_{\widehat{P}_Z\in\mathcal{P}(\mathcal{A})} D(\widehat{P}_Z \| P_Z) - f\big(H(\widehat{P}_Z)\big) \nonumber\\ &\le \min_{\widehat{P}_Z \in \mathfrak{T}(P_Z)} D(\widehat{P}_Z \| P_Z) - f\big(H(\widehat{P}_Z)\big). \end{align}\] On the other hand, from Lemma 4, item 3, \[\begin{align} &\min_{\widehat{P}_Z\in\mathcal{P}(\mathcal{A})} D(\widehat{P}_Z \| P_Z) - f\big(H(\widehat{P}_Z)\big) \nonumber\\ &\ge \min_{\widehat{P}_Z\in\mathcal{P}(\mathcal{A})} D\big(\Pi_{\mathfrak{T}(P_Z)}(\widehat{P}_Z) \| P_Z\big) - f\bigg(H\big(\Pi_{\mathfrak{T}(P_Z)}(\widehat{P}_Z)\big)\bigg)\\ &= \min_{\widehat{P}_Z\in\mathfrak{T}(P_Z)} D\big(\widehat{P}_Z \| P_Z\big) - f\big(H(\widehat{P}_Z)\big). \end{align}\] Together, this shows that \[\begin{align} &\min_{\widehat{P}_Z\in\mathcal{P}(\mathcal{A})} D(\widehat{P}_Z \| P_Z) - f\big(H(\widehat{P}_Z)\big) \nonumber\\ &= \min_{\widehat{P}_Z \in \mathfrak{T}(P_Z)} D(\widehat{P}_Z \| P_Z) - f\big(H(\widehat{P}_Z)\big)\\ &= \min_{\beta\in\mathbb{R}} D(\widetilde{P}_{\beta} \| P_Z) - f\big(H(\widetilde{P}_{\beta})\big). \end{align}\]

The proof of ?? follows the same lines as that of [41], but in the specific case of additive channels; details are omitted. We now prove ?? . Applying Lemma 5 to ?? , we get \[E_d(R;g_{\alpha}) = \min_{\beta\in\mathbb{R}} D(\widetilde{P}_{\beta} \| P_Z) + \left[ \log|\mathcal{A}| - H(\widetilde{P}_{\beta}) - R \right]_+.\] Using the notation from Appendix 8, we have \[\begin{align} f(\beta) &\mathrel{\vcenter{:}}= D(\widetilde{P}_{\beta} \| P_Z) + \left[ \log|\mathcal{A}| - H(\widetilde{P}_{\beta}) - R \right]_+\\ &= \begin{cases} f_1(\beta), &H(\widetilde{P}_{\beta}) \ge \log|\mathcal{A}|-R ,\\ f_2(\beta), & H(\widetilde{P}_{\beta}) \le \log|\mathcal{A}|-R. \end{cases} \end{align}\] where \[\begin{align} f_1(\beta) &\mathrel{\vcenter{:}}= (\beta-1)\psi_P'(\beta) - \psi_P(\beta),\\ f_2(\beta) &\mathrel{\vcenter{:}}= (2\beta-1)\psi_P'(\beta) - 2\psi_P(\beta) + \log|\mathcal{A}|-R. \end{align}\] We can now explicitly identify the minimiser \(\beta^{\star}\). Since \(f_1'(\beta) = (\beta-1)\psi_P''(\beta)\) and \(\psi_P''(\beta) \ge 0\), we find that \(f_1\) is increasing for \(\beta\ge1\), and decreasing elsewhere, with minimum value \(f_1(1)=0\). Similarly, \(f_2\) is increasing for \(\beta\ge1/2\), decreasing elsewhere, and has minimum value \(f_2(1/2) = \log|\mathcal{A}|-R-H_{1/2}(P_Z)\). If \(P_Z\) is uniform, then \(f_2(1/2) = -R\) and \(f=f_1\equiv0\); in this case, \(C=0\) and the result follows. In the following, we suppose \(P_Z\) non-uniform. Denote \(\alpha_R\) (resp., \(\overline{\alpha}_R\)) the unique non-negative (resp., non-positive) solution on \(\alpha\in\mathbb{R}\) to \(H(\widetilde{P}_{\alpha}) = \log|\mathcal{A}|-R\). We split into two cases.

Case 1: \(\beta\ge0\). In this case, \(\beta\mapsto H(\widetilde{P}_{\beta})\) is decreasing, and \(\log|\mathcal{A}|-R \le H(\widetilde{P}_{\beta}) \iff \beta \le \alpha_R \iff f_1 \ge f_2\). We can then identify \(\min_{\beta\ge0} f(\beta)\) by analysing separately the three following subcases: a) \(0 \le \alpha_R \le \frac{1}{2}\): for \(\beta\le\alpha_R\), \(f=f_1\) and is decreasing, and, for \(\beta\ge\alpha_R\), \(f=f_2\) which achieves minimum at \(\beta^{\star}=1\); b) \(\frac{1}{2}\le\alpha_R\le1\): for \(\beta\le\alpha_R\), \(f=f_1\) and is decreasing, and, for \(\beta\ge\alpha_R\), \(f=f_2\) and is increasing; thus the minimum is at \(\beta^{\star}=\alpha_R\); c) \(\alpha_R\ge1\): for \(\beta\le\alpha_R\), \(f=f_1\) attains minimum at \(\beta^{\star}=1\), and \(\beta\ge\alpha_R\), \(f=f_2\) which is increasing. Therefore, \[\min_{\beta\ge0} f(\beta) = \begin{cases} \log|\mathcal{A}| - R - H_{1/2}(P_Z), & 0 \le \alpha_R \le \frac{1}{2},\\ D(\widetilde{P}_{\alpha_R}\| P_Z), &\frac{1}{2} \le \alpha_R \le 1,\\ 0, & \alpha_R\ge1. \end{cases}\]

Case 2: \(\beta<0\). In this case, \(\beta \mapsto H(\widetilde{P}_{\beta})\) is increasing. We have \(\log|\mathcal{A}|-R \le H(\widetilde{P}_{\beta}) \iff \beta \ge \overline{\alpha}_R \iff f_1(\beta) \ge f_2(\beta)\). In this interval, \(f\) is decreasing and attains minimum \(f(0) = f_1(0)\), but this is always lower bounded by the solution of the case \(\beta\ge0\), since \(f_1\) is minimised at \(\beta^{\star}=1\).

Thus, the solution of the minimisation is \(\min_{\beta\in\mathbb{R}} f(\beta) = \min_{\beta\ge0} f(\beta)\), as given above. Finally, using the monotonicity of \(\alpha \mapsto H(\widetilde{P}_{\alpha})\) for \(\alpha\ge0\) and the definition of \(\alpha_R\), we have that \[\begin{align} \alpha_R \le \frac{1}{2} &\iff H(\widetilde{P}_{\alpha_R}) \ge H(\widetilde{P}_{1/2})\\ &\iff \log|\mathcal{A}|-R \ge H(\widetilde{P}_{1/2})\\ &\iff R \le \log|\mathcal{A}|-H(\widetilde{P}_{1/2}) = R_c, \end{align}\] and \[\begin{align} \alpha_R \ge 1 &\iff H(\widetilde{P}_{\alpha_R}) \ge H(P_Z)\\ &\iff \log|\mathcal{A}|-R \ge H(P_Z)\\ &\iff R \le \log|\mathcal{A}|-H(P_Z) = C. \end{align}\] This concludes the proof.

In view of Lemma 3, we have \[\label{eq:proof-complexity-deterministic-doteq} \overline{q}_{d}(n,M) \doteq \mathbb{E}\left[ \min\left\{ G_u(\pmb{Z}_1),\;\frac{|\mathcal{A}|^n}{M} \right\} \right].\tag{24}\] The function \(G_u\) ranks sequences according to the values of \(u_n(\pmb{z}) \propto e^{ng(\widehat{P}_{\pmb{z}})}\), so the sequences in a type class have the same value of decoding metric. Since ties between sequences with the same metric are broken uniformly at random, the average value of \(G_u(\pmb{z})\) is \[\begin{align} G_u(\pmb{z}) &= \left| \left\{ \overline{\pmb{z}} \in \mathcal{A}^n \; \colon \;g(\widehat{P}_{\overline{\pmb{z}}}) > g(\widehat{P}_{\pmb{z}}) \right\} \right|\\ &\quad+ \frac{1}{2} \left( 1+ \left| \left\{ \overline{\pmb{z}} \in \mathcal{A}^n \; \colon \;g(\widehat{P}_{\overline{\pmb{z}}}) = g(\widehat{P}_{\pmb{z}}) \right\} \right|\right). \end{align}\] We can thus bound \[\begin{align} &\frac{1}{2} \left| \left\{ \overline{\pmb{z}} \in \mathcal{A}^n \; \colon \;g(\widehat{P}_{\overline{\pmb{z}}}) \ge g(\widehat{P}_{\pmb{z}}) \right\} \right|\\ &\le G_u(\pmb{z}) \le \left| \left\{ \overline{\pmb{z}} \in \mathcal{A}^n \; \colon \;g(\widehat{P}_{\overline{\pmb{z}}}) \ge g(\widehat{P}_{\pmb{z}}) \right\} \right|. \end{align}\] Using the method of types, we obtain \[\begin{align} &\left| \left\{ \overline{\pmb{z}} \in \mathcal{A}^n \; \colon \;g(\widehat{P}_{\overline{\pmb{z}}}) \ge g(\widehat{P}_{\pmb{z}}) \right\} \right|\\ &= \sum_{\widehat{P}_Z' \in \mathcal{P}_n(\mathcal{A}) \; \colon \;g(\widehat{P}_Z') \ge g(\widehat{P}_{\pmb{z}})} \left| \mathcal{T}_n(\widehat{P}_Z') \right| \nonumber\\ &\doteq e^{n \max_{\widehat{P}_Z' \in \mathcal{P}_n(\mathcal{A}) \colon g(\widehat{P}_Z') \ge g(\widehat{P}_{\pmb{z}})} H(\widehat{P}_Z')}. \end{align}\] Replacing that in 24 , we get \[\begin{align} \overline{q}_d(n,M) &\doteq \mathbb{E}\left[ e^{n \min\left\{ \max_{\widehat{P}_Z' \colon g(\widehat{P}_Z') \ge g(\widehat{P}_{\pmb{z}})} H(\widehat{P}_Z'),\;\log|\mathcal{A}|-R \right\}} \right] \nonumber\\ &\doteq \sum_{\widehat{P}_Z \in \mathcal{P}_n(\mathcal{A})} e^{-nD(\widehat{P}_Z \| P_Z)}\\ & \times e^{n \min\left\{ \max_{\widehat{P}_Z' \colon g(\widehat{P}_Z') \ge g(\widehat{P}_{Z})} H(\widehat{P}_Z'),\;\log|\mathcal{A}|-R \right\}} \nonumber\\ &\doteq e^{n \max_{\widehat{P}_Z \in \mathcal{P}(\mathcal{A})} \min\big\{ F_1(\widehat{P}_Z),\log|\mathcal{A}|-R \big\} - D(\widehat{P}_Z \| P_Z) }. \end{align}\]

It is enough to consider the case \(\alpha=1\). From Theorem 4 with matched decoding metric 10 , we get \[\begin{align} F_d(R;g_1) = \max_{\widehat{P}_Z\in\mathcal{P}(\mathcal{A})} &\min\left\{ F_1(\widehat{P}_Z),\;\log|\mathcal{A}|-R \right\}\\ &\quad- D(\widehat{P}_Z \| P_Z), \end{align}\] where \[\begin{align} F_1(\widehat{P}_Z) = \max_{\widehat{P}_Z' \colon H(\widehat{P}_Z'\| P_Z) \le H(\widehat{P}_Z \| P_Z)} H(\widehat{P}_Z'). \end{align}\] Noting that \(F_1(\widehat{P}_Z) \ge H(\widehat{P}_Z)\), we find \[\begin{align} F_d(R;g_1) \ge \max_{\widehat{P}_Z\in\mathcal{P}(\mathcal{A})} &\min\left\{ H(\widehat{P}_Z),\;\log|\mathcal{A}|-R \right\} \nonumber\\ &\quad- D(\widehat{P}_Z \| P_Z). \label{eq:aux-lower-bound-00} \end{align}\tag{25}\] We then prove the other direction, with an argument similar to that of [41]. Denote \(\widehat{P}_Z^{\star}\) the maximiser of \(\widehat{P}_Z \mapsto \min\big\{ H(\widehat{P}_Z), \log|\mathcal{A}|-R \big\} - D(\widehat{P}_Z\|P_Z)\). Now fix \(\widehat{P}_Z\) and denote \(\widehat{P}^{'\star}_{Z}\) the maximiser of \(H(\widehat{P}_Z')\) subject to \(H(\widehat{P}_Z'\| P_Z) \le H(\widehat{P}_Z \| P_Z)\). Two cases can occur. If \(H(\widehat{P}^{'\star}_{Z}) \le H(\widehat{P}_Z)\), then we immediately have \[\begin{align} &\min\left\{ H(\widehat{P}^{'\star}_{Z}),\;\log|\mathcal{A}|-R \right\} - D(\widehat{P}_Z\|P_Z)\\ &\le \min\left\{ H(\widehat{P}_{Z}),\;\log|\mathcal{A}|-R \right\} - D(\widehat{P}_Z\|P_Z)\\ &\le \min\left\{ H(\widehat{P}^{\star}_{Z}),\;\log|\mathcal{A}|-R \right\} - D(\widehat{P}^{\star}_Z\|P_Z). \end{align}\] Otherwise, \(H(\widehat{P}^{'\star}_{Z}) > H(\widehat{P}_Z)\), which, together with \(H(\widehat{P}^{'\star}_Z\| P_Z) \le H(\widehat{P}_Z \| P_Z)\), implies that \(D(\widehat{P}^{'\star}_Z \| P_Z) < D(\widehat{P}_Z \| P_Z)\), yielding \[\begin{align} &\min\left\{ H(\widehat{P}^{'\star}_{Z}),\;\log|\mathcal{A}|-R \right\} - D(\widehat{P}_Z\|P_Z)\\ &< \min\left\{ H(\widehat{P}^{'\star}_{Z}),\;\log|\mathcal{A}|-R \right\} - D(\widehat{P}^{'\star}_Z\|P_Z)\\ &\le \min\left\{ H(\widehat{P}^{\star}_{Z}),\;\log|\mathcal{A}|-R \right\} - D(\widehat{P}^{\star}_Z\|P_Z). \end{align}\] The conclusion is the same in either case, and valid for any \(\widehat{P}_Z\in\mathcal{P}(\mathcal{A})\), in particular for the one realising the maximum of the expression. So, together with 25 , we conclude that \[\begin{align} F_d(R;g_1) = \max_{\widehat{P}_Z\in\mathcal{P}(\mathcal{A})}&\min\left\{ H(\widehat{P}_{Z}),\;\log|\mathcal{A}|-R \right\}\\ &\quad- D(\widehat{P}_Z\|P_Z). \end{align}\] Since \(F_d(R;g_1) = F_d(R;g_{\alpha})\) for any \(\alpha>0\), we obtain ?? .

To prove ?? , we proceed similarly to Appendix 9; some details are omitted. Invoking Lemma 5, we obtain \[\begin{align} F_d(R;g_{\alpha}) = \max_{\beta\in\mathbb{R}}&\min\left\{ H(\widetilde{P}_{\beta}),\, \log|\mathcal{A}|-R \right\} - D(\widetilde{P}_{\beta}\|P_Z). \end{align}\] We can write \(F_d(R;g_{\alpha}) = \max_{\beta\in\mathbb{R}} f(\beta)\), where \[\begin{align} f(\beta) &\mathrel{\vcenter{:}}= \min\left\{H(\widetilde{P}_{\beta}),\;\log|\mathcal{A}|-R\right\} - D( \widetilde{P}_{\beta} \| P_Z )\\ &= \begin{cases} f_1(\beta), &H(\widetilde{P}_{\beta}) \le \log|\mathcal{A}|-R \\ f_2(\beta), &H(\widetilde{P}_{\beta}) \ge \log|\mathcal{A}|-R, \end{cases} \end{align}\] and \[\begin{align} f_1(\beta) &\mathrel{\vcenter{:}}= 2\psi_P(\beta) - (2\beta-1)\psi_P'(\beta),\\ f_2(\beta) &\mathrel{\vcenter{:}}= \log|\mathcal{A}|-R - (\beta-1)\psi_P'(\beta) + \psi_P(\beta). \end{align}\]

By studying the derivatives, we find that \(f_1\) is increasing for \(\beta\le1/2\) and decreasing elsewhere, with maximum value \(f_1(1/2) = 2\psi_P(1/2)\); \(f_2\) is increasing for \(\beta \le 1\) and decreasing elsewhere, with maximum \(f_2(1) = \log|\mathcal{A}|-R\). Denote \(\alpha_R\) (resp., \(\overline{\alpha}_R\)) the unique non-negative (resp., non-positive) solution on \(\alpha\in\mathbb{R}\) to \(H(\widetilde{P}_{\alpha}) = \log|\mathcal{A}|-R\). Consider the two cases.

Case 1: \(\beta\ge0\). In this case, \(H(\widetilde{P}_{\beta}) \le \log|\mathcal{A}|-R \iff \beta \le \alpha_R \iff f_1(\beta) \le f_2(\beta)\). We can identify \(\max_{\beta\ge0} f(\beta)\) by splitting the three different cases: \[\begin{align} \max_{\beta\ge0} f(\beta) = \begin{cases} 2\psi_P(1/2), & 0 \le \alpha_R \le \frac{1}{2},\\ \log|\mathcal{A}|-R-D(\widetilde{P}_{\alpha_R}\| P_Z), &\frac{1}{2} \le \alpha_R \le 1,\\ \log|\mathcal{A}|-R, &\alpha_R \ge 1. \end{cases} \end{align}\]

Case 2: \(\beta\le0\). In this case, \(H(\widetilde{P}_{\beta}) \le \log|\mathcal{A}|-R \iff \beta \ge \overline{\alpha}_R \iff f_1(\beta) \le f_2(\beta)\), and \(\min_{\beta\le0} f(\beta) = f_2(0)\), which is always less than the maximiser of the first case.

The solution is \(\max_{\beta\in\mathbb{R}} f(\beta) = \max_{\beta\ge0} f(\beta)\), as given above. The description of the intervals is the same as in Appendix 9.

Item 1 follows from the monotonicity of \(\alpha \mapsto E_r(R;g_{\alpha})\) in ?? and the optimality of the ML decoder.

For item 2, we invoke [15], which states that the average probability of error of matched randomised decoding is at most twice that of matched deterministic decoding, that is, \(\overline{p}_{e,d}(n,M;g_{1}) \le \overline{p}_{e,r}(n,M;g_{1}) \le 2 \overline{p}_{e,d}(n,M;g_{1})\), which implies that \(E_{r}(R;g_1) = E_d(R;g_1)\).

For the remaining, we note that, by the same arguments used in Lemma 5, the minimisations in ?? can be reduced to tilted distributions, and the exponent can be written as \[\begin{align} E_r(R;{g}_{\alpha}) = &\min_{\gamma\in\mathbb{R}} D(\widetilde{P}_{\gamma} \| P_Z )\\ &+ \min_{\beta\in\mathbb{R}} \bigg[ \alpha \left[ H(\widetilde{P}_{\beta}\| P_Z) - H(\widetilde{P}_{\gamma}\| P_Z) \right]_+\\ &+ \log|\mathcal{A}| - H(\widetilde{P}_{\beta}) - R \bigg]_+. \end{align}\] Since \(\beta \mapsto \psi_P'(\beta)\) is increasing, \(H(\widetilde{P}_{\beta} \| P_Z) - H(\widetilde{P}_{\gamma} \| P_Z) \ge 0\) whenever \(\beta\le\gamma\). So we can split the inner minimisation into \[\begin{align} F(\gamma) &\mathrel{\vcenter{:}}= \min_{\beta\in\mathbb{R}} \bigg[ \alpha \left[ H(\widetilde{P}_{\beta}\| P_Z) - H(\widetilde{P}_{\gamma}\| P_Z) \right]_+\\ &+ \log|\mathcal{A}| - H(\widetilde{P}_{\beta}) - R \bigg]_+ \nonumber\\ &= \min\Bigg\{ \min_{\beta\le\gamma} \bigg[ \alpha \left( H(\widetilde{P}_{\beta}\| P_Z) - H(\widetilde{P}_{\gamma}\| P_Z) \right)\\ &+ \log|\mathcal{A}| - H(\widetilde{P}_{\beta}) - R \bigg]_+ ,\; \nonumber\\ &\min_{\beta \ge \gamma} \left[ \log|\mathcal{A}|-H(\widetilde{P}_{\beta})-R \right]_+ \Bigg\}. \end{align}\] Denote \[\begin{align} f_{1}(\beta) &\mathrel{\vcenter{:}}= \alpha \left( H(\widetilde{P}_{\beta}\| P_Z) - H(\widetilde{P}_{\gamma}\| P_Z) \right)\\ &\quad + \log|\mathcal{A}| - H(\widetilde{P}_{\beta}) - R\\ &= \alpha \psi_P'(\gamma) + \left( \beta - \alpha \right)\psi_P'(\beta) - \psi_P(\beta) + \log|\mathcal{A}| - R. \end{align}\] The function \(f_1\) is increasing for \(\beta \ge \alpha\), and decreasing elsewhere; thus \[\begin{align} \label{eq:ch3-aux-f-bar-1} F_1(\gamma) \mathrel{\vcenter{:}}= \min_{\beta\le\gamma} \left[ f_1(\beta) \right]_+ = \begin{cases} \left[ f_1(\gamma) \right]_+, & \gamma\le \alpha,\\ \left[ f_1\left( \alpha \right) \right]_+, & \gamma \ge \alpha. \end{cases} \end{align}\tag{26}\] Similarly, denote \[\begin{align} f_2(\beta) &\mathrel{\vcenter{:}}= \log|\mathcal{A}| - H(\widetilde{P}_{\gamma}) - R\\ &= \log|\mathcal{A}| - R - \psi_P(\beta) + \beta\psi_P'(\beta). \end{align}\] This function is decreasing for \(\beta\le0\) and increasing for \(\beta\ge0\), with minimum value \(f_2(0) = -R\). Note that \(f_2\) is negative for \(0 \le \beta \le \alpha_R\), with \(\alpha_R>0\) satisfying \(H(\widetilde{P}_{\alpha_R}) = \log|\mathcal{A}|-R\). We deduce that \[\begin{align} \label{eq:ch3-aux-f-bar-2} F_2(\gamma) \mathrel{\vcenter{:}}= \min_{\beta\ge\gamma} \left[ f_2(\beta) \right]_+ = \begin{cases} 0, & \gamma \le \alpha_R,\\ f_2(\gamma), &\gamma \ge \alpha_R. \end{cases} \end{align}\tag{27}\] With these, we have \(F(\gamma) = \min\left\{ F_1(\gamma),\; F_2(\gamma) \right\}\) and \[\label{eq:ch3-aux-min-F} E_r(R;g_{\alpha}) = \min_{\gamma\in\mathbb{R}} D(\widetilde{P}_{\gamma} \| P_Z ) + F(\gamma).\tag{28}\]

For item 3, consider \(0 \le \alpha_R\le1/2\) and \(\alpha = 1/2\). Taking that into account in 26 and 27 , we have \[F(\gamma) = \begin{cases} 0, &\gamma \le \alpha_R,\\ \log|\mathcal{A}|-H(\widetilde{P}_{\gamma})-R, &\alpha_R \le \gamma \le \frac{1}{2},\\ (\spadesuit), &\gamma\ge\frac{1}{2}. \end{cases}\] with \[\begin{align} (\spadesuit) = &\frac{1}{2}\left( H(\widetilde{P}_{1/2}\|P_Z) - H(\widetilde{P}_{\gamma}\|P_Z) \right)\\ &+ \log|\mathcal{A}| - H(\widetilde{P}_{1/2}) - R. \end{align}\]

Accordingly, the minimisation in 28 declines in three cases, which can be treated separately using again the same techniques. Namely, \[\begin{align} \widetilde{E}_1 &\mathrel{\vcenter{:}}= \min_{\gamma \le \alpha_R} D(\widetilde{P}_{\gamma} \| P_Z)\\ &= D(\widetilde{P}_{\alpha_R} \| P_Z),\\ \widetilde{E}_2 &\mathrel{\vcenter{:}}= \min_{\alpha_R \le \gamma \le 1/2} D(\widetilde{P}_{\gamma} \| P_Z) + \log|\mathcal{A}|-H(\widetilde{P}_{\gamma})-R\\ &= D(\widetilde{P}_{1/2} \| P_Z) + \log|\mathcal{A}|-H(\widetilde{P}_{1/2})-R,\\ \widetilde{E}_3 &\mathrel{\vcenter{:}}= \min_{\gamma\ge1/2} D(\widetilde{P}_{\gamma} \| P_Z) + \frac{1}{2}\left( H(\widetilde{P}_{1/2}\|P_Z) - H(\widetilde{P}_{\gamma}\|P_Z) \right)\\ &+ \log|\mathcal{A}| - H(\widetilde{P}_{1/2}) - R\\ &= D(\widetilde{P}_{1/2} \| P_Z) + \log|\mathcal{A}|-H(\widetilde{P}_{1/2})-R, \end{align}\] and \(E_r(R;g_{\alpha}) = \min\{ \widetilde{E}_1,\, \widetilde{E}_2,\, \widetilde{E}_3 \}\). We have \(\widetilde{E}_1 \ge \widetilde{E}_2 = \widetilde{E}_3\), which can be seen by noting that \(\alpha \mapsto D(\widetilde{P}_{\alpha}\|P_Z) - H(\widetilde{P}_{\alpha})\) is minimised at \(\alpha=1/2\), and recalling that \(H(\widetilde{P}_{\alpha_R}) = \log|\mathcal{A}|-R\). Thus, in this case, we have \[\begin{align} E_r(R;g_{\alpha}) &= D(\widetilde{P}_{1/2} \| P_Z) + \log|\mathcal{A}|- H(\widetilde{P}_{1/2}) - R\nonumber\\ &= \log|\mathcal{A}| - R - H_{1/2}(P_Z), \end{align}\] where we used that \(D(\widetilde{P}_{1/2} \| P_Z) -H(\widetilde{P}_{1/2}) = -H_{1/2}(P_Z)\). This expression coincides with \(E_d(R;g_1)\) in the same regime (see ?? ). Using ?? , we conclude that the same is true for any \(\alpha\ge1/2\).

For item 4, consider \(1/2 \le \alpha_R \le 1\) and \(\alpha=\alpha_R\). Note that \[\begin{align} &f_1\left( \alpha_R \right) \le f_2(\gamma)\\ &\iff g(\gamma) \mathrel{\vcenter{:}}= \psi_P(\alpha_R) + (\gamma-\alpha_R) \psi_P'(\gamma) - \psi_P(\gamma) \ge 0, \end{align}\] which can be seen to be true by noting that \(\gamma \mapsto g(\gamma)\) has minimum value \(g(\alpha_R) = 0\). Considering 26 and 27 , we conclude that \[\begin{align} F(\gamma) = \begin{cases} 0, & \gamma \le \alpha_R\\ \alpha_R \left( \psi_P'(\gamma) - \psi_P'(\alpha_R) \right), & \gamma \ge \alpha_R., \end{cases} \end{align}\] and thus, \[\begin{align} E_r(R;{g}_{\alpha}) &= \min \bigg\{ \min_{\gamma \le \alpha_R} D(P_{\gamma}\|P_Z),\\ &\min_{\gamma\ge\alpha_R} D(P_{\gamma}\|P_Z) + \alpha_R \left( \psi_P'(\gamma) - \psi_P'(\alpha_R) \right) \bigg\}. \end{align}\] Using the same techniques as before, we can show that \[\begin{align} \min_{\gamma \le \alpha_R} D(P_{\gamma}\|P_Z) &= \min_{\gamma \le \alpha_R}(\gamma-1)\psi_P'(\gamma)-\psi_P(\gamma) \\ &= \begin{cases} 0, & \alpha_R \ge 1\\ D(\widetilde{P}_{\alpha_R} \| P_Z), & \alpha_R \le 1, \end{cases} \end{align}\] and \[\begin{align} &\min_{\gamma\ge\alpha_R} D(P_{\gamma}\|P_Z) + \alpha_R \left( \psi_P'(\gamma) - \psi_P'(\alpha_R) \right)\\ &= \min_{\gamma\ge\alpha_R} (\gamma-1+\alpha_R)\psi_P'(\gamma) - \psi_P(\gamma) - \alpha_R\psi_P'(\alpha_R)\\ &= D(\widetilde{P}_{\alpha_R}\| P_Z). \end{align}\] Combining these, we get, in this case, \[E_r(R;{g}_{\alpha}) = D(\widetilde{P}_{\alpha_R}\| P_Z),\] which once again agrees with \(E_d(R;g_1)\) in the same regime (see ?? ). And ?? allows us to conclude the same holds for any \(\alpha\ge\alpha_R\).

Since \(Q_u\left( \bigcup_{m'=1}^{M} \left\{ \pmb{Z}_{m'} \right\} \right) \le \sum_{m'=1}^{M} Q_u(\pmb{Z}_{m'})\), we immediately get the lower bound \[\begin{align} \overline{q}_r(n,M) \ge \mathbb{E}\left[ \frac{1}{Q_u\left( \pmb{Z}_1 \right) + \sum_{m'=1}^{M} Q_u\left( \pmb{Z}_{m'} \right)} \right]. \label{eq:ch3-union-sum-lower-bound} \end{align}\tag{29}\]

For the upper bound, fix \(\pmb{Z}_1 = \pmb{z}_1\) in 22 and study the expectation with respect to the other variables. Define the random variables \(\widetilde{N}_{\pmb{z}} \mathrel{\vcenter{:}}= \widetilde{N}_{\pmb{z}}\left(\pmb{Z}_2, \dots, \pmb{Z}_M\right) \mathrel{\vcenter{:}}= \sum_{m'=2}^{M} \mathbb{1}_{\{\pmb{z}\}}(\pmb{Z}_{m'})\), and \(N_{\pmb{z}} \mathrel{\vcenter{:}}= N_{\pmb{z}} \left(\pmb{z}_1, \pmb{Z}_2, \dots, \pmb{Z}_M\right) \mathrel{\vcenter{:}}= \mathbb{1}_{\{\pmb{z}\}}(\pmb{z}_1) + \widetilde{N}_{\pmb{z}}\), as well as the set \[\mathcal{E}_n \mathrel{\vcenter{:}}= \left\{ (\pmb{z}_1,\dots,\pmb{z}_M) \; \colon \;\forall {\pmb{z}\in \mathcal{A}^n},\;N_{\pmb{z}}(\pmb{z}_1,\dots,\pmb{z}_M) \le n^2+1 \right\}.\] For convenience, denote \[\Psi(\pmb{Z}_2,\dots,\pmb{Z}_M) \mathrel{\vcenter{:}}= \frac{1}{Q_u\left( \left\{ \pmb{z}_1 \right\} \cup \bigcup_{m'=2}^{M} \left\{ \pmb{Z}_{m'} \right\} \right)},\] and split the expectation 22 into \[\begin{align} \label{eq:split-inner-expectation} &\mathbb{E}\left[ \Psi(\pmb{Z}_2,\dots,\pmb{Z}_M) \right]\nonumber\\ &= \mathbb{E}\left[ \Psi(\pmb{Z}_2,\dots,\pmb{Z}_M) \mathbb{1}_{\mathcal{E}_n}(\pmb{z}_1,\pmb{Z}_2,\dots,\pmb{Z}_M) \right] \nonumber\\ &\quad+ \mathbb{E}\left[ \Psi(\pmb{Z}_2,\dots,\pmb{Z}_M) \mathbb{1}_{\mathcal{E}_n^{\mathsf{c}}}(\pmb{z}_1,\pmb{Z}_2,\dots,\pmb{Z}_M) \right]. \end{align}\tag{30}\]

The first term of 30 only counts the sequences such that \((\pmb{z}_1,\pmb{Z}_2,\dots,\pmb{Z}_M) \in \mathcal{E}_n\). For those, we have \[\begin{align} \frac{1}{\Psi(\pmb{Z}_2,\dots,\pmb{Z}_M)} &= \sum_{\pmb{z}\in\mathcal{A}^n} Q_u(\pmb{z}) \mathbb{1}_{\{ \pmb{z}_1, \pmb{Z}_2, \dots, \pmb{Z}_M \}}(\pmb{z}) \nonumber\\ &\ge \sum_{\pmb{z}\in\mathcal{A}^n} Q_u(\pmb{z}) \frac{N_{\pmb{z}}}{n^2+1} \nonumber\\ &= \frac{1}{n^2+1} \left( Q_u(\pmb{z}_{1}) + \sum_{m'=2}^{M} Q_u(\pmb{Z}_{m'}) \right). \end{align}\] And, thus, \[\begin{align} &\mathbb{E}\left[ \Psi(\pmb{Z}_2,\dots,\pmb{Z}_M) \mathbb{1}_{\mathcal{E}_n}(\pmb{z}_1,\pmb{Z}_2,\dots,\pmb{Z}_M) \right] \nonumber\\ &\le \big( n^2+1 \big) \mathbb{E}\left[ \frac{1}{Q_u(\pmb{z}_1) + \sum_{m'=2}^{M} Q_u(\pmb{Z}_{m'}) } \right]. \label{eq:split-inner-expecatation-term-1} \end{align}\tag{31}\]

For the second term of 30 , we have \[\begin{align} &\mathbb{E}\left[ \Psi(\pmb{Z}_2,\dots,\pmb{Z}_M) \mathbb{1}_{\mathcal{E}_n^{\mathsf{c}}}(\pmb{z}_1,\pmb{Z}_2,\dots,\pmb{Z}_M) \right]\nonumber\\ &\le \frac{1}{\min_{\pmb{z}\in\mathcal{A}} Q_u(\pmb{z})} \, \mathbb{P}\left( (\pmb{z}_1,\pmb{Z}_{2},\dots,\pmb{Z}_M) \notin \mathcal{E}_n \right). \nonumber \end{align}\] We apply Chernoff’s bound to bound the probability . Specifically, noting that \(\widetilde{N}_{\pmb{z}} \sim \mathsf{Bin}\left( M-1, |\mathcal{A}|^{-n} \right)\), we have \[\begin{align} &\mathbb{P}\left( (\pmb{z}_1,\pmb{Z}_2,\dots,\pmb{Z}_M) \notin \mathcal{E}_n \right)\\ &= \mathbb{P}\left( \bigcup_{\pmb{z}\in\mathcal{A}^n} \left\{ N_{\pmb{z}} > n^2+1 \right\} \right)\\ &\le \sum_{\pmb{z}\in\mathcal{A}^n} \mathbb{P}\left( \mathbb{1}\{\pmb{z}_1=\pmb{z}\} + \widetilde{N}_{\pmb{z}} > n^2+1 \right)\\ &\le |\mathcal{A}|^n \cdot \mathbb{P}\left( \widetilde{N}_{\pmb{z}} > n^2 \right)\\ &\le |\mathcal{A}|^n \exp\left( - (M-1)\, d\left( \frac{n^2}{M-1} \middle\| \frac{1}{|\mathcal{A}|^n} \right) \right)\\ &\le \exp\left( - n^3 \left( \log|\mathcal{A}| - R + \epsilon(n) \right) \right), \end{align}\] where \(\epsilon(n) \mathrel{\vcenter{:}}= {(2\log n - 1)}/{n} - {(\log|\mathcal{A}|)}/{n^2}\) and in the last step we used that \(d(p\|q) \ge p\log\frac{p}{q}-p\) [42]. Thus, \[\begin{align} &\mathbb{E}\left[ \Psi(\pmb{Z}_2,\dots,\pmb{Z}_M) \mathbb{1}_{\mathcal{E}_n^{\mathsf{c}}}(\pmb{z}_1,\pmb{Z}_2,\dots,\pmb{Z}_M) \right]\nonumber\\ &\le e^{nC_0} \cdot \exp\left( - n^3 \left( \log|\mathcal{A}| - R + \epsilon(n) \right) \right), \label{eq:split-inner-expecatation-term-2} \end{align}\tag{32}\]

Replacing 31 and 32 in 30 and taking the expectation with respect to \(\pmb{Z}_1\), we find \[\begin{align} \overline{q}_{r}(n,M) &\le \big( n^2+1 \big) \mathbb{E}\left[ \frac{1}{Q_u(\pmb{Z}_1) + \sum_{m'=2}^{M} Q_u(\pmb{Z}_{m'}) } \right] \nonumber \\ &+ e^{n C_0} e^{-n^3 \left( \log|\mathcal{A}|-R+\epsilon(n) \right)}. \label{eq:ch3-union-sum-upper-bound} \end{align}\tag{33}\]

With the hypotheses in the statement, 33 is dominated by the expectation term, and \(\overline{q}_{r}(n,M) \mathop{\mathrm{\,\dot{\le}\,}}e^{F_0}\). The lower bound 29 implies that \(\overline{q}_{r}(n,M) \mathop{\mathrm{\,\dot{\ge}\,}}e^{F_0}\), which establishes the desired result.

We need to bound the integral in 35 . The lower bound is shown in 5, and the upper bound in 6.

This is inspired by  [43]. Denote \(\epsilon(n) \mathrel{\vcenter{:}}= \epsilon_1(n) + \epsilon_2(n)\). Note, using 37 , 38 and 39 in 40 , that we are looking for the largest value of \(\theta \in \mathbb{R}_+\) such that \[\begin{align} &\min_{\widehat{P}_{Z} \in \mathcal{P}_n(\mathcal{A})} \log|\mathcal{A}| - H(\widehat{P}_{Z}) - R + \epsilon(n)\\ &+ \left[ \widetilde{g}_n(\widehat{P}_{Z}) - \theta - \zeta(n) \right]_+ \ge 0. \end{align}\] Using the identity \(\left[x\right]_+ = \max_{\rho\in\left[0,1\right]} \rho x\), this is equivalent to \(\forall \widehat{P}_{Z} \in \mathcal{P}_n(\mathcal{A}),\; \exists \rho\in\left[0,1\right]\) such that \[\begin{align} \log|\mathcal{A}| - H(\widehat{P}_{Z}) - R + \epsilon(n) + \rho \left( \widetilde{g}_n(\widehat{P}_{Z}) - \theta - \zeta(n) \right) \ge 0, \end{align}\] or, equivalently, \[\begin{align} \theta \le \widetilde{g}_n(\widehat{P}_{Z}) - \zeta(n) + \frac{\log|\mathcal{A}| - H(\widehat{P}_{Z}) - R + \epsilon(n)}{\rho}. \end{align}\] This can also be written as \[\begin{align} \theta \le &\min_{\widehat{P}_{Z} \in \mathcal{P}_n(\mathcal{A})} \max_{\rho\in\left[0,1\right]} \widetilde{g}_n(\widehat{P}_{Z}) - \zeta(n)\\ &+ \frac{\log|\mathcal{A}| - H(\widehat{P}_{Z}) - R + \epsilon(n)}{\rho}. \end{align}\] Note that \[\begin{align} &\max_{\rho\in\left[0,1\right]} \frac{\log|\mathcal{A}| - H(\widehat{P}_{Z}) - R + \epsilon(n)}{\rho} \\ &=\begin{cases} +\infty, &\log|\mathcal{A}| - H(\widehat{P}_{Z}) - R + \epsilon(n) > 0,\\ (\clubsuit), &\log|\mathcal{A}| - H(\widehat{P}_{Z}) - R + \epsilon(n) \le 0, \end{cases} \end{align}\] where \((\clubsuit) = \log|\mathcal{A}| - H(\widehat{P}_{Z}) - R + \epsilon(n)\). Therefore, the minimum can only happen in the second case, and the largest value of \(\theta\) such that \(\Phi_n(\theta) \ge 0\) is \[\begin{align} \theta_n^{*} =\min_{\widehat{P}_{Z} \in \mathcal{V}_n} \widetilde{g}_n(\widehat{P}_{Z}) - \zeta(n) + \log|\mathcal{A}| - H(\widehat{P}_{Z}) - R + \epsilon(n). \end{align}\] The result for \(\theta^*\) is analogous.

Since \(\overline{\theta}>0\), we have \(\overline{\theta}_n > 0\) for \(n\) large enough; we work in that regime. The upper bound is trivial: \[\begin{align} I_1(n) \le \int_{0}^{\overline{\theta}_n} e^{n\theta}~\mathrm{d}\theta = \frac{e^{n\overline{\theta}_n}-1}{n} \doteq e^{n\overline{\theta}}. \end{align}\] For the lower bound, we use that \[\begin{align} &\mathbb{P}\left( \bigcap_{\widehat{P}_{Z} \in \mathcal{P}_n(\mathcal{A})} \left\{ N_n(\widehat{P}_{Z}) \le e^{n\lambda_\theta(\widehat{P}_Z)} \right\} \right) \nonumber\\ &= 1 - \mathbb{P}\left( \bigcup_{\widehat{P}_{Z} \in \mathcal{P}_n(\mathcal{A})} \left\{ N_n(\widehat{P}_{Z}) > e^{n\lambda_\theta(\widehat{P}_Z)} \right\} \right) \nonumber\\ &\ge 1 - \sum_{\widehat{P}_{Z} \in \mathcal{P}_n(\mathcal{A})} \mathbb{P}\left( N_n(\widehat{P}_{Z}) > e^{n\lambda_\theta(\widehat{P}_Z)} \right)\nonumber\\ &\ge 1 - |\mathcal{P}_n(\mathcal{A})| \max_{\widehat{P}_{Z} \in \mathcal{P}_n(\mathcal{A})} \mathbb{P}\left( N_n(\widehat{P}_{Z}) > e^{n\lambda_\theta(\widehat{P}_Z)} \right). \label{eq:aux-bound-prob-inter} \end{align}\tag{45}\] If \(\lambda_{n,\theta}(\widehat{P}_{Z}) < 0\), then we have, by Markov’s inequality, \[\begin{align} \mathbb{P}\left( N_n(\widehat{P}_{Z}) > e^{n \lambda_{n,\theta}(\widehat{P}_{Z}) } \right) &= \mathbb{P}\left( N_n(\widehat{P}_{Z}) \ge 1 \right)\\ &\le \frac{\mathbb{E}\left[ N_n(\widehat{P}_{Z}) \right]}{1}\\ &= e^{-n\left( B_n(\widehat{P}_{Z}) - A_n \right)}. \end{align}\] And, if \(\lambda_{n,\theta}(\widehat{P}_{Z}) \ge 0\), another application of Markov’s inequality yields \[\begin{align} \mathbb{P}\left( N_n(\widehat{P}_{Z}) > e^{n \lambda_{n,\theta}(\widehat{P}_{Z}) } \right) &\le \frac{\mathbb{E}\left[ N_n(\widehat{P}_{Z}) \right]}{e^{n \lambda_{n,\theta}(\widehat{P}_{Z}) }}\\ &= e^{-n\left( B_n(\widehat{P}_Z) - A_n + \lambda_{n,\theta}(\widehat{P}_Z) \right)}. \end{align}\] Together, we have \[\begin{align} &\mathbb{P}\left( N_n(\widehat{P}_{Z}) > e^{n \lambda_{n,\theta}(\widehat{P}_{Z}) } \right) \nonumber\\ &\le e^{-n\left( B_n(\widehat{P}_Z) - A_n + \left[\lambda_{n,\theta}(\widehat{P}_Z)\right]_+ \right)}. \label{eq:aux-bound-prob-tail-0} \end{align}\tag{46}\] Note that \(\theta < \overline{\theta}_n\) implies \(\theta < \theta_n^{*}\), and, by the definition in 41 , for \(0 \le \theta < \theta_n^*\), \[\begin{align} \min_{\widehat{P}_{Z} \in \mathcal{P}_n(\mathcal{A})} B_n(\widehat{P}_{Z}) - A_n + \left[ \lambda_{n,\theta}(\widehat{P}_{Z}) \right]_+ > 0. \end{align}\]

Take \(\varepsilon > 0\). We can bound \[\begin{align} &I_1(n)\\ &\ge \int_{0}^{\overline{\theta}_n - \varepsilon} e^{n\theta}\\ &\quad\times \mathbb{P}\left( \bigcap_{\widehat{P}_{Z} \in \mathcal{P}_n(\mathcal{A})} \left\{ N_n(\widehat{P}_{Z}) \le e^{n\lambda_\theta(\widehat{P}_Z)} \right\} \right) \mathrm{d}\theta\\ &\ge \int_{0}^{\overline{\theta}_n - \varepsilon} e^{n\theta}\\ &\times \left( 1 - |\mathcal{P}_n(\mathcal{A})|\max_{\widehat{P}_{Z}} \mathbb{P}\left( N_n(\widehat{P}_{Z}) > e^{n\lambda_\theta(\widehat{P}_Z)} \right)\right) \mathrm{d}\theta\\ &\ge \int_{0}^{\overline{\theta}_n - \varepsilon} e^{n\theta} \left(1 - e^{- n \left( \Phi_n(\theta) - \delta(n) \right) }\right) \mathrm{d}\theta\\ &\ge \left(1 - e^{- n \left( \Phi_n(\overline{\theta}_n - \varepsilon) - \delta(n) \right) }\right) \frac{e^{n(\overline{\theta}_n-\varepsilon)}-1}{n}, \end{align}\] where in the second inequality we used 45 ; in the third, 46 and the notation from 40 ; in the fourth, that \(\theta \mapsto \Phi_n(\theta)\) is non-increasing. Noting that \(\Phi_n(\overline{\theta}_n-\epsilon)>0\), we get \(I_1(n) \mathop{\mathrm{\,\dot{\ge}\,}}e^{n(\overline{\theta} - \varepsilon)}\), and the proof is concluded by letting \(\varepsilon\to0\).

The lower bound \(I_2(n) \ge 0\) is immediate. If \(\widetilde{g}_n(\widehat{P}_{\pmb{z}_1}) + \eta(n) \le \theta_n^{*}\), then \(I_2(n) = 0\), and we are done. So, to complete the proof, in the following we suppose \(\widetilde{g}_n(\widehat{P}_{\pmb{z}_1}) + \eta(n) > \theta_n^{*}\). For \(\theta > \theta_n^{*}\), the definition of \(\theta_n^*\) in 41 implies that \[\begin{align} \min_{\widehat{P}_{Z} \in \mathcal{P}_n(\mathcal{A})} B_n(\widehat{P}_{Z}) - A_n + \left[ \lambda_{n,\theta}(\widehat{P}_{Z}) \right]_+ < 0, \end{align}\] or, equivalently, there exists \(\widetilde{P}_{Z} \in \mathcal{P}_n(\mathcal{A})\) such that \[\begin{align} \max\left\{ B_n(\widetilde{P}_{Z}) - A_n,\; B_n(\widetilde{P}_{Z}) - A_n + \lambda_{n,\theta}(\widetilde{P}_{Z}) \right\} < 0, \end{align}\] that is, such that \(A_n > B_n(\widetilde{P}_{Z})\) and \(A_n > B_n(\widetilde{P}_{Z}) + \lambda_{n,\theta}(\widetilde{P}_{Z})\). Take \(\varepsilon > 0\). We can bound \[\begin{align} I_2(n) &= \int_{\theta_n^{*}}^{\widetilde{g}_n(\widehat{P}_{\pmb{z}_1}) + \eta(n)} e^{n\theta}\\ &\times \mathbb{P}\left( \bigcap_{\widehat{P}_{Z} \in \mathcal{P}_n(\mathcal{A})} \left\{ N_n(\widehat{P}_{Z}) \le e^{n\lambda_{n,\theta}(\widehat{P}_Z)} \right\} \right) \mathrm{d}\theta\\ &\le \int_{\theta_n^{*}}^{\widetilde{g}_n(\widehat{P}_{\pmb{z}_1}) + \eta(n)} e^{n\theta} \cdot \mathbb{P}\left( N_n(\widetilde{P}_{Z}) \le e^{n \lambda_{n,\theta}(\widetilde{P}_{Z})} \right) \mathrm{d}\theta\\ &\le \underbrace{\int_{\theta_n^{*}}^{\theta_n^{*}+\varepsilon} e^{n\theta} \mathrm{d}\theta}_{I_{2,a}(n)}\\ &\quad+ \underbrace{\int_{\theta_n^{*}+\varepsilon}^{\widetilde{g}_n(\widehat{P}_{\pmb{z}_1}) + \eta(n)} e^{n\theta} \cdot \mathbb{P}\left( N_n(\widetilde{P}_{Z}) \le e^{n \lambda_{n,\theta}(\widetilde{P}_{Z})} \right) \mathrm{d}\theta}_{I_{2,b}(n)}. \end{align}\]

Applying Chernoff’s bound and using that \(d(p\|q) \ge p \log\frac{p}{q}+q-p\) [42], we get \[\begin{align} &\mathbb{P}\left( {N}_n(\widetilde{P}_Z) \le e^{n \lambda_\theta(\widetilde{P}_Z)} \right)\\ &\le \exp \left( -e^{n A_n} d\left( e^{-n({A}_n- \lambda_\theta(\widetilde{P}_Z))} \middle\| e^{-n{B}_n(\widetilde{P}_Z)} \right) \right)\\ &\le \exp \left( -e^{n\left({A}_n - {B}_n(\widetilde{P}_Z)\right)} \right)\\ &\times\exp \left( n e^{n \lambda_{n,\theta}(\widetilde{P}_Z) } \left( {A}_n - {B}_n(\widetilde{P}_Z) - \lambda_{n,\theta}(\widetilde{P}_Z) + \frac{1}{n} \right) \right), \end{align}\] which decays super-exponentially, and is responsible for the super exponential decay of \(I_{2,b}(n) \to 0\). The first term is \(I_{2,a}(n) \doteq e^{n(\overline{\theta} + \varepsilon)}\) and dominates the expression of \(I_2(n)\). To conclude, take \(\varepsilon\to0\).

From 43 , Propositions 19, 20 and 21, we have, for each fixed \(\pmb{z}_1\in\mathcal{A}^n\) such that \(\overline{\theta}>0\), \[\begin{align} I(n) &= I_1(n) + I_2(n)\\ &\doteq e^{n \min\left\{ -g(\widehat{P}_{\pmb{z}_1}),\;\log|\mathcal{A}|-R+ F_3(R;g) \right\}}. \end{align}\] If \(\overline{\theta}=0\), then \(I_1(n) \doteq 0\) and \(I_2(n) \doteq 1\), so the above asymptotic equality holds as well. From Proposition 18 and using the method of types to average over \(\pmb{Z}_1 \sim P_{\pmb{Z}}\), we obtain \[\begin{align} &\mathbb{E}\left[ \frac{1}{Q_u(\pmb{Z}_1) + \sum_{m'=2}^{M} Q_u(\pmb{Z}_{m'})} \right]\\ &\doteq \sum_{\pmb{z}_1\in\mathcal{A}^n} P_{\pmb{Z}}(\pmb{z}_1) e^{n \min\left\{ -{g}(\widehat{P}_{\pmb{z}_1}),\;\log|\mathcal{A}|-R+ F_3(R;{g}) \right\}}\\ &\doteq \sum_{\widehat{P}_Z \in \mathcal{P}_n(\mathcal{A})} e^{-nD(\widehat{P}_Z\|P_Z)} e^{n \min\left\{ -{g}(\widehat{P}_{Z}),\;\log|\mathcal{A}|-R+ F_3(R;{g}) \right\}}\\ &\doteq e^{n \min_{\widehat{P}_Z \in \mathcal{P}(\mathcal{A})} \left( \min\left\{ -{g}(\widehat{P}_{Z}),\;\log|\mathcal{A}|-R+ F_3(R;{g}) \right\} - D(\widehat{P}_Z\|P_Z) \right)}. \end{align}\] Finally, we invoke Proposition 17 with the above result to conclude.

The expression ?? is directly obtained by using 9 in Theorem 11. We now prove ?? . An application of Lemma 5 to ?? reveals that \[\begin{align} F_r(R;{g}_{\alpha}) = \max_{\beta\in\mathbb{R}} &\min\left\{ H\big( \widetilde{P}_{\beta} \| \widetilde{P}_{\alpha}\big), \log|\mathcal{A}| - R + F_3(R;g_{\alpha}) \right\}\\ &- D\big( \widetilde{P}_{\beta} \| P_Z \big). \end{align}\] Using the notation from Appendix 8, and introducing \(\nu_\alpha(R) \mathrel{\vcenter{:}}= \log|\mathcal{A}| - R + F_3(R;g_{\alpha})\), we have \(F_r(R;{g}_{\alpha}) = \max_{\beta\in\mathbb{R}} f(\beta)\), where \[\begin{align} f(\beta) &\mathrel{\vcenter{:}}= \min\left\{ -\alpha\psi_P'(\beta)+\psi_P(\alpha),\;\nu_{\alpha}(R) \right\}\\ &\quad- (\beta-1)\psi_P'(\beta) + \psi_P(\beta)\\ &=\begin{cases} f_1(\beta), &\beta\in\mathcal{R}_1,\\ f_2(\beta), &\beta\in\mathcal{R}_2, \end{cases} \end{align}\] with \[\begin{align} f_1(\beta) &\mathrel{\vcenter{:}}= (1-\alpha-\beta) \psi_P'(\beta)+\psi_P(\alpha) + \psi_P(\beta),\\ f_2(\beta) &\mathrel{\vcenter{:}}= \nu_{\alpha}(R) - (\beta-1)\psi_P'(\beta) + \psi_P(\beta),\\ \mathcal{R}_1 &\mathrel{\vcenter{:}}= \left\{ \beta\in\mathbb{R}\; \colon \; \alpha\psi_P'(\beta) \ge \psi_P(\alpha) - \nu_{\alpha}(R) \right\}, \end{align}\] and \(\mathcal{R}_2 \mathrel{\vcenter{:}}= \mathbb{R}\setminus \mathcal{R}_1\). Since \(\beta \mapsto \psi_P'(\beta)\) is increasing (Proposition 16, item 2), the regions take the form of intervals \(\mathcal{R}_1 = \left[\beta_{\alpha,R},\; +\infty \right[\) and \(\mathcal{R}_2 = \left]-\infty,\; \beta_{\alpha,R}\right[\), where \(\beta_{\alpha,R}\mathrel{\vcenter{:}}= \inf_{\beta\in\mathbb{R}} \mathcal{R}_1\) is such that \[\label{eq:def-beta-alpha-r} \alpha\psi'_P(\beta_{\alpha,R}) = \psi_P(\alpha) - \nu_{\alpha}(R).\tag{47}\]

Studying the derivatives, we deduce that \(f_1\) is increasing for \(\beta\le1-\alpha\) and decreasing elsewhere; \(f_2\) is increasing for \(\beta\le1\) and decreasing elsewhere. We can identify the maximiser \(\beta^{\star}\) of \(f\), by considering three cases.

• Regime I: \(\beta_{a,R} \le 1 - \alpha\). For \(\beta\le\beta_{\alpha,R}\), \(f=f_2\) and is increasing. For \(\beta\ge\beta_{\alpha,R}\), \(f=f_1\), which increases until attaining the maximum at \(\beta=1-\alpha\), and then decreases. Thus, in this regime, \(\beta^{\star}=1-\alpha\), and \[f(\beta^{\star}) = f_1(1-\alpha) = \psi_P(\alpha) + \psi_P(1-\alpha).\]

• Regime II: \(1-\alpha \le \beta_{\alpha,R} \le 1\). For \(\beta\le\beta_{\alpha,R}\), \(f=f_2\) and is increasing. For \(\beta\ge\beta_{\alpha,R}\), \(f=f_1\) and is decreasing. Thus, the maximum is attained at \(\beta^{\star} = \beta_{\alpha,R}\), with \[\begin{align} f(\beta^{\star}) &= f_1(\beta_{\alpha,R})\\ &= (1-\alpha-\beta_{\alpha,R})\psi_P'(\beta_{\alpha,R}) + \psi_P(\alpha) + \psi_P(\beta_{\alpha,R}). \end{align}\]

• Regime III: \(\beta_{\alpha,R} \ge 1\). For \(\beta\le\beta_{\alpha,R}\), \(f=f_2\) and attains the maximum at \(\beta=1\). For \(\beta\ge\beta_{\alpha,R}\), \(f=f_1\) and is decreasing. The maximum is thus at \(\beta^{\star}=1\), and \[f(\beta^{\star}) = f_2(1) = \nu_{\alpha}(R).\]

The three equations above are equivalent to ?? . To characterise the regimes, we note that \(\beta \le \beta_{\alpha,R} \iff \psi'_{P}(\beta) \le \psi'_P(\beta_{\alpha,R})\), as \(\beta \mapsto \psi_P'(\beta)\) is increasing. So we have the following.

• Regime I: \(\beta_{\alpha,R} \le 1-\alpha \iff \alpha \psi_P'(1-\alpha) \ge \alpha \psi_P'(\beta_{\alpha,R}) = \psi_P(\alpha) - \nu_\alpha(R)\).

• Regime II: \(1-\alpha \le \beta_{\alpha,R} \le 1 \iff \alpha \psi_P'(1-\alpha) \le \psi_P(\alpha) - \nu_\alpha(R) \le \alpha \psi_P'(1)\).

• Regime III: \(\beta_{\alpha,R} \ge 1 \iff\psi_P(\alpha) - \nu_\alpha(R) \ge \alpha \psi_P'(1)\).

These are equivalent to 1, and the proof is concluded.

We specialise the result and derivation of Theorem 12 (see Appendix 14) to \(\alpha=1\). We have \(\nu_{1}(R) = \log|\mathcal{A}| - R + F_3(R;g_1)\), with \(F_3(R;g_1) = E_{\mathrm{sp}}(R)\). Note that \(\beta_{1,R}\) satisfies \(\psi_P'(\beta_{1,R}) = - \log|\mathcal{A}| + R - E_{\mathrm{sp}}(R)\).

• Regime I: \(\beta_{1,R}\le0\) and \(F_r(R;g_1) = \log|\mathcal{A}|\).

• Regime II: \(0\le \beta_{1,R} \le 1\) and \(F_r(R;g_1) = \psi_P(\beta_{1,R}) - \beta_{1,R}\psi_P'(\beta_{1,R})\).

• Regime III: \(\beta_{1,R} \ge 1\) and \(F_r(R;g_1) = \log|\mathcal{A}| - R + E_{\mathrm{sp}}(R)\).

First, consider \(R \ge C = \log|\mathcal{A}| - H(P_Z)\). In this case, \(E_{\mathrm{sp}}(R) = 0\), see 17 , and, due to the monotonicity of \(\beta\mapsto\psi_P'(\beta)\), we have \[\begin{align} \beta_{1,R} \ge 1 &\iff \psi_P'(\beta_{1,R}) \ge \psi_P'(1)\\ &\iff R \ge \log|\mathcal{A}| - H(P_Z). \end{align}\] This is always satisfied, so we are in regime III, in which, \[F_r(R;g_1) = \log|\mathcal{A}| - R.\]

Now, consider \(0 \le R < C = \log|\mathcal{A}| - H(P_Z)\). In this case, \(E_{\mathrm{sp}}(R) = \min_{Q \colon H(Q)=\log|\mathcal{A}|-R} D(Q \| P_Z)\), and by Lemma 6, \(E_{\mathrm{sp}}(R) = D(\widetilde{P}_{\alpha_R} \| P_Z)\), with \(\alpha_R>0\) such that \(H(\widetilde{P}_{\alpha_R}) = \log|\mathcal{A}| - R\). Note that \[\begin{align} \psi_P'(\beta_{1,R}) &= - \log|\mathcal{A}| + R - D(\widetilde{P}_{\alpha_R}\|P_Z)\\ &= -H(\widetilde{P}_{\alpha_R}) - D(\widetilde{P}_{\alpha_R}\|P_Z) = \psi_P'(\alpha_R). \end{align}\] By the monotonicity of \(\alpha\mapsto\psi_P'(\alpha)\), we deduce that \(\beta_{1,R} = \alpha_R\). We show that in this case we are in regime II: on the one hand, \(\alpha_R\ge0\) by Lemma 6; on the other hand, since \(R<C\), we have \(H(\widetilde{P}_{\alpha_R}) = \log|\mathcal{A}| - R \ge H(P_Z) = H(\widetilde{P}_1)\), so \(\alpha_R \le 1\). In that regime, \[\begin{align} F_r(R;g_1) &= \psi_P(\beta_{1,R}) - \beta_{1,R}\psi_P'(\beta_{1,R})\\ &= H(\widetilde{P}_{\beta_{1,R}}) = H(\widetilde{P}_{\alpha_R})\\ &= \log|\mathcal{A}|-R. \end{align}\]

Fix a rate \(R>0\). We will study the function \(\alpha \mapsto F_{r}(R,{g}_{\alpha})\). Call region A the set \(\big\{ {\alpha>0} \; \colon \;R \ge \log|\mathcal{A}| - H(\widetilde{P}_{\alpha}) \big\}\) and region B its complementary. We adopt the notations of Appendix 8 and \(\nu_{\alpha}(R) \mathrel{\vcenter{:}}= \log|\mathcal{A}| - R + F_3(R;{g}_{\alpha})\).

16.1 Study of Region A↩︎

First, we show that \(\alpha \mapsto F_{r}(R,{g}_{\alpha})\) is non-increasing in region A. Note that, in this region, \(F_3(R;g_{\alpha}) = 0\) (see 17 ). We study the three regimes described in 1.

• Regime I: In this case, we have \[F_r(R;{g}_{\alpha}) = \psi_P(\alpha) + \psi_P(1-\alpha).\] In region A, we have \(R \ge \log|\mathcal{A}| + \alpha\psi'_P(\alpha) - \psi_P(\alpha)\) (Proposition 16, item 4); in Regime I, we have \(\log|\mathcal{A}|-R \ge \psi_P(\alpha) - \alpha\psi_P'(1-\alpha)\). Summing the two inequalities, we get \(\psi_P'(1-\alpha) \ge \psi_P'(\alpha)\). So, taking the derivative, we get \[\frac{\mathrm{d}}{\mathrm{d}\alpha}F_r(R;{g}_{\alpha}) = \psi'_P(\alpha) - \psi'_P(1-\alpha) \le 0.\] Note that, since \(\alpha\mapsto\psi_P'(\alpha)\) is increasing, this also implies \(\alpha \le 1/2\).

• Regime II: In this case, we have \[\begin{align} F_r(R;{g}_{\alpha}) &= \psi_P(\alpha) + \psi_P(\beta_{\alpha,R}) \nonumber\\ &\quad+ (1-\alpha-\beta_{\alpha,R})\psi_P'(\beta_{\alpha,R}). \end{align}\] Recall that, in this region, \(\beta_{\alpha,R}\) satisfies \(\alpha\psi_P'(\beta_{\alpha,R}) = \psi_P(\alpha) - \log|\mathcal{A}| + R\); differentiating that expression with respect to \(\alpha\), we get \[\begin{align} \beta_{\alpha,R}' = \frac{\psi_P'(\alpha) - \psi_P'(\beta_{\alpha,R})}{\alpha \psi_P''(\beta_{\alpha,R})}. \end{align}\] We can now differentiate and use the equation above to get \[\begin{align} \frac{\mathrm{d}}{\mathrm{d}\alpha}F_r(R;{g}_{\alpha}) &= \frac{1-\beta_{\alpha,R}}{\alpha} \left( \psi'_P(\alpha) - \psi_P'(\beta_{\alpha,R}) \right). \end{align}\] From the condition of region A, we have \[\begin{align} &R \ge \log|\mathcal{A}| + \alpha \psi_P'(\alpha) - \psi_P(\alpha)\\ &\iff \alpha \psi_P'(\alpha) \le \psi_P(\alpha) - \log|\mathcal{A}| + R = \alpha \psi'_P(\beta_{\alpha,R}), \end{align}\] where we used the property of \(\beta_{\alpha,R}\) used above. This shows that \(\psi'_P(\alpha) - \psi_P'(\beta_{\alpha,R}) \le 0\). Moreover, \(\alpha>0\), and, in regime II, \(\beta_{\alpha,R} \le 1\), so we conclude that \(\frac{\mathrm{d}}{\mathrm{d}\alpha}F_r(R;g_{\alpha}) \le 0\).

• Regime III: In this case, \[F_r(R;{g}_{\alpha}) = \log|\mathcal{A}|-R,\] which is constant.

16.2 Study of Region B↩︎

We now study what happens in region B. In this case, \(R < \log|\mathcal{A}| - H(\widetilde{P}_{\alpha})\) and \(F_3(R;{g}_\alpha) = \min_{Q \colon H(Q) = \log|\mathcal{A}|-R }D(Q \| \widetilde{P}_{\alpha})\) (see 17 ). From Lemma 6 we know that \(F_3(R;\widetilde{g}_{\alpha}) = D(\widetilde{P}_{\alpha_R} \| \widetilde{P}_{\alpha})\), with \(\alpha_R>0\) satisfying \(H(\widetilde{P}_{\alpha_R}) = \log|\mathcal{A}|-R\). Since \(\alpha\mapsto H(\widetilde{P}_{\alpha})\) is decreasing for \(\alpha>0\), region B can be equivalently characterised by \(H(\widetilde{P}_{\alpha}) < \log|\mathcal{A}| - R \iff \alpha > \alpha_R\).

• Regime I: In this case, we have \[\label{eq:ch3-regionB-regimeI} F_r(R;{g}_{\alpha}) = \psi_P(\alpha) + \psi_P(1-\alpha).\tag{48}\] In regime I we have \[\begin{align} \alpha\psi_P'(1-\alpha) &\ge \psi_P(\alpha) - \log|\mathcal{A}| + R - D(\widetilde{P}_{\alpha_R} \| \widetilde{P}_{\alpha})\\ &= \psi_P(\alpha) - H(\widetilde{P}_{\alpha_R}) - D(\widetilde{P}_{\alpha_R} \| \widetilde{P}_{\alpha})\\ &= \alpha\psi_P'(\alpha_R). \end{align}\] Since \(\alpha\mapsto\psi_P(\alpha)\) is increasing and \(\alpha>0\), this implies \(1-\alpha \ge \alpha_R\). Together with the condition for region B, we find \(\alpha_R < \alpha \le 1-\alpha_R\), that is, this regime corresponds to the interval \(\left]\alpha_R,1-\alpha_R\right]\), and it only exists if \(\alpha_R\le1/2\) (otherwise regime I is absent from region B). If this regime exists, \(F_r(R;{g}_{\alpha})\) is minimised at \(\alpha=1/2\), which indeed belongs to the interval \(\left]\alpha_R,1-\alpha_R\right]\).

• Regime II: In this case, we have \(F_r(R;{g}_{\alpha}) = \psi_P(\alpha) + \psi_P(\beta_{\alpha,R}) + (1-\alpha-\beta_{\alpha,R}) \psi_P'(\beta_{\alpha,R})\). From the definition of \(\beta_{\alpha,R}\), we have, in region B, \[\begin{align} \alpha \psi_P'(\beta_{\alpha,R}) &= \psi_P(\alpha) - \log|\mathcal{A}| + R - D(\widetilde{P}_{\alpha_R}\|\widetilde{P}_{\alpha})\\ &= \alpha\psi_P'(\alpha_R). \end{align}\] Therefore, \(\beta_{\alpha,R}=\alpha_R\), and \[\label{eq:ch3-regionB-regimeII} F_r(R;{g}_{\alpha}) = \psi_P(\alpha) + \psi_P(\alpha_R) + (1-\alpha-\alpha_R) \psi_P'(\alpha_R).\tag{49}\] Taking the derivative, we get \[\frac{\mathrm{d}}{\mathrm{d}\alpha} F_r(R;{g}_{\alpha}) = \psi_P'(\alpha) - \psi_P'(\alpha_R) \ge 0,\] for \(\alpha \mapsto \psi_P'(\alpha)\) is increasing and \(\alpha>\alpha_R\) in region B.

• Region III: In this case, we have \[\begin{align} F_r(R;{g}_{\alpha}) &= \log|\mathcal{A}|-R + D(\widetilde{P}_{\alpha_R}\|\widetilde{P}_{\alpha}) \nonumber\\ &= \log|\mathcal{A}|-R+(\alpha_R-\alpha)\psi_P'(\alpha_R) \nonumber\\ &\quad- \psi_P(\alpha_R) + \psi_P(\alpha). \label{eq:ch3-regionB-regimeIII} \end{align}\tag{50}\] Taking the derivative, we have, as in regime II, \[\frac{\mathrm{d}}{\mathrm{d}\alpha} F_r(R;\widetilde{g}_{\alpha}) = \psi_P'(\alpha) - \psi_P'(\alpha_R) \ge 0\]

16.3 Optimal Complexity Exponent↩︎

We want to minimise \(F_r(R;g_{\alpha})\) on \(\alpha\). For that, consider two cases. Since \(\alpha \mapsto F_r(R;{g}_{\alpha})\) is non-increasing in region A, the minimum in that region occurs at \(\alpha=\alpha_R\).

1. Case \(\alpha_R\le 1/2\): regime I in region B exists. The function \(\alpha \mapsto F_r(R;{g}_{\alpha})\) is non-increasing in region A, that is, in \(\left[0,\alpha_R\right]\). It attains its minimum at \(\alpha=1/2\) in regime I of region B, that is, in \(\left]\alpha_R,1-\alpha_R\right]\). After that, in regimes II and III of region B, the function is non-decreasing. Thus, the minimum is \(\alpha^\star(R) = 1/2\).

2. Case \(\alpha_R > 1/2\): regime I in region B is absent. The function \(\alpha \mapsto F_r(R;{g}_{\alpha})\) is non-increasing in \(\left[0,\alpha_R\right]\) (region A), and non-decreasing in \(\left]\alpha_R,\infty\right[\) (region B). The minimum is thus attained at the boundary \(\alpha^\star(R) = \alpha_R\).

Finally, using the monotonicity of \(\alpha \mapsto H(\widetilde{P}_{\alpha})\) for \(\alpha>0\) and the definition of \(\alpha_R\), we have that \[\begin{align} \alpha_R \le \frac{1}{2} &\iff H(\widetilde{P}_{\alpha_R}) \ge H(\widetilde{P}_{1/2})\\ &\iff R \le \log|\mathcal{A}|-H(\widetilde{P}_{1/2}), \end{align}\] where we recognise the critical rate 2 .

We now deduce the complexity exponent obtained with \(\alpha = \alpha^{\star}(R)\). If \(\alpha_R \le 1/2\), then \(\alpha^{\star}(R) = 1/2\), and, from 48 , \[F_r(R;g_{\alpha^{\star}(R)}) = 2 \psi_P(1/2).\] If \(\alpha > 1/2\), then \(\alpha^{\star}(R) = \alpha_R\), and we are either in regime II or III of region B. From the definition of the regions, region III occurs whenever \(\beta_{\alpha,R} \ge 1\). Using 47 , we equivalently have \[\begin{align} &\psi_P(\alpha_R) - \nu_{\alpha_R}(R) \ge \alpha_R \psi_P'(1)\\ &\iff \psi_P(\alpha_R) - H(\widetilde{P}_{\alpha_R}) \ge \alpha_R \psi_P'(1)\\ &\iff \alpha_R \psi_P'(\alpha_R) \ge \alpha_R \psi_P'(1)\\ &\iff \alpha_R \ge 1. \end{align}\] Thus, from 49 and 50 , we have \[F_r(R;g_{\alpha^{\star}(R)}) = \begin{cases} &2\psi_P(1/2), \qquad 0 \le \alpha_R \le \frac{1}{2},\\ &2\psi_P(\alpha_R) + (1-2\alpha_R)\psi_P'(\alpha_R),\\ &\frac{1}{2} \le \alpha_R \le 1,\\ &\log|\mathcal{A}|-R, \qquad \alpha_R \ge 1. \end{cases}\] This coincides with the result of Theorem 5. Furthermore, note that, for \(\alpha_R \ge 1\), this is the same exponent as if we took \(\alpha=1\) (Theorem 13), so in that case it is enough to take \(\alpha^{\star}(R) = 1\).

16.4 Optimal Error Exponent↩︎

The optimality with the choice \(\alpha = \alpha^{\star}(R)\) follows from Theorem 9 in three cases: for \(0 \le \alpha_R\le1/2\), \(\alpha^{\star}(R) = 1/2\), from item 3; for \(1/2 \le \alpha_R \le 1\), \(\alpha^{\star}(R) = \alpha_R\), from item 4; and, for \(\alpha_R \ge 1\), \(\alpha^{\star}(R) = 1\), from item 2. In all cases, we have \[E_r(R;g_{\alpha^{\star}(R)}) = E_d(R;g_1).\]