\section{Introduction}
\label{sec_main}
Binary Hypothesis Testing (BHT) is a common problem in statistics and it has been richly used as a method  to statistical signal detection~\cite{4205085, 985674}.   In particular, the celebrated {\em Neyman-Pearson lemma} provides the optimal detection scheme for this testing task~\cite{4102537}.  

On the specifics, let us consider the classical $n$-length BHT setting given by 
\begin{equation}
\left\{\begin{array}{lll}
H_0:  &\ X_1^n \sim  P^n,\nonumber\\
H_1: &\ X_1^n \sim Q^n,
\end{array} \right. \label{eq_sec_main_1}
\end{equation}
where $P, Q \in \mathcal{P}(\mathbb{X})$ with  $D(P\|Q)>0$. In this work, we restrict our attention to the case of a finite-alphabet $\mathbb{X}$, where $\mathcal{P}(\mathbb{X})$ denotes the family of probabilities on $\mathbb{X}$.   A decision rule $\phi_n$ of length $n$ is a function $\phi_n: \mathbb{X}^n \rightarrow \Theta \triangleq  \{0,1 \}, $
from which two types of errors are induced \cite{kullback1951information}:
$$
\begin{array}{lll}
P_0(\phi_n)& \equiv & P^n( \left\{ x_1^n \in \mathbb{X}^n: \phi_n(x_1^n) \neq 0 \right\}) \triangleq P^n(\mathcal{A}^c(\phi_n)),\\
P_1(\phi_n)& \equiv &  Q^n(  \left\{ x_1^n\in \mathbb{X}^n:  \phi_n(x_1^n) = 0 \right\} ) \triangleq Q^n(\mathcal{A}(\phi_n) )
\end{array}
$$
with  decision region $\mathcal{A}(\phi_n) \triangleq \{ x_1^n\in \mathbb{X}^n : \phi_n(x_1^n) = 0\}$. 

For a given sequence $(\epsilon_n)_{n}$ of non-negative values such that $\lim_{n\rightarrow \infty}\limits \epsilon_n=0$, we study the solution to: 
\begin{equation}
\beta_n(\epsilon_n) \equiv \min_{\begin{subarray}{c} \phi_n \in \Phi_n 
\end{subarray}} \{P_1(\phi_n): \text{ s.t. }  P_0(\phi_n)\leq \epsilon_n \},  \forall n\geq 1, 
\label{typeII}
\end{equation}
where $\Phi_n \equiv  \left\{\phi_n: \mathbb{X}^n \rightarrow  \Theta \right\}$ denotes the class of $n$-length detectors.
Importantly, $(\beta_n(\epsilon_n))_{n\geq 1}$ represents the optimum Type II error sequence that satisfies a sequence of fixed Type I error constraints. 

The \emph{Neyman-Pearson} lemma~\cite{neyman1933ix} offers the optimal trade-off between the two type of errors\footnote{See \cite{6210366} for a new proof based on properties of exponential  density function families.}. In this context, the determination of the (exponential) rate of convergence of the Type II error, which is known as the error exponent, has been a central problem in HT's analysis. Indeed, the error exponent is seen as an indicator of the complexity of the decision task (function of $P_0$, $P_1$ and $(\epsilon_n)_{n}$) and has found numerous applications \cite{marano_2019,Wang_2018}. For the important case when $\epsilon_n=\epsilon>0$ for all $n$, the celebrated {\em Stein's lemma} establishes that the error exponent of the Type II error is given by the KL divergence  $D(P\|Q) \equiv \sum_{x\in \mathbb{X}} P(x) \log \frac{P(x)}{Q(x)}$ \cite{kullback1951information,cover2012elements}.
\begin{lemma}[\textit{Stein's lemma}~\cite{chernoff1952measure,cover2012elements}]
	\label{lemma_stein}

	For any fixed $\epsilon \in (0,1)$,

	$\lim_{n \rightarrow \infty} -\frac{1}{n } \log (\beta_n(\epsilon)) =  D(P\|Q)$.

\end{lemma}
Importantly,
the error exponent limit in Lemma \ref{lemma_stein} is independent of $\epsilon>0$.  
However, this limit changes when we impose a setting with a monotonic decreasing Type I error restrictions.
In particular, Han {\it et al.} \cite{han1989exponential} studied the case when the Type I error sequence has an exponential decreasing behaviour. Nagakawa {\it et al.} \cite{nakagawa1993converse} extended this analysis for a
family of decreasing sequence of Type I error restrictions:
\begin{lemma}\cite[Nakagawa]{nakagawa1993converse}
\label{nakagawalemma}
Let us assume that $\epsilon_n \leq e^{-rn}$ for some $r \in (0,D(P\|Q))$, then
$\lim_{n\rightarrow \infty}-\frac{1}{n} \log (\beta_n(\epsilon_n))=D(P_{t^{\ast}}\|Q)$,
where
$P_{t^{\ast}}(x)\equiv  C_{t^{\ast}}P(x)^{1-t^{\ast}}Q(x)^{t^{\ast}}$ $\forall x \in \mathbb{X}$, and $t^{\ast}$ is the solution of $D(P_{t^\ast}\|P)=r$.
\end{lemma}
A direct implication of Lemma \ref{nakagawalemma} is the following result: 
\begin{corollary}\label{cor_nakagawalemma} \cite{nakagawa1993converse}
Let us assume that
           
            $({1}/{\epsilon_n})_n$ is  $o(e^{rn})$ for any $r>0$,
 then
$\lim_{n\rightarrow \infty} - \frac{1}{n} \log (\beta_n(\epsilon_n))=D(P\|Q)$. 
\end{corollary}
Importantly,  Corollary \ref{cor_nakagawalemma} shows that the same
error exponent of the Stein's lemma is obtained for these stringent family of
problems --- where $(\epsilon_n)_{n}$ tends to zero at a sub-exponential rate. In contrast, when the Type I error restriction tends to zero exponentially fast (Lemma \ref{nakagawalemma}), the error exponent is strictly smaller than $D(P\|Q)$.   

\subsection{Finite-Length Context  and Contribution}
\label{sub_sec_unconstrained_finite_length_result} 
In many practical problems, the statistician has access only to a finite number of observations. Consequently,  it is critical to obtain non-asymptotic bounds for the probability of error $\beta_n(\epsilon_n)$ for a finite $n$. 
Concerning the non-asymptotic analysis of this problem, the following  result was derived by Strassen for the specific regime when $\epsilon_n=\epsilon>0$ for all $n\geq 1$ \cite{strassen2009asymptotic}.
\begin{lemma} \label{th_strassen2009asymptotic} \cite{strassen2009asymptotic} 
Let us consider $\epsilon \in (0,1)$, then eventually with $n$, it follows that
$-\frac{\log(\beta_n(\epsilon))}{n}=D(P\|Q)+\sqrt{\frac{V(P\|Q)}{n}}\Phi^{-1}(\epsilon)+\frac{\log n}{2n} + \mathcal{O}\left (\frac{1}{n} \right)$,
where $V(P\|Q) \equiv \displaystyle \sum_{x \in \mathbb{X}}\limits P(\{x\})\left [\log \left (\frac{P(\{x\})}{Q(\{x\})} \right ) -D(P\|Q) \right ]^2$.
\end{lemma} 
Lemma \ref{th_strassen2009asymptotic}
shows that 
$\left \rvert D(P\|Q)- \left( -\frac{1}{n}\log(\beta_n(\epsilon)) \right )\right \rvert$ is $\mathcal{O}\left(\frac{1}{\sqrt{n}}\right)$,
which expresses the velocity of convergence of $ -\frac{1}{n}\log(\beta_n(\epsilon))$
to its
 limit $D(P\|Q)$.
Given the practical importance of this type of finite length results,
it is very relevant to derive new results that extend 
Lemma \ref{th_strassen2009asymptotic}
to our general problem in (\ref{typeII}),  
as a function of $P$, $Q$,  $(\epsilon_n)_n$ and  $n$. In addition, it is critical that these bounds can be evaluated for its practical use. This last aspect is not achieved in Lemma \ref{th_strassen2009asymptotic}, which from that perspective is an asymptotic (convergence) result.

The main contribution of this paper goes in this direction, where we derive new upper and lower bounds for the discrepancy between $- \frac{1}{n}\log (\beta_n(\epsilon_n))$ and its information limit $D(P\|Q)$ for any finite $n\geq 1$ when $(\epsilon_n)_{n}$ tends to zero at a sub-exponential rate. 
These expressions can be evaluated and interpreted numerically in any context where we know the models ($P$ and $Q$) and the parameters of the problem ($\epsilon_n$ and $n$). In addition, these new bounds stipulate the velocity at which the error exponent is achieved as the sample size tends to infinity. From this, we could assess how realistic the information limits (asymptotic results) are in practice when facing a problem with a finite number of observations. To conclude our analysis, we numerically compute and evaluate the expressions obtained by our result to show the derived bounds' tightness for some specific scenarios.

\subsection{Related Work} 
In a Bayesian setting,
Sason \cite{sason2012moderate} obtained an upper bound to the optimal Bayesian probability of error (non-asymptotic) by bounding the Type I and Type II errors simultaneously in such a way that they both decay to zero sub-exponentially with $n$. 
It is worth to mention that this work differs from the current setting in the sense that we are interested in bounding the discrepancy between $- \frac{1}{n}\log (\beta_n(\epsilon_n))$ and its information limit and how this analysis depends on the vanishing Type I error restrictions. In addition, we are interested in the velocity of convergence of  $- \frac{1}{n}\log (\beta_n(\epsilon_n))$ to its  information limit
and the impact of considering stringent restriction on Type I errors $(\epsilon_n)_n$.
Complementing this paper, 
\cite{espinosa2019new} studies
a distributed (two-terminal) version of the BHT problem subject to communication (rates) constraints. Our results here  do not derive from \cite{espinosa2019new} since the setups are very different from each other, and different tools are used to address them. 
Finally,  a similar
analysis of the Type I error has been addressed by Bahadur \cite{nikitin1995asymptotic}. In contrast to this work's focus, this analysis considers 
a fixed restriction on the power of a test ($1-$Type II error) to determine the exponential rate of convergence of their sizes (Type I error) as $n$
tends to infinity.


\subsection{Notations and Organization}
$(b_n)_n$ being $o(a_n)$ indicates that $\limsup_{n\rightarrow \infty} \left(b_n/a_n\right)=0$ and
$(b_n)_n$ being  $\mathcal{O} (a_n)$ 
indicates that $\limsup_{n\rightarrow \infty}  | b_n/a_n|  <\infty $. We say that $(f(n))_n \approx (g(n))_n$ if  there exists a constant $C>0$ such that $f(n)=Cg(n)$ eventually in $n$.
The rest of the paper is organized as follows: Section \ref{sec_finite_lenght} presents the main result of this work.
Numerical analysis and discussions are presented in Section \ref{numan}. The proof of  is in Sect.~\ref{proofresult3}.
 
\section{Main Result}
\label{sec_finite_lenght}
The main result of this letter extends Lemma \ref{th_strassen2009asymptotic} offering new non-asymptotic bounds for $\beta_n(\epsilon_n)$ in (\ref{typeII}) under sub-exponential Type I error restrictions. 
In particular, the next result provides upper and lower bounds for the discrepancy between $- \frac{1}{n}\log (\beta_n(\epsilon_n))$ and $D(P\|Q)$. 
\begin{theorem}[]\label{theorem3}
Let us assume that $P\ll Q$  and 
                                
                                 that $(1/\epsilon_n)_n$ is  $o(e^{rn})$ for any $r>0$. 
Then, eventually in $n$, it follows that:
$$
\begin{array}{ll}
 -\frac{1}{n}\log(\beta_n(\epsilon_n)) \geq   D(P\|Q) - \displaystyle C_X(P,Q) \sqrt{\frac{2\ln(1/\epsilon_n)}{n}} \\
-\frac{1}{n}\log(\beta_n(\epsilon_n)) \leq  D(P\|Q)+\frac{\displaystyle  \log\left (\displaystyle \frac{1}{1-\epsilon_n-\delta_{n}}\right )}{\displaystyle  n} +\delta_{n}
\end{array}
$$
where $C_X(P,Q) \equiv  \sup_{x \in \mathbb{X}}\limits \left \rvert \log\left( \frac{P(\{x \})}{Q(\{ x\})}\right)\right \rvert$ and $\delta_{n} \equiv  C_X(P,Q) \sqrt{\frac{2\ln(1/\epsilon_n)}{n}}$.
\end{theorem}

\subsection{Interpretation and Discussion of Theorem \ref{theorem3}}
{\bf 1:} This result establishes a non-asymptotic rate of convergence for the Type II error when we impose a vanishing condition on  $(\epsilon_n)_{n}$ that is sub-exponential. Interestingly, the bounds for the discrepancy $-\frac{1}{n}\log(\beta_n(\epsilon_n))$
depend explicitly on the sequence $(\epsilon_n)_{n}$.\\  
{\bf 2:} It is worth noting that the dependency on $(\epsilon_n)_{n}$ observed in our result is non-observed in the asymptotic limit in Corollary \ref{cor_nakagawalemma}, 
which is  $D(P\|Q)$ as long as $(1/\epsilon_n)_{n}$ is sub-exponential.\\
{\bf 3:} Adding on the previous point, the fact that the asymptotic error exponent is invariant from the simpler fixed Type I setup  (in Lemma \ref{lemma_stein})
to the more restrictive sub-exponential Type I error decay setting (in Corollary \ref{cor_nakagawalemma}), it is however manifested in our non-asymptotic result  in term of the rate of convergence to the limit $D(P\|Q)$.
In particular,  there is a concrete penalty  $\mathcal{O}(\sqrt{\log(1/\epsilon_n)})$ on the velocity of convergence to zero of the discrepancy $( -\frac{1}{n}\log \beta_n(\epsilon_n) - D(P\|Q))$  in our result compared with what is obtained in Lemma \ref{th_strassen2009asymptotic}.\\
{\bf 4:} The proof of the Theorem~\ref{theorem3} has two parts: the constructive and unfeasibility arguments. Both arguments are constructed from concentration inequalities using the i.i.d. structure of the observations. For the constructive argument,  we apply the bounded difference inequality \cite{boucheron2013concentration}. On the unfeasibility argument,  we use (concentration) results from typical sequences \cite{cover2012elements} to construct a lower bound on the minimum probability of Type II error.\\ 
{\bf 5:}
If we impose a fixed value of $\epsilon_n=\epsilon \in (0,1)$,  our result recovers the rate of convergence for the Type II error given by Lemma \ref{th_strassen2009asymptotic}. However, we obtained explicit bounds.\\

\section{Practical Implications of Theorem~\ref{theorem3}}
\label{numan}
In this section, we show how Theorem \ref{theorem3} may be adopted by a statistician to obtain  bounds on  $\beta_n(\epsilon_n)$ when $n$ is finite. The resulting bounds
provide an interval of feasibility for
$\beta_n(\epsilon_n)$:
\begin{align*}
 \textrm{UB}(\epsilon_n) & \equiv \exp\Big [-n\Big (D(P\|Q) - \sqrt{\frac{2\ln(1/\epsilon_n)}{n}}C_X(P,Q)\Big ) \Big ], \\
 \textrm{LB}(\epsilon_n) & \equiv
  \exp\Big [-n\Big (D(P\|Q)-\frac{1}{n}\log\big (1-\epsilon_n-\delta_{n}(\epsilon_n)\Big ) \nonumber \\
& +\delta_{n}(\epsilon_n) \big ) \Big ].
\end{align*}
The length of $[\textrm{LB}(\epsilon_n),\textrm{UB}(\epsilon_n)]$ indicates the precision of the result
and, at the same time, the interval $[\textrm{LB}(\epsilon_n),\textrm{UB}(\epsilon_n)]$  
can be used to measure how close $\beta_n(\epsilon_n)$ is to $e^{-nD(P\|Q)}$.
\begin{figure}
    \centering
    \begin{minipage}{0.5\textwidth}
        \centering
        \includegraphics[width=1.0\linewidth]{Images/HighD} 
        \caption{Critical number of samples (CSS) predicted by Th. \ref{theorem3} 
        across different values of $\delta=10^{-k}$.
        High divergence case with $D(P\|Q)=2.5$ and  $C_X(P,Q)=2.04$.
        }
        \label{High}
    \end{minipage}\hfill
    \begin{minipage}{0.5\textwidth}
        \centering
       \includegraphics[width=1.0\linewidth]{Images/lowD} 
        \caption
        CSS predicted by Th. \ref{theorem3}
        across different values of $\delta=10^{-k}$.
        Low divergence case with $D(P\|Q)=0.5$  and  $C_X(P,Q)=1.03$.
        The dashed lines show an estimation of  the exact  CSS obtained from $\beta_n(\epsilon_n)$ directly. 
       
        }
           \label{Low}
    \end{minipage}
\end{figure}

\begin{table*}[ht]
\centering
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline
  & \multicolumn{8}{c|}{Number of observations $n$ } \\
\hline
 $\epsilon_n$     & 50 & 150 & 250 & 350 & 450 & 550 & 650 & 750  \\
\hline
 $1/\log(n)$  &     2.3587e-10 & 3.3962e-45 & 1.0595e-83& 9.4592e-124 & 1.0229e-164& 2.6103e-206& 2.2862e-248 & 8.6970e-291 \\
$1/n^{0.1}$  &  7.8229e-17 &  8.1724e-57 &  9.1096e-99& 1.3994e-141& 6.4863e-185&  1.3117e-228 & 1.4272e-272&  9.5440e-317\\
$1/n$   &       0.5571  & 3.7757e-25& 7.4403e-56& 2.7823e-89& 2.3527e-124& 1.4443e-160& 1.2489e-197& 2.3163e-235 \\
\hline
\end{tabular}
\vspace{2mm}
\caption{Magnitude of $  \textrm{UB}(\epsilon_n)- \textrm{LB}(\epsilon_n)$ function of $\epsilon_n$ and $n$ for the case when $D(P\|Q)=1$.}
\label{Tablap}
\end{table*}

Table \ref{Tablap} presents the length of $[\textrm{LB}(\epsilon_n),\textrm{UB}(\epsilon_n)]$ for three regimes of:  $\epsilon_n \in \{n^{-1},n^{-0.1},1/\log(n) \}$, and  two models $P$, $Q$ where  $D(P\|Q)=1$ with $|\mathbb{X}|=15$. First, we observe that the length of $[\textrm{LB}(\epsilon_n), \textrm{UB}(\epsilon_n)]$ vanishes exponentially fast 
with the sample size. From this exponential decay, we observe that the centered value predicted by Theorem \ref{theorem3}, i.e., the exponential behavior  $\exp(-n D(P\|Q))$,  is a good approximation for $\beta_n(\epsilon_n)$ provided that $n$ is sufficiently large. This  supports the idea that 
 $\exp(-n D(P\|Q))$ is a useful proxy for  $\beta_n(\epsilon_n)$ provided that a Critical Sample Size (CSS) is achieved (more details on this below).
Table \ref{Tablap} also shows that the result's precision is affected by the velocity of convergence of the Type I error restriction $(\epsilon_n)_{n}$, which is consistent with the statement and the analysis of our main result. In particular, for a faster speed of convergence of $(\epsilon_n)_{n}$ to zero (i.e., a stringer problem), the gap between the bounds is more prominent, which means that the bounds of Theorem \ref{theorem3} are expected to be less informative about  $\beta_n(\epsilon_n)$. 


Regarding  the implications of the above bounds to  measure the gap between $\beta_n(\epsilon_n)$ and  $e^{-nD(P\|Q)}$, we address the
following question: given an arbitrary value of $\delta>0$ of the form $10^{-k}$ with $k \in \left\{1,\dots ,8 \right\}$, and for two arbitrary models $P$ and $Q$, we want to predict from Theorem \ref{theorem3} the minimum number of samples required  to guarantee that $\beta_n(\epsilon_n) \in (e^{-nD(P\|Q)}- \delta, e^{-nD(P\|Q)} + \delta)$. The exponential decay of the length of $[\textrm{LB}(\epsilon_n),\textrm{UB}(\epsilon_n)]$,  observed in Table  \ref{Tablap}, implies that this should  happen eventually with $n$ very quickly. Indeed, we can derive an upper bound for this critical number of samples (CSS) from the expressions we have for $\textrm{LB}(\epsilon_n)$ and $\textrm{UB}(\epsilon_n)$.\footnote{The predicted CSS is the first $n\geq 1$ such that $\max\{ \textrm{UB}(\epsilon_n)- e^{-nD(P\|Q)},e^{-nD(P\|Q)}-\textrm{LB}(\epsilon_n) \}  \leq \delta$, which is finite for any $\delta>0$.}  Figures \ref{High} and \ref{Low} present the predicted CSS versus  $\delta= 10^{-k}$ for different scenarios of $P$, $Q$ (in terms of $D(P\|Q)$) and $(\epsilon_n)_n$. We consider two scenarios for $P$ and $Q$ (low divergence $D(P\|Q)=0.5$ and high divergence $D(P\|Q)=2.5$) and we explore $(\epsilon_n)_n  \in \{n^{-1}, n^{-0.1},1/\log(n), 0.1\}$. Figures \ref{High} and \ref{Low} show that even for really small precision $\delta=10^{-8}$ the point at which $\beta_n(\epsilon_n)$ can be well approximated by $e^{-nD(P\|Q)}$ requires at most $16$ samples  and  $60$ samples for high and low divergence cases, respectively, and   the majority of $(\epsilon_n)_n$. The dependency of these curves on the magnitude of $D(P\|Q)$ and $(\epsilon_n)_n$ is clearly expressed in these findings, which is consistent with our previous analyses.

Finally, to evaluate the tightness of our predictions, we simulate i.i.d. samples according to $P$ and $Q$ from which a  precise empirical estimation of $\beta_n(\epsilon_n)$ is derived. In particular, given $P$, $Q$ and $(\epsilon_n)_n$, we obtained empirical estimations of the error probabilities (Type I and Type II) from which we estimate $\beta_n(\epsilon_n)$. For this purpose,  $2.5\cdot 10^6$ realizations of $P$ and $Q$ were used to have good estimations of these probabilities.  Using the estimated values of  $\beta_n(\epsilon_n)$, we obtain the point where $\beta_n(\epsilon_n) \in (e^{-nD(P\|Q)}- \delta, e^{-nD(P\|Q)} + \delta)$ directly.  Figure \ref{Low} contrasts our predictions and the true (estimated) values (the dashed lines) of the CSS. 
Consistent with our result's nature, our prediction of the CSS is more conservative than the true CSS estimated from simulations.
Importantly, this discrepancy is not significant overall, expressing that our bounds are useful for this analysis and can be adopted in cases where it is impractical to estimate $\beta_n(\epsilon_n)$ from data. Indeed, in this analysis, we face this issue, and it is very difficult to obtain accurate estimates of  $\beta_n(\epsilon_n)$ for high divergence regimes. Notice that $\beta_n(\epsilon_n)$ is of order:  $O(e^{- n D(P\|Q)})$ for which  around $e^{n D(P\|Q)}$ simulations (i.e., i.i.d. samples from $P$ and $Q$) are needed. This becomes  impractical even for $n$ less than $30$ when $D(P\|Q)$ is relatively large.

\section{Proof of Theorem \ref{theorem3}}
\label{proofresult3}
We divide the proof of Theorem \ref{theorem3} in two parts. 

\subsubsection{Lower Bound Analysis}
Under the assumption of Theorem \ref{theorem3},  let us verify that
           
\begin{equation*}
 D(P\|Q)- \left( -\frac{1}{n}\log \beta_n(\epsilon_n) \right )\leq \sqrt{\frac{2\ln(1/\epsilon_n)}{n}}C_X(P,Q).
\end{equation*}
Let us consider the corresponding optimal decision regions from the Neyman-Pearson Lemma parameterized in the following way: $\forall t >0$,
\begin{equation}
\mathcal{B}_{n,t}= \left \{x_1^n \in \mathbb{X}^n : \frac{P^n(\{x_1^n \})}{Q^n(\{x_1^n \})} > e^{nt}\right \}.
\end{equation}
Considering the induced test $\phi_{n,t}(\cdot): \mathbb{X}^n \mapsto \{0,1 \}$ such that $\phi_{n,t}^{-1}(\left\{ 0 \right\})=\mathcal{B}_{n,t}$. The Type I error probability is given by $P^n(\mathcal{B}^c_{n,t})$. An upper bound for the Type II follows as:
\begin{equation}
Q^n\left (\mathcal{B}_{n,t}\right )  \leq e^{-nt}.
\label{typeIIerrorcound}
\end{equation}
Then, for any finite $n>0$ and $\epsilon_n>0$,  finding an achievable Type II error exponent from this construction (and the bound in Eq.(\ref{typeIIerrorcound})) reduces to solve the following 
problem:
\begin{equation}
t^{\ast}_n(\epsilon_n)\triangleq\sup_t \{t:
P^n (\mathcal{B}^c_{n,t}) \leq \epsilon_n \}.
\label{optimumt2}
\end{equation}
It will be convenient to re-parameterize $t$  with respect to 
the value $D(P\|Q)$. More precisely, let us define
$$t_{\delta}\triangleq  D(P\|Q) -\delta,$$ for any $\delta >0$. Then using the bounded difference inequality \cite{boucheron2013concentration},  we obtain
\begin{align} \label{eq_lemma_achievability_th4}
P^n \left (	B^c_{n,t_{\delta}} \right )&=P^n \left (	x_1^n \in \mathbb{X}^n :   \Biggr \rvert \hat{D}(P\|Q)-D(P\|Q) \Biggr \rvert \geq \delta  \right ) \nonumber \\
& \leq \exp\left (  \frac{-n\delta^2}{2C_X(P,Q)^2}\right ),
\end{align}
where $\hat{D}(P\|Q) \triangleq \frac{1}{n} \sum_{i=1}^n \log \left (\frac{P(\{x_i\} )}{Q(\{x_i\})} \right )$ is the empirical divergence. Finally, from Eq. (\ref{optimumt2}) a lower bound for $t^{\ast}_n(\epsilon_n)$ can be determined from Eq. (\ref{eq_lemma_achievability_th4}) by letting  $\tilde{\delta}_{n}(\epsilon_n)$ to be the solution of the following equality:
\begin{equation}
\exp \left ( \frac{-n\tilde{\delta}_{n}(\epsilon_n)^2}{2C_X(P,Q)^2}\right )=\epsilon_n.
\end{equation}
Consequently, we have that
\begin{equation}
t^{\ast}_{n}(\epsilon_n)\geq  t_{\tilde{\delta}_{n}(\epsilon_n)}\triangleq D(P\|Q) -\sqrt{\frac{2\log(1/\epsilon_n)}{n}}C_X(P,Q).
\label{boundupperR2}
\end{equation}
Finally, replacing the bound of (\ref{boundupperR2}) in (\ref{typeIIerrorcound}) and taking logarithm we have that:
\begin{equation}
 D(P\|Q)- \left( -\frac{1}{n}\log(\beta_n(\epsilon_n)) \right )\leq \sqrt{\frac{2\ln(1/\epsilon_n)}{n}}C_X(P,Q), 
\end{equation}
which concludes this part. 


\subsubsection{Upper Bound Analysis}
Let us consider the set
\begin{equation}
\mathcal{A}_{n,\delta }^c\triangleq \left \{ x_1^n\in \mathbb{X}^n : \Biggr \rvert \frac{1}{n}\log \left (\frac{P^n(\{ x_1^n \} )}{Q^n(\{ x_1^n \}  )} \right ) -  D(P\|Q) \Biggr \rvert \geq \delta  \right \},
\label{Adelta}
\end{equation}
for any $\delta>0$. 
We have the following result:
\begin{lemma}
 \cite[Sect 11.8]{cover2012elements} 
 \label{lemma_needed}
 For any set $ \mathcal{B}_n \subseteq \mathbb{X}^n$ and its induced test $\phi_n$\footnote{Meaning that $\phi_{n}(x_1^n)=0$ if $x_1^n\in \mathcal{B}_{n}$.} such that operates at Type I error $\epsilon_n$ (i.e. $P^n(	\mathcal{B}^c_n ) \leq \epsilon_n$), then
\begin{equation}
Q^n(\mathcal{B}_n) \geq (1-\epsilon_n-\delta)2^{-n(D(P\|Q)+\delta)}.
\label{cover_converse}
\end{equation}
\end{lemma} 
\noindent By construction, it is clear that there exists $\delta >0$ such that $\mathcal{A}^c_{n,\delta }$ operates at Type I error $\epsilon_n$. In fact, we consider
\begin{equation}
\delta^{\ast}_{n} \triangleq \sup \{\delta: P^n(\mathcal{A}^c_{n,\delta }) \leq \epsilon_n \}.
\label{36delta}
\end{equation}
Using the bounded difference inequality \cite{boucheron2013concentration}, we get that
\begin{align} \label{eq_lemma_converseth4}
P^n \left (	\mathcal{A}_{n,\delta }^c \right )&=P^n \left (x_1^n \in \mathbb{X}^n :   \Biggr \rvert \hat{D}(P\|Q)-D(P\|Q) \Biggr \rvert \geq \delta \right )\nonumber \\
& \leq \exp\left (  \frac{-n\delta^2}{2C_X(P,Q)^2}\right ).
\end{align}
Using the same argument from the lower bound analysis, we obtain a lower bound for $\delta^{\ast}_{n}$ given by
\begin{equation}
\delta^{\ast}_{n} \geq \delta_{n} \triangleq \sqrt{\frac{2\log(1/\epsilon_n)}{n}}C_X(P,Q).
\label{boundlowerR2}
\end{equation}

Finally, replacing $\delta_{n}$ in Eq. (\ref{cover_converse}) and taking logarithm, we have that for any set $\mathcal{B}_n$
satisfying the assumptions of Lemma \ref{lemma_needed}:
\begin{equation}
-\frac{1}{n}\log(Q^n(\mathcal{B}_n))  \leq D(P\|Q)+\frac{\log\left (\frac{1}{1-\epsilon_n-\delta_{n}}\right )}{n}+\delta_n.
\end{equation}
Therefore, we can choose the optimum set which implies that
\begin{equation}
-\frac{1}{n}\log(\beta_n(\epsilon_n))  \leq D(P\|Q)+\frac{\log\left (\frac{1}{1-\epsilon_n-\delta_{n}}\right )}{n}+\delta_{n}.
\end{equation}
This concludes the proof.

\ifCLASSOPTIONcaptionsoff
  \newpage
\fi





\bibliographystyle{IEEEtran}

\section{Introduction}
\label{sec_main}
Binary Hypothesis Testing (BHT) is a common problem in statistics and it has been richly used as a method  to statistical signal detection~\cite{4205085, 985674}.   In particular, the celebrated {\em Neyman-Pearson lemma} provides the optimal detection scheme for this testing task~\cite{4102537}.  

On the specifics, let us consider the classical $n$-length BHT setting given by 
\begin{equation}
\left\{\begin{array}{lll}
H_0:  &\ X_1^n \sim  P^n,\nonumber\\
H_1: &\ X_1^n \sim Q^n,
\end{array} \right. \label{eq_sec_main_1}
\end{equation}
where $P, Q \in \mathcal{P}(\mathbb{X})$ with  $D(P\|Q)>0$. In this work, we restrict our attention to the case of a finite-alphabet $\mathbb{X}$, where $\mathcal{P}(\mathbb{X})$ denotes the family of probabilities on $\mathbb{X}$.   A decision rule $\phi_n$ of length $n$ is a function $\phi_n: \mathbb{X}^n \rightarrow \Theta \triangleq  \{0,1 \}, $
from which two types of errors are induced \cite{kullback1951information}:
$$
\begin{array}{lll}
P_0(\phi_n)& \equiv & P^n( \left\{ x_1^n \in \mathbb{X}^n: \phi_n(x_1^n) \neq 0 \right\}) \triangleq P^n(\mathcal{A}^c(\phi_n)),\\
P_1(\phi_n)& \equiv &  Q^n(  \left\{ x_1^n\in \mathbb{X}^n:  \phi_n(x_1^n) = 0 \right\} ) \triangleq Q^n(\mathcal{A}(\phi_n) )
\end{array}
$$
with  decision region $\mathcal{A}(\phi_n) \triangleq \{ x_1^n\in \mathbb{X}^n : \phi_n(x_1^n) = 0\}$. 

For a given sequence $(\epsilon_n)_{n}$ of non-negative values such that $\lim_{n\rightarrow \infty}\limits \epsilon_n=0$, we study the solution to: 
\begin{equation}
\beta_n(\epsilon_n) \equiv \min_{\begin{subarray}{c} \phi_n \in \Phi_n 
\end{subarray}} \{P_1(\phi_n): \text{ s.t. }  P_0(\phi_n)\leq \epsilon_n \},  \forall n\geq 1, 
\label{typeII}
\end{equation}
where $\Phi_n \equiv  \left\{\phi_n: \mathbb{X}^n \rightarrow  \Theta \right\}$ denotes the class of $n$-length detectors.
Importantly, $(\beta_n(\epsilon_n))_{n\geq 1}$ represents the optimum Type II error sequence that satisfies a sequence of fixed Type I error constraints. 

The \emph{Neyman-Pearson} lemma~\cite{neyman1933ix} offers the optimal trade-off between the two type of errors\footnote{See \cite{6210366} for a new proof based on properties of exponential  density function families.}. In this context, the determination of the (exponential) rate of convergence of the Type II error, which is known as the error exponent, has been a central problem in HT's analysis. Indeed, the error exponent is seen as an indicator of the complexity of the decision task (function of $P_0$, $P_1$ and $(\epsilon_n)_{n}$) and has found numerous applications \cite{marano_2019,Wang_2018}. For the important case when $\epsilon_n=\epsilon>0$ for all $n$, the celebrated {\em Stein's lemma} establishes that the error exponent of the Type II error is given by the KL divergence  $D(P\|Q) \equiv \sum_{x\in \mathbb{X}} P(x) \log \frac{P(x)}{Q(x)}$ \cite{kullback1951information,cover2012elements}.
\begin{lemma}[\textit{Stein's lemma}~\cite{chernoff1952measure,cover2012elements}]
	\label{lemma_stein}

	For any fixed $\epsilon \in (0,1)$,

	$\lim_{n \rightarrow \infty} -\frac{1}{n } \log (\beta_n(\epsilon)) =  D(P\|Q)$.

\end{lemma}
Importantly,
the error exponent limit in Lemma \ref{lemma_stein} is independent of $\epsilon>0$.  
However, this limit changes when we impose a setting with a monotonic decreasing Type I error restrictions.
In particular, Han {\it et al.} \cite{han1989exponential} studied the case when the Type I error sequence has an exponential decreasing behaviour. Nagakawa {\it et al.} \cite{nakagawa1993converse} extended this analysis for a
family of decreasing sequence of Type I error restrictions:
\begin{lemma}\cite[Nakagawa]{nakagawa1993converse}
\label{nakagawalemma}
Let us assume that $\epsilon_n \leq e^{-rn}$ for some $r \in (0,D(P\|Q))$, then
$\lim_{n\rightarrow \infty}-\frac{1}{n} \log (\beta_n(\epsilon_n))=D(P_{t^{\ast}}\|Q)$,
where
$P_{t^{\ast}}(x)\equiv  C_{t^{\ast}}P(x)^{1-t^{\ast}}Q(x)^{t^{\ast}}$ $\forall x \in \mathbb{X}$, and $t^{\ast}$ is the solution of $D(P_{t^\ast}\|P)=r$.
\end{lemma}
A direct implication of Lemma \ref{nakagawalemma} is the following result: 
\begin{corollary}\label{cor_nakagawalemma} \cite{nakagawa1993converse}
Let us assume that
           
            $({1}/{\epsilon_n})_n$ is  $o(e^{rn})$ for any $r>0$,
 then
$\lim_{n\rightarrow \infty} - \frac{1}{n} \log (\beta_n(\epsilon_n))=D(P\|Q)$. 
\end{corollary}
Importantly,  Corollary \ref{cor_nakagawalemma} shows that the same
error exponent of the Stein's lemma is obtained for these stringent family of
problems --- where $(\epsilon_n)_{n}$ tends to zero at a sub-exponential rate. In contrast, when the Type I error restriction tends to zero exponentially fast (Lemma \ref{nakagawalemma}), the error exponent is strictly smaller than $D(P\|Q)$.   

\subsection{Finite-Length Context  and Contribution}
\label{sub_sec_unconstrained_finite_length_result} 
In many practical problems, the statistician has access only to a finite number of observations. Consequently,  it is critical to obtain non-asymptotic bounds for the probability of error $\beta_n(\epsilon_n)$ for a finite $n$. 
Concerning the non-asymptotic analysis of this problem, the following  result was derived by Strassen for the specific regime when $\epsilon_n=\epsilon>0$ for all $n\geq 1$ \cite{strassen2009asymptotic}.
\begin{lemma} \label{th_strassen2009asymptotic} \cite{strassen2009asymptotic} 
Let us consider $\epsilon \in (0,1)$, then eventually with $n$, it follows that
$-\frac{\log(\beta_n(\epsilon))}{n}=D(P\|Q)+\sqrt{\frac{V(P\|Q)}{n}}\Phi^{-1}(\epsilon)+\frac{\log n}{2n} + \mathcal{O}\left (\frac{1}{n} \right)$,
where $V(P\|Q) \equiv \displaystyle \sum_{x \in \mathbb{X}}\limits P(\{x\})\left [\log \left (\frac{P(\{x\})}{Q(\{x\})} \right ) -D(P\|Q) \right ]^2$.
\end{lemma} 
Lemma \ref{th_strassen2009asymptotic}
shows that 
$\left \rvert D(P\|Q)- \left( -\frac{1}{n}\log(\beta_n(\epsilon)) \right )\right \rvert$ is $\mathcal{O}\left(\frac{1}{\sqrt{n}}\right)$,
which expresses the velocity of convergence of $ -\frac{1}{n}\log(\beta_n(\epsilon))$
to its
 limit $D(P\|Q)$.
Given the practical importance of this type of finite length results,
it is very relevant to derive new results that extend 
Lemma \ref{th_strassen2009asymptotic}
to our general problem in (\ref{typeII}),  
as a function of $P$, $Q$,  $(\epsilon_n)_n$ and  $n$. In addition, it is critical that these bounds can be evaluated for its practical use. This last aspect is not achieved in Lemma \ref{th_strassen2009asymptotic}, which from that perspective is an asymptotic (convergence) result.

The main contribution of this paper goes in this direction, where we derive new upper and lower bounds for the discrepancy between $- \frac{1}{n}\log (\beta_n(\epsilon_n))$ and its information limit $D(P\|Q)$ for any finite $n\geq 1$ when $(\epsilon_n)_{n}$ tends to zero at a sub-exponential rate. 
These expressions can be evaluated and interpreted numerically in any context where we know the models ($P$ and $Q$) and the parameters of the problem ($\epsilon_n$ and $n$). In addition, these new bounds stipulate the velocity at which the error exponent is achieved as the sample size tends to infinity. From this, we could assess how realistic the information limits (asymptotic results) are in practice when facing a problem with a finite number of observations. To conclude our analysis, we numerically compute and evaluate the expressions obtained by our result to show the derived bounds' tightness for some specific scenarios.

\subsection{Related Work} 
In a Bayesian setting,
Sason \cite{sason2012moderate} obtained an upper bound to the optimal Bayesian probability of error (non-asymptotic) by bounding the Type I and Type II errors simultaneously in such a way that they both decay to zero sub-exponentially with $n$. 
It is worth to mention that this work differs from the current setting in the sense that we are interested in bounding the discrepancy between $- \frac{1}{n}\log (\beta_n(\epsilon_n))$ and its information limit and how this analysis depends on the vanishing Type I error restrictions. In addition, we are interested in the velocity of convergence of  $- \frac{1}{n}\log (\beta_n(\epsilon_n))$ to its  information limit
and the impact of considering stringent restriction on Type I errors $(\epsilon_n)_n$.
Complementing this paper, 
\cite{espinosa2019new} studies
a distributed (two-terminal) version of the BHT problem subject to communication (rates) constraints. Our results here  do not derive from \cite{espinosa2019new} since the setups are very different from each other, and different tools are used to address them. 
Finally,  a similar
analysis of the Type I error has been addressed by Bahadur \cite{nikitin1995asymptotic}. In contrast to this work's focus, this analysis considers 
a fixed restriction on the power of a test ($1-$Type II error) to determine the exponential rate of convergence of their sizes (Type I error) as $n$
tends to infinity.


\subsection{Notations and Organization}
$(b_n)_n$ being $o(a_n)$ indicates that $\limsup_{n\rightarrow \infty} \left(b_n/a_n\right)=0$ and
$(b_n)_n$ being  $\mathcal{O} (a_n)$ 
indicates that $\limsup_{n\rightarrow \infty}  | b_n/a_n|  <\infty $. We say that $(f(n))_n \approx (g(n))_n$ if  there exists a constant $C>0$ such that $f(n)=Cg(n)$ eventually in $n$.
The rest of the paper is organized as follows: Section \ref{sec_finite_lenght} presents the main result of this work.
Numerical analysis and discussions are presented in Section \ref{numan}. The proof of  is in Sect.~\ref{proofresult3}.
 
\section{Main Result}
\label{sec_finite_lenght}
The main result of this letter extends Lemma \ref{th_strassen2009asymptotic} offering new non-asymptotic bounds for $\beta_n(\epsilon_n)$ in (\ref{typeII}) under sub-exponential Type I error restrictions. 
In particular, the next result provides upper and lower bounds for the discrepancy between $- \frac{1}{n}\log (\beta_n(\epsilon_n))$ and $D(P\|Q)$. 
\begin{theorem}[]\label{theorem3}
Let us assume that $P\ll Q$  and 
                                
                                 that $(1/\epsilon_n)_n$ is  $o(e^{rn})$ for any $r>0$. 
Then, eventually in $n$, it follows that:
$$
\begin{array}{ll}
 -\frac{1}{n}\log(\beta_n(\epsilon_n)) \geq   D(P\|Q) - \displaystyle C_X(P,Q) \sqrt{\frac{2\ln(1/\epsilon_n)}{n}} \\
-\frac{1}{n}\log(\beta_n(\epsilon_n)) \leq  D(P\|Q)+\frac{\displaystyle  \log\left (\displaystyle \frac{1}{1-\epsilon_n-\delta_{n}}\right )}{\displaystyle  n} +\delta_{n}
\end{array}
$$
where $C_X(P,Q) \equiv  \sup_{x \in \mathbb{X}}\limits \left \rvert \log\left( \frac{P(\{x \})}{Q(\{ x\})}\right)\right \rvert$ and $\delta_{n} \equiv  C_X(P,Q) \sqrt{\frac{2\ln(1/\epsilon_n)}{n}}$.
\end{theorem}

\subsection{Interpretation and Discussion of Theorem \ref{theorem3}}
{\bf 1:} This result establishes a non-asymptotic rate of convergence for the Type II error when we impose a vanishing condition on  $(\epsilon_n)_{n}$ that is sub-exponential. Interestingly, the bounds for the discrepancy $-\frac{1}{n}\log(\beta_n(\epsilon_n))$
depend explicitly on the sequence $(\epsilon_n)_{n}$.\\  
{\bf 2:} It is worth noting that the dependency on $(\epsilon_n)_{n}$ observed in our result is non-observed in the asymptotic limit in Corollary \ref{cor_nakagawalemma}, 
which is  $D(P\|Q)$ as long as $(1/\epsilon_n)_{n}$ is sub-exponential.\\
{\bf 3:} Adding on the previous point, the fact that the asymptotic error exponent is invariant from the simpler fixed Type I setup  (in Lemma \ref{lemma_stein})
to the more restrictive sub-exponential Type I error decay setting (in Corollary \ref{cor_nakagawalemma}), it is however manifested in our non-asymptotic result  in term of the rate of convergence to the limit $D(P\|Q)$.
In particular,  there is a concrete penalty  $\mathcal{O}(\sqrt{\log(1/\epsilon_n)})$ on the velocity of convergence to zero of the discrepancy $( -\frac{1}{n}\log \beta_n(\epsilon_n) - D(P\|Q))$  in our result compared with what is obtained in Lemma \ref{th_strassen2009asymptotic}.\\
{\bf 4:} The proof of the Theorem~\ref{theorem3} has two parts: the constructive and unfeasibility arguments. Both arguments are constructed from concentration inequalities using the i.i.d. structure of the observations. For the constructive argument,  we apply the bounded difference inequality \cite{boucheron2013concentration}. On the unfeasibility argument,  we use (concentration) results from typical sequences \cite{cover2012elements} to construct a lower bound on the minimum probability of Type II error.\\ 
{\bf 5:}
If we impose a fixed value of $\epsilon_n=\epsilon \in (0,1)$,  our result recovers the rate of convergence for the Type II error given by Lemma \ref{th_strassen2009asymptotic}. However, we obtained explicit bounds.\\

\section{Practical Implications of Theorem~\ref{theorem3}}
\label{numan}
In this section, we show how Theorem \ref{theorem3} may be adopted by a statistician to obtain  bounds on  $\beta_n(\epsilon_n)$ when $n$ is finite. The resulting bounds
provide an interval of feasibility for
$\beta_n(\epsilon_n)$:
\begin{align*}
 \textrm{UB}(\epsilon_n) & \equiv \exp\Big [-n\Big (D(P\|Q) - \sqrt{\frac{2\ln(1/\epsilon_n)}{n}}C_X(P,Q)\Big ) \Big ], \\
 \textrm{LB}(\epsilon_n) & \equiv
  \exp\Big [-n\Big (D(P\|Q)-\frac{1}{n}\log\big (1-\epsilon_n-\delta_{n}(\epsilon_n)\Big ) \nonumber \\
& +\delta_{n}(\epsilon_n) \big ) \Big ].
\end{align*}
The length of $[\textrm{LB}(\epsilon_n),\textrm{UB}(\epsilon_n)]$ indicates the precision of the result
and, at the same time, the interval $[\textrm{LB}(\epsilon_n),\textrm{UB}(\epsilon_n)]$  
can be used to measure how close $\beta_n(\epsilon_n)$ is to $e^{-nD(P\|Q)}$.
\begin{figure}
    \centering
    \begin{minipage}{0.5\textwidth}
        \centering
        \includegraphics[width=1.0\linewidth]{Images/HighD} 
        \caption{Critical number of samples (CSS) predicted by Th. \ref{theorem3} 
        across different values of $\delta=10^{-k}$.
        High divergence case with $D(P\|Q)=2.5$ and  $C_X(P,Q)=2.04$.
        }
        \label{High}
    \end{minipage}\hfill
    \begin{minipage}{0.5\textwidth}
        \centering
       \includegraphics[width=1.0\linewidth]{Images/lowD} 
        \caption
        CSS predicted by Th. \ref{theorem3}
        across different values of $\delta=10^{-k}$.
        Low divergence case with $D(P\|Q)=0.5$  and  $C_X(P,Q)=1.03$.
        The dashed lines show an estimation of  the exact  CSS obtained from $\beta_n(\epsilon_n)$ directly. 
       
        }
           \label{Low}
    \end{minipage}
\end{figure}

\begin{table*}[ht]
\centering
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline
  & \multicolumn{8}{c|}{Number of observations $n$ } \\
\hline
 $\epsilon_n$     & 50 & 150 & 250 & 350 & 450 & 550 & 650 & 750  \\
\hline
 $1/\log(n)$  &     2.3587e-10 & 3.3962e-45 & 1.0595e-83& 9.4592e-124 & 1.0229e-164& 2.6103e-206& 2.2862e-248 & 8.6970e-291 \\
$1/n^{0.1}$  &  7.8229e-17 &  8.1724e-57 &  9.1096e-99& 1.3994e-141& 6.4863e-185&  1.3117e-228 & 1.4272e-272&  9.5440e-317\\
$1/n$   &       0.5571  & 3.7757e-25& 7.4403e-56& 2.7823e-89& 2.3527e-124& 1.4443e-160& 1.2489e-197& 2.3163e-235 \\
\hline
\end{tabular}
\vspace{2mm}
\caption{Magnitude of $  \textrm{UB}(\epsilon_n)- \textrm{LB}(\epsilon_n)$ function of $\epsilon_n$ and $n$ for the case when $D(P\|Q)=1$.}
\label{Tablap}
\end{table*}

Table \ref{Tablap} presents the length of $[\textrm{LB}(\epsilon_n),\textrm{UB}(\epsilon_n)]$ for three regimes of:  $\epsilon_n \in \{n^{-1},n^{-0.1},1/\log(n) \}$, and  two models $P$, $Q$ where  $D(P\|Q)=1$ with $|\mathbb{X}|=15$. First, we observe that the length of $[\textrm{LB}(\epsilon_n), \textrm{UB}(\epsilon_n)]$ vanishes exponentially fast 
with the sample size. From this exponential decay, we observe that the centered value predicted by Theorem \ref{theorem3}, i.e., the exponential behavior  $\exp(-n D(P\|Q))$,  is a good approximation for $\beta_n(\epsilon_n)$ provided that $n$ is sufficiently large. This  supports the idea that 
 $\exp(-n D(P\|Q))$ is a useful proxy for  $\beta_n(\epsilon_n)$ provided that a Critical Sample Size (CSS) is achieved (more details on this below).
Table \ref{Tablap} also shows that the result's precision is affected by the velocity of convergence of the Type I error restriction $(\epsilon_n)_{n}$, which is consistent with the statement and the analysis of our main result. In particular, for a faster speed of convergence of $(\epsilon_n)_{n}$ to zero (i.e., a stringer problem), the gap between the bounds is more prominent, which means that the bounds of Theorem \ref{theorem3} are expected to be less informative about  $\beta_n(\epsilon_n)$. 


Regarding  the implications of the above bounds to  measure the gap between $\beta_n(\epsilon_n)$ and  $e^{-nD(P\|Q)}$, we address the
following question: given an arbitrary value of $\delta>0$ of the form $10^{-k}$ with $k \in \left\{1,\dots ,8 \right\}$, and for two arbitrary models $P$ and $Q$, we want to predict from Theorem \ref{theorem3} the minimum number of samples required  to guarantee that $\beta_n(\epsilon_n) \in (e^{-nD(P\|Q)}- \delta, e^{-nD(P\|Q)} + \delta)$. The exponential decay of the length of $[\textrm{LB}(\epsilon_n),\textrm{UB}(\epsilon_n)]$,  observed in Table  \ref{Tablap}, implies that this should  happen eventually with $n$ very quickly. Indeed, we can derive an upper bound for this critical number of samples (CSS) from the expressions we have for $\textrm{LB}(\epsilon_n)$ and $\textrm{UB}(\epsilon_n)$.\footnote{The predicted CSS is the first $n\geq 1$ such that $\max\{ \textrm{UB}(\epsilon_n)- e^{-nD(P\|Q)},e^{-nD(P\|Q)}-\textrm{LB}(\epsilon_n) \}  \leq \delta$, which is finite for any $\delta>0$.}  Figures \ref{High} and \ref{Low} present the predicted CSS versus  $\delta= 10^{-k}$ for different scenarios of $P$, $Q$ (in terms of $D(P\|Q)$) and $(\epsilon_n)_n$. We consider two scenarios for $P$ and $Q$ (low divergence $D(P\|Q)=0.5$ and high divergence $D(P\|Q)=2.5$) and we explore $(\epsilon_n)_n  \in \{n^{-1}, n^{-0.1},1/\log(n), 0.1\}$. Figures \ref{High} and \ref{Low} show that even for really small precision $\delta=10^{-8}$ the point at which $\beta_n(\epsilon_n)$ can be well approximated by $e^{-nD(P\|Q)}$ requires at most $16$ samples  and  $60$ samples for high and low divergence cases, respectively, and   the majority of $(\epsilon_n)_n$. The dependency of these curves on the magnitude of $D(P\|Q)$ and $(\epsilon_n)_n$ is clearly expressed in these findings, which is consistent with our previous analyses.

Finally, to evaluate the tightness of our predictions, we simulate i.i.d. samples according to $P$ and $Q$ from which a  precise empirical estimation of $\beta_n(\epsilon_n)$ is derived. In particular, given $P$, $Q$ and $(\epsilon_n)_n$, we obtained empirical estimations of the error probabilities (Type I and Type II) from which we estimate $\beta_n(\epsilon_n)$. For this purpose,  $2.5\cdot 10^6$ realizations of $P$ and $Q$ were used to have good estimations of these probabilities.  Using the estimated values of  $\beta_n(\epsilon_n)$, we obtain the point where $\beta_n(\epsilon_n) \in (e^{-nD(P\|Q)}- \delta, e^{-nD(P\|Q)} + \delta)$ directly.  Figure \ref{Low} contrasts our predictions and the true (estimated) values (the dashed lines) of the CSS. 
Consistent with our result's nature, our prediction of the CSS is more conservative than the true CSS estimated from simulations.
Importantly, this discrepancy is not significant overall, expressing that our bounds are useful for this analysis and can be adopted in cases where it is impractical to estimate $\beta_n(\epsilon_n)$ from data. Indeed, in this analysis, we face this issue, and it is very difficult to obtain accurate estimates of  $\beta_n(\epsilon_n)$ for high divergence regimes. Notice that $\beta_n(\epsilon_n)$ is of order:  $O(e^{- n D(P\|Q)})$ for which  around $e^{n D(P\|Q)}$ simulations (i.e., i.i.d. samples from $P$ and $Q$) are needed. This becomes  impractical even for $n$ less than $30$ when $D(P\|Q)$ is relatively large.

\section{Proof of Theorem \ref{theorem3}}
\label{proofresult3}
We divide the proof of Theorem \ref{theorem3} in two parts. 

\subsubsection{Lower Bound Analysis}
Under the assumption of Theorem \ref{theorem3},  let us verify that
           
\begin{equation*}
 D(P\|Q)- \left( -\frac{1}{n}\log \beta_n(\epsilon_n) \right )\leq \sqrt{\frac{2\ln(1/\epsilon_n)}{n}}C_X(P,Q).
\end{equation*}
Let us consider the corresponding optimal decision regions from the Neyman-Pearson Lemma parameterized in the following way: $\forall t >0$,
\begin{equation}
\mathcal{B}_{n,t}= \left \{x_1^n \in \mathbb{X}^n : \frac{P^n(\{x_1^n \})}{Q^n(\{x_1^n \})} > e^{nt}\right \}.
\end{equation}
Considering the induced test $\phi_{n,t}(\cdot): \mathbb{X}^n \mapsto \{0,1 \}$ such that $\phi_{n,t}^{-1}(\left\{ 0 \right\})=\mathcal{B}_{n,t}$. The Type I error probability is given by $P^n(\mathcal{B}^c_{n,t})$. An upper bound for the Type II follows as:
\begin{equation}
Q^n\left (\mathcal{B}_{n,t}\right )  \leq e^{-nt}.
\label{typeIIerrorcound}
\end{equation}
Then, for any finite $n>0$ and $\epsilon_n>0$,  finding an achievable Type II error exponent from this construction (and the bound in Eq.(\ref{typeIIerrorcound})) reduces to solve the following 
problem:
\begin{equation}
t^{\ast}_n(\epsilon_n)\triangleq\sup_t \{t:
P^n (\mathcal{B}^c_{n,t}) \leq \epsilon_n \}.
\label{optimumt2}
\end{equation}
It will be convenient to re-parameterize $t$  with respect to 
the value $D(P\|Q)$. More precisely, let us define
$$t_{\delta}\triangleq  D(P\|Q) -\delta,$$ for any $\delta >0$. Then using the bounded difference inequality \cite{boucheron2013concentration},  we obtain
\begin{align} \label{eq_lemma_achievability_th4}
P^n \left (	B^c_{n,t_{\delta}} \right )&=P^n \left (	x_1^n \in \mathbb{X}^n :   \Biggr \rvert \hat{D}(P\|Q)-D(P\|Q) \Biggr \rvert \geq \delta  \right ) \nonumber \\
& \leq \exp\left (  \frac{-n\delta^2}{2C_X(P,Q)^2}\right ),
\end{align}
where $\hat{D}(P\|Q) \triangleq \frac{1}{n} \sum_{i=1}^n \log \left (\frac{P(\{x_i\} )}{Q(\{x_i\})} \right )$ is the empirical divergence. Finally, from Eq. (\ref{optimumt2}) a lower bound for $t^{\ast}_n(\epsilon_n)$ can be determined from Eq. (\ref{eq_lemma_achievability_th4}) by letting  $\tilde{\delta}_{n}(\epsilon_n)$ to be the solution of the following equality:
\begin{equation}
\exp \left ( \frac{-n\tilde{\delta}_{n}(\epsilon_n)^2}{2C_X(P,Q)^2}\right )=\epsilon_n.
\end{equation}
Consequently, we have that
\begin{equation}
t^{\ast}_{n}(\epsilon_n)\geq  t_{\tilde{\delta}_{n}(\epsilon_n)}\triangleq D(P\|Q) -\sqrt{\frac{2\log(1/\epsilon_n)}{n}}C_X(P,Q).
\label{boundupperR2}
\end{equation}
Finally, replacing the bound of (\ref{boundupperR2}) in (\ref{typeIIerrorcound}) and taking logarithm we have that:
\begin{equation}
 D(P\|Q)- \left( -\frac{1}{n}\log(\beta_n(\epsilon_n)) \right )\leq \sqrt{\frac{2\ln(1/\epsilon_n)}{n}}C_X(P,Q), 
\end{equation}
which concludes this part. 


\subsubsection{Upper Bound Analysis}
Let us consider the set
\begin{equation}
\mathcal{A}_{n,\delta }^c\triangleq \left \{ x_1^n\in \mathbb{X}^n : \Biggr \rvert \frac{1}{n}\log \left (\frac{P^n(\{ x_1^n \} )}{Q^n(\{ x_1^n \}  )} \right ) -  D(P\|Q) \Biggr \rvert \geq \delta  \right \},
\label{Adelta}
\end{equation}
for any $\delta>0$. 
We have the following result:
\begin{lemma}
 \cite[Sect 11.8]{cover2012elements} 
 \label{lemma_needed}
 For any set $ \mathcal{B}_n \subseteq \mathbb{X}^n$ and its induced test $\phi_n$\footnote{Meaning that $\phi_{n}(x_1^n)=0$ if $x_1^n\in \mathcal{B}_{n}$.} such that operates at Type I error $\epsilon_n$ (i.e. $P^n(	\mathcal{B}^c_n ) \leq \epsilon_n$), then
\begin{equation}
Q^n(\mathcal{B}_n) \geq (1-\epsilon_n-\delta)2^{-n(D(P\|Q)+\delta)}.
\label{cover_converse}
\end{equation}
\end{lemma} 
\noindent By construction, it is clear that there exists $\delta >0$ such that $\mathcal{A}^c_{n,\delta }$ operates at Type I error $\epsilon_n$. In fact, we consider
\begin{equation}
\delta^{\ast}_{n} \triangleq \sup \{\delta: P^n(\mathcal{A}^c_{n,\delta }) \leq \epsilon_n \}.
\label{36delta}
\end{equation}
Using the bounded difference inequality \cite{boucheron2013concentration}, we get that
\begin{align} \label{eq_lemma_converseth4}
P^n \left (	\mathcal{A}_{n,\delta }^c \right )&=P^n \left (x_1^n \in \mathbb{X}^n :   \Biggr \rvert \hat{D}(P\|Q)-D(P\|Q) \Biggr \rvert \geq \delta \right )\nonumber \\
& \leq \exp\left (  \frac{-n\delta^2}{2C_X(P,Q)^2}\right ).
\end{align}
Using the same argument from the lower bound analysis, we obtain a lower bound for $\delta^{\ast}_{n}$ given by
\begin{equation}
\delta^{\ast}_{n} \geq \delta_{n} \triangleq \sqrt{\frac{2\log(1/\epsilon_n)}{n}}C_X(P,Q).
\label{boundlowerR2}
\end{equation}

Finally, replacing $\delta_{n}$ in Eq. (\ref{cover_converse}) and taking logarithm, we have that for any set $\mathcal{B}_n$
satisfying the assumptions of Lemma \ref{lemma_needed}:
\begin{equation}
-\frac{1}{n}\log(Q^n(\mathcal{B}_n))  \leq D(P\|Q)+\frac{\log\left (\frac{1}{1-\epsilon_n-\delta_{n}}\right )}{n}+\delta_n.
\end{equation}
Therefore, we can choose the optimum set which implies that
\begin{equation}
-\frac{1}{n}\log(\beta_n(\epsilon_n))  \leq D(P\|Q)+\frac{\log\left (\frac{1}{1-\epsilon_n-\delta_{n}}\right )}{n}+\delta_{n}.
\end{equation}
This concludes the proof.

\ifCLASSOPTIONcaptionsoff
  \newpage
\fi





\bibliographystyle{IEEEtran}
