# Second-Order Asymptotics of Hoeffding-Like Hypothesis Tests

K. V. Harsha, Jithin Ravi,2 and Tobias Koch3
Part of this work was done while K. V. Harsha and J. Ravi were with the Signal
Theory and Communications Department, Universidad Carlos III de Madrid,
Leganés, Spain. K. V. Harsha, J. Ravi, and T. Koch have received funding from
the European Research Council (ERC) under the European Union’s Horizon 2020
research and innovation programme (Grant No. 714161). T. Koch has further
received funding from the Spanish Ministerio de Ciencia e Innovación under
Grant PID2020-116683GB-C21 / AEI / 10.13039/501100011033. 2Indian Institute of
Technology Kharagpur, India
3Universidad Carlos III de Madrid, Leganés, Spain and Gregorio Marañón Health
Research Institute, Madrid, Spain.
Emails<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

We consider a binary statistical hypothesis testing problem, where $n$
independent and identically distributed random variables $Z^{n}$ are either
distributed according to the null hypothesis $P$ or the alternate hypothesis
$Q$, and only $P$ is known. For this problem, a well-known test is the
Hoeffding test, which accepts $P$ if the Kullback-Leibler (KL) divergence
between the empirical distribution of $Z^{n}$ and $P$ is below some threshold.
In this paper, we consider Hoeffding-like tests, where the KL divergence is
replaced by other divergences, and characterize, for a large class of
divergences, the first and second-order terms of the type-II error for a fixed
type-I error. Since the considered class includes the KL divergence, we obtain
the second-order term of the Hoeffiding test as a special case.

##  I Introduction

Statistical hypothesis testing is known to have applications in areas such as
information theory, signal processing, and machine learning. The most simple
form of hypothesis testing is binary hypothesis testing, where the goal is to
determine the distribution of a random variable $Z$ between a null hypothesis
$P$ and an alternate hypothesis $Q$. There can be two types of errors in a
binary hypothesis testing: The type-I error is the probability of declaring
the hypothesis as $Q$ when the true distribution is $P$. The type-II error is
the probability of declaring the hypothesis as $P$ when the true distribution
is $Q$. In general, we are interested in analyzing the trade-off between these
two types of errors for a given test. This test may have full or only partial
access to the distributions $P$ and $Q$.

When both $P$ and $Q$ are known, the likelihood ratio test (also known as
Neyman-Pearson test [1]) achieves the optimal error trade-off between type-I
and type-II errors. The Neyman-Pearson test is also investigated in an
asymptotic setting, where one observes $n$ independent copies of $Z$ and the
errors are analyzed asymptotically as $n$ tends to infinity. In this case, we
are often interested in the behaviour of the type-II error $\beta_{n}$ for a
fixed type-I error $\alpha_{n}$. It is known that for
$\alpha_{n}\leq\epsilon,\;\epsilon\in(0,1)$, the corresponding type-II error
satisfies [2, Prop. 2.3]

$\displaystyle-\ln\beta_{n}$ $\displaystyle=$ $\displaystyle
nD(P\|Q)-\sqrt{nV(P\|Q)}Q^{-1}(\epsilon)+o(\sqrt{n}),\quad\text{as}\quad
n\rightarrow\infty$ (1)

where $D(P\|Q)$ is the Kullback-Leibler (KL) divergence between $P$ and $Q$,
defined as

$\displaystyle D(P\|Q)\triangleq\sum_{i=1}^{k}P_{i}\ln\frac{P_{i}}{Q_{i}},$
(2)

$Q^{-1}(\cdot)$ denotes the inverse of the tail probability of the standard
Normal distribution,

$\displaystyle
V(P\|Q)\triangleq\sum_{i=1}^{k}P_{i}\left[\left(\ln\frac{P_{i}}{Q_{i}}-D(P\|Q)\right)^{2}\right],$

and $o(\sqrt{n})$ denotes a term that grows more slowly than $\sqrt{n}$ as
$n\to\infty$. Thus the first-order term of $-\ln\beta_{n}$, defined as
$\lim_{n\rightarrow\infty}\frac{-\ln\beta_{n}}{n}$ and sometimes referred to
as the error exponent, is given by $D(P\|Q)$. The second-order term, defined
as $\frac{-\ln\beta_{n}-nD(P\|Q)}{\sqrt{n}}$, is given by
$-\sqrt{V(P\|Q)}Q^{-1}(\epsilon)$.

The case where the test has only partial access to the distributions $P$ and
$Q$ is generally studied under the name of composite hypothesis testing. Here,
the assumption is that $P$ and $Q$ belong to certain classes of distributions
denoted by $\mathcal{P}$ and $\mathcal{Q}$, respectively. Several special
cases of composite hypothesis testing have been investigated in the
literature. Two such cases are: 1) $P$ is known and $Q$ can be any
distributions but $P$; 2) $P$ is known and $Q$ belongs to a special class
$\mathcal{Q}$. A test proposed by Hoeffding [3], known as the Hoeffding test,
is suitable for these two cases. In the Hoeffding test, the null hypothesis
$P$ is accepted if the KL divergence between the type $t_{Z^{n}}$ (the
empirical distribution) of the observations $Z^{n}=(Z_{1},\cdots,Z_{n})$ and
$P$ is below some threshold $c$. Otherwise, the alternative hypothesis is
accepted. Mathematically,

$\displaystyle\text{if}\;D(t_{Z^{n}}\|P)<c,\text{ then accept }H_{0};\text{
otherwise accept }H_{1}.$

In [4, Th. III.2], it was shown that the Hoeffding test achieves the same
first-order term of $-\ln\beta_{n}$ as the Neyman-Pearson test. Consequently,
not having access to the distribution of the alternate hypothesis does not
affect the first-order term. To analyze the second-order term of
$-\ln\beta_{n}$ in the above two cases of composite hypothesis testing,
Watanabe proposed a test that is second-order optimal in some sense [5].

The Hoeffding test does not require side information about the special class
$\mathcal{Q}$ to which $Q$ belongs. It is therefore perhaps not surprising
that tests that have knowledge of $Q$ (case 2 of composite hypothesis testing)
may outperform the Hoeffding test. Such tests include the generalized
likelihood ratio test (GLRT) [6] and test via mismatched divergence [7]. For
example, it has been observed through simulations that the test via mismatched
divergence performs better than the Hoeffding test [7]. However, an analytical
comparison between the Hoeffding test and other tests is missing since refined
asymptotics of the Hoeffding are not available.

In this paper, we wish to understand the behavior of the second-order term of
the Hoeffding test as well as of Hoeffding-like tests where the KL divergence
is replaced by other divergences, in the following referred to as divergence
test. For a large class of divergences, we demonstrate that the second-order
term is given by$-\sqrt{V(P\|Q)Q^{-1}_{\chi^{2},k-1}(\epsilon)}$, where
$Q^{-1}_{\chi^{2},k-1}(\cdot)$ denotes the inverse of the tail probability of
the chi-squared distribution with $k-1$ degrees of freedom. This class of
divergences includes the KL divergence, so we obtain the second-order term of
the Hoeffding test, as a special case.

The rest of this paper is organized as follows. Section II presents notations
and the problem formulation. Section III discusses our main results. Section
IV presents the proof of our results. Section V concludes the paper with a
summary and discussion of our results.

##  II Notations and Problem Formulation

###  II-A Notations

Let $f(x)$ and $g(x)$ be two real-valued functions. For
$a\in\mathbb{R}\cup\\{\infty\\}$, we write $f(x)=O(g(x))$ as $x\rightarrow a$
if $\limsup_{x\to a}\frac{|f(x)|}{|g(x)|}<\infty$. Similarly, we write
$f(x)=o(g(x))$ as $x\rightarrow a$ if $\lim_{x\to a}\frac{|f(x)|}{|g(x)|}=0$.
Finally, we write $f(x)=\Theta(g(x))$ as $x\to a$ if $f(x)=O(g(x))$ and
$\liminf_{x\to a}\frac{|f(x)|}{|g(x)|}>0$.

Let $\\{a_{n}\\}$ be a sequence of positive real numbers. We say that a
sequence of random variables is $X_{n}=o_{p}(a_{n})$ if for every
$\epsilon>0$, we have

$\displaystyle\lim_{n\rightarrow\infty}P\left(\left|\frac{X_{n}}{a_{n}}\right|>\epsilon\right)=0.$

Similarly, we say that $X_{n}=O_{p}(a_{n})$ if for every $\epsilon>0$ there
exist $M_{\epsilon}>0$ and $N_{\epsilon}\in\mathbb{N}$ such that

$\displaystyle
P\left(\left|\frac{X_{n}}{a_{n}}\right|>M_{\epsilon}\right)\leq\epsilon,\quad
n\geq N_{\epsilon}.$

###  II-B Divergence and Divergence Test

We consider a divergence test on a random variable $Z$ that takes value in a
discrete set $\mathcal{Z}=\\{a_{1},\cdots,a_{k}\\}$, where $k\geq 2$. We
denote the probability distribution function of $Z$ by a $k$-length vector
$P=(P_{1},\cdots,P_{k})^{T}$, where

$\displaystyle P_{i}\triangleq\text{Pr}\\{Z=a_{i}\\},\quad i=1,\cdots,k.$

Let

$\displaystyle\bar{\mathcal{P}}(\mathcal{Z})\triangleq\left\\{P=(P_{1},\cdots,P_{k})^{T}\;|\;P_{i}\geq
0,\;i=1,\cdots,k\mbox{ and }\sum_{i=1}^{k}P_{i}=1\right\\}$

be the set of all such probability distributions. The set of all positive
probability distributions with $P_{i}>0,\;i=1,\cdots,k$ on $\mathcal{Z}$ is
denoted by $\mathcal{P}(\mathcal{Z})$. Let $Z^{n}=(Z_{1},\cdots,Z_{n})$ denote
an $n$-length i.i.d. sequence of $Z$. By denoting the realization of $Z^{n}$
by $z^{n}$, we define the type distribution
$t_{z^{n}}=(t_{z^{n}}(a_{1}),\cdots,t_{z^{n}}(a_{k}))^{T}$ of the sequence
$z^{n}$ as

$\displaystyle(t_{z^{n}}(a_{1}),\cdots,t_{z^{n}}(a_{k}))^{T}\triangleq\left(\frac{N_{a_{1}|z^{n}}}{n},\cdots,\frac{N_{a_{k}|z^{n}}}{n}\right)^{T}$

where $N_{a_{i}|z^{n}},\;i=1,\cdots,k$ denotes the number of times $a_{i}$
occurs in the sequence $z^{n}$. Since $\sum_{i=1}^{k}P_{i}=1$, a probability
vector $P=(P_{1},\cdots,P_{k})^{T}\in\mathcal{P}(\mathcal{Z})$ can be
represented by any $(k-1)$ components of $P$. With this representation, the
set $\mathcal{P}(\mathcal{Z})$ can be identified as a $(k-1)$-dimensional
manifold; see [8]. In this paper, we choose the coordinate system of the
probability distribution $P=(P_{1},\cdots,P_{k})^{T}$ as the first $(k-1)$
components denoted by $\mathbf{P}=(P_{1},\cdots,P_{k-1})^{T}$.

Given any two probability distributions $P,Q\in\mathcal{P}(\mathcal{Z})$, one
can define a non-negative binary function $\tilde{D}(P\|Q)$ called a
divergence which represents a measure of discrepancy between them. A
divergence is not necessarily symmetric in its arguments and also need not
satisfy the triangle inequality; see [8, 9] for more details. Mathematically,
a divergence is defined as follows.

###### Definition 1

Consider two points $P$ and $Q$ in $\mathcal{P}(\mathcal{Z})$ whose
coordinates are $\mathbf{P}=(P_{1},\cdots,P_{k-1})^{T}$ and
$\mathbf{Q}=(Q_{1},\cdots,Q_{k-1})^{T}$. A divergence $\tilde{D}(P\|Q)$
between $P$ and $Q$ is a smooth function of $\mathbf{P}$ and $\mathbf{Q}$ (we
may write $\tilde{D}(P\|Q)=\tilde{D}(\mathbf{P}\|\mathbf{Q})$) satisfying the
following conditions:

  1. 1.

$\tilde{D}(P\|Q)\geq 0$ for any $P,Q\in\mathcal{P}(\mathcal{Z})$.

  2. 2.

$\tilde{D}(P\|Q)=0$ if, and only if, $P=Q$.

  3. 3.

The Taylor expansion of $\tilde{D}$ satisfies

$\displaystyle\tilde{D}(\mathbf{P}+\varepsilon\|\mathbf{P})=\frac{1}{2}\sum_{i,j=1}^{k-1}g_{ij}(\mathbf{P})\varepsilon_{i}\varepsilon_{j}+O(\|\varepsilon\|_{2}^{3}),\quad\text{as
}\|\varepsilon\|_{2}\rightarrow 0,$

for some $(k-1)\times(k-1)$-dimensional positive-definite matrix $G=(g_{ij})$
that depends on $\mathbf{P}$ and
$\varepsilon=(\varepsilon_{1},\cdots,\varepsilon_{k-1})^{T}$, and where
$\|\varepsilon\|_{2}\triangleq\sqrt{\sum_{i=1}^{k-1}(\varepsilon_{i})^{2}}$ is
the Euclidean norm of $\varepsilon$.

For any $\tilde{D}(P\|Q)=\tilde{D}(\mathbf{P}\|\mathbf{Q})$, the partial
derivatives of $\tilde{D}(P\|Q)$ with respect to the first variable
$\mathbf{P}=(P_{1},\cdots,P_{k-1})^{T}$ are given by $\frac{\partial}{\partial
P_{i}}\tilde{D}(P\|Q)=\frac{\partial}{\partial
P_{i}}\tilde{D}(\mathbf{P}\|\mathbf{Q}),\;i=1,\cdots,k-1$. Similarly, the
partial derivatives of $\tilde{D}(P\|Q)$ with respect to the second variable
$\mathbf{Q}=(Q_{1},\cdots,Q_{k-1})^{T}$ are given by $\frac{\partial}{\partial
Q_{i}}\tilde{D}(P\|Q)=\frac{\partial}{\partial
Q_{i}}\tilde{D}(\mathbf{P}\|\mathbf{Q}),\;i=1,\cdots,k-1$. Since, by
definition, every divergence $\tilde{D}$ attains a minimum at $P=Q$, it holds
that

$\displaystyle\left.\frac{\partial}{\partial
P_{i}}\tilde{D}(P\|Q)\right|_{P=Q}=0,\quad i=1,\cdots,k-1$ (3)
$\displaystyle\left.\frac{\partial}{\partial
Q_{i}}\tilde{D}(P\|Q)\right|_{P=Q}=0,\quad i=1,\cdots,k-1.$

See [9, (3.1)–(3.4)] for more details.

There are many classes of divergences that are widely used in various fields
of science and engineering; see, e.g., [10] for more details. A well-known
example of a divergence is the $f$-divergence defined as follows: Let
$f:(0,\in\infty)\rightarrow\mathbb{R}$ be a convex function with $f(1)=0$.
Then, the $f$-divergence between $P$ and $Q$ is defined as

$\displaystyle D_{f}(P\|Q)\triangleq\sum
Q_{i}f\left(\frac{P_{i}}{Q_{i}}\right).$ (4)

When $f(u)=u\log u$, $D_{f}$ is the Kullback-Leibler divergence. For

$\displaystyle
f(u)=\frac{4}{1-\alpha^{2}}(1-u^{(1+\alpha)/2}),\;\text{where}\;\alpha\neq\pm
1$ (5)

the $f$-divergence is the $\alpha$-divergence given by

$\displaystyle D_{\alpha}(P\|Q)\triangleq\frac{4}{1-\alpha^{2}}\left[1-\sum
P_{i}^{\frac{1-\alpha}{2}}Q_{i}^{\frac{1+\alpha}{2}}\right],\quad\alpha\neq\pm
1.$ (6)

We next define a divergence test for case 1 of composite hypothesis testing
(see Section I), That is, it is known that under hypothesis $H_{0}$ the
distribution is $P$, while under hypothesis $H_{1}$ the distribution is
anything but $P$. A Hoeffding-like test or divergence test
$T_{n}^{\tilde{D}}(r)$ for testing $H_{0}:\bar{P}=P$ against the alternative
$H_{1}:\bar{P}=Q$ is defined as follows:

> Upon observing $z^{n}$, if $\tilde{D}(t_{z^{n}}\|P)<r$ for some $r>0$, then
> the null hypothesis $P$ is accepted; else $P$ is rejected.

For $r>0$, define the acceptance region for $P$ as

$\displaystyle\mathcal{A}^{\tilde{D}}_{n}(r)\triangleq\left\\{z^{n}\;\left|\right.\;\tilde{D}(t_{z^{n}}\|P)<r\right\\}.$

Then, the type-I and the type-II errors are given by

$\displaystyle\alpha_{n}(T_{n}^{\tilde{D}}(r))$ $\displaystyle\triangleq
P^{n}\left(\mathcal{A}^{\tilde{D}}_{n}(r)^{c}\right)$
$\displaystyle\beta_{n}(T_{n}^{\tilde{D}}(r))$ $\displaystyle\triangleq
Q^{n}(\mathcal{A}^{\tilde{D}}_{n}(r)).$

Our goal is to analyze the asymptotics of the type-II error when the type-I
error satisfies $\alpha_{n}\leq\epsilon,\;0<\epsilon<1$. Following the
discussion in Section I, we define the first-order term $\beta^{\prime}$ and
the second-order term $\beta^{\prime\prime}$ for the divergence test as
follows:

$\displaystyle\beta^{\prime}$ $\displaystyle\triangleq$
$\displaystyle\lim\limits_{n\rightarrow\infty}-\frac{1}{n}\log\beta_{n}$
$\displaystyle\beta^{\prime\prime}$ $\displaystyle\triangleq$
$\displaystyle\lim\limits_{n\rightarrow\infty}\frac{-\ln\beta_{n}-n\beta^{\prime}}{\sqrt{n}}$

if the limits exist. For the Hoeffding test, it is known that
$\beta^{\prime}=D(P\|Q)$. In this paper, we generalize this result to the
divergence test for a class of divergences defined in Definition 2. We further
obtain $\beta^{\prime\prime}$ for the divergence test.

##  III Second-order Asymptotics of the Divergence Test

We shall consider the following class of divergences.

###### Definition 2

Let $\varXi$ denote the class of divergences satisfying the following
conditions:

  1. 1.

For any $P,T\in\mathcal{P}(\mathcal{Z})$, the second-order Taylor
approximation of $\tilde{D}(T\|P)$ around $T=P$ is given by

$\displaystyle\tilde{D}(T\|P)$ $\displaystyle=$ $\displaystyle\eta
d_{\chi^{2}}(T,P)+O(\|\mathbf{T}-\mathbf{P}\|_{2}^{3}),\quad\text{as}\quad\|\mathbf{T}-\mathbf{P}\|_{2}\rightarrow
0$ (7)

for some constant $\eta>0$ (that possibly depends on $P$). In (7),
$\mathbf{T}=(T_{1},\cdots,T_{k-1})^{T}$,
$\mathbf{P}=(P_{1},\cdots,P_{k-1})^{T}$, and $d_{\chi^{2}}$ is the
$\chi^{2}$-divergence defined as

$\displaystyle
d_{\chi^{2}}(T,P)\triangleq\sum_{i=1}^{k}\frac{(T_{i}-P_{i})^{2}}{P_{i}}.$ (8)

  2. 2.

For any $P,T\in\mathcal{P}(\mathcal{Z})$, the divergence $\tilde{D}$ satisfies
the Pinsker-type inequality

$\displaystyle\tilde{C}\|T-P\|^{2}_{1}\leq\tilde{D}(T\|P),\quad\text{for some
}\tilde{C}>0$ (9)

where $\|T-P\|_{1}\triangleq\sum_{i=1}^{k}|T_{i}-P_{i}|$ denotes the $L^{1}$
norm of $T-P$.

  3. 3.

The CDF of the statistic $\eta^{-1}n\tilde{D}(t_{z^{n}}\|P)$ can be
approximated as

$\displaystyle
P^{n}(\eta^{-1}n\tilde{D}(t_{Z^{n}}\|P)<c)=F_{\chi^{2},k-1}(c)+O(\delta_{n}),\quad
c>0$ (10)

for some positive sequence $\delta_{n}$ satisfying
$\lim_{n\rightarrow\infty}\delta_{n}=0$, where $F_{\chi^{2},k-1}$ is the CDF
of the chi-squared random variable $\chi^{2}_{k-1}$ with $k-1$ degrees of
freedom.

The following theorem characterizes $\beta^{\prime}$ and
$\beta^{\prime\prime}$ of the divergence test for any divergence $\tilde{D}$
in $\varXi$.

###### Theorem 1

Let $\tilde{D}\in\varXi$ and $0<\epsilon<1$. Consider the divergence test
$T_{n}^{\tilde{D}}(r)$ for testing $H_{0}:P$ against the alternative
$H_{1}:Q$, where $P,Q\in\mathcal{P}(\mathcal{Z})$ and $P\neq Q$. Then, the
type-II error satisfies the following:
Part 1: There exists a threshold value $r_{n}$ satisfying

$\displaystyle\alpha_{n}(T_{n}^{\tilde{D}}(r_{n}))\leq\epsilon$ (11)

such that, as $n\rightarrow\infty$,

$\displaystyle-\ln\beta_{n}(T_{n}^{\tilde{D}}(r_{n}))$ $\displaystyle\geq
nD(P\|Q)-\sqrt{nV(P\|Q)Q^{-1}_{\chi^{2},k-1}(\epsilon)}+O(\max\\{\delta_{n}\sqrt{n},\ln
n\\}).$ (12)

Part 2: For all $r_{n}>0$ satisfying (11), we have as $n\rightarrow\infty$

$\displaystyle-\ln\beta_{n}(T_{n}^{\tilde{D}}(r_{n}))$ $\displaystyle\leq
nD(P\|Q)-\sqrt{nV(P\|Q)Q^{-1}_{\chi^{2},k-1}(\epsilon)}+O(\max\\{\delta_{n}\sqrt{n},\ln
n\\})$ (13)

where $Q^{-1}_{\chi^{2},k-1}(\cdot)$ is the inverse of $c\mapsto
1-F_{\chi^{2},k-1}(c)$.

###### Proof.

See Section IV. ∎

Since the sequence $\delta_{n}$ in (12) and (13) tends to zero as
$n\to\infty$, we have that $O(\max\\{\delta_{n}\sqrt{n},\ln
n\\})=o(\sqrt{n})$. Consequently, (12) and (13) imply that, for the optimal
threshold value $r_{n}$,

$\displaystyle-\ln\beta_{n}(T_{n}^{\tilde{D}}(r_{n}))$
$\displaystyle=nD(P\|Q)-\sqrt{nV(P\|Q)Q^{-1}_{\chi^{2},k-1}(\epsilon)}+o(\sqrt{n}).$
(14)

Thus, Theorem 1 characterizes the first and second-order terms of the
divergence test for any $\tilde{D}\in\varXi$. It can be verified that
$\sqrt{Q^{-1}_{\chi^{2},k-1}(\epsilon)}>Q^{-1}(\epsilon)$ for all
$0<\epsilon<1$. Consequently, the second-order term $\beta^{\prime\prime}$ of
the divergence test is strictly smaller than the second-order term of the
Neyman-Pearson test.

For certain divergences in $\varXi$, we can obtain more precise asymptotics
than the one in (14) by tightening the $o(\sqrt{n})$ term. To this end, we
shall first discuss the three conditions stated in Definition 2, which we
shall do one by one.

_Condition 1_ : When $\tilde{D}$ is the $f$-divergence $D_{f}$, it follows
from a Taylor-series expansion of $D_{f}(T\|P)$ around $T=P$ that $D_{f}$
satisfies (7) with $\eta=\frac{f^{\prime\prime}(1)}{2}$ [11, Th. 4.1]. Since
both the $\alpha$-divergence and the KL divergence $D$ belong to the
$f$-divergence class with $f^{\prime\prime}(1)=1$, we obtain that
$\tilde{D}=\\{D_{\alpha},D\\}$ satisfy (7) with $\eta=\frac{1}{2}$ [12].
Furthermore, for the Renyi divergence of order $\alpha>0$, defined as

$\displaystyle
I_{\alpha}(P\|Q)=\frac{1}{\alpha-1}\left[\ln\left(\sum_{i=1}^{k}P_{i}^{\alpha}Q_{i}^{1-\alpha}\right)\right],\quad\alpha\neq
1$

we can show that $\eta=\frac{\alpha}{2},\;i=1,\cdots,k-1$. Thus, $I_{\alpha}$
satisfies (7) with $\eta=\frac{\alpha}{2}$. There are many more divergences
that satisfy (7), such as the Battacharya divergence, the Tsallis divergence,
and the Sharma-Mittal divergence; see [10] for more details. In information
geometry, such divergences are referred to as invariant divergences [10, Eq.
2.29].

_Condition 2_ : It is well-known that the KL divergence $D$ satisfies
Pinsker’s inequality [13, Lemma 11.6.1]. From [14, Th. 3], it further follows
that Pinsker’s inequality can be generalized to many $f$-divergences under
some conditions on $f$. In particular, it follows from [14, Cor. 6] that the
$\alpha$-divergence satisfies a Pinsker-type inequality when $3\leq\alpha\leq
3,\alpha\neq\pm 1$:

$\displaystyle\frac{1}{2}\|T-P\|^{2}_{1}\leq D_{\alpha}(T\|P).$

It follows from the same corollary that the Renyi divergence $I_{\alpha}$ also
satisfies (9). Furthermore, for any $f$-divergence, [15, Th. 1] demonstrates
that, if $D_{f}(T,P)<\epsilon$ for a sufficiently small $\epsilon$, then
$\frac{f^{\prime\prime}(1)}{2\sqrt{2}}\|T-P\|^{2}_{1}<\epsilon$. This implies,
that if $D_{f}(T,P)=O(a_{n})$ for some positive sequence $a_{n}$ such that
$a_{n}\rightarrow 0$, then $\|T-P\|_{1}=O(\sqrt{a_{n}})$, which is sufficient
to prove Theorem 1. In fact, condition 2 can be replaced by the condition
that, if $\tilde{D}(T,P)=O(a_{n})$ for some positive sequence $a_{n}$ such
that $a_{n}\rightarrow 0$, then $\|T-P\|_{1}=O(\sqrt{a_{n}})$.

_Condition 3_ : Note that this condition is a Berry-Esseen-type convergence of
the statistic $\eta^{-1}n\tilde{D}(t_{Z^{n}}\|P)$ to the chi-squared
distribution with $k-1$ degrees of freedom. For both the $\alpha$-divergence
and the KL divergence, we have $\eta=\frac{1}{2}$. The following result
implies that, for these divergences, (10) holds with
$\delta_{n}=\frac{1}{\sqrt{n}}$. Indeed, it follows from [16, Th. 3.1] and
[17, Th. 3] that the power divergence statistics

$\displaystyle T_{\lambda}(\mathbf{Y})$ $\displaystyle\overset{\Delta}{=}$
$\displaystyle\frac{2}{\lambda(\lambda+1)}\sum_{i=1}^{k}Y_{i}\left[\left(\frac{Y_{i}}{nP_{i}}\right)^{\lambda}-1\right],\quad\lambda\in\mathbb{R}\setminus\\{0,-1\\}$
$\displaystyle T_{0}(\mathbf{Y})$ $\displaystyle\overset{\Delta}{=}$
$\displaystyle\lim_{\lambda\rightarrow 0}T_{\lambda}(\mathbf{Y})$
$\displaystyle T_{-1}(\mathbf{Y})$ $\displaystyle\overset{\Delta}{=}$
$\displaystyle\lim_{\lambda\rightarrow-1}T_{\lambda}(\mathbf{Y})$

satisfies

$\displaystyle
P^{n}(T_{\lambda}(\mathbf{Y})<c)=F_{\chi^{2},k-1}(c)+O(n^{-1/2}),\quad
c>0,\;\lambda\in\mathbb{R}.$ (15)

See [18] for more details. Letting
$\lambda=\frac{-(1+\alpha)}{2},\;\alpha\neq\pm 1$, we can write
$T_{\lambda}(\mathbf{Y})$ in terms of the $\alpha$-divergence as

$\displaystyle
T_{\lambda}(\mathbf{Y})=2nD_{\alpha}(t_{Z^{n}}\|P),\quad\alpha\neq\pm 1.$

Similarly, for $\lambda=0$, $T_{0}(\mathbf{Y})$ can be expressed in terms of
the KL divergence as $T_{0}(\mathbf{Y})=2nD(t_{z^{n}}\|P)$. It then follows
from (15) that $\tilde{D}=\\{D_{\alpha},D\\},\;\alpha\neq\pm 1$ satisfies
(10).

From the above discussion, we conclude that $\tilde{D}=\\{D,D_{\alpha}\\}$
with $-3\leq\alpha\leq 3,\alpha\neq\pm 1$ satisfy all three conditions in
Definition 2 with $\delta_{n}=\frac{1}{\sqrt{n}}$ and thus belong to the class
$\varXi$. We thus have the following corollary to Theorem 1, which sharpens
the third-order term in (14).

###### Corollary 2

Let $0<\epsilon<1$. Consider the divergence test $T_{n}^{\tilde{D}}(r)$ for
$\tilde{D}=\\{D,D_{\alpha}\\}$, $-3\leq\alpha\leq 3,\alpha\neq\pm 1$, for
testing $H_{0}:P$ against the alternative $H_{1}:Q$, where
$P,Q\in\mathcal{P}(\mathcal{Z})$ and $P\neq Q$. Then, the type-II error of
$T_{n}^{\tilde{D}}(r_{n})$ minimized over all the threshold values $r_{n}$
satisfying

$\displaystyle\alpha_{n}(T_{n}^{\tilde{D}}(r_{n}))\leq\epsilon$

can be characterized as

$\displaystyle-\ln\beta_{n}(T_{n}^{\tilde{D}}(r_{n}))=nD(P\|Q)-\sqrt{nV(P\|Q)Q^{-1}_{\chi^{2},k-1}(\epsilon)}+O(\ln
n),\quad\text{as}\quad n\rightarrow\infty.$

Note that, when $\tilde{D}$ is the KL divergence, the divergence test
$T_{n}^{\tilde{D}}(r)$ is the Hoeffding test. Hence, the above corollary
recovers the second-order asymptotics of the Hoeffding test as a special case.

##  IV Proof of Theorem 1

###  IV-A Proof of Part 1 of Theorem 1

From (10), it follows that there exist $M_{0}>0$ and $N_{0}\in\mathbb{N}$ such
that

$\displaystyle\left|P^{n}\left(\eta^{-1}n\tilde{D}(t_{Z^{n}}\|P)\geq
c\right)-Q_{\chi^{2},k-1}(c)\right|\leq M_{0}\delta_{n},\quad n\geq N_{0}.$
(16)

For $0<\epsilon<1$, let

$\displaystyle r_{n}=\frac{\eta}{n}Q_{\chi^{2},k-1}^{-1}\left(\epsilon-
M_{0}\delta_{n}\right).$ (17)

Then, from (16), it follows that the type-I error is upper-bounded by
$\epsilon$:

$\displaystyle\alpha_{n}(T_{n}^{\tilde{D}}(r_{n}))$ $\displaystyle=$
$\displaystyle P^{n}(\tilde{D}(t_{Z^{n}}\|P)\geq r_{n})$ $\displaystyle=$
$\displaystyle P^{n}\left(\eta^{-1}nD(t_{Z^{n}}\|P)\geq
Q_{\chi^{2},k-1}^{-1}(\epsilon-M_{0}\delta_{n})\right)$ $\displaystyle\leq$
$\displaystyle Q_{\chi^{2},k-1}\left(Q_{\chi^{2},k-1}^{-1}\left(\epsilon-
M_{0}\delta_{n}\right)\right)+M_{0}\delta_{n}$ $\displaystyle=$
$\displaystyle\epsilon,\quad n\geq N_{0}.$

We next consider the type-II error for $r_{n}$ in (17). To this end, define

$\displaystyle A_{\tilde{D}}(r^{\prime})$ $\displaystyle\triangleq$
$\displaystyle\left\\{T\in\mathcal{P}(\mathcal{Z})\mid\tilde{D}(T\|P)<r^{\prime}\right\\},\quad
r^{\prime}>0.$

Then,

$\displaystyle\beta_{n}(T_{n}^{\tilde{D}}(r_{n}))$ $\displaystyle=$
$\displaystyle Q^{n}(\tilde{D}(t_{Z^{n}}\|P)<r_{n})$ (18) $\displaystyle=$
$\displaystyle\sum_{z^{n}:\tilde{D}(t_{z^{n}}\|P)<r_{n}}Q^{n}(z^{n})$
$\displaystyle=$ $\displaystyle\sum_{\tilde{P}\in\mathcal{P}_{n}\cap
A_{\tilde{D}}(r_{n})}Q^{n}(T(\tilde{P}))$ $\displaystyle\leq$
$\displaystyle\sum_{\tilde{P}\in\mathcal{P}_{n}\cap
A_{\tilde{D}}(r_{n})}\exp\\{-nD(\tilde{P}\|Q)\\},\quad n\geq N_{0}$

where the last step follows from [13, Th. 11.1.4]. In (18), $\mathcal{P}_{n}$
denotes the set of types with denominator $n$ and $T(\tilde{P})$ is the type
class of $\tilde{P}$, defined as

$\displaystyle
T(\tilde{P})\triangleq\left\\{z^{n}\in\mathcal{Z}^{n}\;|\;t_{z^{n}}=\tilde{P}\right\\}.$
(19)

We next derive a lower bound on $D(\tilde{P}\|Q)$ for
$\tilde{P}\in\mathcal{P}_{n}\cap A_{\tilde{D}}(r_{n})$. To this end, we shall
use the following auxiliary results.

###### Lemma 3

For any two probability distributions $Q=(Q_{1},\cdots,Q_{k})^{T}$ and
$T=(T_{1},\cdots,T_{k})^{T}$, the second-order Taylor approximation of the
function $T\mapsto D(T\|Q)$ around the null hypothesis $T=P$ is given by

$\displaystyle
D(T\|Q)=D(P\|Q)+\sum_{i=1}^{k}(T_{i}-P_{i})\ln\left(\frac{P_{i}}{Q_{i}}\right)+\frac{1}{2}d_{\chi^{2}}(T,P)+O(\|\mathbf{T}-\mathbf{P}\|_{2}^{3})$
(20)

as $\|\mathbf{T}-\mathbf{P}\|_{2}\rightarrow 0$.

###### Proof:

See Appendix A. ∎

By the Pinsker-type inequality, we obtain that, for every $T\in
A_{\tilde{D}}(r)$, we have $\|T-P\|_{1}\leq\tilde{k}\sqrt{r}$ for some
constant $\tilde{k}$. This implies that
$\|\mathbf{T}-\mathbf{P}\|_{1}\leq\tilde{k}_{1}\sqrt{r}$ for some constant
$\tilde{k}_{1}$. Since any two norms on a finite-dimensional Euclidean space
are equivalent, there exists a constant $C_{0}>0$ such that the Euclidean
distance is bounded by

$\displaystyle\|\mathbf{T}-\mathbf{P}\|_{2}$ $\displaystyle\leq$
$\displaystyle C_{0}\sqrt{r}.$ (21)

Thus, for any $T\in A_{\tilde{D}}(r_{n})$ with $r_{n}$ in (17), it follows
that

$\displaystyle\|\mathbf{T}-\mathbf{P}\|_{2}=O\left(\frac{1}{\sqrt{n}}\right)$
(22)

since $r_{n}=O\left(\frac{1}{n}\right)$. Then, for any $T\in
A_{\tilde{D}}(r_{n})$ with $r_{n}$ in (17), (7) and (20) and can be written as

$\displaystyle\tilde{D}(T\|P)$ $\displaystyle=$ $\displaystyle\eta
d_{\chi^{2}}(T,P)+O\left(\frac{1}{n^{3/2}}\right)$ (23) $\displaystyle
D(T\|Q)$ $\displaystyle=$ $\displaystyle
D(P\|Q)+\sum_{i=1}^{k}(T_{i}-p_{i})\ln\left(\frac{p_{i}}{q_{i}}\right)+\frac{1}{2}d_{\chi^{2}}(T,P)+O\left(\frac{1}{n^{3/2}}\right).$
(24)

The expansion (23) implies that there exist $M>0$ and $N_{1}\geq N_{0}$ such
that, for all $n\geq N_{1}$ and $T\in A_{\tilde{D}}(r_{n})$,

$\displaystyle|\tilde{D}(T\|P)-\eta d_{\chi^{2}}(T,P)|\leq\frac{M}{n^{3/2}}.$
(25)

Next define

$\displaystyle A_{\chi^{2}}(r^{\prime})$ $\displaystyle\triangleq$
$\displaystyle\left\\{T\in\mathcal{P}(\mathcal{Z})\mid
d_{\chi^{2}}(T,P)<r^{\prime}\right\\},\quad r^{\prime}>0$
$\displaystyle\bar{A}_{\chi^{2}}(r^{\prime})$ $\displaystyle\triangleq$
$\displaystyle\left\\{T\in\mathcal{P}(\mathcal{Z})\mid d_{\chi^{2}}(T,P)\leq
r^{\prime}\right\\},\quad r^{\prime}>0.$

We have the following lemma.

###### Lemma 4

Let $r_{n}$ be given in (17). Then, we have

$\displaystyle
A_{\tilde{D}}(r_{n})\subseteq\bar{A}_{\chi^{2}}\left(\frac{r_{n}}{\eta}+\frac{M}{\eta
n^{3/2}}\right),\quad n\geq N_{1}.$ (26)

###### Proof:

It follows from (25) that, for $T\in A_{\tilde{D}}(r_{n})$ and $n\geq N_{1}$,

$\displaystyle\eta d_{\chi^{2}}(T,P)-\frac{M}{n^{3/2}}$ $\displaystyle\leq$
$\displaystyle\tilde{D}(T\|P)<r_{n}.$

This implies that

$\displaystyle d_{\chi^{2}}(T,P)<\frac{r_{n}}{\eta}+\frac{M}{\eta n^{3/2}}.$

Thus $T\in A_{\chi^{2}}\left(\frac{r_{n}}{\eta}+\frac{M}{\eta
n^{3/2}}\right)\subseteq\bar{A}_{\chi^{2}}\left(\frac{r_{n}}{\eta}+\frac{M}{\eta
n^{3/2}}\right)$. ∎

We next use (24) to lower-bound the term $D(\tilde{P}\|Q)$ for
$\tilde{P}\in\mathcal{P}_{n}\cap A_{D}(r)$. Indeed, it follows from (24) that
there exist $M_{2}>0$ and $\ddot{N}_{2}\in\mathbb{N}$ such that, for all
$n\geq\ddot{N}_{2}$ and $T\in A_{\tilde{D}}(r_{n})$,

$\displaystyle|D(T\|Q)-D(P\|Q)-\sum_{i=1}^{k}(T_{i}-P_{i})\ln\left(\frac{P_{i}}{Q_{i}}\right)-\frac{1}{2}d_{\chi^{2}}(T,P)|\leq\frac{M_{2}}{n^{3/2}}.$

Consequently, for all $n\geq\ddot{N}_{2}$ and $T\in A_{\tilde{D}}(r_{n})$,

$\displaystyle D(T\|Q)$ $\displaystyle\geq$ $\displaystyle
D(P\|Q)+\sum_{i=1}^{k}(T_{i}-P_{i})\ln\left(\frac{P_{i}}{Q_{i}}\right)+\frac{1}{2}d_{\chi^{2}}(T,P)-\frac{M_{2}}{n^{3/2}}$
(27) $\displaystyle\geq$ $\displaystyle
D(P\|Q)+\sum_{i=1}^{k}(T_{i}-P_{i})\ln\left(\frac{P_{i}}{Q_{i}}\right)-\frac{M_{2}}{n^{3/2}}$

where the last inequality follows since $d_{\chi^{2}}(T,P)$ is non-negative.

To proceed further, let us consider the following function, defined for a
probability distribution
$\Gamma=(\Gamma_{1},\cdots,\Gamma_{k})^{T}\in\mathcal{P}(\mathcal{Z})$

$\displaystyle\ell(\Gamma)$ $\displaystyle\triangleq$
$\displaystyle\sum_{i=1}^{k}(\Gamma_{i}-P_{i})\alpha_{i}$ (28)

where

$\displaystyle\alpha_{i}\triangleq\ln\left(\frac{P_{i}}{Q_{i}}\right),\quad
i=1,\cdots,k.$ (29)

For $n\geq N_{1}$ and $\tilde{P}\in\mathcal{P}_{n}\cap A_{\tilde{D}}(r_{n})$,
we have that

$\displaystyle\ell(\tilde{P})\geq\min_{\mathcal{P}_{n}\cap
A_{\tilde{D}}(r_{n})}\ell(\Gamma)\geq\min_{\bar{A}_{\chi^{2}}\left(\frac{r_{n}}{\eta}+\frac{M}{\eta
n^{3/2}}\right)}\ell(\Gamma)$ (30)

where the last inequality follows from (26).

To compute the right-most minimum in (30), we define the following quantities:

$\displaystyle\mathcal{I}$ $\displaystyle\triangleq$
$\displaystyle\left\\{i=1,\cdots,k\;|\;\alpha_{i}-D(P\|Q)>0\right\\}$ (31)
$\displaystyle\mathcal{B}$ $\displaystyle\triangleq$
$\displaystyle\left\\{\alpha_{j}-D(P\|Q),j\in\mathcal{I}\right\\}$ (32)
$\displaystyle\tau$ $\displaystyle\triangleq$ $\displaystyle\max\mathcal{B}.$
(33)

We then have the following result.

###### Lemma 5

Let $0<\sqrt{\tilde{r}}<\frac{\sqrt{V(P\|Q)}}{\tau}$. Then, the probability
distribution $\Gamma^{*}=(\Gamma^{*}_{1},\cdots,\Gamma^{*}_{k})$ that
minimizes $\ell(\Gamma)$ over $\bar{A}_{\chi^{2}}(\tilde{r})$ is given by

$\displaystyle\Gamma^{*}_{i}$ $\displaystyle=$ $\displaystyle
P_{i}+\frac{\sqrt{\tilde{r}}\left(D(P\|Q)-\alpha_{i}\right)P_{i}}{\sqrt{V(P\|Q)}};\quad
i=1,\cdots,k.$ (34)

Moreover,

$\displaystyle\min_{\Gamma\in\bar{A}_{\chi^{2}}\left(\tilde{r}\right)}\ell(\Gamma)=-\sqrt{V(P\|Q)\tilde{r}}.$
(35)

###### Proof:

See Appendix B. ∎

###### Remark 1

Since $\Gamma^{*}$ and $P$ are probability distributions, by taking summation
on both sides of (34), we obtain

$\displaystyle\sum_{i=1}^{k}(D(P\|Q)-\alpha_{i})P_{i}=0.$ (36)

By the assumption of Theorem 1, we have that $P\neq Q$. Hence,
$D(P\|Q)-\alpha_{i}$ cannot be zero for all $i=1,\cdots,k$. This implies that
there exist two distinct indices $l,l^{\prime}\in\\{1,\cdots,k\\}$, such that
$D(P\|Q)-\alpha_{l}<0$ and $D(P\|Q)-\alpha_{l^{\prime}}>0$. It follows that
$l\in\mathcal{I}$, which in turn yields that $\mathcal{B}$ is a non-empty set.

Let

$\displaystyle r^{\prime}_{n}=\frac{r_{n}}{\eta}+\frac{M}{\eta n^{3/2}}.$ (37)

Since $r^{\prime}_{n}$ is vanishing as $n\rightarrow\infty$, we can choose
$\ddot{N}$ such that, for $n\geq\ddot{N}$, $r^{\prime}_{n}$ satisfies
$\sqrt{r^{\prime}_{n}}<\frac{\sqrt{V(P\|Q)}}{\tau}$ with $\tau$ defined in
(33). Then, (30) and (35) yield that, for $\tilde{P}\in\mathcal{P}_{n}\cap
A_{\tilde{D}}(r_{n})$ and $n\geq
N_{2}\triangleq\max\\{N_{1},\ddot{N}_{2},\ddot{N}\\}$,

$\displaystyle\ell(\tilde{P})$ $\displaystyle\geq$
$\displaystyle\min_{\bar{A}_{\chi^{2}}(r^{\prime}_{n})}\ell(\Gamma)$ (38)
$\displaystyle=$ $\displaystyle-\sqrt{V(P\|Q)r^{\prime}_{n}}.$

It follows that, for any $\tilde{P}\in\mathcal{P}_{n}\cap
A_{\tilde{D}}(r_{n})$, (27) can be further lower-bounded as

$\displaystyle D(\tilde{P}\|Q)$ $\displaystyle\geq$ $\displaystyle
D(P\|Q)-\sqrt{V(P\|Q)r^{\prime}_{n}}-\frac{M_{2}}{n^{3/2}},\quad n\geq N_{2}.$
(39)

Applying (39) to (18), the type-II error can be upper-bounded as

$\displaystyle\beta_{n}(T_{n}^{\tilde{D}}(r_{n}))$ $\displaystyle\leq$
$\displaystyle\sum_{\tilde{P}\in\mathcal{P}_{n}\cap
A_{\tilde{D}}(r_{n})}\exp\\{-nD(\tilde{P}\|Q)\\}$ (40) $\displaystyle\leq$
$\displaystyle\sum_{\tilde{P}\in\mathcal{P}_{n}\cap
A_{\tilde{D}}(r_{n})}\exp\left\\{-nD(P\|Q)+n\sqrt{V(P\|Q)r^{\prime}_{n}}+\frac{M_{2}}{\sqrt{n}}\right\\}$
$\displaystyle\leq$
$\displaystyle(n+1)^{\mid\mathcal{Z}\mid}\exp\left\\{-nD(P\|Q)+n\sqrt{V(P\|Q)r^{\prime}_{n}}+\frac{M_{2}}{\sqrt{n}}\right\\},\quad
n\geq N_{2}$

where the last inequality follows since
$|\mathcal{P}_{n}|\leq(n+1)^{|\mathcal{Z}|}$ [13, Th. 11.1.1]. By taking
logarithms on both sides of (40), we obtain

$\displaystyle\ln\beta_{n}(T_{n}^{\tilde{D}}(r_{n}))\leq|\mathcal{Z}|\ln(n+1)-nD(P\|Q)+n\sqrt{V(P\|Q)r^{\prime}_{n}}+\frac{M_{2}}{\sqrt{n}},\quad
n\geq N_{2}.$ (41)

By (17) and (37),

$\displaystyle\sqrt{r^{\prime}_{n}}$ $\displaystyle=$
$\displaystyle\sqrt{\frac{r_{n}}{\eta}+\frac{M}{\eta n^{3/2}}}$ (42)
$\displaystyle=$
$\displaystyle\sqrt{\frac{1}{n}Q_{\chi^{2},k-1}^{-1}\left(\epsilon-
M_{0}\delta_{n}\right)+\frac{M}{\eta n^{3/2}}}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{n}}\sqrt{Q_{\chi^{2},k-1}^{-1}\left(\epsilon-
M_{0}\delta_{n}\right)+\frac{M}{\eta\sqrt{n}}}.$

A Taylor-series expansion of $\sqrt{x+\delta}$ around $x>0$ yields then that

$\displaystyle\sqrt{r^{\prime}_{n}}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{n}}\sqrt{Q_{\chi^{2},k-1}^{-1}\left(\epsilon-
M_{0}\delta_{n}\right)+\frac{M}{\eta\sqrt{n}}}$ (43) $\displaystyle\leq$
$\displaystyle\frac{1}{\sqrt{n}}\left[\sqrt{Q_{\chi^{2},k-1}^{-1}\left(\epsilon-
M_{0}\delta_{n}\right)}+\frac{M}{2\eta\sqrt{n}\sqrt{Q_{\chi^{2},k-1}^{-1}\left(\epsilon-
M_{0}\delta_{n}\right)}}\right]$ $\displaystyle\leq$
$\displaystyle\frac{1}{\sqrt{n}}\sqrt{Q_{\chi^{2},k-1}^{-1}\left(\epsilon-
M_{0}\delta_{n}\right)}+\frac{M}{2\eta
n\sqrt{Q_{\chi^{2},k-1}^{-1}(\epsilon)}}$

where the last inequality holds since the function
$Q_{\chi^{2},k-1}^{-1}(\cdot)$ is monotonically decreasing. It follows that
(41) can be further upper-bounded as

$\displaystyle\ln\beta_{n}(T_{n}^{\tilde{D}}(r_{n}))$ $\displaystyle\leq$
$\displaystyle|\mathcal{Z}|\ln(n+1)-nD(P\|Q)+n\sqrt{V(P\|Q)r^{\prime}_{n}}+\frac{M_{2}}{\sqrt{n}}$
(44) $\displaystyle\leq$
$\displaystyle|\mathcal{Z}|\ln(n+1)-nD(P\|Q)+\sqrt{nV(P\|Q)}\sqrt{Q_{\chi^{2},k-1}^{-1}\left(\epsilon-
M_{0}\delta_{n}\right)}$ $\displaystyle\hskip
56.9055pt+\frac{\sqrt{V(P\|Q)}M}{2\eta\sqrt{Q_{\chi^{2},k-1}^{-1}(\epsilon)}}+\frac{M_{2}}{\sqrt{n}},\quad
n\geq N_{2}.$

Using a Taylor-series expansion of $\sqrt{Q_{\chi^{2},k-1}^{-1}(\epsilon-
M_{0}\delta_{n})}$ around $\epsilon$, we obtain

$\displaystyle\sqrt{Q_{\chi^{2},k-1}^{-1}\left(\epsilon-
M_{0}\delta_{n}\right)}$ $\displaystyle=$
$\displaystyle\sqrt{Q_{\chi^{2},k-1}^{-1}(\epsilon)}+O\left(\delta_{n}\right).$
(45)

Consequently, (44) can be expanded as

$\displaystyle\ln\beta_{n}(T_{n}^{\tilde{D}}(r_{n}))$ $\displaystyle\leq$
$\displaystyle|\mathcal{Z}|\ln(n+1)-nD(P\|Q)+\sqrt{nV(P\|Q)}\sqrt{Q_{\chi^{2},k-1}^{-1}(\epsilon)}+O(\sqrt{n}\delta_{n})$
$\displaystyle\hskip
14.22636pt+\frac{\sqrt{V(P\|Q)}M}{2\eta\sqrt{Q_{\chi^{2},k-1}^{-1}(\epsilon)}}+\frac{M_{2}}{\sqrt{n}}$
$\displaystyle=$ $\displaystyle-
nD(P\|Q)+\sqrt{nV(P\|Q)}\sqrt{Q_{\chi^{2},k-1}^{-1}(\epsilon)}+O(\max\\{\delta_{n}\sqrt{n},\ln
n\\}).$

This proves Part 1 of Theorem 1.

###  IV-B Proof of Part 2 of Theorem 1

Define for $0<\epsilon<1$ and $n\in\mathbb{N}$,

$\displaystyle
R_{n}^{\epsilon}\triangleq\left\\{r>0\;\left.\right|\;P^{n}\left(\tilde{D}(t_{Z^{n}}\|P)\geq
r\right)\leq\epsilon\right\\}$ (46) $\displaystyle
r^{\epsilon}_{n}\triangleq\inf R_{n}^{\epsilon}.$ (47)

###### Lemma 6

For $M_{0}$ and $\delta_{n}$ given in (16), we have

$\displaystyle
r^{\epsilon}_{n}=\frac{\eta}{n}Q^{-1}_{\chi^{2},k-1}(\epsilon)+O\left(\frac{\delta_{n}}{n}\right).$
(48)

###### Proof.

For any $r>0$, we can write

$\displaystyle P^{n}\left(\tilde{D}(t_{Z^{n}}\|P)\geq
r\right)=P^{n}\left(\frac{n}{\eta}\tilde{D}(t_{Z^{n}}\|P)\geq\frac{nr}{\eta}\right).$

Then, it follows from (16) that, for $n\geq N_{0}$ and any $r>0$,

$\displaystyle
Q_{\chi^{2},k-1}\left(\frac{nr}{\eta}\right)-M_{0}\delta_{n}\leq
P^{n}(\tilde{D}(t_{Z^{n}}\|P)\geq r)\leq
Q_{\chi^{2},k-1}\left(\frac{nr}{\eta}\right)+M_{0}\delta_{n}.$ (49)

Let

$\displaystyle\dot{r}_{n}=\frac{\eta}{n}Q^{-1}_{\chi^{2},k-1}\left(\epsilon-
M_{0}\delta_{n}\right).$

Substituting the value of $\dot{r}_{n}$ in (49), we get for $n\geq N_{0}$,

$\displaystyle P^{n}(\tilde{D}(t_{Z^{n}}\|P)\geq\dot{r}_{n})$
$\displaystyle\leq\epsilon.$

Thus, by the definition of $r_{n}^{\epsilon}$

$\displaystyle r^{\epsilon}_{n}$ $\displaystyle\leq$
$\displaystyle\dot{r}_{n}$ (50) $\displaystyle=$
$\displaystyle\frac{\eta}{n}Q^{-1}_{\chi^{2},k-1}\left(\epsilon-
M_{0}\delta_{n}\right),\quad n\geq N_{0}.$

Furthermore, (IV-B) implies that $r_{n}^{\epsilon}$ exists. Indeed, the set
$R_{n}^{\epsilon}$ is lower-bounded by $0$. Then, it follows from (IV-B) that,
for $n\geq N_{0}$, we have $\dot{r}_{n}\in R_{n}^{\epsilon}$. This implies
that $R_{n}^{\epsilon}$ is a non-empty subset of the real numbers $\mathbb{R}$
that has a lower bound. Hence, by the completeness property of $\mathbb{R}$,
$r_{n}^{\epsilon}$ exists.

We next derive a lower bound on $r_{n}^{\epsilon}$. Let

$\displaystyle\ddot{r}_{n}=\frac{\eta}{n}Q^{-1}_{\chi^{2},k-1}\left(\epsilon+2M_{0}\delta_{n}\right).$

Substituting the value of $\ddot{r}_{n}$ in (49), we get for $n\geq N_{0}$,

$\displaystyle
P^{n}(\tilde{D}(t_{Z^{n}}\|P)\geq\ddot{r}_{n})\geq\epsilon+M_{0}\delta_{n}>\epsilon.$
(51)

The above equation implies that $\ddot{r}_{n}$ does not belong to the set
$R_{n}^{\epsilon}$. It follows from the property of the infimum that

$\displaystyle r^{\epsilon}_{n}$ $\displaystyle\geq$
$\displaystyle\ddot{r}_{n}$ (52) $\displaystyle=$
$\displaystyle\frac{\eta}{n}Q^{-1}_{\chi^{2},k-1}\left(\epsilon+2M_{0}\delta_{n}\right),\quad
n\geq N_{0}.$

Thus, from (50) and (52) we obtain

$\displaystyle\frac{\eta}{n}Q^{-1}_{\chi^{2},k-1}\left(\epsilon+2M_{0}\delta_{n}\right)\leq
r_{n}^{\epsilon}\leq\frac{\eta}{n}Q^{-1}_{\chi^{2},k-1}\left(\epsilon-
M_{0}\delta_{n}\right),\quad n\geq N_{0}.$ (53)

Taylor-series expansions of
$Q^{-1}_{\chi^{2},k-1}\left(\epsilon+2M_{0}\delta_{n}\right)$ and
$Q^{-1}_{\chi^{2},k-1}\left(\epsilon-M_{0}\delta_{n}\right)$ around $\epsilon$
yield then that

$\displaystyle
r^{\epsilon}_{n}=\frac{\eta}{n}Q^{-1}_{\chi^{2},k-1}(\epsilon)+O\left(\frac{\delta_{n}}{n}\right).$
(54)

∎

For any $T\in A_{\tilde{D}}(r^{\epsilon}_{n})$ with $r^{\epsilon}_{n}$ in
(54), it follows from (21) that

$\displaystyle\|\mathbf{T}-\mathbf{P}\|_{2}=O\left(\frac{1}{\sqrt{n}}\right).$
(55)

Then, (7) and (20) can be written as

$\displaystyle\tilde{D}(T\|P)$ $\displaystyle=$ $\displaystyle\eta
d_{\chi^{2}}(T,P)+O\left(\frac{1}{n^{3/2}}\right)$ (56) $\displaystyle
D(T\|Q)$ $\displaystyle=$ $\displaystyle
D(P\|Q)+\sum_{i=1}^{k}(T_{i}-P_{i})\ln\left(\frac{P_{i}}{Q_{i}}\right)+\frac{1}{2}d_{\chi^{2}}(T,P)+O\left(\frac{1}{n^{3/2}}\right).$
(57)

The first equation (56) implies that there exist $\bar{M}^{\prime}_{0}>0$ and
$\bar{N}^{\prime}_{0}\in\mathbb{N}$ such that, for all
$n\geq\bar{N}^{\prime}_{0}$ and for $T\in A_{\tilde{D}}(r^{\epsilon}_{n})$,

$\displaystyle|\tilde{D}(T\|P)-\eta
d_{\chi^{2}}(T,P)|<\frac{\bar{M}^{\prime}_{0}}{n^{3/2}}.$ (58)

If
$T\in\bar{A}_{\chi^{2}}\left(\frac{r^{\epsilon}_{n}}{\eta}-\frac{\bar{M}^{\prime}_{0}}{\eta
n^{3/2}}\right)$, then we have
$d_{\chi^{2}}(T,P)\leq\frac{r^{\epsilon}_{n}}{\eta}-\frac{\bar{M}^{\prime}_{0}}{\eta
n^{3/2}}$. Furthermore, by the definition of the $\chi^{2}$-divergence in (8)
and the fact that $P_{i}<1,\;i=1,\cdots,k$, we have that
$d_{\chi^{2}}(T,P)\geq\|T-P\|_{2}^{2}$. Since
$r^{\epsilon}_{n}=O\left(\frac{1}{n}\right)$, these two inequalities imply
that $\|T-P\|_{2}=O\left(\frac{1}{\sqrt{n}}\right)$ and, hence, also
$\|\mathbf{T}-\mathbf{P}\|_{2}=O\left(\frac{1}{\sqrt{n}}\right)$ for every
$T\in\bar{A}_{\chi^{2}}\left(\frac{r^{\epsilon}_{n}}{\eta}-\frac{\bar{M}^{\prime}_{0}}{\eta
n^{3/2}}\right)$. It follows from (7) that there exist
$\bar{M}^{\prime}_{1}>0$ and $\bar{N}^{\prime}_{1}\in\mathbb{N}$ such that,
for all $n\geq\bar{N}^{\prime}_{1}$ and
$T\in\bar{A}_{\chi^{2}}\left(\frac{r^{\epsilon}_{n}}{\eta}-\frac{\bar{M}^{\prime}_{0}}{\eta
n^{3/2}}\right)$,

$\displaystyle|\tilde{D}(T\|P)-\eta
d_{\chi^{2}}(T,P)|<\frac{\bar{M}^{\prime}_{1}}{n^{3/2}}.$ (59)

Then we have the following lemma.

###### Lemma 7

For $n\geq
N^{\prime}_{1}\triangleq\max\\{\bar{N}^{\prime}_{0},\bar{N}^{\prime}_{1}\\}$,
we have

$\displaystyle\bar{A}_{\chi^{2}}\left(\frac{r^{\epsilon}_{n}}{\eta}-\frac{M^{\prime}_{1}}{\eta
n^{3/2}}\right)\subseteq A_{\tilde{D}}(r^{\epsilon}_{n})$ (60)

where
$M^{\prime}_{1}\triangleq\max\\{\bar{M}^{\prime}_{0},\bar{M}^{\prime}_{1}\\}$
and $r^{\epsilon}_{n}$ satisfies (54).

###### Proof:

Since $M^{\prime}_{1}=\max\\{\bar{M}^{\prime}_{0},\bar{M}^{\prime}_{1}\\}$, we
have $\bar{M}^{\prime}_{0}\leq M^{\prime}_{1}$. This implies that

$\displaystyle\bar{A}_{\chi^{2}}\left(\frac{r^{\epsilon}_{n}}{\eta}-\frac{M^{\prime}_{1}}{\eta
n^{3/2}}\right)\subseteq\bar{A}_{\chi^{2}}\left(\frac{r^{\epsilon}_{n}}{\eta}-\frac{\bar{M}^{\prime}_{0}}{\eta
n^{3/2}}\right).$ (61)

Then, using (59), we have for
$T\in\bar{A}_{\chi^{2}}\left(\frac{r^{\epsilon}_{n}}{\eta}-\frac{M^{\prime}_{1}}{\eta
n^{3/2}}\right)$ and for $n\geq
N^{\prime}_{1}=\max\\{\bar{N}^{\prime}_{0},\bar{N}^{\prime}_{1}\\}$ that

$\displaystyle\tilde{D}(T\|P)$ $\displaystyle<$ $\displaystyle\eta
d_{\chi^{2}}(T,P)+\frac{\bar{M}^{\prime}_{1}}{n^{3/2}}$ $\displaystyle\leq$
$\displaystyle\eta\left(\frac{r^{\epsilon}_{n}}{\eta}-\frac{M^{\prime}_{1}}{\eta
n^{3/2}}\right)+\frac{\bar{M}^{\prime}_{1}}{n^{3/2}}$ $\displaystyle\leq$
$\displaystyle r^{\epsilon}_{n}.$

Hence, we obtain $T\in A_{\tilde{D}}(r^{\epsilon}_{n})$. ∎

From (57), we obtain that, for $T\in A_{\tilde{D}}(r^{\epsilon}_{n})$, there
exist $M_{2}^{\prime}>0$ and $N_{2}^{\prime}\in\mathbb{N}$ such that

$\displaystyle|D(T\|Q)-D(P\|Q)-\sum_{i=1}^{k}(T_{i}-P_{i})\ln\left(\frac{P_{i}}{Q_{i}}\right)-\frac{1}{2}d_{\chi^{2}}(T,P)|\leq\frac{M_{2}^{\prime}}{n^{3/2}},\quad
n\geq N_{2}^{\prime}.$ (62)

If $r<r^{\epsilon}_{n}$, then, by definition of $r^{\epsilon}_{n}$, the type-I
error $\alpha_{n}(T^{\tilde{D}})$ exceeds $\epsilon$. Hence such a threshold
violates (11). We thus assume without loss of optimality that $r\geq
r^{\epsilon}_{n}$. In this case,

$\displaystyle\beta_{n}(T_{n}^{\tilde{D}}(r))\triangleq
Q^{n}\left(\tilde{D}(t_{Z^{n}}\|P)<r\right)\geq
Q^{n}\left(\tilde{D}(t_{Z^{n}}\|P)<r^{\epsilon}_{n}\right).$ (63)

Together with Lemma 7, this implies that, for $r^{\epsilon}_{n}$ and $n\geq
N_{1}^{\prime}$, the type-II error of the divergence test
$T_{n}^{\tilde{D}}(r)$ can be lower-bounded as

$\displaystyle\beta_{n}(T_{n}^{\tilde{D}}(r))$ $\displaystyle\geq$
$\displaystyle Q^{n}(\tilde{D}(t_{Z^{n}}\|P)<r^{\epsilon}_{n})$ (64)
$\displaystyle=$ $\displaystyle\sum_{z^{n}:\;t_{z^{n}}\in
A_{\tilde{D}}(r^{\epsilon}_{n})}Q^{n}(z^{n})$ $\displaystyle=$
$\displaystyle\sum_{\tilde{P}\in\mathcal{P}_{n}\cap
A_{\tilde{D}}(r^{\epsilon}_{n})}Q^{n}(T(\tilde{P}))$ $\displaystyle\geq$
$\displaystyle\sum_{\tilde{P}\in\mathcal{P}_{n}\cap\bar{A}_{\chi^{2}}\left(\bar{r}_{n}\right)}Q^{n}(T(\tilde{P}))$

where

$\bar{r}_{n}=\frac{r^{\epsilon}_{n}}{\eta}-\frac{M^{\prime}_{1}}{\eta
n^{3/2}}.$ (65)

By (54), $\bar{r}_{n}$ vanishes as $n\to\infty$. We can therefore find an
$\tilde{N}^{\prime}$ such that, for $n\geq\tilde{N}^{\prime}$, we have that
$\sqrt{\bar{r}_{n}}<\frac{\sqrt{V(P\|Q)}}{\tau}$ with $\tau$ defined in (33).
To lower-bound the type-II error further, let us consider the following lemma.

###### Lemma 8

Consider the minimizing probability distribution $\Gamma^{*}$ given in (34) in
Lemma 5, namely

$\displaystyle\Gamma^{*}_{i}$ $\displaystyle=$ $\displaystyle
P_{i}+\frac{\sqrt{\bar{r}_{n}}(D(P\|Q)-\alpha_{i})P_{i}}{\sqrt{V(P\|Q)}};\quad
i=1,\cdots,k$ (66)

with $\bar{r}_{n}$ given in (65), $\alpha_{i}$ given in (29), and
$n\geq\tilde{N}^{\prime}$. Then, there exist $\tilde{N}\in\mathbb{N}$ and a
type distribution
$T^{*}_{n}=(T^{*}_{n}(a_{1}),\cdots,T^{*}_{n}(a_{k}))\in\mathcal{P}_{n}\cap\bar{A}_{\chi^{2}}\left(\bar{r}_{n}\right)$
such that

$\displaystyle|n\ell(\Gamma^{*})-n\ell(T^{*}_{n})|\leq\kappa,\quad
n\geq\tilde{N}$ (67)

for some constant $\kappa>0$.

###### Proof:

See Appendix C. ∎

From (64), the type-II error of the divergence test can be lower-bounded as

$\displaystyle\beta_{n}(T_{n}^{\tilde{D}}(r))$ $\displaystyle\geq$
$\displaystyle\sum_{\tilde{P}\in\mathcal{P}_{n}\cap\bar{A}_{\chi^{2}}\left(\bar{r}_{n}\right)}Q^{n}(T(\tilde{P}))$
(68) $\displaystyle\geq$ $\displaystyle Q^{n}(T(T^{*}_{n}))$
$\displaystyle\geq$
$\displaystyle\frac{1}{(n+1)^{|\mathcal{Z}|}}\exp\\{-nD(T^{*}_{n}\|Q)\\},\quad
n\geq\tilde{N}_{1}$

where
$\tilde{N}_{1}\triangleq\max\\{N_{1}^{\prime},N_{2}^{\prime},\tilde{N}\\}$ and
$T^{*}_{n}\in\mathcal{P}_{n}\cap\bar{A}_{\chi^{2}}\left(\bar{r}_{n}\right)$ is
a type distribution satisfying (67). The last inequality in (68) follows from
[13, Th. 11.1.4].

We next upper-bound $D(T^{*}_{n}\|Q)$. To this end, we use (62) and (67), and
we recall that $\ell(\Gamma^{*})=-\sqrt{V(P,Q)\bar{r}_{n}}$, to obtain

$\displaystyle nD(T^{*}_{n}\|Q)$ $\displaystyle\leq$ $\displaystyle
nD(P\|Q)+n\ell(T^{*}_{n})+\frac{1}{2}nd_{\chi^{2}}(T^{*}_{n},P)+\frac{M^{\prime}_{2}}{\sqrt{n}}$
(69) $\displaystyle\leq$ $\displaystyle
nD(P\|Q)+n\ell(\Gamma^{*})+\kappa+\frac{1}{2}nd_{\chi^{2}}(T^{*}_{n},P)+\frac{M^{\prime}_{2}}{\sqrt{n}}$
$\displaystyle\leq$ $\displaystyle
nD(P\|Q)-n\sqrt{V(P,Q)\bar{r}_{n}}+\kappa+\frac{n\bar{r}_{n}}{2}+\frac{M^{\prime}_{2}}{\sqrt{n}},\quad
n\geq\tilde{N}_{1}$

where the last inequality follows because
$T_{n}^{*}\in\bar{A}_{\chi^{2}}\left(\bar{r}_{n}\right)$. Substituting (69) in
(68), we get

$\displaystyle\beta_{n}(T_{n}^{\tilde{D}}(r))$ $\displaystyle\geq$
$\displaystyle\frac{1}{(n+1)^{|\mathcal{Z}|}}\exp\left[-nD(P\|Q)+n\sqrt{V(P\|Q)\bar{r}_{n}}-\kappa-\frac{n\bar{r}_{n}}{2}-\frac{M^{\prime}_{2}}{\sqrt{n}}\right],\quad
n\geq\tilde{N}_{1}.$ (70)

Taking logarithm on both sides, we obtain

$\displaystyle\ln\beta_{n}(T_{n}^{\tilde{D}}(r))$ $\displaystyle\geq$
$\displaystyle-|\mathcal{Z}|\ln(n+1)-nD(P\|Q)+n\sqrt{V(P\|Q)\bar{r}_{n}}-\kappa-\frac{n\bar{r}_{n}}{2}-\frac{M^{\prime}_{2}}{\sqrt{n}}.$
(71)

Note that, by (54) and (65),

$\displaystyle\bar{r}_{n}$ $\displaystyle=$
$\displaystyle\frac{1}{n}Q^{-1}_{\chi^{2},k-1}(\epsilon)+O\left(\frac{\delta_{n}}{n}\right)-\frac{M^{\prime}_{1}}{\eta
n^{3/2}}.$ (72)

Depending on whether the last two terms are of order
$O\left(\frac{1}{n^{3/2}}\right)$ or of order
$O\left(\frac{\delta_{n}}{n}\right)$, we either have

$\displaystyle\sqrt{\bar{r}_{n}}$ $\displaystyle=$
$\displaystyle\sqrt{\frac{1}{n}Q^{-1}_{\chi^{2},K-1}(\epsilon)+O\left(\frac{1}{n^{3/2}}\right)}$
(73) $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{n}}\sqrt{Q^{-1}_{\chi^{2},k-1}(\epsilon)}+O\left(\frac{1}{n}\right)$

or

$\displaystyle\sqrt{\bar{r}_{n}}$ $\displaystyle=$
$\displaystyle\sqrt{\frac{1}{n}Q^{-1}_{\chi^{2}}(\epsilon)+O\left(\frac{\delta_{n}}{n}\right)}$
(74) $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{n}}\sqrt{Q^{-1}_{\chi^{2}}(\epsilon)}+O\left(\frac{\delta_{n}}{\sqrt{n}}\right).$

It follows that (71) can be written as

$\displaystyle-\ln\beta_{n}(T_{n}^{\tilde{D}}(r))$ $\displaystyle\leq$
$\displaystyle
nD(P\|Q)-\sqrt{nV(P\|Q)Q^{-1}_{\chi^{2}}(\epsilon)}+O(\max\\{\delta_{n}\sqrt{n},\ln
n\\}).$ (75)

This proves Part 2 of Theorem 1.

##  V Conclusions

For the divergence test and for a large class of divergences, we established
the first-order and the second-order terms of the type-II error given that the
type-I error is upper-bounded by a given value. The divergence test does not
require the knowledge of the distribution of the alternative hypothesis,
hence, it is suitable for problems where we only have access to the
distribution of the null hypothesis. The class of divergences considered in
this paper includes well-known divergences such as the KL divergence and the
$\alpha$-divergence, and our divergence test specializes to the Hoeffding test
if the chosen divergence is the KL divergence. It is well-known that the
Hoeffding test is first-order optimal in the sense that its first-order term
is equal to the first-order term of the Neyman-Pearson test. However, our
results demonstrate that the second-order term of the divergence test for the
class of divergences considered in this paper, and therefore also of the
Hoeffding test, is strictly smaller than the second-order term of the optimal
Neyman-Pearson test. The question whether there exists a test that only
requires the knowledge of the distribution of the null hypothesis and that
achieves the second-order term of the Hoeffding test for the some $Q$’s while
it achieves a higher second-order term for the remaining $Q$’s is yet to be
explored.

##  Appendix A Proof of Lemma 3

For the probability distribution $T=(T_{1},\cdots,T_{k})^{T}$ and
$Q\in\mathcal{P}(\mathcal{Z})$, the function $f_{Q}(T)\triangleq D(T\|P)$ is a
smooth function of $\mathbf{T}=(T_{1},\cdots,T_{k-1})^{T}$ given by

$\displaystyle f_{Q}(\mathbf{T})$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{k-1}T_{i}\ln\left(\frac{T_{i}}{Q_{i}}\right)+\left(1-\sum_{i=1}^{k-1}T_{i}\right)\ln\left(\frac{(1-\sum_{i=1}^{k-1}T_{i})}{Q_{k}}\right).$
(76)

The partial derivatives of $f_{Q}(\cdot)$ with respect to
$T_{i},i=1,\cdots,k-1$ up to third orders are given by

$\displaystyle\frac{\partial f_{Q}(\mathbf{T})}{\partial T_{i}}$
$\displaystyle=$
$\displaystyle\ln\left(\frac{T_{i}}{Q_{i}}\right)-\ln\left(\frac{T_{k}}{Q_{k}}\right)$
(77) $\displaystyle\frac{\partial^{2}f_{Q}(\mathbf{T})}{\partial T_{i}T_{j}}$
$\displaystyle=$
$\displaystyle\begin{cases}\frac{1}{T_{i}}+\frac{1}{T_{k}},\quad&\text{if}\quad
i=j\\\ \frac{1}{T_{k}},\quad&\text{if}\quad i\neq j\end{cases}$ (78)
$\displaystyle\frac{\partial^{3}f_{Q}(\mathbf{T})}{\partial T_{i}T_{j}T_{l}}$
$\displaystyle=$
$\displaystyle\begin{cases}\frac{-1}{T_{i}^{2}}+\frac{1}{T_{k}^{2}},\quad&\text{if}\quad
i=j=l\\\ \frac{1}{T_{k}^{2}},\quad&\text{otherwise}.\end{cases}$ (79)

Consequently, the second-order Taylor approximation of $f_{Q}(\mathbf{T})$
around $P$ is given by

$\displaystyle f_{Q}(\mathbf{T})$ $\displaystyle=$ $\displaystyle
f_{Q}(\mathbf{P})+\sum_{i=1}^{k-1}\frac{\partial f_{Q}(\mathbf{P})}{\partial
T_{i}}(T_{i}-P_{i})+\frac{1}{2}\sum_{i,j=1}^{k-1}\frac{\partial^{2}f_{Q}(\mathbf{P})}{\partial
T_{i}T_{j}}(T_{i}-P_{i})(T_{j}-P_{j})+R_{3}(\mathbf{T})$ (80)

where the remainder term $R_{3}(\mathbf{T})$ in Lagrange’s form is given by

$\displaystyle
R_{3}(\mathbf{T})=\frac{1}{3!}\sum_{i,j,l=1}^{k-1}\frac{\partial^{3}f_{Q}(\Pi)}{\partial
T_{i}T_{j}T_{l}}(T_{i}-P_{i})(T_{j}-P_{j})(T_{l}-P_{l})$ (81)

for $\mathbf{\Pi}=\mathbf{P}+t(\mathbf{T}-\mathbf{P})$, $t\in(0,1)$. The
absolute value of this term can be upper-bounded by

$\displaystyle|R_{3}(\mathbf{T})|$ $\displaystyle=$
$\displaystyle\left|\frac{1}{3!}\sum_{i,j,l=1}^{k-1}\frac{\partial^{3}f_{Q}(\mathbf{\Pi})}{\partial
T_{i}T_{j}T_{l}}(T_{i}-P_{i})(T_{j}-P_{j})(T_{l}-P_{l})\right|$ (82)
$\displaystyle\leq$
$\displaystyle\frac{1}{3!}\sum_{i,j,l=1}^{k-1}\left|\frac{\partial^{3}f_{Q}(\mathbf{\Pi})}{\partial
T_{i}T_{j}T_{l}}\right|\left|(T_{i}-P_{i})(T_{j}-P_{j})(T_{l}-P_{l})\right|.$

When $\|\mathbf{T}-\mathbf{P}\|_{2}\rightarrow 0$, we have that
$P_{i}-\delta<T_{i}<P_{i}+\delta$ for an arbitrary $\delta>0$ and
$i=1,\cdots,k-1$. This implies that
$P_{k}-(k-1)\delta<T_{k}<P_{k}+(k-1)\delta$. Choosing
$\delta\triangleq\frac{1}{4(k-1)}\min_{1\leq i\leq k}P_{i}$, it follows that
$P_{i}-\delta_{0}>0$ and $P_{k}-(k-1)\delta>0$. Consequently,

$\displaystyle\frac{1}{T_{i}^{2}}<\frac{1}{(P_{i}-\delta)^{2}},\quad
i=1,\cdots,k-1$ (83)

and

$\displaystyle\frac{1}{T_{k}^{2}}<\frac{1}{(P_{k}-(k-1)\delta)^{2}}.$ (84)

Using (83), (84), and (79), one can show that, for any $\mathbf{T}$ satisfying
$0<\|\mathbf{T}-\mathbf{P}\|_{2}<\delta$,

$\displaystyle\left|\frac{\partial^{3}f_{Q}(\mathbf{T})}{\partial
T_{i}T_{j}T_{l}}\right|$ $\displaystyle\leq$ $\displaystyle C_{1}$ (85)

where

$\displaystyle
C_{1}\triangleq\max_{i}\frac{1}{(P_{i}-\delta)^{2}}+\frac{1}{(P_{k}-(k-1)\delta)^{2}}.$
(86)

Hence, from (82),

$\displaystyle|R_{3}(\mathbf{T})|$ $\displaystyle\leq$
$\displaystyle\frac{1}{3!}C_{1}\sum_{i,j,l=1}^{k-1}\left|(T_{i}-P_{i})(T_{j}-P_{j})(T_{l}-P_{l})\right|$
(87) $\displaystyle\leq$ $\displaystyle
C^{\prime}\|\mathbf{T}-\mathbf{P}\|_{2}^{3}$

where $C^{\prime}\triangleq\frac{1}{3!}C_{1}(k-1)^{3}$ and the last inequality
follows since $|T_{i}-P_{i}|\leq\|\mathbf{T}-\mathbf{P}\|_{2}$ for all
$i=1,\cdots,k-1$.

Note that $f_{Q}(P)=D(P\|Q)$. Since
$T_{k}-P_{k}=\sum_{i=1}^{k-1}(P_{i}-T_{i})$, we obtain that

$\displaystyle\sum_{i=1}^{k-1}\frac{\partial f_{Q}(P)}{\partial
T_{i}}(T_{i}-P_{i})$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{k-1}\left[\ln\left(\frac{P_{i}}{Q_{i}}\right)-\ln\left(\frac{P_{k}}{Q_{k}}\right)\right](T_{i}-P_{i})$
(88) $\displaystyle=$
$\displaystyle\sum_{i=1}^{k}(T_{i}-P_{i})\ln\left(\frac{P_{i}}{Q_{i}}\right)$

and

$\displaystyle\sum_{i,j=1}^{k-1}\frac{\partial^{2}f_{Q}(P)}{\partial
T_{i}T_{j}}(T_{i}-P_{i})(T_{j}-P_{j})$
$\displaystyle=\sum_{i=1}^{k-1}\left(\frac{1}{P_{i}}+\frac{1}{P_{k}}\right)(T_{i}-P_{i})^{2}+\sum_{i,j=1,\cdots,k-1,i\neq
j}\frac{(T_{i}-P_{i})(T_{j}-P_{j})}{P_{k}}$
$\displaystyle=\sum_{i=1}^{k-1}\frac{(T_{i}-P_{i})^{2}}{P_{i}}+\sum_{i,j=1}^{k-1}\frac{(T_{i}-P_{i})(T_{j}-P_{j})}{P_{k}}$
$\displaystyle=\sum_{i}^{k}\frac{(T_{i}-P_{i})^{2}}{P_{i}}.$ (89)

Thus, by (88), (89), and the definition of the $\chi^{2}$-divergence, (80) can
be written as

$\displaystyle f_{Q}(T)$ $\displaystyle=$ $\displaystyle D(P\parallel
Q)+\sum_{i=1}^{k}(T_{i}-P_{i})\ln\left(\frac{P_{i}}{Q_{i}}\right)+\frac{1}{2}d_{\chi^{2}}(T,P)+O(\|\mathbf{T}-\mathbf{P}\|_{2}^{3})$
(90)

as $\|\mathbf{T}-\mathbf{P}\|_{2}\rightarrow 0$.

##  Appendix B Proof of Lemma 5

Let $\Gamma=(\Gamma_{1},\cdots,\Gamma_{k})$. Consider the minimization problem

$\displaystyle\underset{\Gamma}{\text{Minimize}}\;\;$
$\displaystyle\ell(\Gamma)=\sum_{i=1}^{k}(\Gamma_{i}-P_{i})\alpha_{i}$ (91)
subject to $\displaystyle d_{\chi^{2}}(\Gamma,P)\leq\tilde{r}$ (94)
$\displaystyle\Gamma_{i}>0,\quad i=1,\cdots,k$
$\displaystyle\sum_{i=1}^{k}\Gamma_{i}=1.$

This is equivalent to

$\displaystyle\underset{\Gamma}{\text{Minimize}}\;\;$
$\displaystyle\ell(\Gamma)=\sum_{i=1}^{k}(\Gamma_{i}-P_{i})\alpha_{i}$ (95)
subject to $\displaystyle
g_{0}(\Gamma)\triangleq\sum_{i=1}^{k}\frac{(\Gamma_{i}-P_{i})^{2}}{P_{i}}-\tilde{r}\leq
0$ (98) $\displaystyle g_{i}(\Gamma)\triangleq-\Gamma_{i}<0,\quad
i=1,\cdots,k$ $\displaystyle
h_{1}(\Gamma)\triangleq\sum_{i=1}^{k}\Gamma_{i}-1=0.$

To find the solution of this constrained optimization problem, we consider the
Karush-Kuhn-Tucker (KKT) conditions. Indeed, consider the Lagrangian function

$\displaystyle\mathcal{L}(\Gamma,\lambda,\mu)$ $\displaystyle=$
$\displaystyle\ell(\Gamma)+\lambda_{0}g_{0}(\Gamma)+\sum_{i=1}^{k}\lambda_{i}g_{i}(\Gamma)+\mu
h_{1}(\Gamma)$ (99) $\displaystyle=$
$\displaystyle\sum_{i=1}^{k}(\Gamma_{i}-P_{i})\alpha_{i}+\lambda_{0}\left(\sum_{i=1}^{k}\frac{(\Gamma_{i}-P_{i})^{2}}{P_{i}}-\tilde{r}\right)-\sum_{i=1}^{k}\lambda_{i}\Gamma_{i}+\mu\left(\sum_{i=1}^{k}\Gamma_{i}-1\right)$

where $\lambda=(\lambda_{0},\lambda_{1},\cdots,\lambda_{k})$ and $\mu$ are KKT
multipliers. Let $\Gamma^{*}=(\Gamma_{1}^{*},\cdots,\Gamma_{k}^{*})^{T}$
denote minimizing probability distribution. The KKT conditions for the above
problem are as follows:

$\displaystyle\frac{\partial\mathcal{L}}{\partial\Gamma_{i}}$
$\displaystyle=0,\quad i=1,\cdots,k$ (100) $\displaystyle g_{0}(\Gamma^{*})$
$\displaystyle\leq 0$ (101) $\displaystyle g_{i}(\Gamma^{*})$
$\displaystyle<0,\quad i=1,\cdots,k$ (102) $\displaystyle h_{1}(\Gamma^{*})$
$\displaystyle=0$ (103) $\displaystyle\lambda_{i}$ $\displaystyle\geq 0,\quad
i=0,1,\cdots,k$ (104) $\displaystyle\lambda_{i}g_{i}(\Gamma^{*})$
$\displaystyle=0,\quad i=0,1,\cdots,k$ (105)

which can be evaluated as

$\displaystyle\alpha_{i}+2\lambda_{0}\left(\frac{\Gamma^{*}_{i}}{P_{i}}-1\right)-\lambda_{i}+\mu$
$\displaystyle=0,\quad i=1,\cdots,k$ (106)
$\displaystyle\sum_{i=1}^{k}\frac{(\Gamma^{*}_{i}-P_{i})^{2}}{P_{i}}-\tilde{r}$
$\displaystyle\leq 0$ (107) $\displaystyle-\Gamma^{*}_{i}$
$\displaystyle<0,\quad i=1,\cdots,k$ (108)
$\displaystyle\sum_{i=1}^{k}\Gamma^{*}_{i}-1$ $\displaystyle=0$ (109)
$\displaystyle\lambda_{i}$ $\displaystyle\geq 0,\quad i=0,1,\cdots,k$ (110)
$\displaystyle\lambda_{0}\left(\sum_{i=1}^{k}\frac{(\Gamma^{*}_{i}-P_{i})^{2}}{P_{i}}-\tilde{r}\right)$
$\displaystyle=0$ (111) $\displaystyle-\lambda_{i}\Gamma^{*}_{i}$
$\displaystyle=0,\quad i=1,\cdots,k.$ (112)

From (108) and (112), we get that

$\displaystyle\lambda_{i}=0,\quad i=1,\cdots,k.$ (113)

We next analyze $\lambda_{0}$, considering the cases $\lambda_{0}=0$ and
$\lambda_{0}\neq 0$ separately. When $\lambda_{0}=0$, (112) and (106) yield

$\displaystyle\alpha_{i}+\mu=0,\quad i=1,\cdots,k.$ (114)

Thus, $\ln\frac{P_{i}}{Q_{i}}=-\mu$ for $i=1,\cdots,k$ which implies that
$P=Q$. However, we have $P\neq Q$ by the assumption of Theorem 1, so
$\lambda_{0}=0$ is not a valid solution.

Thus, we have $\lambda_{0}>0$. Then, we obtain from (106) and (111) that

$\displaystyle\Gamma^{*}_{i}$ $\displaystyle=$ $\displaystyle
P_{i}-\frac{P_{i}\mu}{2\lambda_{0}}-\frac{P_{i}\alpha_{i}}{2\lambda_{0}},\quad
i=1,\cdots,k$ (115)

and

$\displaystyle\sum_{i=1}^{k}\frac{(\Gamma^{*}_{i}-P_{i})^{2}}{P_{i}}-\tilde{r}=0.$
(116)

Substituting (115) in (109) yields

$\displaystyle\frac{-\mu}{2\lambda_{0}}-\frac{1}{2\lambda_{0}}\sum_{i=1}^{k}P_{i}\alpha_{i}=0$
(117)

hence

$\displaystyle\mu=-\sum_{i=1}^{k}P_{i}\alpha_{i}=-D(P\|Q).$ (118)

Using (115) and (118), (116) can be written as

$\displaystyle\frac{1}{4\lambda_{0}^{2}}\sum_{i=1}^{k}P_{i}\left(\alpha_{i}-D(P\|Q)\right)^{2}=\tilde{r}.$
(119)

Since

$\displaystyle\sum_{i=1}^{k}P_{i}\left(\alpha_{i}-D(P\|Q)\right)^{2}=V(P\|Q)$
(120)

it follows that

$\displaystyle\lambda_{0}$ $\displaystyle=$
$\displaystyle\frac{\sqrt{V(P\|Q)}}{2\sqrt{\tilde{r}}}.$ (121)

From (115), (118), and (121), we obtain that

$\displaystyle\Gamma^{*}_{i}$ $\displaystyle=$ $\displaystyle
P_{i}+\frac{\sqrt{\tilde{r}}(D(P\|Q)-\alpha_{i})P_{i}}{\sqrt{V(P\|Q)}},\quad
i=1,\cdots,k.$ (122)

Note that we have $P_{i}>0,i=1,\cdots,k$. Hence, if $D(P\|Q)-\alpha_{j}\geq
0$, then it follows from the above equation that $\Gamma^{*}_{j}>0$.
Similarly, if $D(P\|Q)-\alpha_{j}<0$ for some $j\in\\{1,\cdots,k\\}$, then
$j\in\mathcal{I}$ and $\alpha_{j}-D(P\|Q)\in\mathcal{B}$, with $\mathcal{I}$
and $\mathcal{B}$ defined in (31) and (32), respectively. Since
$0<\sqrt{\tilde{r}}<\frac{\sqrt{V(P\|Q)}}{\tau}$, it follows that, for any
$j\in\mathcal{I}$,

$\displaystyle\sqrt{\tilde{r}}$ $\displaystyle<$
$\displaystyle\frac{\sqrt{V(P\|Q)}}{\tau}$ (123) $\displaystyle\leq$
$\displaystyle\frac{\sqrt{V(P\|Q)}}{\alpha_{j}-D(P\|Q)}$

where the last inequality follows since $\alpha_{j}-D(P\|Q)\leq\tau$ for any
$j\in\mathcal{I}$ by the definition of $\tau$ in (33). It follows from (122)
and (123) that $\Gamma^{*}_{j}>0$.

To summarize, the solution to (106)–(112) is given by

$\displaystyle\lambda_{0}$ $\displaystyle=$
$\displaystyle\frac{\sqrt{V(P\|Q)}}{2\sqrt{\tilde{r}}}$ (124)
$\displaystyle\lambda_{i}$ $\displaystyle=$ $\displaystyle 0,\quad
i=1,\cdots,k$ (125) $\displaystyle\mu$ $\displaystyle=$
$\displaystyle-D(P\|Q)$ (126) $\displaystyle\Gamma^{*}_{i}$ $\displaystyle=$
$\displaystyle
P_{i}+\frac{\sqrt{\tilde{r}}(D(P\|Q)-\alpha_{i})P_{i}}{\sqrt{V(P\|Q)}},\quad
i=1,\cdots,k.$ (127)

Since the objective function $\ell(\cdot)$ of the minimization problem and the
inequality constraints $g_{i}(\cdot),i=0,1,\cdots,k$ are convex functions and
the equality constraint $h_{1}(\cdot)$ is affine, the above solution is
optimal. Thus, the minimizing probability distribution
$\Gamma^{*}=(\Gamma^{*}_{1},\cdots,\Gamma^{*}_{k})$ is given by

$\displaystyle\Gamma^{*}_{i}$ $\displaystyle=$ $\displaystyle
P_{i}+\frac{\sqrt{\tilde{r}}\left(D(P\|Q)-\alpha_{i}\right)P_{i}}{\sqrt{V(P\|Q)}},\quad
i=1,\cdots,k$ (128)

and the minimum value is

$\displaystyle\min_{\Gamma\in\bar{A}_{\chi^{2}}(\tilde{r})}\ell(\Gamma)=\ell(\Gamma^{*})=-\sqrt{V(P\|Q)\tilde{r}}.$
(129)

##  Appendix C Proof of Lemma 8

Note that, by (66), the probability distribution
$\Gamma^{*}=(\Gamma^{*}_{1},\cdots,\Gamma^{*}_{k})^{T}$ is given by

$\displaystyle\Gamma^{*}_{i}$ $\displaystyle=$ $\displaystyle
P_{i}+\frac{\sqrt{\bar{r}}(D(P\|Q)-\alpha_{i})P_{i}}{\sqrt{V(P\|Q)}},\quad
i=1,\cdots,k,\quad n\geq\tilde{N}^{\prime}.$ (130)

In the following, we present an algorithm that produces a distribution
$T^{*}_{n}=(T^{*}_{n}(a_{1}),\cdots,T^{*}_{n}(a_{k}))^{T}$ satisfying the
following conditions:

  1. 1.

$T^{*}_{n}$ is a type distribution, i.e., for each $i=1,\cdots,k$,
$nT^{*}_{n}(a_{i})$ is a non-negative integer and

$\displaystyle\sum_{i=1}^{k}nT^{*}_{n}(a_{i})=n.$ (131)

  2. 2.

$T^{*}_{n}$ satisfies

$\displaystyle d_{\chi^{2}}(T^{*}_{n},P)\leq\bar{r}_{n}.$ (132)

  3. 3.

$T^{*}_{n}$ further satisfies

$\displaystyle|n\ell(\Gamma^{*})-n\ell(T^{*}_{n})|\leq\kappa,\quad\text{ for
some }\kappa>0.$ (133)

Before proceeding to the proof, let us observe that

$\displaystyle d_{\chi^{2}}(\Gamma^{*},P)$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{k}\frac{(\Gamma^{*}_{i}-P_{i})^{2}}{P_{i}}$ (134)
$\displaystyle=$
$\displaystyle\sum_{i=1}^{k}\frac{\left(\sqrt{\bar{r}}\left(D(P\|Q)-\alpha_{i}\right)P_{i}\right)^{2}}{V(P\|Q)}\frac{1}{P_{i}}$
$\displaystyle=$
$\displaystyle\frac{\bar{r}}{V(P\|Q)}\sum_{i=1}^{k}\left(D(P\|Q)-\alpha_{i}\right)^{2}P_{i}$
$\displaystyle=$ $\displaystyle\bar{r}_{n}.$

Next, it follows from Remark 1 that there exist two indices
$l,l^{\prime}\in\\{1,\cdots,k\\},l\neq l^{\prime}$ such that
$D(P\|Q)-\alpha_{l}<0$ and $D(P\|Q)-\alpha_{l^{\prime}}>0$, which implies that
$\Gamma^{*}_{l}<P_{l}$ and $\Gamma^{*}_{l^{\prime}}>P_{l^{\prime}}$. Without
loss of generality, let us assume that $l=k-1$ and $l^{\prime}=k$, i.e.,

$\displaystyle(D(P\|Q)-\alpha_{i})P_{i}$ $\displaystyle<0,\quad i=k-1$ (135)
$\displaystyle(D(P\|Q)-\alpha_{i})P_{i}$ $\displaystyle>0,\quad i=k$ (136)

and also that, for some $0\leq m\leq k-2$,

$\displaystyle(D(P\|Q)-\alpha_{i})P_{i}$ $\displaystyle=0,\quad i=1,\cdots,m,$
(137) $\displaystyle(D(P\|Q)-\alpha_{i})P_{i}$ $\displaystyle\neq 0,\quad
i=m+1,\cdots,k-2.$ (138)

Further note that, by (54) and (65), $\bar{r}_{n}=\Theta(1/n)$.

By (130), we have for $i=1,\cdots,k$

$\displaystyle n\Gamma^{*}_{i}-nP_{i}$ $\displaystyle=$
$\displaystyle\frac{n\sqrt{\bar{r}_{n}}(D(P\|Q)-\alpha_{i})P_{i}}{\sqrt{V(P\|Q)}}$
(139)

which implies that

$\displaystyle n\Gamma^{*}_{i}-nP_{i}$ $\displaystyle=$
$\displaystyle\Theta(\sqrt{n}),\quad i=m+1,\cdots,k.$ (140)

Next let

$\displaystyle C^{\prime}$ $\displaystyle=\sum_{i=1}^{m}\frac{1}{P_{i}}.$
(141)

It then follows from (140) that, for each $i=m+1,\cdots,k$, there exists an
$N_{i}$ such that $|n\Gamma^{*}_{i}-nP_{i}|\geq C^{\prime}+k$ for $n\geq
N_{i}$. So, for $n\geq\tilde{N}\triangleq\max\\{N_{i}:i=m+1,\cdots,k\\}$, we
have

$\displaystyle|n\Gamma^{*}_{i}-nP_{i}|\geq C^{\prime}+k,\quad i=m+1,\cdots,k.$
(142)

In the following, we describe an algorithm that outputs $T^{*}_{n}$ for all
$n\geq\tilde{N}$ satisfying (131), (132) and (133).

Algorithm

Step 1: For $i=1,\cdots,m$, set

$\displaystyle nT^{*}_{n}(a_{i})$ $\displaystyle=$ $\displaystyle\lfloor
n\Gamma^{*}_{i}\rfloor$ (143) $\displaystyle=$ $\displaystyle\lfloor
nP_{i}\rfloor$

where $\lfloor\cdot\rfloor$ is the floor function defined as $\lfloor
x\rfloor\triangleq\max\\{u\in\mathbb{Z}\;|\;u\leq x\\}$. The second step in
(143) holds because (137) and (139) imply that $n\Gamma^{*}_{i}=nP_{i}$ for
$i=1,\cdots,m$.

Step 2: For $i=m+1,\cdots,k-2$, set

$\displaystyle{}nT^{*}_{n}(a_{i})$ $\displaystyle=$
$\displaystyle\begin{cases}\lceil
n\Gamma^{*}_{i}\rceil,\quad&\text{if}\;n\Gamma^{*}_{i}-nP_{i}<0\\\ \lfloor
n\Gamma^{*}_{i}\rfloor,\quad&\text{if}\;n\Gamma^{*}_{i}-nP_{i}>0\end{cases}$
(144)

where $\lceil\cdot\rceil$ is the ceiling function defined as $\lceil
x\rceil\triangleq\min\\{u\in\mathbb{Z}\;|\;u\geq x\\}$.

Step 3: Let

$\displaystyle\gamma_{i}$ $\displaystyle\triangleq
n\Gamma^{*}_{i}-nT^{*}_{n}(a_{i}),\quad i=1,\cdots,k$ (145)
$\displaystyle\mathbf{\gamma}$
$\displaystyle\triangleq\sum_{i=1}^{k-2}\gamma_{i}.$ (146)

We set $T^{*}_{n}(a_{k-1})$ or $T^{*}_{n}(a_{k-1})$ depending on whether
$\gamma\leq 0$ or $\gamma>0$:
Case 1: If $\gamma\leq 0$, set

$\displaystyle nT^{*}_{n}(a_{k-1})$ $\displaystyle=$ $\displaystyle\lceil
n\Gamma^{*}_{k-1}+C^{\prime}P_{k-1}\rceil$ (147) $\displaystyle
nT^{*}_{n}(a_{k})$ $\displaystyle=$ $\displaystyle
n\Gamma^{*}_{k}+\gamma^{\prime},\quad\text{where
}\gamma^{\prime}=\gamma+\gamma_{k-1}<0.$ (148)

Case 2: If $\gamma>0$, set

$\displaystyle nT^{*}_{n}(a_{k})$ $\displaystyle=$ $\displaystyle\lfloor
n\Gamma^{*}_{k}-C^{\prime}P_{k}\rfloor$ (149) $\displaystyle
nT^{*}_{n}(a_{k-1})$ $\displaystyle=$ $\displaystyle
n\Gamma^{*}_{k-1}+\gamma^{\prime},\quad\text{where
}\gamma^{\prime}=\gamma+\gamma_{k}>0.$ (150)

We next demonstrate that $T^{*}_{n}$ produced by this algorithm satisfies
(131)–(133).

### Proof of (131):

When $i=1,\cdots,k-2$, since $nT^{*}_{n}(a_{i})$ is defined using the floor or
ceiling function, $nT^{*}_{n}(a_{i})$ is clearly a non-negative integer. For
case 1, $nT^{*}_{n}(a_{k-1})$ is also a non-negative integer since both
$n\Gamma^{*}_{k-1}$ and $C^{\prime}P_{k-1}$ are non-negative numbers and
$nT^{*}_{n}(a_{k-1})$ is defined using the ceiling function of the sum of
these two numbers. It follows from (147) that

$\displaystyle n\Gamma^{*}_{k-1}+C^{\prime}P_{k-1}\leq nT^{*}_{n}(a_{k-1})\leq
n\Gamma^{*}_{k-1}+C^{\prime}P_{k-1}+1.$ (151)

Furthermore, by (148),

$\displaystyle|\gamma^{\prime}|$ $\displaystyle\leq$
$\displaystyle\sum_{i=1}^{k-2}|\gamma_{i}|+|\gamma_{k-1}|$ (152)
$\displaystyle\leq$ $\displaystyle k-2+C^{\prime}P_{k-1}+1$ $\displaystyle=$
$\displaystyle k-1+C^{\prime}P_{k-1}$

where the second inequality follows from the definition of
$\gamma_{i},\;i=1,\cdots,k-1$ and (151). Thus, we have

$\displaystyle-(k-1)-C^{\prime}P_{k-1}\leq\gamma^{\prime}\leq(k-1)+C^{\prime}P_{k-1}.$
(153)

Together with (148), this yields

$\displaystyle nT^{*}_{n}(a_{k})$ $\displaystyle=$ $\displaystyle
n\Gamma^{*}_{k}+\gamma^{\prime}$ (154) $\displaystyle\geq$ $\displaystyle
n\Gamma^{*}_{k}-(k-1)-C^{\prime}P_{k-1}$ $\displaystyle>$ $\displaystyle
n\Gamma^{*}_{k}-C^{\prime}-k$ $\displaystyle\geq$ $\displaystyle nP_{k}$
$\displaystyle\geq$ $\displaystyle 0$ (155)

where (154) follows from (142), (130) and (136). We further have that

$\displaystyle nT^{*}_{n}(a_{k})=$ $\displaystyle
n\Gamma^{*}_{k}+\gamma^{\prime}$ $\displaystyle=$ $\displaystyle
n\Gamma^{*}_{k}+\sum_{i=1}^{k-1}\left(n\Gamma^{*}_{i}-nT^{*}_{n}(a_{i})\right)$
$\displaystyle=$ $\displaystyle n-\sum_{i=1}^{k-1}nT^{*}_{n}(a_{i}).$ (156)

From (155), we obtain that $T^{*}_{n}(a_{k})$ is non-negative. Since we have
already shown that $nT^{*}_{n}(a_{i}),i=1,\cdots,k-1$ are non-negative
integers, it follows from (156) that $nT^{*}_{n}(a_{k})$ is an integer, too.
From (156), we also obtain that $\sum_{i=1}^{k}nT^{*}_{n}(a_{i})=n$. This
completes the proof of (131) for case 1.

We next prove (131) for case 2. From (142) and (136), we have that
$n\Gamma^{*}_{k}-nP_{k}\geq C^{\prime}+k$. It follows that
$nT^{*}_{n}(a_{k})=\lfloor n\Gamma^{*}_{k}-C^{\prime}P_{k}\rfloor$ is non-
negative. The fact that $nT^{*}_{n}(a_{k})$ is an integer follows from its
definition. Furthermore, it is easy to see that $nT^{*}_{n}(a_{k-1})$ is non-
negative by (150). Finally, we have

$\displaystyle nT^{*}_{n}(a_{k-1})$ $\displaystyle=$ $\displaystyle
n\Gamma^{*}_{k-1}+\gamma^{\prime}$ (157) $\displaystyle=$ $\displaystyle
n\Gamma^{*}_{k-1}+\sum_{i=1}^{k-2}\left(n\Gamma^{*}_{i}-nT^{*}_{n}(a_{i})\right)+n\Gamma^{*}_{k}-nT^{*}_{n}(a_{k})$
$\displaystyle=$ $\displaystyle
n-\sum_{i=1}^{k-2}nT^{*}_{n}(a_{i})-nT^{*}_{n}(a_{k}).$

Since $nT^{*}_{n}(a_{i}),i=1,\cdots,k-2$ and $nT^{*}_{n}(a_{k})$ are integers,
it follows from (157) that $nT^{*}_{n}(a_{k})$ is an integer, too. From (157),
we also obtain that $\sum_{i=1}^{k}nT^{*}_{n}(a_{i})=n$. This demonstrates
that $\Gamma^{*}$ satisfies (131).

### Proof of (132):

Since, by (134), $\bar{r}_{n}=d_{\chi^{2}}(\Gamma^{*},P)$, (132) is equivalent
to

$\displaystyle\sum_{i=1}^{k}\frac{(nT^{*}_{n}(a_{i})-nP_{i})^{2}}{n^{2}P_{i}}$
$\displaystyle\leq$
$\displaystyle\sum_{i=1}^{k}\frac{(n\Gamma^{*}_{i}-nP_{i})^{2}}{n^{2}P_{i}}.$
(158)

For $i=1,\cdots,k$, let

$\displaystyle l_{i}^{\prime}$ $\displaystyle=$
$\displaystyle\frac{(nT^{*}_{n}(a_{i})-nP_{i})^{2}}{n^{2}P_{i}}$ (159)
$\displaystyle l_{i}$ $\displaystyle=$
$\displaystyle\frac{(n\Gamma^{*}_{i}-nP_{i})^{2}}{n^{2}P_{i}}.$ (160)

Then, (158) is equivalent to

$\displaystyle\sum_{i=1}^{k}l_{i}^{\prime}\leq\sum_{i=1}^{k}l_{i}.$ (161)

We have

$\displaystyle\sum_{i=1}^{k}l_{i}^{\prime}$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{m}l_{i}^{\prime}+\sum_{i=m+1}^{k-2}l_{i}^{\prime}+l_{k-1}^{\prime}+l_{k}^{\prime}.$
(162)

By (143), the first sum can be upper-bounded as

$\displaystyle\sum_{i=1}^{m}l_{i}^{\prime}$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{m}\frac{(\lfloor nP_{i}\rfloor-
nP_{i})^{2}}{n^{2}P_{i}}$ (163) $\displaystyle\leq$
$\displaystyle\sum_{i=1}^{m}\frac{1}{n^{2}P_{i}}=\frac{C^{\prime}}{n^{2}}.$

From (144), it follows that, for $i=m+1,\cdots,k-2$,

$\displaystyle(nT^{*}_{n}(a_{i})-nP_{i})^{2}$ $\displaystyle\leq$
$\displaystyle(n\Gamma^{*}_{i}-nP_{i})^{2}$ (164)

so the second sum can be upper-bounded as

$\displaystyle\sum_{i=m+1}^{k-2}l_{i}^{\prime}\leq\sum_{i=m+1}^{k-2}l_{i}.$
(165)

We next prove (161) for case 1 in the algorithm. From (148), we have

$\displaystyle nT^{*}_{n}(a_{k})-nP_{k}$ $\displaystyle=$ $\displaystyle
n\Gamma^{*}_{k}-nP_{k}+\gamma^{\prime}.$ (166)

Since $\gamma^{\prime}<0$, we have
$nT^{*}_{n}(a_{k})-nP_{k}<n\Gamma^{*}_{k}-nP_{k}$. This, together with the
fact that $nT^{*}_{n}(a_{k})-nP_{k}>0$ (cf. (154)), implies that

$\displaystyle l_{k}^{\prime}<l_{k}.$ (167)

As for index $k-1$, we shall show that

$\displaystyle l_{k-1}^{\prime}\leq l_{k-1}-\frac{C^{\prime}}{n^{2}}$ (168)

which is equivalent to

$\displaystyle(n\Gamma^{*}_{k-1}-nP_{k-1})^{2}-(nT^{*}_{n}(a_{k-1})-nP_{k-1})^{2}\geq
C^{\prime}P_{k-1}.$ (169)

Let $b=nP_{k-1}-n\Gamma^{*}_{k-1}>0$ and $s=nP_{k-1}-nT^{*}_{n}(a_{k-1})$.
Then, we have

$\displaystyle s$ $\displaystyle=nP_{k-1}-\lceil
n\Gamma^{*}_{k-1}+C^{\prime}P_{k-1}\rceil$
$\displaystyle>nP_{k-1}-n\Gamma^{*}_{k-1}-C^{\prime}P_{k-1}-1$
$\displaystyle\geq C^{\prime}+k-C^{\prime}P_{k-1}-1$ $\displaystyle>0$ (170)

where the first step follows from (147), the third step is due to (142) and
the fact that $nP_{k-1}>n\Gamma^{*}_{k-1}$ (by using (135) in (130)), and the
last step follows since $P_{k-1}\leq 1$ and $k\geq 2$. Next note that

$\displaystyle(n\Gamma^{*}_{k-1}-nP_{k-1})^{2}-(nT^{*}_{n}(a_{k-1})-nP_{k-1})^{2}=b^{2}-s^{2}=(b-s)(b+s).$
(171)

From (142), it follows that $b\geq C^{\prime}+k$, which yields

$\displaystyle s+b\geq 1$ (172)

since $s>0$ by (170) and $C^{\prime}+k\geq 1$.Furthermore, (151) yields that

$\displaystyle b-s$ $\displaystyle=$ $\displaystyle
nT^{*}_{n}(a_{k-1})-n\Gamma^{*}_{k-1}\geq C^{\prime}P_{k-1}.$ (173)

We thus obtain (169) from (172) and (173). It follows from (163), (165),
(167), and (168) that, for case 1 in the algorithm,

$\displaystyle\sum_{i=1}^{k}l_{i}^{\prime}$ $\displaystyle=$
$\displaystyle\sum_{i=m+1}^{k-2}l_{i}^{\prime}+\sum_{i=1}^{m}l_{i}^{\prime}+l_{k-1}^{\prime}+l_{k}^{\prime}$
(174) $\displaystyle\leq$
$\displaystyle\sum_{i=m+1}^{k-2}l_{i}+\frac{C^{\prime}}{n^{2}}+l_{k-1}-\frac{C^{\prime}}{n^{2}}+l_{k}$
$\displaystyle=$ $\displaystyle\sum_{i=m+1}^{k}l_{i}$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{k}l_{i}$

where the last step follows since, by (130), (137), and (160), we have
$\sum_{i=1}^{m}l_{i}=0$.

We next argue that, by following similar steps as above, we also obtain (161)
for case 2. To this end, we use that

$\displaystyle n\Gamma^{*}_{k-1}<nT^{*}_{n}(a_{k-1})<nP_{k-1}$ (175)

where the first inequality follows since
$nT^{*}_{n}(a_{k-1})=n\Gamma^{*}_{k-1}+\gamma^{\prime}$ and
$\gamma^{\prime}>0$ (by (150)), and the second inequality follows since

$\displaystyle nP_{k-1}$ $\displaystyle\geq n\Gamma^{*}_{k-1}+C^{\prime}+k$
$\displaystyle>n\Gamma^{*}_{k-1}+\gamma^{\prime}$
$\displaystyle=nT^{*}_{n}(a_{k-1}).$ (176)

Here, the first step is due to (142) and the fact that $nP_{k-1}\geq
n\Gamma^{*}_{k-1}$ (by using (135) in (130)), the second step follows from the
fact that $\gamma^{\prime}<C^{\prime}+k$ (by (152)), and the last step follows
from (150). By (175), we have that
$|nT^{*}_{n}(a_{k-1})-nP_{k-1}|<|n\Gamma^{*}_{k-1}-nP_{k-1}|$, which implies
that

$\displaystyle l_{k-1}^{\prime}<l_{k-1}.$ (177)

We finally obtain

$\displaystyle l_{k}^{\prime}<l_{k}-\frac{C^{\prime}}{n^{2}}$ (178)

by letting $b=(n\Gamma^{*}_{k}-nP_{k})$, $s=(nT^{*}_{n}(a_{k})-nP_{k})$, and
by then following the steps that led to (173). Thus, (161) follows from (163),
(165), (177), and (178), and by using that $\sum_{i=1}^{m}l_{i}=0$. This
demonstrate that $\Gamma^{*}$ satisfies (132).

###  Proof of (133):

For case 1 in the algorithm, we obtain from (144), (151), (152), and the
definition of $\ell(\cdot)$ in (28)

$\displaystyle|n\ell(\Gamma^{*})-n\ell(T^{*}_{n})|$ $\displaystyle=$
$\displaystyle\left|\sum_{i=1}^{k}(n\Gamma^{*}_{i}-nT^{*}_{n}(a_{i}))\alpha_{i}\right|$
(179) $\displaystyle\leq$
$\displaystyle\sum_{i=1}^{k}|n\Gamma^{*}_{i}-nT^{*}_{n}(a_{i})||\alpha_{i}|$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{k-2}|n\Gamma^{*}_{i}-nT^{*}_{n}(a_{i})||\alpha_{i}|+|n\Gamma^{*}_{k-1}-nT^{*}_{n}(a_{k-1})||\alpha_{k-1}|$
$\displaystyle\hskip
56.9055pt+|n\Gamma^{*}_{k}-nT^{*}_{n}(a_{k})||\alpha_{k}|$ $\displaystyle\leq$
$\displaystyle\sum_{i=1}^{k-2}|\alpha_{i}|+|\alpha_{k-1}|(C^{\prime}P_{k-1}+1)+|\alpha_{k}|(C^{\prime}P_{k-1}+k-1)$
$\displaystyle\triangleq$ $\displaystyle\kappa_{1}$

where $\kappa_{1}$ is a positive constant.

Similarly, for case 2 in the algorithm, we have that

$\displaystyle|n\ell(\Gamma^{*})-n\ell(T^{*}_{n})|$ $\displaystyle=$
$\displaystyle\left|\sum_{i=1}^{k}(n\Gamma^{*}_{i}-nT^{*}_{n}(a_{i}))\alpha_{i}\right|$
$\displaystyle\leq$
$\displaystyle\sum_{i=1}^{k}|n\Gamma^{*}_{i}-nT^{*}_{n}(a_{i})||\alpha_{i}|$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{k-2}|n\Gamma^{*}_{i}-nT^{*}_{n}(a_{i})||\alpha_{i}|+|n\Gamma^{*}_{k-1}-nT^{*}_{n}(a_{k-1})||\alpha_{k-1}|$
$\displaystyle\hskip
56.9055pt+|n\Gamma^{*}_{k}-nT^{*}_{n}(a_{k})||\alpha_{k}|$ $\displaystyle\leq$
$\displaystyle\sum_{i=1}^{k-2}|\alpha_{i}|+|\alpha_{k-1}|(C^{\prime}P_{k}+k-1)+|\alpha_{k}|(C^{\prime}P_{k}+1)$
$\displaystyle\triangleq$ $\displaystyle\kappa_{2}$

where $\kappa_{2}$ is a positive constant.

By taking $\kappa=\max\\{\kappa_{1},\kappa_{2}\\}$, we obtain

$\displaystyle|n\ell(\Gamma^{*})-n\ell(T^{*}_{n})|\leq\kappa$

thus demonstrating that $\Gamma^{*}$ satisfies (133).

## Acknowledgment

The authors would like to thank Shun Watanabe for his helpful comments during
the initial phase of this work and for pointing out relevant literature.

## References

  * [1] J. Neyman and E. S. Pearson, “On the problem of the most efficient tests of statistical hypotheses,” _Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character_ , vol. 231, no. 694-706, pp. 289–337, Feb. 1933.
  * [2] V. Y. Tan, “Asymptotic estimates in information theory with non-vanishing error probabilities,” _Foundations and Trends® in Communications and Information Theory_ , vol. 11, no. 1-2, pp. 1–184, 2014.
  * [3] W. Hoeffding, “Asymptotically optimal tests for multinomial distributions,” _The Annals of Mathematical Statistics_ , pp. 369–401, Apr. 1965.
  * [4] I. Csiszár, “The method of types,” _IEEE Transactions on Information Theory_ , vol. 44, no. 6, pp. 2505–2523, Oct. 1998.
  * [5] S. Watanabe, “Second-order optimal test in composite hypothesis testing,” in _Proc. 2018 International Symposium on Information Theory and Its Applications (ISITA)_ , Singapore, Oct. 2018, pp. 722–726.
  * [6] O. Zeitouni, J. Ziv, and N. Merhav, “When is the generalized likelihood ratio test optimal?” _IEEE Transactions on Information Theory_ , vol. 38, no. 5, pp. 1597–1602, Sep. 1992.
  * [7] J. Unnikrishnan, D. Huang, S. P. Meyn, A. Surana, and V. V. Veeravalli, “Universal and composite hypothesis testing via mismatched divergence,” _IEEE Transactions on Information Theory_ , vol. 57, no. 3, pp. 1587–1603, Mar. 2011.
  * [8] S.-I. Amari, _Information geometry and its applications_. Springer, 2016, vol. 194.
  * [9] S. Eguchi, “A differential geometric approach to statistical inference on the basis of contrast functionals,” _Hiroshima mathematical journal_ , vol. 15, no. 2, pp. 341–391, 1985.
  * [10] A. Cichocki, R. Zdunek, A. H. Phan, and S.-I. Amari, _Nonnegative matrix and tensor factorizations: applications to exploratory multi-way data analysis and blind source separation_. John Wiley & Sons, 2009.
  * [11] I. Csiszár and P. C. Shields, _Information theory and statistics: A tutorial_. Now Publishers Inc, 2004.
  * [12] S.-I. Amari and A. Cichocki, “Information geometry of divergence functions,” _Bulletin of the polish academy of sciences. Technical sciences_ , vol. 58, no. 1, pp. 183–195, 2010.
  * [13] T. Cover and J. Thomas, _Elements of Information Theory_ , 2nd ed. New York, NY, USA: Wiley-Interscience, 2006.
  * [14] G. L. Gilardoni, “On Pinsker’s and Vajda’s type inequalities for Csiszár’s $f$-divergences,” _IEEE Transactions on Information Theory_ , vol. 56, no. 11, pp. 5377–5386, Nov. 2010.
  * [15] I. Csiszár, “On topological properties of f-divergences,” _Studia Math. Hungar._ , vol. 2, pp. 329–339, 1967.
  * [16] T. R. Read, “Closer asymptotic approximations for the distributions of the power divergence goodness-of-fit statistics,” _Ann. Inst. Statist. Math._ , vol. 36, pp. 59–69, Dec. 1984.
  * [17] J. K. Yarnold, “Asymptotic approximations for the probability that a sum of lattice random vectors lies in a convex set,” _The Annals of Mathematical Statistics_ , pp. 1566–1580, Oct. 1972.
  * [18] V. V. Ulyanov and V. N. Zubov, “Refinement on the convergence of one family of goodness-of-fit statistics to chi-squared distribution,” _Hiroshima Mathematical Journal_ , vol. 39, no. 1, pp. 133–161, 2009.


* [98] MEG Collaboration, A. M. Baldini et al., Search for the lepton flavour violating decay $\mu^{+}\rightarrow\mathrm{e}^{+}\gamma$ with the full dataset of the MEG experiment, Eur. Phys. J. C 76 (2016), no. 8 434, [arXiv:1605.05081].
  * [99] BaBar Collaboration, B. Aubert et al., Searches for Lepton Flavor Violation in the Decays tau+- —$>$ e+- gamma and tau+- —$>$ mu+- gamma, Phys. Rev. Lett. 104 (2010) 021802, [arXiv:0908.2381].
  * [100] Belle Collaboration, A. Abdesselam et al., Search for lepton-flavor-violating tau-lepton decays to $\ell\gamma$ at Belle, JHEP 10 (2021) 19, [arXiv:2103.12994].
  * [101] SINDRUM Collaboration, U. Bellgardt et al., Search for the Decay mu+ —$>$ e+ e+ e-, Nucl. Phys. B 299 (1988) 1–6.
  * [102] K. Hayasaka et al., Search for Lepton Flavor Violating Tau Decays into Three Leptons with 719 Million Produced Tau+Tau- Pairs, Phys. Lett. B 687 (2010) 139–143, [arXiv:1001.3221].
  * [103] SINDRUM II Collaboration, C. Dohmen et al., Test of lepton flavor conservation in mu —$>$ e conversion on titanium, Phys. Lett. B 317 (1993) 631–636.
  * [104] SINDRUM II Collaboration, W. H. Bertl et al., A Search for muon to electron conversion in muonic gold, Eur. Phys. J. C 47 (2006) 337–346.
  * [105] D. V. Forero, S. Morisi, M. Tortola, and J. W. F. Valle, Lepton flavor violation and non-unitary lepton mixing in low-scale type-I seesaw, JHEP 09 (2011) 142, [arXiv:1107.6009].
  * [106] I. Esteban, M. C. Gonzalez-Garcia, M. Maltoni, T. Schwetz, and A. Zhou, The fate of hints: updated global analysis of three-flavor neutrino oscillations, JHEP 09 (2020) 178, [arXiv:2007.14792].
  * [107] A. Caputo, P. Hernandez, J. Lopez-Pavon, and J. Salvado, The seesaw portal in testable models of neutrino masses, JHEP 06 (2017) 112, [arXiv:1704.08721].
  * [108] Z.-z. Xing, Correlation between the Charged Current Interactions of Light and Heavy Majorana Neutrinos, Phys. Lett. B 660 (2008) 515–521, [arXiv:0709.2220].
  * [109] F. J. Escrihuela, D. V. Forero, O. G. Miranda, M. Tortola, and J. W. F. Valle, On the description of nonunitary neutrino mixing, Phys. Rev. D 92 (2015), no. 5 053009, [arXiv:1503.08879]. [Erratum: Phys.Rev.D 93, 119905 (2016)].
  * [110] M. Blennow, P. Coloma, E. Fernandez-Martinez, J. Hernandez-Garcia, and J. Lopez-Pavon, Non-Unitarity, sterile neutrinos, and Non-Standard neutrino Interactions, JHEP 04 (2017) 153, [arXiv:1609.08637].
  * [111] KATRIN Collaboration, M. Aker et al., Direct neutrino-mass measurement with sub-electronvolt sensitivity, Nature Phys. 18 (2022), no. 2 160–166, [arXiv:2105.08533].
  * [112] Planck Collaboration, N. Aghanim et al., Planck 2018 results. VI. Cosmological parameters, Astron. Astrophys. 641 (2020) A6, [arXiv:1807.06209]. [Erratum: Astron.Astrophys. 652, C4 (2021)].
  * [113] G. J. Feldman and R. D. Cousins, A Unified approach to the classical statistical analysis of small signals, Phys. Rev. D 57 (1998) 3873–3889, [physics/9711021].
  * [114] J. A. Casas and A. Ibarra, Oscillating neutrinos and $\mu\to e,\gamma$, Nucl. Phys. B 618 (2001) 171–204, [hep-ph/0103065].
  * [115] S. Antusch, S. Blanchet, M. Blennow, and E. Fernandez-Martinez, Non-unitary Leptonic Mixing and Leptogenesis, JHEP 01 (2010) 017, [arXiv:0910.5957].
  * [116] M. Blennow and E. Fernandez-Martinez, Parametrization of Seesaw Models and Light Sterile Neutrinos, Phys. Lett. B 704 (2011) 223–229, [arXiv:1107.3992].